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.
Section 5.4.3 showed that the longest run of heads is \(\Theta(\lg n)\) by proving that a streak of length about \(\tfrac{1}{2} \lg n\) is likely. This exercise pushes the lower end much closer to the truth: a streak of nearly \(\lg n\) heads, falling short of the full \(\lg n\) only by a \(2 \lg \lg n\) correction, is almost certain.
The idea is the same chopping trick the book uses. Cut the \(n\) flips into consecutive blocks of \(s = \lg n - 2 \lg \lg n\) flips each. A block that comes up all heads is itself a streak of \(s\) heads, so if even one block is all heads we have found our long streak. We will show that the chance of every block failing to be all heads is below \(1/n\), which makes a long streak overwhelmingly likely.
A single block of \(s\) fair flips is all heads with probability \(2^{-s}\), and this number is larger than it might first appear:
\[\begin{align*} 2^{-s} &= 2^{-(\lg n - 2 \lg \lg n)} \\ &= \frac{2^{2 \lg \lg n}}{2^{\lg n}} \\ &= \frac{(\lg n)^2}{n}. \end{align*}\]Split the flips into \(m = \lfloor n/s \rfloor\) blocks. Because the blocks use disjoint flips, the events “block \(i\) is all heads” are independent, so the probability that no block is all heads is exactly
\[\left(1 - \frac{(\lg n)^2}{n}\right)^{m},\]and applying the standard inequality \(1 - x \leq e^{-x}\) gives
\[\Pr\{\text{no block all heads}\} \leq \exp\left(-m \cdot \frac{(\lg n)^2}{n}\right).\]Everything now hinges on how many blocks we have, and this is the step where it is easy to be too generous and lose the bound. Since \(s = \lg n - 2 \lg \lg n\) is smaller than \(\lg n\), dividing by \(s\) yields more blocks than dividing by \(\lg n\) would:
\[m = \left\lfloor \frac{n}{s} \right\rfloor \geq \frac{n}{s} - 1 > \frac{n}{\lg n} - 1.\]Feeding this back in, and using that \((\lg n)^2/n \leq 1\) for \(n \geq 16\),
\[\begin{align*} m \cdot \frac{(\lg n)^2}{n} &> \left(\frac{n}{\lg n} - 1\right)\frac{(\lg n)^2}{n} \\ &= \lg n - \frac{(\lg n)^2}{n} \\ &\geq \lg n - 1. \end{align*}\]Therefore
\[\begin{align*} \Pr\{\text{no block all heads}\} &\leq \exp(-(\lg n - 1)) \\ &= e \cdot e^{-\lg n} \\ &= e \cdot n^{-1/\ln 2} \\ &\approx e \cdot n^{-1.443}. \end{align*}\]This sits comfortably below \(1/n\): the inequality \(e \cdot n^{-1.443} < n^{-1}\) is the same as \(e < n^{0.443}\), which holds for every \(n \geq 16\). So for all sufficiently large \(n\),
\[\Pr\{\text{no streak of length } \lg n - 2 \lg \lg n\} < \frac{1}{n}.\]Notice that we proved something stronger than asked: the bound is really \(n^{-1.443}\), beating the required \(1/n\) by a factor of about \(n^{0.443}\). That slack is exactly what lets the floor in \(\lfloor n/s \rfloor\) and the \(1 - x \leq e^{-x}\) approximation pass without costing us the result. It is also what was thrown away in the tempting but wrong move of using only \(n/(2\lg n)\) blocks, which halves the exponent and leaves nothing to spare.
Equivalently, with probability greater than \(1 - 1/n\) there is a run of at least \(\lg n - 2 \lg \lg n\) consecutive heads. Together with the \(O(\lg n)\) upper bound from Section 5.4.3, the longest run of heads is \(\Theta(\lg n)\), and more precisely it sits at \(\lg n - \Theta(\lg \lg n)\), a noticeably sharper statement than the \(\tfrac{1}{2} \lg n\) bound we started from.