Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

What is the probability of getting 15 or more CONSECUTIVE heads over 40 coin tosses?

  1. Aug 19, 2009 #1
    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.
     
    Last edited: Aug 19, 2009
  2. jcsd
  3. Aug 20, 2009 #2
    Re: What is the probability of getting 15 or more CONSECUTIVE heads over 40 coin toss

    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
    [tex]\sum_{i=15}^{38} (2\cdot 2^{40-i-1} + (i+2) 2^{40-i-2})[/tex]
    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
    [tex]\frac{1}{2^{40}} \left ( \sum_{i=15}^{40} f(i) - \sum_{i=15}^{40} \sum_{j=15}^{40} h(i,j) \right )[/tex]
    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).
     
    Last edited: Aug 20, 2009
  4. Aug 20, 2009 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Re: What is the probability of getting 15 or more CONSECUTIVE heads over 40 coin toss

    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.
     
  5. Aug 20, 2009 #4
    Re: What is the probability of getting 15 or more CONSECUTIVE heads over 40 coin toss

    thanks a lot!
     
  6. Aug 21, 2009 #5

    statdad

    User Avatar
    Homework Helper

    Re: What is the probability of getting 15 or more CONSECUTIVE heads over 40 coin toss

    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
     
  7. Aug 22, 2009 #6
    Re: What is the probability of getting 15 or more CONSECUTIVE heads over 40 coin toss



    Well , I dont 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
     
  8. Aug 22, 2009 #7
    Re: What is the probability of getting 15 or more CONSECUTIVE heads over 40 coin toss

    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!
     
    Last edited: Aug 22, 2009
  9. Aug 22, 2009 #8
    Re: What is the probability of getting 15 or more CONSECUTIVE heads over 40 coin toss

    Srijithju, 0.0004119... is the right answer, as I confirmed using Hurkyl's method. There are a few problems with your calculations.
     
  10. Aug 23, 2009 #9
    Re: What is the probability of getting 15 or more CONSECUTIVE heads over 40 coin toss

    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 :
    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 seperate 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
     
    Last edited: Aug 23, 2009
  11. Aug 8, 2010 #10
    Re: What is the probability of getting 15 or more CONSECUTIVE heads over 40 coin toss

    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.
     
  12. Aug 10, 2010 #11
    Re: What is the probability of getting 15 or more CONSECUTIVE heads over 40 coin toss

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

    Marc
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: What is the probability of getting 15 or more CONSECUTIVE heads over 40 coin tosses?
Loading...