# Probability for the length of the longest run in nn 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.

This problem was solved using generating functions by de Moivre in 1738.
The formula you want is

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)

The combinatorial class of all coin toss sequences without a run of $m$ heads
in a row is

with corresponding counting generating function

We introduce probability by replacing $h$ with $ps$ and $t$ by $qs$,
where $q=1-p$:

The coefficient of $s^n$ in $G(s)$ is $\mathbb{P}(\ell_n

The function $1/(1-s(1-p^ m s^ m q ))$ can be rewritten as

The coefficient of $s^n$ in this function is $c(n)=\sum_{j\geq 0}{n-j m \choose j}(-p^ m q)^j$. Therefore the coefficient of $s^n$ in $G(s)$ is $c(n)-p^ m c(n- m ).$
Finally,