How would one go about finding the expected value of the maximum number of consecutive heads when flipping a coin $n$ times? For small $n$, it seems easy to brute-force it (i.e. when $n = 3$, the sample space is $\{HHH, HHT, HTH, HTT, TTT, TTH,THT,THH\}$ and so the maximum number of consecutive heads is $\{3,2,1,1,0,1,1,2\}$ so the expected value of the number of maximum consecutive heads should be $11/8$). However, for $n>5$, it becomes pretty hard to brute force this.
For a research project, I am really wondering how the solution to this problem behaves for $ 50 \leq n \leq 100 $. In other words, if I flip $50$ coins, what is the maximum run length of heads that should be expected?
Any advice on how to solve this problem for either the $n$ in the above bound, or for $n$ in general?
Best Answer
Suppose we compute the generating function of binary strings having at most $q$ consecutive heads. There are four cases, according to whether the string starts with heads or tails and ends with heads or tails.
We get $$G_{HH}(z) = z\frac{1-z^{q}}{1-z} \sum_{k=0}^\infty \left(\frac{z}{1-z}z\frac{1-z^{q}}{1-z}\right)^k.$$
Continuing we get $$G_{HT}(z) = G_{HH}(z) \frac{z}{1-z}.$$
Furthermore $$G_{TT}(z) = \frac{z}{1-z} \sum_{k=0}^\infty \left(z\frac{1-z^{q}}{1-z}\frac{z}{1-z}\right)^k.$$
Finally we have $$G_{TH}(z) = G_{TT}(z) z\frac{1-z^{q}}{1-z}.$$
The sum term is $$\frac{1}{1-z^2(1-z^q)/(1-z)^2} = \frac{1-2z+z^2}{1-2z+z^2-z^2(1-z^q)} = \frac{1-2z+z^2}{1-2z+z^{q+2}}.$$
The factor on this is $$z\frac{1-z^{q}}{1-z} \left(1+\frac{z}{1-z}\right) + \frac{z}{1-z} \left(1+z\frac{1-z^{q}}{1-z}\right)$$ which is $$z\frac{1-z^{q}}{(1-z)^2} + \frac{z}{(1-z)^2} (1-z^{q+1}) = \frac{2z-z^{q+1}-z^{q+2}}{(1-z)^2}.$$
Multiplying we obtain the generating function $$G_q(z) = \frac{2z-z^{q+1}-z^{q+2}}{1-2z+z^{q+2}}.$$
It follows that the expectation times $2^n$ is given by
$$ [z^n] \left(0\times G_0(z) + \sum_{q=1}^n q (G_q(z)-G_{q-1}(z)) \right).$$
The sum simplifies to $$\sum_{q=1}^n q G_q(z) - \sum_{q=0}^{n-1} (q+1) G_q(z) = \sum_{q=0}^n q G_q(z) - \sum_{q=0}^{n-1} (q+1) G_q(z) \\ = n G_n(z) - \sum_{q=0}^{n-1} G_q(z).$$
and hence the expectation is $$\frac{1}{2^n} [z^n] \left( n G_n(z) - \sum_{q=0}^{n-1} G_q(z) \right).$$
This gives the sequence $$1/2,1,{\frac {11}{8}},{\frac {27}{16}},{\frac {31}{16}},{ \frac {69}{32}},{\frac {75}{32}},{\frac {643}{256}},{\frac { 1363}{512}},{\frac {1433}{512}},\ldots$$
Multiplying by $2^n$ we obtain $$1, 4, 11, 27, 62, 138, 300, 643, 1363, 2866, \ldots$$ which is OEIS A119706 where the above computation is confirmed.
The following Maple code can be used to explore these generating functions. The procedure v computes the generating function of the maximal run length of a string of $n$ bits by total enumeration. The procedure w computes it from the generating function $G_q(z).$
Here are two examples.
Addendum. Responding to the question of the OP, the maximum run length distribution for $n=50$ is