Consecutive heads in $N$ coin tosses. Suppose we toss a fair coin $n$ times. We want to show that we can find a run of $\log_2 n - O(\log_2 \log_2 n)$ heads with probability at least $1 - 1/n^c$ for any $c \geq 1$.
I realize that there are already questions and answers on stack exchange where the length of the run is for arbitrary $k$. However, in this case I have a specific run length and am trying to show that we can find a relatively simple lower bound.
Initially, I feel like the "trick" is try to find a way to deal with the $O(\log_2 \log_2 n)$ term. In order to try to accomplish this, we can use a union bound argument to show that the probability of $\log_2 n$ consecutive heads is bounded above by 1. The problem with this is it makes it very difficult to deal with the $O(\log_2 \log_2 n)$ term and as a result, I get stuck.
This isn't homework, but is a problem I came across awhile back. It has really been bugging me. Any help/hint would be appreciated. :)
 A: 
The result holds for runs of length $\log_2n-3\log_2\log_2n$.

To show this, note that a sequence of length $n=k\ell$ is the concatenation of $k$ disjoint subsequences of length $\ell$ and each of these subsequences is part of a run of length at least $\ell$ with probability $1/2^\ell$. By independence, the probability $p_n$ that there is no run of length at least $\ell$ is such that
$$
p_n\leqslant(1-1/2^\ell)^k=(1-1/2^\ell)^{n/\ell}.
$$
Since $1-x\leqslant\mathrm e^{-x}$ for every $x$,
$$
p_n\leqslant\exp(-n/(\ell2^\ell)).
$$
Assume that $\ell=\log_2n-3\log_2\log_2n$, then $2^\ell=n/(\log_2n)^3$ hence
$$
\frac{n}{\ell2^\ell}=\frac{(\log_2n)^3}{\ell}\sim(\log_2n)^2.
$$
This implies that, for every $n$ large enough,
$$
p_n\leqslant\exp(-(\log_2n)^2).
$$For every $c$,
$$
n^c\,p_n\leqslant\exp(c\log n-(\log_2n)^2),
$$
for every $n$ large enough, hence $n^cp\to0$, in particular,
$$
p_n\leqslant\frac1{n^c},
$$
for every $n$ large enough, QED.
Edit: Following the fate of the factor $3$ in  $\ell=\log_2n-3\log_2\log_2n$, one sees that the proof actually shows that the result holds for longer runs, namely, for runs of length $\ell=\log_2n-2\log_2\log_2n-k_n$, as soon as $k_n\to+\infty$.
