A coin is biased with P(heads)=p.
What is the expected number of flips to get n consecutive heads?
For a fair coin, here is the original Many Heads.
(In reply to
trial and error with the computer by Charlie)
Charlie's empirical solution can be proven to be correct via induction
(in the spirit of the puzzle's link).
He has:
Ek = (1/p^(k+1)-1/p) / (1/p - 1)
Ek = (1-p^k) / (p^k-p^(k+1)) (1)
First, we prove it is true for k=1, one head in a row (elementary):
For an outcome of probability p, E1 = 1/p to get the outcome.
Proof: on the first event, the outcome occurs with probability p
and does not occur with (1-p). If not, then it will happen in E1 more events. So
E1 = p (1) + (1-p) (E1+1)
E1 = 1/p
Likewise, in (1),
E1 = 1/p
Second, we get a relationship for k+1 from k:
The expectation for k-1 heads in a row is E(k-1). Then, on the next throw, we will either finish, getting a heads with probability p, or not with (1-p). If not, it will take Ek more throws. So,
Ek = p (E(k-1) + 1) + (1-p) ( E(k-1) + 1 + Ek )
Ek = (1/p) ( E(k-1) + 1 )
E(k+1) = (1/p) (Ek + 1)
Back to (1), does E(k+1) follow this recursion?
(1/p) (Ek + 1)
= (1/p) [ (1-p^k)/(p^k - p^k+1) + (p^k-p^(k+1))/(p^k-p^(k+1))]
= (1-p(k+1))/(p^(k+1)-p^(k+2))
= E(k+1)
QED
===============
This then leaves the need for a derivation from fundamental principles to get (1) in the first place :-)
Edited on August 18, 2021, 12:32 am
re: trial and error with the computer -> Proof
