   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 6, 2005 Recent Topics Fog Creek Home