Fog Creek Software
Discussion Board




flipping coins

On average, how many times would you have to flip a coin until you got two consecative heads? How many times before you got three consecutive heads? I like these sort of problems because they are easy to simulate on a computer.

John
Saturday, February 26, 2005

When I tried to figure this problem out I got one number for the two consecutive head scenario, but when I ran a simulation I got six as the answer--different from what I actually calculated theoretically. I am still t rying to figure out where I went wrong in my calculation. I am also working on a simulation for the three consecutive heads scenario--wish me luck:)

Katrina
Sunday, February 27, 2005

Cute riddle. It seems that the average sequence for 2 consecutive heads is 6, for 3 it is 14 and for N it should be ... say 2^N-2 ? ;)

It's very easy though to mistake "what is the average number of flips" for "what number of flips gives 50% chances". Good thing you, John, pointed out in another problem that these two are actually different numbers.

DK
Monday, February 28, 2005

even 2^(N+1)-2

DK
Monday, February 28, 2005

It's neat how the Fibonacci series arises.

Let h(n) be the number of ways you can have n coin flips without two consecutive heads, and with the last flip be a head.
Similarly, let t(n) be the number of ways you can have n coin flips without two consecutive heads, and with the last flip be a tail.

If the last flip is a head, the next-to-last flip must be a tail:
h(n) = t(n-1)                 
If the last flip is a tail, the next-to-last can be a head or tail:
t(n) = h(n-1) + t(n-1)

Substituting the first formula into the second,
t(n) = t(n-1) + t(n-2)
which gives you the Fibonacci sequence.

The probability that that n flips don't include a double head is
p(n) = [h(n) + t(n)] / 2^n

The expected number of flips is
1 + sum (n=1 to infinity)  p(n)

I could do the rest of the algrebra, but I'm too lazy.

Julian
Monday, April 25, 2005

Let H(k,n) be the expected number of flips to get n heads in a row given that the last k flips were heads (so you only need n-k more).
For simplicity, I'll right this is H(k) with an implicit fixed n.

By definition, H(n) = 0 (you've already got n heads).

Note that:
H(i) = 1 + 1/2 H(i+1) + 1/2 H(0) if (i < n)
(Half the time, you get a head, giving you i+1 heads in a row.  Half the time you get a tail, making you start over).

If H(i) = H(0) - K(i), then
H(i) = 1 + 1/2 H(i+1) + 1/2 H(0) (substite H(i))
H(0) - K = 1 + 1/2 H(i+1) + 1/2 H(0) (multiply by two)
2 H(0) - 2K = 2 + H(i+1) + H(0)
H(i+1) = H(0) - 2K(i) - 2

Thus, K(i+1) = 2 (K(i) + 1)

H(0) = 1 + 1/2 H(1) + 1/2 H(0) reduces to
H(1) = H(0) - 2, so K(1) = 2

This gives a recurrence to solve K.

I will show, by induction, that K(i) = 2^(i+1)-2

K(1) = 2 = 2^(1+1) - 2
Presume K(i) = 2^(i+1) - 2.
K(i+1) = 2*(2^(i+1) - 2 + 1) = 2^((i+1)+1) - 2.
QED.

H(n) = H(0) - K(n), so H(0) = K(n).
Therefore,
  H(0) = 2^(n+1) - 2.

Anonymous
Friday, May 06, 2005

*  Recent Topics

*  Fog Creek Home