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.
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:)
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.
Monday, February 28, 2005
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.
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).
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.
H(n) = H(0) - K(n), so H(0) = K(n).
H(0) = 2^(n+1) - 2.
Friday, May 6, 2005
Fog Creek Home