mersenneforum.org N Heads in a Row
 Register FAQ Search Today's Posts Mark Forums Read

 2018-04-04, 17:42 #1 petrw1 1976 Toyota Corona years forever!     "Wayne" Nov 2006 Saskatchewan, Canada 5×911 Posts 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
 2018-04-04, 18:12 #2 Nick     Dec 2012 The Netherlands 1,627 Posts It's the negative binomial distribution (with parameters N and p).
 2018-04-04, 20:01 #3 petrw1 1976 Toyota Corona years forever!     "Wayne" Nov 2006 Saskatchewan, Canada 107138 Posts 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
2018-04-04, 21:34   #4
Nick

Dec 2012
The Netherlands

1,627 Posts

Quote:
 Originally Posted by petrw1 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

2018-04-04, 22:07   #5
wblipp

"William"
May 2003
New Haven

3×787 Posts

Quote:
 Originally Posted by Nick 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.

2018-04-04, 23:37   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts

Quote:
 Originally Posted by petrw1 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% ?

 2018-04-05, 04:53 #7 wblipp     "William" May 2003 New Haven 3×787 Posts 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.