If I flip a coin $n$ times, what is the expected maximum number of heads or tails in a row?

Question

Question: If I flip a coin $n$ times, what is the maximum number of heads or tails in a row that I should expect?

Answer 1

This is not an easy question.

Let $Z_0(n)$ be a random variable denoting the longest sequence of heads in a sequence of $n$ flips. In 1980, Guibas and Odlyzko showed that $$\mathbb{E}(Z_0(n)) = \log_2(n)+\frac{\gamma}{\log 2} -\frac{3}{2} +\rho_0(n)+o(1)$$ where $\gamma$ is the Euler-Mascheroni constant, and $\rho_0(n)$ is an osscilatory function of $\log (n)$ bounded in absolute value by $1.6\cdot10^{-6}$. In particular, this leads to the surprising result that $$\mathbb{E}(Z_0(n))-\log_2(n)$$ does not have a limit. See this paper, An Extreme Value Theory for Long Head Runs, by Gordon, Schilling, Waterman for more details.