Suppose the probability to get a head when throwing an unfair coin is p, what's the expected number of throwings in order to get two consecutive heads? We will stop once we get two consecutive heads.I was stuck in this question. Maybe I am a little nervous during the phone interview. This is really a common question that we did in college.

Let p_n be the probability of getting two consecutive heads after exactly n throws. p_1 = 0, p_2 = p^2, p_3 = p^3, etc.Calculate p_n using multi-step induction.

e_t = p(e_h + 1) + (1-p)(e_t + 1)e_h = p + (1-p)(e_t + 1)=> e_t (expected number of tosses to get 2 h from the "tail" state, which is the same as the game not having started in this case) = 1/p + 1/p^2

QuoteOriginally posted by: kwse_t = p(e_h + 1) + (1-p)(e_t + 1)e_h = p + (1-p)(e_t + 1)=> e_t (expected number of tosses to get 2 h from the "tail" state, which is the same as the game not having started in this case) = 1/p + 1/p^2Nice solution, kws!

QuoteOriginally posted by: kwse_t = p(e_h + 1) + (1-p)(e_t + 1)e_h = p + (1-p)(e_t + 1)=> e_t (expected number of tosses to get 2 h from the "tail" state, which is the same as the game not having started in this case) = 1/p + 1/p^2Cool!

Q. What is the probability of getting two consecutive heads after exactly n throws? Say p = 1/2.

Q. What is the probability of getting two consecutive heads after exactly n throws? Say p = 1/2.You do the math. The probability of the game ending at step n is p^2 times the probability that in step n-2 you are in a state that does not follow a head. EDIT: After some grinding, you can actually get the expected value this way too. Kws's solution is much nicer though.

QuoteOriginally posted by: needaclueQ. What is the probability of getting two consecutive heads after exactly n throws? Say p = 1/2.this should be straight forward:(1/2)^nThere is only one path to achieve this result.

There is only one path to achieve this result.For n=4 there are two: TTHH and HTHH.P_4 = 1/8 and not 1/16.

oops .. u'r right.

There is something interesting about the final expression for p_n as a function of "n" which is why I ask the question...QuoteOriginally posted by: benczurQ. What is the probability of getting two consecutive heads after exactly n throws? Say p = 1/2.You do the math. The probability of the game ending at step n is p^2 times the probability that in step n-2 you are in a state that does not follow a head. EDIT: After some grinding, you can actually get the expected value this way too. Kws's solution is much nicer though.

Yes, that is interesting. The unreduced numerator is a Fibonacci series.

QuoteOriginally posted by: kwse_t = p(e_h + 1) + (1-p)(e_t + 1)e_h = p + (1-p)(e_t + 1)=> e_t (expected number of tosses to get 2 h from the "tail" state, which is the same as the game not having started in this case) = 1/p + 1/p^2I think of this in a slightly different way (completely equaivalent, of course): We have an expected number of flips, E. I consider the three outcomes {HH, HT, T}. Each of these outcomes either ends the game, or resturns me to my starting point where I would expect E flips again. With probability p^2 I get two heads in a row and the game ends. With probability p(1-p) I get a head and then a tail, at which point I am back to my starting point, and have an expected number E flips awaiting me to finish. Finally, with probability (1-p) I flip a tail and am back to my starting point again. Putting this together givesE = (2) p^2 + (2+E) p (1-p) + (1+E) (1-p),and solving for E gives the same result.

That's right...for p=1/2, P(n) = F(n-1)/2^n where F(n) is the n'th term in the Fibonacci series 1,1,2,3,5,8,...QuoteOriginally posted by: kwsYes, that is interesting. The unreduced numerator is a Fibonacci series.

The unreduced numerator is a Fibonacci series.I see now what you are saying. If p=1/2 and then you get and , i.e Q_n is the the Fibonacci series.I am not sure how relevant this is, but it suggests another proof: All the paths of length n (n>3) for a game which terminates, can be obtained by sticking an HT in the front of the paths of length n-2 or sticking a T in the front of the ones of length n-1. If p=1/2 all paths carry an equal weight of 1/2^n, so P_n = Q_n/2^n. If p is not 1/2, one recovers the recursion for P_n mentioned above/below.