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 ℓn, exceeds a given number m, i.e. P(ℓ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.
Answer
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({njm+1\over j}\right)(1p)\right){njm\choose j1}p^{jm}(1p)^{j1}.
References

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

Chapter V, Section 3 Introduction to Mathematical Probability by Uspensky

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)
Added:
The combinatorial class of all coin toss sequences without a run of m heads
in a row is
\sum_{k\geq 0}(\mbox{seq}_{< m }(H)\,T)^k \,\mbox{seq}_{< m }(H),
with corresponding counting generating function
H(h,t)={\sum_{0\leq j< m }h^j\over 1(\sum_{0\leq j< m }h^j)t}={1h^ m \over 1h(1h^ m )t}.
We introduce probability by replacing h with ps and t by qs,
where q=1p:
G(s)={1p^ m s^ m \over1s+p^ m s^{ m +1}q}.
The coefficient of s^n in G(s) is \mathbb{P}(\ell_n<m).
The function 1/(1s(1p^ m s^ m q )) can be rewritten as
\begin{eqnarray*}
\sum_{k\geq 0}s^k(1p^ m s^ m q )^k
&=&\sum_{k\geq 0}\sum_{j\geq 0} {k\choose j} (p^ m q)^js^{k+j m }\\
%&=&\sum_{j\geq 0}\sum_{k\geq 0} {k\choose j} (p^ m q )^js^{k+j m }.
\end{eqnarray*}
The coefficient of s^n in this function is c(n)=\sum_{j\geq 0}{nj 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,
\begin{eqnarray*}
\mathbb{P}(\ell_n\geq m)&=&1\mathbb{P}(\ell_n<m)\\[8pt]
&=&p^ m c(n m )+1c(n)\\[8pt]
&=&p^ m \sum_{j\geq 0}(1)^j{n(j+1) m \choose j}(p^ m q)^j+\sum_{j\geq 1}(1)^{j+1}{nj m \choose j}(p^ m q)^j\\[8pt]
&=&p^ m \sum_{j\geq 1}(1)^{j1}{nj m \choose j1}(p^m q)^{j1}+\sum_{j\geq 1}(1)^{j+1}{nj m \choose j}(p^mq )^j\\[8pt]
&=&\sum_{j\geq 1}(1)^{j+1} \left[{nj m \choose j1}+{nj m \choose j}q\right]p^{ jm } q^{j1}\\[8pt]
&=&\sum_{j\geq 1}(1)^{j+1} \left[{nj m \choose j1}p+{nj m \choose j1}q+{nj m \choose j}q\right]p^{ jm } q^{j1}\\[8pt]
&=&\sum_{j\geq 1}(1)^{j+1} \left[{nj m \choose j1}p+{nj m +1\choose j}q \right]p^{ jm} q^{j1}\\[8pt]
&=&\sum_{j\geq 1}(1)^{j+1} \left[p+{nj m +1\over j}\, q\right] {nj m \choose j1}\,p^{ jm} q^{j1}.
\end{eqnarray*}
Attribution
Source : Link , Question Author : Sasha , Answer Author : Community