wilmott.com

This problem is probably too easy for this forum, but the answer is so beautiful that I'll post it anyway.You have an unfair coin. Probability of tossing a head is p. What is the expected number of tosses needed to get N consecutive heads?

close to (Np+1-p)*p^(N-1)

draw a tree at N-1 consecutive heads: with probability p you get N consecutive heads. With probability (1-p) you go back to the start and you have used one more throw.Thus:Expected time to get N consecutive heads = Expected time to get (N-1) consecutive heads + p*1 + (Expected time to get N consecutive heads + 1)(1-p)letting x_n be the obvious (expected time for n consecutive heads):x_n = x_{n-1} + p + (x_n + 1)(1-p)so we get a recursion relation x_n = (1/p)(x_{n-1} + 1)since x_1 = 1/p, we can find all the others.This then seems to be the recursion relation for x_n = Sum(1/p^i), where the sum is between i=1 and i=n

QuoteOriginally posted by: amit7ulclose to (Np+1-p)*p^(N-1)This is far from close: This value will actually be less than N for most values of p(You can't get N consecutive heads in less than N tosses )The upper bound (.. a quite liberal one) is: We're looking for THHHHH....H (no. of H = N), (except for the case if we get N heads in first N tosses, when T is not needed).So, if we cut chunks of (N+1) in our sequence of tosses, probability of a chunk having THHH...H is (1-p)*p^N; hence number of chunks needed are 1/[(1-p)p^N] ... so that length of the sequence expected = (N+1)/[(1-p)*p^N] as each chunk is (N+1) long.By same argument N/(p^N) is a tigher upper bound, but the one listed above is, i guess, closer on the path of reaching the actual solution which allows "overlapping" chunks. Edit: I agree with timeds solution below: Sum (1/p^i) .... which is also less than the upper bound of N/(p^N).

While timeds solution is correct, the recursion can also be written a little differently.Let x_i = Expected number of tosses to get n consecutive heads, from a "state" of i consecutive heads. So x_0 is what we are after.Then,x_{i-1} = (x_{i} +1)*p + (1-p)*(x_0 +1)and x_n =0. So, x_{n-1} = p + (1-p)*x_0, and x_{n-2} = p^2 + p + (1+x_0)(1-p^2) etc.The pattern is quite easy to see, so thatx_{n-i} = p^i + p^{i-1} + .... + p + (1-p)*(1+x_0)Setting i=n and solving for x_0 we getx_0 = 1/p + 1/p^2 + .... + 1/p^n

quick calculation gives(1-p^N)/(1-p)/p^N