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. :)