Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 3 down vote accepted
+50

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$.

share|improve this answer
    
"By independence..." well, the runlengths are not independent –  leonbloy Apr 5 at 20:14
    
@leonbloy This is irrelevant to the proof in my post. –  Did Apr 5 at 20:28
    
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 at 21:12
    
Ah, I missed the "at most", the next equation should be an inequation –  leonbloy Apr 5 at 21:16
    
@leonbloy Right. My bad. –  Did Apr 5 at 21:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.