Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 23 down vote favorite
7

Suppose a biased coin (probability of head being $p$) was flipped $n$ times. I would like to find the probability that the length of the longest run of heads, say $\ell_n$, exceeds a given number $m$, i.e. $\mathbb{P}(\ell_n > m)$.

It suffices to find the probability that length of any run of heads exceeds $m$. I was trying to approach the problem by fixing a run of $m+1$ heads, and counting the number of such configurations, but did not get anywhere.

It is easy to simulate it:

Distribution of the length of the longest run of head in a sequence of 1000 Bernoulli trials with 60% change of getting a head

I would appreciate any advice on how to analytically solve this problem, i.e. express an answer in terms of a sum or an integral.

Thank you.

share|improve this question
4  
You could have a Markov chain with states $0, 1, 2, \ldots l$ where the probability you move from $i$ to $i+1$ is $p$ and from $i$ to $0$ is $1-p$ for $i<l$ and the probability you move from $l$ to $l$ is $1$. Then you could look at $n$th power of the transition matrix for this chain and read off the answer. – ShawnD Aug 25 '11 at 17:29
@Shawn What you suggest is a Markov chain that would give rise to geometric probability for the length of a single run, yet in $n$ simulations there might be more runs that that. The number of runs is random itself, so distribution I expect to get is not geometric. Besides your idea does not take into account the number of coin flipping. – Sasha Aug 25 '11 at 17:52
I believe my "l" is your "m." The number of flips you make is accounted for by the power of the transition matrix you look at. – ShawnD Aug 25 '11 at 18:09
It is well-known that $\ell_n / \log_2 n \to 1 \,\mathrm{a.s.}$, and not hard to show that for any $\epsilon > 0$, $\mathbb{P}(\ell_n > (1-\epsilon)\log_2 n) \geq 1 - \exp( -n^\epsilon / 2 \log_2 n )$ for large enough $n$. – cardinal Aug 25 '11 at 18:22
@Sasha: Both of your concerns are taken into account in Shawn's proposal. The fact that the transition from $m$ to $m$ has probability $1$ takes care of the possibility of multiple runs of length $m$; the system stays in state $m$ after the first such run. If all you need is the result for a particular $m$, you can use Shawn's approach. Another question is whether the structure of the transition matrix allows one to write the probability in closed form for general $m$ and $n$. – joriki Aug 25 '11 at 18:26
show 5 more comments

4 Answers

up vote 27 down vote accepted

This problem was solved using generating functions by de Moivre in 1738. The formula you want is $$\mathbb{P}(\ell_n \geq m)=\sum_{j=1}^{\lfloor n/m\rfloor} (-1)^{j+1}\left(p+\left({n-jm+1\over j}\right)(1-p)\right){n-jm\choose j-1}p^{jm}(1-p)^{j-1}.$$

References

  1. Section 14.1 Problems and Snapshots from the World of Probability by Blom, Holst, and Sandell

  2. Chapter V, Section 3 Introduction to Mathematical Probability by Uspensky

  3. Section 22.6 A History of Probability and Statistics and Their Applications before 1750 by Hald gives solutions by de Moivre (1738), Simpson (1740), Laplace (1812), and Todhunter (1865)

share|improve this answer
3  
Well damn, didn't see that coming. – anon Aug 25 '11 at 19:17
@Byron Wow, thank you! This is really beyond my expectations. I will check those books out. – Sasha Aug 25 '11 at 19:19
1  
Great answer, Byron. – Mike Spivey Aug 25 '11 at 23:11
up vote 6 down vote

Define a Markov chain with states $0, 1, \ldots m$ so that with probability $1$ the chain moves from $m$ to $m$ and for $i<m$ with probability $p$ the chain moves from $i$ to $i+1$ and with probability $1-p$ the chain moves from $i$ to $0$. If you look at the $n$th power of the transition matrix for this chain you can read off the probability that in $n$ flips you have a sequence of at least $m$ consecutive heads.

share|improve this answer
Shawn Thanks for posting your question (+1). I think I should accept Byron's answer as the one that provides an analytic answer. But your answer has proven a valuable lesson in Markov chains, so thank you again very much for that. – Sasha Aug 25 '11 at 19:24
Yes, his answer is better. – ShawnD Aug 25 '11 at 20:03
@Shawn: The Markov should have $(m+1)(m+2)/2$ states instead of $m+1$. Each state should be an ordered pair $(R,r)$, where $0\le R\le m$ is the length (capped at $m$) of the longest run so far, and $0\le r\le R$ is the length of the current run. Then $(R,r)$ should go to $(R,0)$ with probability $1-p$, and go to state $(R+1,r+1)$ (or itself if $R=m$) with probability $p$. – user1551 Aug 25 '11 at 21:00
@user1551 Shawn's proposal will do just fine, because as I said, the probability equals to probability that length of any run exceeds $m$. Indeed $\max(x_1, x_2, \ldots, x_k) > m$ is logically equivalent to $x_1>m \land x_2 > m \land \ldots \land x_k>m$. – Sasha Aug 25 '11 at 21:07
There was an error in my comment above. State $(R,r)$ should go, with probability $p$, to $(R, r+1)$ if $r<R$, or $(R+1,r+1)$ if $r=R<m$, or itself if $r=R=m$. – user1551 Aug 25 '11 at 21:27
up vote 5 down vote

You can find a limiting distribution, otherwise it's a difficult problem and the closed form solution won't have much practical value. See this for an elementary approach.

share|improve this answer
Thank you for the link. In regards to closed form comment, see Byron's answer above. – Sasha Aug 25 '11 at 19:39
That's a nice reference. Thanks! – Byron Schmuland Aug 25 '11 at 19:58
up vote 5 down vote

I don't think you'll get a simple analytic formula. The problem is essentially equivalent to this one, see my answer there: it involves the $n$-power of a $m \times m$ stochastic matrix (notice that there we are interested in the runs equal or greater than $m$), using a Markov chain (as suggested in the comments by Shawn). You can find also there some asymptotics.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.