# Probability for the length of the longest run in $n$ Bernoulli trials

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:

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.

-
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

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)

-
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
Great answer, Byron. – Mike Spivey Aug 25 '11 at 23:11

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.

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

-