Hi,
I recently thought of the following problem and my basic grasp of probability and combinatorics is not enough to handle it:
You flip a coin N times. What is the probability P(N,H) that you get at least one sequence of at least H heads in a row?
This is not a school/homework problem, so don't worry about the "right" or "intended" way to do it. However, I would appreciate a solution that is, like the problem, relatively simple to understand. Through bruteforce in Mathematica I found that P(20,7) = 3813/65536 ~= 0.0581818, so please make sure your answer fits with this result.
Here is a thread where I decribe what I've tried.
Thanks.
P(H heads in a row) given N coin flips = ?
Moderators: gmalivuk, Moderators General, Prelates
Re: P(H heads in a row) given N coin flips = ?
Ok, I'll have a go at this. Firstly, let P(N,H) = F(N,H) / 2^N
So now F(N,H) is the number of possible combinations of length H in a string of length N.
It turns out that F(N,H) = 2^N  Fibonacci H step (N+2)
I find it very hard to justify this, since I did some number crunching and found OEIS was telling me that my numbers met a certain sequence. Checking mathworld showed that this was a known result (and stems from the fact that the chance of not getting H heads in N throws is found by (Fibonacci H step (N+2))/ 2^N
Formulae for any Fibonacci sequences are recursive, so not very nice, but if you looked around a bit there is probably a paper on why these numbers at the ones you want.
Edit: http://mathworld.wolfram.com/FibonaccinStepNumber.html
So now F(N,H) is the number of possible combinations of length H in a string of length N.
It turns out that F(N,H) = 2^N  Fibonacci H step (N+2)
I find it very hard to justify this, since I did some number crunching and found OEIS was telling me that my numbers met a certain sequence. Checking mathworld showed that this was a known result (and stems from the fact that the chance of not getting H heads in N throws is found by (Fibonacci H step (N+2))/ 2^N
Formulae for any Fibonacci sequences are recursive, so not very nice, but if you looked around a bit there is probably a paper on why these numbers at the ones you want.
Edit: http://mathworld.wolfram.com/FibonaccinStepNumber.html
G4!!
Grob FTW,
Hello. Smithers. You're. Quite good. At. Turning. Me. On.
Grob FTW,
Hello. Smithers. You're. Quite good. At. Turning. Me. On.
Re: P(H heads in a row) given N coin flips = ?
...isn't it just 1/(2^n) ?
P(1 head)=1/2
P(2 heads in a row)= (1/2)*(1/2)=(1/2)^2=(1/2^2)
Same applies for all reals.
P(1 head)=1/2
P(2 heads in a row)= (1/2)*(1/2)=(1/2)^2=(1/2^2)
Same applies for all reals.
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffercait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

 Posts: 97
 Joined: Sun May 03, 2009 4:27 pm UTC
Re: P(H heads in a row) given N coin flips = ?
joshz wrote:...isn't it just 1/(2^n) ?
P(1 head)=1/2
P(2 heads in a row)= (1/2)*(1/2)=(1/2)^2=(1/2^2)
Same applies for all reals.
That would work if H=N, but when we want to get, say, five heads in a row out of twentyfive flips, or whatever, then that no longer works.
Re: P(H heads in a row) given N coin flips = ?
Oh, I misunderstood the question.
You, sir, name? wrote:If you have over 26 levels of nesting, you've got bigger problems ... than variable naming.
suffercait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.
Re: P(H heads in a row) given N coin flips = ?
OverBored wrote:Ok, I'll have a go at this. Firstly, let P(N,H) = F(N,H) / 2^N
So now F(N,H) is the number of possible combinations of length H in a string of length N.
It turns out that F(N,H) = 2^N  Fibonacci H step (N+2)
I find it very hard to justify this, since I did some number crunching and found OEIS was telling me that my numbers met a certain sequence. Checking mathworld showed that this was a known result (and stems from the fact that the chance of not getting H heads in N throws is found by (Fibonacci H step (N+2))/ 2^N
Formulae for any Fibonacci sequences are recursive, so not very nice, but if you looked around a bit there is probably a paper on why these numbers at the ones you want.
Edit: http://mathworld.wolfram.com/FibonaccinStepNumber.html
OK thanks for your help. After Googling, I found a similar solution here among others that I can't understand. One solution that I found notable due to its relative simplicity is:
where:
r=how many in a row
p=probability of a single head= 1/2
n=number of flips

 Posts: 30
 Joined: Wed Jul 15, 2009 1:17 am UTC
Re: P(H heads in a row) given N coin flips = ?
P(N, H) = Valid Strings/All Possibilities
There are clearly 2^N possible strings.
For the valid strings, there are (NH+1) possible starting positions for the H heads in a row.
The other (NH) flips can be anything, so the number of valid strings is:
2^(NH) * (NH+1)
This yields a probability of
2^(NH) * (NH+1)/2^N = (NH+1)/2^H
Hope this helps! (And that I didn't mess up somewhere)
There are clearly 2^N possible strings.
For the valid strings, there are (NH+1) possible starting positions for the H heads in a row.
The other (NH) flips can be anything, so the number of valid strings is:
2^(NH) * (NH+1)
This yields a probability of
2^(NH) * (NH+1)/2^N = (NH+1)/2^H
Hope this helps! (And that I didn't mess up somewhere)
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: P(H heads in a row) given N coin flips = ?
EclipseEnigma wrote:P(N, H) = Valid Strings/All Possibilities
There are clearly 2^N possible strings.
For the valid strings, there are (NH+1) possible starting positions for the H heads in a row.
The other (NH) flips can be anything, so the number of valid strings is:
2^(NH) * (NH+1)
This yields a probability of
2^(NH) * (NH+1)/2^N = (NH+1)/2^H
Hope this helps! (And that I didn't mess up somewhere)
You messed up somewhere. You're double counting strings with two or more blocks with N heads.
I currently have a fairly hideous recurrence. Will write it up and hopefully solve it tomorrow.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: P(H heads in a row) given N coin flips = ?
So start with 2H > N  ie, there not being enough room for two runs.
There are 2^N possible coin flip arrangements.
There are NH+1 possible starting locations for your run.
If the run is not starting at the beginning of the con flips, the prior coin must be a tail.
The other coins can be whatever they want to be.
That isn't hard to express. And it avoids doublecounting by requiring the "TH" transition at the start of the sequence.

When you have room for 2, you get a more complex expression. This is probably where rabbit has a complex recurrance relation.
To simplify, what if we first treated the flips as a 'ring buffer'. Next, when we find a run, we cut it from the sequence, and stitch the ends back together.
Finally, we count how many of the runs crossed any of the stitch points.
Meh, that ends up not being any simpler.
There are 2^N possible coin flip arrangements.
There are NH+1 possible starting locations for your run.
If the run is not starting at the beginning of the con flips, the prior coin must be a tail.
The other coins can be whatever they want to be.
That isn't hard to express. And it avoids doublecounting by requiring the "TH" transition at the start of the sequence.

When you have room for 2, you get a more complex expression. This is probably where rabbit has a complex recurrance relation.
To simplify, what if we first treated the flips as a 'ring buffer'. Next, when we find a run, we cut it from the sequence, and stitch the ends back together.
Finally, we count how many of the runs crossed any of the stitch points.
Meh, that ends up not being any simpler.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: P(H heads in a row) given N coin flips = ?
The standard way to solve a problem like this is by recursion. Let [imath]s_{n, k}[/imath] denote the number of sequences of [imath]n[/imath] coin flips with the property that
1) there are never [imath]H[/imath] or more heads in a row, and
2) the sequence ends in [imath]k[/imath] heads, [imath]k = 0, 1, ... H1[/imath].
Then I claim that the following system of linear recurrences holds:
[math]s_{n, H1} = s_{n1, H2}[/math]
[math]s_{n, H2} = s_{n2, H3}[/math]
...
[math]s_{n,0} = s_{n1,0} + s_{n1,1} + ... + s_{n1, H1}.[/math]
These can be proven by looking at all the possible last flips. This is equivalent to the single recurrence
[math]s_{n,0} = s_{n1,0} + s_{n2,0} + ... + s_{nH,0}.[/math]
Are you familiar with how to solve linear recurrences? (Based on the form of this recurrence, the solution you quoted for its "relative simplicity" is almost certainly wrong.)
1) there are never [imath]H[/imath] or more heads in a row, and
2) the sequence ends in [imath]k[/imath] heads, [imath]k = 0, 1, ... H1[/imath].
Then I claim that the following system of linear recurrences holds:
[math]s_{n, H1} = s_{n1, H2}[/math]
[math]s_{n, H2} = s_{n2, H3}[/math]
...
[math]s_{n,0} = s_{n1,0} + s_{n1,1} + ... + s_{n1, H1}.[/math]
These can be proven by looking at all the possible last flips. This is equivalent to the single recurrence
[math]s_{n,0} = s_{n1,0} + s_{n2,0} + ... + s_{nH,0}.[/math]
Are you familiar with how to solve linear recurrences? (Based on the form of this recurrence, the solution you quoted for its "relative simplicity" is almost certainly wrong.)
Who is online
Users browsing this forum: No registered users and 12 guests