Probability of 15+ Consecutive Heads Over 40 Coin Tosses

[redphoton]

What is the probability of getting 15 OR MORE CONSECUTIVE heads over 40 coin tosses?

Can you approximate the solution with simulations?

Is there an analytical way to get the exact solution?

(I'm getting conflicting figures around 0.0004) Thanks in advance.

 

[mXSCNT]

It is possible, although somewhat tedious, to do this exactly using the principle of inclusion and exclusion. If it were 20 heads in a row instead of 15 it would be a little simpler.

We want to count the number of ways to get 15 or more heads in a row. Start by trying to count the number of ways to get exactly 15 heads in a row, then count the number of ways to get exactly 16, and so forth, and add them. For a first attempt to count the ways to get exactly 15, we first choose a position to start our run of 15, then let the flips that are not in the run vary at will. The cases are:
- position 1 (first head of the run is at the start of the string). 16 determined spots including the tail after the run of heads, 24 left to vary. 2^24 possible ways, one position
- position 2-25 (middle of the string). 17 determined spots including the tail before and after the run, 23 left to vary. 2^23 possible ways, 24 positions
- position 26 (end of the string) 16 determined spots including the tail before the run of heads, 24 left to vary. 2^24 possible ways, one position.
So we get as our first attempt 2*2^24 + 24*2^23. But this is not exactly correct, because what if there are 2 runs of exactly 15 heads? We'd be counting that case twice.

Fortunately, 2 runs of 15 heads is incredibly unlikely, so we can make a good first approximation if we simply ignore this hitch. Continuing, we find that the number of ways f(i) to have a run of exactly i heads, ignoring the edge cases of runs of length 39 or 40, is about
f(i) = 2 * 2^(40 - i - 1) + (40-i-1) * 2^(40 - i - 2)
That would give a value of
\sum_{i=15}^{38} (2\cdot 2^{40-i-1} + (i+2) 2^{40-i-2})
Divide this by 2^40 to get a reasonably close approximation of your probability, 0.00041199.

If you want, we can be exact. We can find the number of ways to get 2 runs of 15 or more heads each, because there is no way to get 3 runs of that length. Define a function:

h(i,j) = the number of ways to get a run of exactly i heads and a different run of exactly j heads (where i,j >= 15, and h(i,j) = 0 if i+j >= 40).
You can reason for yourself (work by cases, as I did for f(i)) what h(i,j) would be, if you're interested. Note that each h(i,j) is counted twice in our earlier approximation; it is counted when we count the run of length i, and it is counted again when we count the run of length j (and if i=j it is counted twice with the run of length i). So we can just subtract each h(i,j), and the _exact_ answer for your probability is
\frac{1}{2^{40}} \left ( \sum_{i=15}^{40} f(i) - \sum_{i=15}^{40} \sum_{j=15}^{40} h(i,j) \right )
It would be tedious to finish defining h(i,j) and f(i) to get a numeric value for this, but you can be assured it is very close to, though a bit less than, 0.00041199. (It's probably the same as the approximation, to that number of digits).

 

[Hurkyl]

If we're doing an iterative calculation, the simplest to set up is to define a function like the following:

f(x,y) = The probability of, over x coin throws, of getting a sequence that ends with exactly y consecutive heads, but does not contain a run of 15 consecutive heads

f(0,y) is easy to compute, and it's a straightforward task to write down a recursive formula for f(n+1,y) in terms of the f(n,z), and then to compute the value you want from this.

If we're using a computer algebra system, it's easy enough to solve this linear recursion to get an explicit (albeit probably messy) formula.

 

[redphoton]

thanks a lot!

 

[statdad]

Look around on the "theory of runs", used in probability and by some folk who study stock fluctuations. Statisticians also used the idea in the investigation of whether the "hot hand" in basketball was real (it isn't).

Here is one introduction
http://faculty.pittstate.edu/~ananda/STATMETHODI/Theory-of-runs.pdf

 

[srijithju]

It is possible, although somewhat tedious, to do this exactly using the principle of inclusion and exclusion. If it were 20 heads in a row instead of 15 it would be a little simpler.

We want to count the number of ways to get 15 or more heads in a row. Start by trying to count the number of ways to get exactly 15 heads in a row, then count the number of ways to get exactly 16, and so forth, and add them. For a first attempt to count the ways to get exactly 15, we first choose a position to start our run of 15, then let the flips that are not in the run vary at will. The cases are:
- position 1 (first head of the run is at the start of the string). 16 determined spots including the tail after the run of heads, 24 left to vary. 2^24 possible ways, one position
- position 2-25 (middle of the string). 17 determined spots including the tail before and after the run, 23 left to vary. 2^23 possible ways, 24 positions
- position 26 (end of the string) 16 determined spots including the tail before the run of heads, 24 left to vary. 2^24 possible ways, one position.
So we get as our first attempt 2*2^24 + 24*2^23. But this is not exactly correct, because what if there are 2 runs of exactly 15 heads? We'd be counting that case twice.

Fortunately, 2 runs of 15 heads is incredibly unlikely, so we can make a good first approximation if we simply ignore this hitch. Continuing, we find that the number of ways f(i) to have a run of exactly i heads, ignoring the edge cases of runs of length 39 or 40, is about
f(i) = 2 * 2^(40 - i - 1) + (40-i-1) * 2^(40 - i - 2)
That would give a value of
\sum_{i=15}^{38} (2\cdot 2^{40-i-1} + (i+2) 2^{40-i-2})
Divide this by 2^40 to get a reasonably close approximation of your probability, 0.00041199.

If you want, we can be exact. We can find the number of ways to get 2 runs of 15 or more heads each, because there is no way to get 3 runs of that length. Define a function:

h(i,j) = the number of ways to get a run of exactly i heads and a different run of exactly j heads (where i,j >= 15, and h(i,j) = 0 if i+j >= 40).
You can reason for yourself (work by cases, as I did for f(i)) what h(i,j) would be, if you're interested. Note that each h(i,j) is counted twice in our earlier approximation; it is counted when we count the run of length i, and it is counted again when we count the run of length j (and if i=j it is counted twice with the run of length i). So we can just subtract each h(i,j), and the _exact_ answer for your probability is
\frac{1}{2^{40}} \left ( \sum_{i=15}^{40} f(i) - \sum_{i=15}^{40} \sum_{j=15}^{40} h(i,j) \right )
It would be tedious to finish defining h(i,j) and f(i) to get a numeric value for this, but you can be assured it is very close to, though a bit less than, 0.00041199. (It's probably the same as the approximation, to that number of digits).

Well , I don't think you need to go to such an extent so as to exclude the cases that you counted twice , where there are 2 runs of 15 heads.I think we can solve the problem as follows :

prob ( 15 or more consec. heads in a run of 40 ) = no.of favourable cases / tot no . of cases.

now ,
no.of favourable cases = no. of cases of 15 or more heads where the first 15 tosses are heads + no. of cases of 15 or more heads where 1st is tail , then 2nd to 16th is head + no. of cases of 15 or more heads where 2nd is tail , then 3rd to 17th is head + ...... + no. of cases of 15 or more heads where 24th is tail ,and 25th to 40 is heads.now ,
no. of cases of 15 or more heads where the first 15 tosses are heads = 2^25 (because the remaining 25 throws can be anything either heads or tails)all other terms in the sum = 2^24,
so,
no. of favourable cases = 2^24 + 24*(2^24)hence prob (that 15 consec heads occur in 40 coin tosses)
= { 2^24 + 24*(2^24) } / 2^40

= 0.00039673

 

[redphoton]

This is a very interesting approach by Srijithju, but it should read P = { 2^25 + 25*(2^24) } / 2^40 = 0.000411987, which is remarkably accurate!
Thanks!

 

[mXSCNT]

Srijithju, 0.0004119... is the right answer, as I confirmed using Hurkyl's method. There are a few problems with your calculations.

 

[srijithju]

Srijithju, 0.0004119... is the right answer, as I confirmed using Hurkyl's method. There are a few problems with your calculations.

Yes there are a few problems with my calculations -

1. As redphoton mentioned it should be :
P = { 2^25 + 25*(2^24) } / 2^40

2. But still I am counting in my method certain cases twice .

Because since I counted all cases with 1st 15 heads in 1 step :

now ,
no. of cases of 15 or more heads where the first 15 tosses are heads = 2^25 (because the remaining 25 throws can be anything either heads or tails)

and then later , I am considering the cases where 16 - 30 is head , 17 - 31 is head etc . It is clear that if there is are two separate runs of 15 heads then these are actually being counted twice .

But the number of overlapping ( the cases I counted twice ) cases can be computed easily :

Two runs of 15 heads occur if 1- 15 is head , and 16- 31 is head and so on .

So we have to count all cases where there are 2 runs of heads when :

16- 30 is head , - 1* 2^10 cases ( because 1-15 are heads and 31- 40 can be anything)
17 - 31 is head , - (1 + 2) * 2^9 cases

18 -32 is head , (1+ 2 + 2^2 ) * 2^8 cases

etc...So number of overlapping cases = 1 * 2^10 + { 1+2 } * 2^9 + { 1 + 2 + 2^2 } *2^8 + {1 + 2 + 2^3 }*2^7 + ... { 1 + 2 + ... 2^10}

= {2^1 - 1} *2^10 + { 2^2 - 1 } *2^9 + {2 ^3 - 1 } *2^8 + ... { 2^11 -1 }
= 11*2^11 - ( 2^11 - 1)
= 10 * 2^11 +1

.

Hence the soln to the problem should be :

P = { 2^25 + 25*(2^24) - 10*2^11 -1 } / 2^40 = 0.00041197

 

[mathman1]

Your question is thoroughly answered (in the most general case of N coins and K heads in a row and a probability p of a head) at:

http://www.askamathematician.com/?p=3126

There you will find an explicit formula as well as sample code for doing the calculation.

 

[Stellaferox]

And in this post, now on page 5:
"Probability Problem - Coin Tossing ( 1 2 3)"

Marc