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. 🙂
Best Answer
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$.