All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Many Heads part 2 (Posted on 2021-08-02) Difficulty: 3 of 5
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.

No Solution Yet Submitted by Jer    
Rating: 4.5000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
re: trial and error with the computer -> Proof Comment 2 of 2 |
(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
  Posted by Steven Lord on 2021-08-17 20:46:05

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (14)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information