## P(H heads in a row) given N coin flips = ?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

brainfsck
Posts: 9
Joined: Sun Apr 05, 2009 12:05 am UTC

### P(H heads in a row) given N coin flips = ?

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 brute-force 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.

OverBored
Posts: 284
Joined: Mon Dec 10, 2007 7:39 pm UTC

### 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/Fibonaccin-StepNumber.html
G4!!

Grob FTW,

Hello. Smithers. You're. Quite good. At. Turning. Me. On.

joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

### Re: P(H heads in a row) given N coin flips = ?

...isn't it just 1/(2^n) ?

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.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

d0nk3y_k0n9
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(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 twenty-five flips, or whatever, then that no longer works.

joshz
Posts: 1466
Joined: Tue Nov 11, 2008 2:51 am UTC
Location: Pittsburgh, PA

### 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.
suffer-cait wrote:it might also be interesting to note here that i don't like 5 fingers. they feel too bulky.

brainfsck
Posts: 9
Joined: Sun Apr 05, 2009 12:05 am UTC

### 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/Fibonaccin-StepNumber.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

EclipseEnigma
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 (N-H+1) possible starting positions for the H heads in a row.
The other (N-H) flips can be anything, so the number of valid strings is:
2^(N-H) * (N-H+1)

This yields a probability of
2^(N-H) * (N-H+1)/2^N = (N-H+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 (N-H+1) possible starting positions for the H heads in a row.
The other (N-H) flips can be anything, so the number of valid strings is:
2^(N-H) * (N-H+1)

This yields a probability of
2^(N-H) * (N-H+1)/2^N = (N-H+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 N-H+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 double-counting by requiring the "T-H" 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.

t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

### 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, ... H-1[/imath].

Then I claim that the following system of linear recurrences holds:
[math]s_{n, H-1} = s_{n-1, H-2}[/math]
[math]s_{n, H-2} = s_{n-2, H-3}[/math]
...
[math]s_{n,0} = s_{n-1,0} + s_{n-1,1} + ... + s_{n-1, H-1}.[/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_{n-1,0} + s_{n-2,0} + ... + s_{n-H,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.)