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

-

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$.
I still don't get the first paragraph. For example, what if a $\ell$ run spans two blocks (without covering any of them)? – leonbloy Apr 5 '14 at 21:12