
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 answerdifferent 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 scenariowish 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^N2 ? ;)
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 nexttolast flip must be a tail:
h(n) = t(n1)
If the last flip is a tail, the nexttolast can be a head or tail:
t(n) = h(n1) + t(n1)
Substituting the first formula into the second,
t(n) = t(n1) + t(n2)
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 nk 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
