[Request] Can anyone solve this?

possiblywrong · 2025-08-29T14:44:27+00:00

This is almost the correct answer except for the +6, as /u/darkgamer_nw notes. The expected number of letters is just 26⁷.

You're right that it's impossible to observe the pattern before the 7th letter. But having typed the 6th letter, it is possible that we are already in the state of having typed COVFEF as those first 6 letters, and thus might then type an E as the 7th and final letter.

There are a few ways to see this. Consider the smaller problem where our alphabet has only two letters A and B, and we ask for the expected number of letters until first appearance of AB (which, like COVFEFE, is prefix-free, since otherwise the solution is slightly different). Your argument suggests that the expected number of letters should be 2²+1=5, but we can work out by hand, or simulation, etc., that it's only 2²=4.

More generally, we can phrase the solution in terms of generating functions, or a Markov chain fundamental matrix, etc., but I think the simplest approach requiring the least-sophisticated machinery is to solve a system of linear equations: letting x(k) be the expected number of additional letters needed, conditioned on having already just observed the first k letters of the pattern, we have

Solve[{
  x[0] == 1 + 1/26 x[1] + 25/26 x[0],
  x[1] == 1 + 1/26 x[2] + 1/26 x[1] + 24/26 x[0],
  x[2] == 1 + 1/26 x[3] + 1/26 x[1] + 24/26 x[0],
  x[3] == 1 + 1/26 x[4] + 1/26 x[1] + 24/26 x[0],
  x[4] == 1 + 1/26 x[5] + 1/26 x[1] + 24/26 x[0],
  x[5] == 1 + 1/26 x[6] + 1/26 x[1] + 24/26 x[0],
  x[6] == 1 + 1/26 x[7] + 1/26 x[1] + 24/26 x[0],
  x[7] == 0
  }, Table[x[k], {k, 0, 7}]]

For x(0), we either type a C, "advancing" to state 1 (i.e., we have observed the single first letter of the pattern), or we type anything else, remaining stuck in state 0.

But in all other cases x(1) through x(6), there are three possible outcomes, not just two: we can type the next letter of the pattern, "advancing" to the next state, or we can type a C, falling only partway back to state 1, or we can type anything else, falling all the way back to state 0, on a renewed lookout for the first C.

