Sharpen the lower bound on streak length by showing that in \(n\) flips of a fair coin, the probability is less than \(1/n\) that no streak longer than \(\lg n - 2 \lg \lg n\) consecutive heads occurs.
This problem improves upon the lower bound analysis in Section 5.4.3, which showed that the expected longest streak is \(\Omega(\lg n)\) by proving a streak of length \(\lfloor (\lg n)/2 \rfloor\) is likely. Here we show that a longer streak of length \(\lg n - 2 \lg \lg n\) is highly likely.
Setup and notation
Let \(s = \lg n - 2 \lg \lg n\) be our target streak length. We want to show:
\[\Pr\{\text{no streak of length } s\} < \frac{1}{n}\]or equivalently:
\[\Pr\{\text{longest streak} \geq s\} > 1 - \frac{1}{n}\]Partitioning the flips
Following the approach in Section 5.4.3, we partition the \(n\) coin flips into approximately \(n/s\) groups of \(s\) consecutive flips. More precisely, we have \(\lfloor n/s \rfloor\) non-overlapping groups.
For group \(i\) starting at position \(i \cdot s + 1\), let \(A_i\) be the event that all \(s\) flips in this group are heads. The probability that group \(i\) is all heads is:
\[\Pr\{A_i\} = \frac{1}{2^s} = \frac{1}{2^{\lg n - 2 \lg \lg n}}\]Simplifying the exponent:
\[\begin{align*} 2^{\lg n - 2 \lg \lg n} &= \frac{2^{\lg n}}{2^{2 \lg \lg n}} \\ &= \frac{n}{2^{\lg (\lg n)^2}} \\ &= \frac{n}{(\lg n)^2} \end{align*}\]Therefore:
\[\Pr\{A_i\} = \frac{(\lg n)^2}{n}\]Probability that no group is all heads
The probability that group \(i\) is not all heads is:
\[\Pr\{\overline{A_i}\} = 1 - \frac{(\lg n)^2}{n}\]The groups are mutually exclusive and independent (non-overlapping flips). The probability that none of the \(\lfloor n/s \rfloor\) groups is all heads is:
\[\begin{align*} \Pr\left\{\bigcap_{i=1}^{\lfloor n/s \rfloor} \overline{A_i}\right\} &= \prod_{i=1}^{\lfloor n/s \rfloor} \left(1 - \frac{(\lg n)^2}{n}\right) \\ &= \left(1 - \frac{(\lg n)^2}{n}\right)^{\lfloor n/s \rfloor} \end{align*}\]Now we need to evaluate \(\lfloor n/s \rfloor\):
\[\begin{align*} \frac{n}{s} &= \frac{n}{\lg n - 2 \lg \lg n} \\ &= \frac{n}{\lg n(1 - 2 \lg \lg n / \lg n)} \end{align*}\]For large \(n\), \(\lg \lg n / \lg n \to 0\), so:
\[\frac{n}{s} \approx \frac{n}{\lg n}\]More precisely, for sufficiently large \(n\):
\[\frac{n}{s} \geq \frac{n}{2 \lg n}\]Therefore:
\[\begin{align*} \left(1 - \frac{(\lg n)^2}{n}\right)^{\lfloor n/s \rfloor} &\leq \left(1 - \frac{(\lg n)^2}{n}\right)^{n/(2\lg n)} \end{align*}\]Using the inequality \(1 - x \leq e^{-x}\):
\[\begin{align*} \left(1 - \frac{(\lg n)^2}{n}\right)^{n/(2\lg n)} &\leq \exp\left(-\frac{(\lg n)^2}{n} \cdot \frac{n}{2 \lg n}\right) \\ &= \exp\left(-\frac{\lg n}{2}\right) \\ &= e^{-\lg n / 2} \\ &= 2^{-\lg n / (2 \ln 2)} \\ &= 2^{-\lg n / 1.443} \\ &< 2^{-\lg n / 2} \\ &= n^{-1/2} \\ &< \frac{1}{n} \end{align*}\]for \(n \geq 4\).
Conclusion
We have shown that:
\[\Pr\{\text{no streak of length } \lg n - 2 \lg \lg n\} < \frac{1}{n}\]This means that with probability at least \(1 - 1/n\), there exists a streak of at least \(\lg n - 2 \lg \lg n\) consecutive heads in \(n\) coin flips.
This is a sharper lower bound than the \(\lfloor (\lg n)/2 \rfloor\) bound from Section 5.4.3. Combined with the upper bound \(O(\lg n)\) from that section, we can conclude that the expected length of the longest streak is:
\[\Theta(\lg n)\]and more precisely, it is concentrated around \(\lg n - \Theta(\lg \lg n)\).