mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2018-04-04, 17:42   #1
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

117716 Posts
Default N Heads in a Row

Given a coin that lands heads with probability 0 < p < 1, what is the expected number of flips needed to get N heads in a row?

Solve with p = 0.73 and N = 20.

Then can someone give a general method / formula based only on p and N?

Thanks
petrw1 is offline   Reply With Quote
Old 2018-04-04, 18:12   #2
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

32·132 Posts
Default

It's the negative binomial distribution (with parameters N and p).
Nick is online now   Reply With Quote
Old 2018-04-04, 20:01   #3
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

17×263 Posts
Default

Pardon my ignorance but ...

maybe I'm not understanding this right, but it looks like negative binomial distribution is used to determine, for instance, the expected number of tails before a pre-determined number of heads, but not necessarily in order
petrw1 is offline   Reply With Quote
Old 2018-04-04, 21:34   #4
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

27618 Posts
Default

Quote:
Originally Posted by petrw1 View Post
maybe I'm not understanding this right
I think I misunderstood you!

In that case, you can work it out from first principles.
Fix a positive integer \(k\geq N\).
How many ways are there of throwing \(k-N\) times without getting \(N\) heads in a row?
What is the probability of each of those possibilities followed by \(N\) consecutive heads?

Last fiddled with by Nick on 2018-04-04 at 21:34 Reason: Fixed typo
Nick is online now   Reply With Quote
Old 2018-04-04, 22:07   #5
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×5×59 Posts
Default

Quote:
Originally Posted by Nick View Post
How many ways are there of throwing \(k-N\) times without getting \(N\) heads in a row? What is the probability of each of those possibilities followed by \(N\) consecutive heads?
Not quite right, either. The \(k-N\) might have ended with one or more heads. I usually grab the density using the transition matrix for the Markov Chain of #heads in a row with an absorbing state at \(N\), but this question asks for the mean.

I'd try an inductive approach on the number of heads. To get one head in a row, the first toss is a head with probability p or a tail with probability (1-p). If heads, you are done. If tails, you need the to start over. So

X1 = p*1 + (1-p)*(X1+1)
X1 = 1/p

For k in a row, you need k-1 in a row, then one more toss either finishes it or starts it over.

Xk = p*(X(k-1)+1) + (1-p)(Xk+X(k-1)+1)
Xk = X(k-1)/p + 1/p

The logic of the last equation is conditioned on the results of the flip after first achieving k-1 heads.

Check that arithmetic - I fixed several errors before posting and might still have some left - but the logic is solid.
wblipp is offline   Reply With Quote
Old 2018-04-04, 23:37   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by petrw1 View Post
Given a coin that lands heads with probability 0 < p < 1, what is the expected number of flips needed to get N heads in a row?

Solve with p = 0.73 and N = 20.

Then can someone give a general method / formula based only on p and N?

Thanks
Take 1-(1-p)ⁿ to be the probability of getting heads n times ? Factor in how far you've advanced and find where it hits 50% ?
science_man_88 is offline   Reply With Quote
Old 2018-04-05, 04:53   #7
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23·5·59 Posts
Default

Oops - this is Homework Help. I had fun working out the inductive equations and their general solution, but I suppose I shouldn't post all that here. So I stand by the previous suggestion that N+1 heads in a row takes N heads in a row plus one more, and then you may be done or you may need to start over. To check your work, I get 2001.6 for p = 0.73 and N = 20.
wblipp is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 18:44.

Tue Dec 1 18:44:41 UTC 2020 up 82 days, 15:55, 2 users, load averages: 1.31, 1.82, 2.05

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.