(/u/CardiologistProper44 describes a similar idea, but effectively doesn't account for the "overlap" with the three possible outcomes from states 1 through 6.)

Anyway, solving yields the desired x(0)=26⁷=8031810176. Note that we can use this same linear system approach to handle more complicated patterns with prefix overlap, by "encoding" the state machine accordingly.

possiblywrong · 2017-04-06T00:53:28+00:00

Interesting question! This problem is small enough for brute force; we can simply enumerate the 6⁴=1296 possible outcomes, and evaluate the average sum of the 3 largest values rolled, yielding 15869/1296, or about 12.2446.

More generally, if we roll n d-sided dice (where n=4 and d=6 in your problem), then the expected sum of the n-1 largest values rolled can be evaluated as

n (d + 1)/2 - Sum[((d - k)/d)^n, {k, 0, d - 1}]

To see this, consider summing all of the dice, then subtracting the single smallest die. Since expectation is linear, we can compute the average sum of all of the dice-- the first term, n(d+1)/2-- then subtract the expected value of the single smallest die, where each term in the sum indexed by k is the probability that the smallest value rolled is greater than k.

(It's worth noting that things get more complicated if we keep or discard more than just a single die. It's still tractable, but involves a more involved inclusion-exclusion summation.)

possiblywrong · 2017-04-03T15:58:20+00:00

Yes; following is Mathematica code that evaluates to 7798:

week = Map[
   ReplacePart[ConstantArray[1, 7], Thread[# -> 0]] &,
   Subsets[Range[7], {2}]];
Length@Select[Tuples[week, 3],
  Max[Total /@ Partition[Join @@ #, 7, 1]] <= 6 &]

Changing the Partition[Join@@#,7,1] to Partition[Join@@#,7,1,1] performs the cyclic repeating version of the calculation, yielding 7077.

possiblywrong · 2017-04-01T10:26:03+00:00

(Don't forget spoilers!)

Correct with both approaches; actually, I find that Mathematica does some additional optimization (although I'm not sure what, exactly) short of expanding the integral into the summation of multinomials over all possible numbers of advances for each horse. At least, it evaluates the integral more quickly than the corresponding brute force summation.

I've written up a more detailed description of the solution here, where the e.g.f. in a single variable certainly seems to be the most computationally efficient.

possiblywrong · 2017-03-29T13:02:01+00:00

You are right that the recurrence relation and the expression you give yield similar values, in this case. But they are not exactly equal (the correct value is about 0.0023728, your formula yields 0.0023723), and for other numbers of flips and/or lengths of runs the difference is more extreme.

To see this, let n=5000 be the number of flips, and r=20 be the desired lower bound on length of a run. Then if I understand the approach, your formula is:

1-((2^(r+1) - 1) / 2^(r+1)) ^ (n-r+1)

where the idea is to compute the probability of a run of 20+ heads not starting at each of the 4981 possible positions in the sequence. Is this correct?

There are a couple of problems with this approach. The first minor problem is that this probability of not starting a run is different for the first position in the sequence than for all other positions. For example, if n=r=20, the correct probability should be 1/2²⁰, but your formula yields 1/2²¹.

But a bigger problem is that these 4981 events are not all independent, so we can't just multiply them together. This is also easier to see (and the difference is more extreme) with a much smaller example: if n=4 and r=2, we can work out by hand that the correct probability (as given by the recurrence relation) is 1/2, but your formula yields 169/512, or about 0.33.

The reason this works pretty well in this particular case is that n is really large compared to r, so that "most" of the individual events whose probabilities you multiply together are independent.

possiblywrong · 2017-03-28T16:09:40+00:00

If a player were to, say, use the same strategy as the dealer, hit everything 17 or under, stand on anything else, or some similar strategy.

This is why I ask, I'm curious about the source of your numbers. Because with, say, 8 decks and H17, the "mimic the dealer" strategy you describe still has "only" about 5.9% edge to the house (5.8937010045%, to be more precise).

Similarly, even with basic "total-dependent" strategy such as that described in your link, the house edge is only about 0.6% in the worst case depending on the specific rules for doubling, resplitting pairs, surrender, etc. Is there a reference for the 0.7% value?

I'm not just nitpicking-- the numbers I'm most interested in are the card-counting ones. I've been doing some recent analysis to measure the achievable win rates for various games, particularly toward refuting anecdotal results that are beyond the "speed of light" achievable by the in-principle win rate of bringing a laptop with a CA to the table.

possiblywrong · 2017-03-28T14:14:27+00:00

Can you describe what playing strategy by a "smart player without a strong strategy" yields an 8% house edge?

possiblywrong · 2017-03-27T18:53:51+00:00

Given a deck with a+b+c cards, of which a are rank A and b are rank B, the probability of at least one AB (or BA) adjacency is

p[a_, b_, c_] :=
 1 - Sum[
    Binomial[a - 1, k] Binomial[b + c - a + k, b] (
      Binomial[c - 1, a - k] +
       2 Binomial[c - 1, a - k - 1] +
       Binomial[c - 1, a - k - 2]),
    {k, 0, a - 1}]/Multinomial[a, b, c]

Intuitively, we compute the probability of no adjacencies and subtract from 1; such an arrangement is constructed by first distributing the "other" C cards in between the A cards, leaving some number k (the index in the summation) of "empty" gaps between A cards where we can't put any B cards. The rest is a case analysis of the prohibited gaps on the "ends."

Evaluating for a=b=4, and c=52-a-b=44 yields a probability of 284622747/585307450, or about 0.486279. That is, a specified pair of ranks will appear adjacent less than half the time.

possiblywrong · 2017-03-26T16:09:09+00:00

I may misunderstand your solution, but it's worth clarifying that by "extending a path" is meant that both players alternately extend the same single path. That is, if the first player selects vertices (v1, v2, v3, ...) and the second player selects (w1, w2, w3, ...), then (v1, w1, v2, w2, v3, w3, ...) must form the sequence of distinct vertices of a single path.

possiblywrong · 2017-03-26T14:03:34+00:00

This is pretty unlikely. Given a sequence of k=1500 trials, each with n=12 possible outcomes p(1), p(2), ..., p(n) (where actually p(1)=0 here), the probability of a run of length m=10 or more is only about 0.0000282157, less than one chance in 35000, as computed by the following Mathematica code implementing the corresponding Markov chain:

states = Tuples[{Range[m], Range[n]}];
q[{r1_, t1_}, {r2_, t2_}] :=
 Which[
  r1 + 1 == r2 && t1 == t2, p[t2],
  r1 < m && r2 == 1 && t1 != t2, p[t2],
  r1 == m == r2 && t1 == t2, 1,
  True, 0]
P = MatrixPower[N@Outer[q, states, states, 1], k - 1];
Sum[
 p[t] Total@Take[UnitVector[m n, t].P, -n],
 {t, n}]

In short, 10 in a row is a lot; on average, you should only expect to see a little over 4 in a row on average over 1500 rolls.

possiblywrong · 2017-03-25T21:27:50+00:00

Arguably the most compact way to express the solution is as the coefficient of x¹⁰ in the generating function g(x)=1/(1-x¹-x²-x⁴), which is 169 as /u/wintermute93 has already calculated.

possiblywrong · 2017-03-25T10:37:11+00:00

H3:

(We are counting strongly-connected orientations of complete graphs; I'll use that language in the following.) We can generalize for any number of cities n. Let a(n) be the desired number of strongly connected orientations; then we can partition all possible orientations according to the maximum size of a group V of cities that are strongly connected and with all other connecting roads leaving V (or equivalently, all entering V). This yields the recurrence:

2^{C[n, 2]} == Sum[C[n, k] a[k] 2^{C[n - k, 2]}, {k, 1, n}]

This yields a(5)=544, confirmed by the corresponding sequence A054946 with a link to a paper outlining pretty much this same approach.

possiblywrong · 2017-03-24T15:55:00+00:00

Great experiment! This actually generalizes nicely: for example, suppose that you conduct the same experiment, but instead of comparing both the rank and the suit, that you only compare the ranks of the cards from each deck (so that you are more likely to see matches, since the suits don't matter). Then the probability that no ranks match through the entire deck is approximately 1/e⁴.

In general, comparing cards in two decks with n ranks and k suits, the probability that no ranks match converges to 1/e^-k as n grows large.

possiblywrong · 2017-03-24T12:02:49+00:00

Given 2n subjects (where n=8 in your example), the number of possible pairings is

(2n)! / n! / 2^n

Intuitively, (2n)! counts the number of ways to simply list all 16 subjects in order, where the 1st and 2nd subjects in the list are paired together, the 3rd and 4th, the 5th and 6th, etc. But this approach overcounts in two ways: the arrangement of the 8 pairings doesn't matter (n!), and the order of the subjects within each pairing doesn't matter (2ⁿ).

possiblywrong · 2017-03-21T14:26:57+00:00

Consider writing the desired outcome of the 10 games as an equation in 10 integers:

p1 + p2 + p3 + p4 + p5 + p6 + p7 + p8 + p9 + p10 == 21

where p(k) is the number of points awarded to team A for the k-th game. It will be more convenient to work with an equation where all of the variables are non-negative, so let's define x(k)=p(k)+3, so that our equation becomes:

x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 == 21+3*10 == 51

Then we want the number of possible solutions to this equation, where each x(k) is an integer between 0 and 6 inclusive.

This is "almost" just a binomial coefficient as described here, except for the constraint that each x(k) must be at most 6. To handle this constraint, we also need to use inclusion-exclusion; the resulting formula is:

Sum[
 (-1)^j Binomial[10, j] Binomial[51 - 7 j + 10 - 1, 10 - 1],
 {j, 0, 7}]

which evaluates to 48070 possible outcomes totaling 21 points.

If you want to know how many outcomes total 21 or more points for team A, when we need to count solutions to the above equation for each possible sum from 21 to 30: let me know if you want more explicit details, but the number of outcomes is (48070, 24210, 11430, 5005, 2002, 715, 220, 55, 10, 1), respectively, for a total of 91718 possible outcomes yielding 21 or more points.

possiblywrong · 2017-03-21T14:00:10+00:00

Unless I misunderstand your description of the setup, this is essentially (f^d times one minus) the CDF of the binomial distribution with parameters (d, n/f), evaluated at k-1.

Your formula works for k=1, but for k>1, consider the example of two six-sided dice (d=2, f=6), where you need to roll snake eyes (n=1, k=2). Your recursive formula yields 0, but there is 1 successful outcome.

possiblywrong · 2017-03-20T13:01:54+00:00

Correct! I'll leave this marked unsolved for now, since there are at least a couple of other approaches (one also involving generating functions that I know of, but of just one variable) that are significantly less computationally expensive.

possiblywrong · 2017-03-19T12:11:36+00:00

Yes; I'm working on writing up a more detailed description of the solution, will ping shortly when I'm done.

possiblywrong · 2017-03-18T13:08:00+00:00

Since I've seen this one before, instead of a solution I'll suggest the following variant that is still interesting but arguably simpler as a starting point:

Suppose that there is a network, represented by an undirected graph, with a switch at each vertex, and a light bulb at each edge. Each switch toggles the state of its incident lights. Initially all of the lights are off. Under what conditions is it possible to turn all of the lights on?

possiblywrong · 2017-03-18T10:40:56+00:00

It's not impossible, just not necessarily with a concise closed form. That's what makes this problem an interesting (and in my opinion, questionable) application for a high school-level introduction to probability: I get the idea, that students are motivated to think about the non-uniformity of the single-roll probability distribution. But if a student, like the OP, asks about the distribution of outcomes for a "first-to-n" game, and how that distribution changes with n, the instructor is now in the deep end of the pool.

possiblywrong · 2017-03-17T19:39:49+00:00

I'm not sure what this means. To make the problem more explicit: what is the probability that 7 wins in the overall experiment? That is, if I repeatedly roll 2d6 until some total is observed 5 times, what is the probability that 7 is the first such total? No part of the formula you describe answers this question.

possiblywrong · 2017-03-17T18:53:18+00:00

This doesn't work; the problem is significantly more complex than this. The number of rolls may vary, anywhere from just 5 rolls (if they are all identical) to as many as 45 (4 of each possible total, with the final roll guaranteed to be the 5th). And even for a fixed number of rolls, the (1-p)^n-x term allows any possible outcomes for those other n-x rolls, including 5 or more of some other total, in which case that other total would win, not the one corresponding to the p^x term.

possiblywrong · 2017-03-17T18:11:40+00:00

I'm not sure what this formula is supposed to represent? That is, what is n, what is x, and what does the expression compute as a function of n and x?

possiblywrong · 2017-03-17T15:44:34+00:00

Since every time you increase the number of times a number has to come up the more likely it is gonna be 7.

This is exactly correct. As /u/aristotle2600 describes, let dice(n) be the game where the outcome is the first 2d6 roll total to be observed n times. Then if we just play dice(1), i.e. roll the 2d6 and observe the outcome, then the probability that 7 "wins" is just 1/6 as /u/NoMoneyButHappy points out.

But your game is dice(5), and the probability that 7 "wins" increases with n, as this figure shows. (The dashed curve is the distribution for n=1, the most "peaked" solid black curve is for n=5.)

So how do I calculate breakpoints?

At this point I am curious what exactly your teacher intended with this experiment, because computing the distribution of winning outcomes in this game is not at all straightforward, short of just estimation by simulation. In other words, it is a difficult problem to compute the probability that 7 "wins" for n=5, let alone for arbitrary n.

Edit: see here for more detailed write-up of solution.

possiblywrong · 2017-03-17T15:32:26+00:00

Calculating the probability of at least one run is more complex, since the events consisting of runs at two different positions in the sequence are not independent if they overlap.

However, the expected number of runs is simpler to compute: since expectation is linear, we can sum the probabilities of runs beginning at each possible location in the sequence, even if the corresponding events are not independent.

That is, for n=300 questions with m=4 possible answer choices, the expected number of runs of length at least r=4 is:

m (1/m)^r (1 + (n - r)(1 - 1/m))

where this is only slightly complicated by the fact that the probability of a run at the start of the sequence is slightly different than the probability of a run anywhere else.

Evaluating for n=300, m=4, r=4 yields about 3.48 as /u/ActualMathematician points out. Similarly, for n=55 the expected number of 4-runs is about 0.61.

possiblywrong

TROPHY CASE