Results 1 to 4 of 4

Math Help - 100 Coin Flips

  1. #1
    Junior Member
    Joined
    Dec 2009
    Posts
    34

    100 Coin Flips

    A fair coin is flipped 100 times. What is the probability (correct to 2 decimal places expressed as a percentage) that you get at least 6 tails in a row?

    Tougher question than it looks. I have 2 potential answers:

    1. 75.00%
    2. 54.61%

    What do YOU get!?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    Re: 100 Coin Flips

    Quote Originally Posted by Corpsecreate View Post
    A fair coin is flipped 100 times. What is the probability (correct to 2 decimal places expressed as a percentage) that you get at least 6 tails in a row?

    Tougher question than it looks. I have 2 potential answers:

    1. 75.00%
    2. 54.61%

    What do YOU get!?
    I get

    3. 66.26%

    Sometimes it is easier to find the complementary probability, i.e. the probability that you do not get 6 tails in a row. To that end, there are 2^100 possible sequences of heads or tails, each of which we assume are equally likely. Let a_n be the number of sequences of n heads or tails in which there are not 6 tails in a row. It's easy to see that
    a_n = 2^n for 1 \leq n \leq 5
    and
    a_6 = 2^5

    For n > 6, consider the number of acceptable sequences ending in H, T, TT, TTT, TTTT, TTTTT. There are a_{n-1}, a_{n-2}, a_{n-3}, a_{n-4}, a_{n-5}, \text{ and } a_{n-6} of these, respectively. So

    a_n =a_{n-1}+ a_{n-2}+ a_{n-3}+ a_{n-4}+ a_{n-5}+ a_{n-6} for n > 6

    We can use this recurrence to find that
    a_{100} \approx 4.27765 \times 10^{29}
    (I used a spreadsheet)
    so the probability that no sequence of 6 tails occurs in 100 flips is approximately

    \frac{4.27765 \times 10^{29}}{2^{100}} = 0.337447

    and the probability that at least one sequence of 6 tails occurs is

     1-  0.337447 = 0.662553
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Dec 2009
    Posts
    34

    Re: 100 Coin Flips

    I ran this problem through a brute force program and the correct answer is 54.61%. An explanation here (not by me):

    It's not easy. I thought about it for a while and came up with the correct answer, but I would not characterise it as easy. I'll start by noting you can find the answer here but that doesn't really offer any insight into where it comes from (and I couldn't find an explanation anywhere).

    The following is how I worked out the answer, but there may be a simpler way to think of it.

    Denote the number of ways to get N tails in a row in A flips by f(A). Obviously, if we flip the coin fewer than N times, there's no chance of getting N tails, so f(A)=0 for A<N. Also obvious is that for A=N, there's exactly one way to do it, so f(N)=1.

    Suppose we know the value of f(V) for some V>N. Now what is f(V+1)? Well, we are just adding a flip to the end, which can come up either tails or heads, so each of the ways in f(V) counts twice -- once with a tail at the end and once with a head at the end. But that's not all because there are some positions of V flips where:
    (1) there were N-1 tails at the end; and
    (2) nowhere in the position were there N tails in a row
    Each of those positions of V flips gives rise to one position of V+1 flips where there are N tails in a row because adding one more tail to the end makes it N rather than N-1 tails. Note that condition (2) is important because otherwise we will double count positions that contain N tails in a row.

    I will denote the "number of ways of flipping a coin V times such that (1) the last N-1 flips are all tails and (2) nowhere in the V flips are there N tails in a row" by Q(V).

    So putting that together, f(V+1) = 2 * f(V) + Q(V)

    But what is Q(V)? Well, we know that out of the V flips, the last N flips are fixed: the last N-1 flips have to be tails, and the flip before the tails has to be a head, because otherwise there would be N tails in a row, which would violate condition (2) and mean it's not actually in Q(V). So N flips are fixed which leaves V-N flips free. If those free flips could be totally anything, there would be 2^(V-N) total positions. But in those V-N flips, there can't be N tails in a row. By definition, there are f(V-N) ways of getting N tails in a row in V-N flips, which we have to subtract off.

    Therefore, Q(V) = 2^(V-N) - f(V-N).

    It turns out that Q(V) is precisely the definition of the V-th Fibonacci N-step number, which is where the formula on that page comes from.

    So now we have the following recurrence relation:
    f(A) = 0 for A < N,
    f(A) = 1 for A = N,
    f(A) = 2 * f(A - 1) + Q(A - 1),
    Q(V) = 0 for A < N, and
    Q(V) = 2^(V-N) - f(V-N) for A >= N.

    Using the recurrence relation, you can evaluate f(A) using a computer program or a spreadsheet. And of course, the answer to the original problem is f(100)/2^100 where N=6. The exact answer is 692255904222999797557597756576/2^100.0. This turns out to be approximately 54.61%.


    Note that the answer is not 75%. If you mistakenly double count positions where "the last N-1 flips are tails and N tails in a row occurs somewhere", then you will get 75%. In other words, if you incorrectly define Q(V) to be 2^(V-N), then you will get 75%, but it's wrong.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    Re: 100 Coin Flips

    Oops, I see I got careless with one of the initial conditions for the recurrence. I should have a_6 = 63.

    With that change, my answer agrees with Corpsecreate's: a_{100} \approx 5.75395 \times 10^{29}, and the probability of at least one run of 6 successive tails is 0.546094.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. probability outcomes about coin flips
    Posted in the Statistics Forum
    Replies: 3
    Last Post: September 30th 2010, 06:56 PM
  2. [SOLVED] How many coin flips until first tail/head
    Posted in the Statistics Forum
    Replies: 2
    Last Post: September 25th 2010, 10:15 PM
  3. flips of coin
    Posted in the Statistics Forum
    Replies: 2
    Last Post: January 1st 2010, 02:36 PM
  4. 100 coin flips, variance?
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: October 13th 2009, 09:29 AM
  5. P(H heads in a row) given N coin flips
    Posted in the Statistics Forum
    Replies: 2
    Last Post: October 3rd 2009, 10:31 PM

/mathhelpforum @mathhelpforum