Expected Minimum Number of Coin Tosses for 3 Tails in a Row

[caffeine]

I've been reviewing prob and stats which I took 10 years ago (ulp!) and came across a problem I can't solve. Consider the problem:

What is the expected minimum number of coin tosses you'd need to make in order to get 3 tails in a row?

Initial thought: the probability of getting a H followed by 3 T is p = (1/2)^4. These are Bernoulli trials, so the expected number of trials to get 3 T is:

E(T=3) = 1/p = 2^4 = 16

However, I've seen that the probability is really p = (1/2)^4 - 2, and the expected number of tosses to get 3 tails is really:

E(T=3) = 2^4 - 2 = 14

I wrote a program in C to calculate this expectation, and the average looks very 14-ish, definitely not 16-ish:

$ ./a.out
Average is 13.992740.
$ ./a.out
Average is 13.996880.
$ ./a.out
Average is 14.003285.
$ ./a.out
Average is 13.956330.
$ ./a.out
Average is 13.982135.
$ ./a.out
Average is 13.982135.
$ ./a.out
Average is 14.000490.

so it appears that 14 is correct. I'm really struggling to understand that "-2" in the probability and expectation value. Does anyone understand it?

 

[Hurkyl]

Well, I can't say I know a direct way to get the answer, I would attack the problem recursively.

Let x denote the expected number of times we need to flip a coin to get three tails in a row.

In what way may we flip a coin to get TTT? (three tails in a row) Let me count the ways:

(1) We start with H, then continue flipping until we get TTT.
(2) We start with TH, then continue flipping until we get TTT.
(3) We start with TTH, then continue flipping until we get TTT.
(4) We start with TTT.

So, if we work out the odds of each case, and the expected number of flips in each case (in terms of x!), then we should get a formula for x (in terms of x), which we should be able to solve for x.



The reason your approach failed is that the individual trials are not independent -- consecutive 4-long attempts at getting HTTT overlap.

 

[kleinwolf]

I feel this solution is wrong...let consider the possible triplet : they are 8, one of them is TTT, so that the average number of trial of triplet experiment should be 4 (average of the possible triplets)...hence 4*3=12. But you know that the last triplet-trial is TTT only if you already know the two last trial before the last T, hence 12+2=14 ? Does this make any sense ?

 

[tmc]

This is what I have:
Let W be the number of consecutive similar tosses, p the probability that the next toss is the same as the previous toss (here, 0.5)
W = 3p^2 + (1+W)p + (2+W)p^2
therefore,
W= -(5p^2+p)/(p^2+p-1)
Plugging in values
W=7
Here, W is the number of tosses to get either 3 heads or 3 tails. Since youre looking for 3 tails only, W must be multiplied by 1/p = 2, such that
W'=14

 

[moose]

Well, the lowest number of tosses POSSIBLE for it to be three tails in a row is three tosses, but other than this I think that 14 is the average amount it takes.