Contest Answer: Minimum Number Of Coin Tosses Such That Probability Of Getting 3 Consecutive Heads Is Greater Than 1/2

On April 25, We announced a contest with a question in probability (check it here). The question went as follows -

A fair coin is tossed multiple times. What is the minimum number of coin tosses such that the probability of getting three consecutive heads is greater than 1/2 (half)

Here is the solution -

As in any mathematical question, lets first denote the events by easily identifiable names. Lets say T denotes that a toss turns Tails and H denotes that a toss turns Head.

As many of you would have realized, there are many cases in which there can be three consecutive heads [remember even 4 or more consecutive heads will have to be counted]. In such cases, it is normally easier to calculate the inverse probability and since p + p’ = 1 we can find p by just finding p’ and subtracting by 1.

So let p = probability of getting three consecutive heads

and p’ probability of not getting three consecutive heads

Alternatively, p’ = (total events with no three consecutive heads)/ (total number of events possible)

The denominator is 2^n where n is the number of coin tosses.

Lets define two functions -

Let T(n) denote the sequence of n events that end with a tail (the last toss) but has no three consecutive heads

and

Let H(n) denote the sequence of n events that end with a head (again the last toss) but has not three consecutive heads

That means, for set of n tosses, we can write

p’ = [T(n) + H(n)]/2^n

For n = 1

T(n) = 1

H(n) = 1

Hence p’ = 1 [i.e. p = 0, zero probability of getting three consecutive heads, understandable)

For n =2

T(n) = 2  [HT, TT]

H(n) = 2 [HH, TH]

p’ = 4/4 = 1

For n = 3

T(n) = 4 [HHT, THT, TTT, HTT]

H(n) = 3 [THH, HTH, TTH]

p’ = 7/8

Now, we can go on like this till be get p’ less than .5 [and p>1/2 as asked in the question]. But here is a better way. What if we can derive T(n+1) and H(n+1) from the previous terms?

T(n+1) can be calculated by summing all the possible events till n tosses. i.e. H(n) and T(n). H(n) followed by a T will result in T(n+1) event similarly for T(n). Hence,

T(n+1) = H(n) + T(n)

What about H(n+1)? This is little tricky. I can write it as

H(n+1) = T(n) + T(n-1)

That is, to avoid three consecutive Hs, the set of previous events will have to be either T(n) – only one H or T(n-1) – two consecutive Hs.

Now we can calcular p, p’, H(n) and T(n) for all n using the above equations. Lets tabulate them -

We can see that the probability of three consecutive heads will keep increasing as the number of tosses increase and if there there are ten tosses or more than ten tosses, the probability will exceed half.

The answer is 10.

[All the students who got the correct answer will be hearing from us shortly]