How do I solve the coin problem?

What are the odds of 5 or more heads or tails in a row out of 20 coin tosses?

• I think that this problem is very difficult partly because it does not have a closed form algebraic solution. I was able to solve it with a Markov transition matrix or a recursive solution. Here is the exact answer using 10 coin tosses and different size streaks from 2 to 10. The extreme cases of 2 and 10 are fairly obvious. -------------- Streak length , probability of a streak at least that length out of 10 coin tosses. 2, 1022/1024 3, 846/1024 4, 476/1024 5, 222/1024 6, 96/1024 7, 40/1024 8, 16/1024 9, 6/1024 10, 2/1024 --------------- You can check your technique using these answers. --------------- The wizard of odds published my paper about this subject on Thursday in his column. http://wizardofodds.com/askthewizard/232 ============== I would like opinions. Is the paper interesting? Do the results suprise you? Do you think people totally understimate the commonality of streaks? Do you think casinos capitalize on this belief? Can you get the results yourself ? If you think you can answer the question I would prefer it n the form the answer is m/2^20 and the value of m= ____, however if you give the answer as a percentage that is fine.

• Answer:

  I got 480670 / 2^20, or 45.84%. Let a(k,n) denote the number of possibilities of getting a streak of k or more in n tosses. For k>n, let a(k,n) be trivially zero. Let n ≥ k. The streak can begin at the very first toss, which generates 2*2^(n-k) positive cases. If the streak does not begin at the first toss, it means that the first run is shorter than k equal tosses. In other words, the result was the same for l<k tosses and then changed. The rest behaves exactly as the definition of a(k, n-l) goes: for each positive case of the couple (k, n-l), we can fill the appropriate "history" only one way. So we just sum a(k, n-l) for 1 ≤ l < k. This gives a recurrence relation: a(k, n) = 2*2^(n-k) + Σ [l=1 to k-1] a(k, n-l), which can be solved in closed form only for a few small k's; for k>5, it presumably leads to insolvable polynomials (of degree ≥ 5). This also excludes finding a closed form for all a(k, n) unless we are extremely lucky to get a sequence of exceptional cases of solvable polynomials. For k=5, it is possible to express a(5, n) analytically but it would take quite some time, so I will calculate the terms explicitly. a(5, 1) = a(5, 2) = a(5, 3) = a(5, 4) = 0 a(5, 5) = 2*2^0 + 0 + 0 + 0 + 0 = 2 a(5, 6) = 2*2^1 + 2 + 0 + 0 + 0 = 4 + 2 = 6 a(5, 7) = 2*2^2 + 6 + 2 + 0 + 0 = 8 + 6 + 2 = 16 a(5, 8) = 2*2^3 + 16 + 6 + 2 + 0 = 16 + 16 + 6 + 2 = 40 a(5, 9) = ... = 96 a(5, 10) = ... = 222 <== We can check with your result cited above a(5, 11) = 502 ... a(5, 19) = 229664 a(5, 20) = 480670 <== For 20 tosses. The probability = number of positive cases / number of all cases = a(5, 20) / 2^20 = 480670 / 1048576 = 45.84%.