Sharpen the lower bound on streak length by showing that in \(n\) flips of a fair coin, the probability is less than \(\frac{1}{n}\) that no streak longer than \(\lg n - 2 \lg ( \lg (n))\) consecutive heads occurs.

We begin by taking those first \(n\) flips and partitioning them into \(\frac{n}{s}\) groups where \(s = \lg (n) - 2 \lg ( \lg (n))\). It will be convenient for us to show that the probability of one of these groups coming up all heads is at least \(\frac{n-1}{n}\). Let the event that describes a grouping of coinflips all coming up heads beginning at index \(i\) be \(A_{i, \lg n - 2 \lg ( \lg (n))}\) with the following probability:

\[Pr(A_{i, \lg n - 2 \lg ( \lg (n))}) = \frac{1}{2^{\lg n - 2 \lg ( \lg (n))}}\]

Our groupings are just sets of coinflips and as such they are independently and identically distributed which means their probabilities are independent:

\[\begin{split} \Pr(\bigwedge\neg A_{i,\lg n - 2\lg(\lg n)}) &= \prod_i\Pr(\neg A_{i,\lg n - 2\lg(\lg n)}) \\ &= \left(1-\frac{\lg n^2}{n}\right)^{\frac{n}{\lg n - 2\lg(\lg n)}} \\ &\le e^{-\frac{\lg n^2}{\lg n - 2\lg(\lg n)}} \\ &= \frac{1}{n} e^{\frac{-2\lg(\lg n)\lg n}{\lg n - 2\lg(\lg n)}} \\ &= n^{-1-\frac{2\lg(\lg n)}{\lg n - 2\lg(\lg n)}} \\ &\lt n^{-1}. \end{split}\]

Therefore, the probability that there is no run of length at least \(\lg n - 2 \lg (\lg(n))\) consecutive heads to be \(\lt \frac{1}{n}\).