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

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.


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


  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
\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}={1-h^ m \over 1-h-(1-h^ m )t}.
We introduce probability by replacing h with ps and t by qs,
where q=1-p:
G(s)={1-p^ m s^ m \over1-s+p^ m s^{ m +1}q}.
The coefficient of s^n in G(s) is \mathbb{P}(\ell_n<m).

The function 1/(1-s(1-p^ m s^ m q )) can be rewritten as
\sum_{k\geq 0}s^k(1-p^ 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 }.

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 ).
\mathbb{P}(\ell_n\geq m)&=&1-\mathbb{P}(\ell_n<m)\\[8pt]
&=&p^ m c(n- m )+1-c(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}{n-j m \choose j}(p^ m q)^j\\[8pt]
&=&p^ m \sum_{j\geq 1}(-1)^{j-1}{n-j m \choose j-1}(p^m q)^{j-1}+\sum_{j\geq 1}(-1)^{j+1}{n-j m \choose j}(p^mq )^j\\[8pt]
&=&\sum_{j\geq 1}(-1)^{j+1} \left[{n-j m \choose j-1}+{n-j m \choose j}q\right]p^{ jm } q^{j-1}\\[8pt]
&=&\sum_{j\geq 1}(-1)^{j+1} \left[{n-j m \choose j-1}p+{n-j m \choose j-1}q+{n-j m \choose j}q\right]p^{ jm } q^{j-1}\\[8pt]
&=&\sum_{j\geq 1}(-1)^{j+1} \left[{n-j m \choose j-1}p+{n-j m +1\choose j}q \right]p^{ jm} q^{j-1}\\[8pt]
&=&\sum_{j\geq 1}(-1)^{j+1} \left[p+{n-j m +1\over j}\, q\right] {n-j m \choose j-1}\,p^{ jm} q^{j-1}.

Source : Link , Question Author : Sasha , Answer Author : Community

Leave a Comment