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 = ?

Postby brainfsck » Sun Oct 04, 2009 8:01 pm UTC

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.

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

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

Postby OverBored » Sun Oct 04, 2009 9:34 pm UTC

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.

User avatar
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 = ?

Postby joshz » Mon Oct 05, 2009 1:38 am UTC

...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.
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 = ?

Postby d0nk3y_k0n9 » Mon Oct 05, 2009 2:10 am UTC

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

User avatar
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 = ?

Postby joshz » Mon Oct 05, 2009 2:17 am UTC

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 = ?

Postby brainfsck » Mon Oct 05, 2009 6:24 am UTC

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:

Image
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 = ?

Postby EclipseEnigma » Mon Oct 05, 2009 2:15 pm UTC

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)

User avatar
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 = ?

Postby jestingrabbit » Mon Oct 05, 2009 2:36 pm UTC

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.

User avatar
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 = ?

Postby Yakk » Mon Oct 05, 2009 4:19 pm UTC

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.

User avatar
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 = ?

Postby t0rajir0u » Mon Oct 05, 2009 4:46 pm UTC

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.)


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 12 guests