I want to prove that in a sequence W of length n, consisting of 1s and 0s, $P$( in $W$ there is at most $\frac{\log_2n}2$ consecutive zeroes ) $\leq \frac{K}{n} $ for some constant K. Can anyone help me start on the problem or refer me to some literature that could be of help.
Thank you very much.
Let $a<1<b$. I prove that for large $n$:
1) the probability that a random sequence of length $n$ has at least $B:=b\log_2 n$ consecutive zeroes is at most $n^{1-b}$;
2) the probability that a random sequence of length $n$ does not contain $A:=\lfloor a\log_2 n\rfloor$ consecutive zeroes is at most $e^{-n^{1-a+o(1)}}=O(n^{-M})$ for any $M>0$.
Proofs. 1) For each possible place of $\lceil B\rceil $ consecutive positions consider the event: all positions are 0. Denote these events $E_1,E_2,\dots$. The sum of their probabilities does not exceed $$\frac{n}{2^B}\leqslant n^{1-b}. $$
2) Choose $m:=\lfloor n/A\rfloor$ disjoint segments of $A$ consecutive places. The probability that none of them contains only zeroes equals $$ (1-2^{-A})^m\leqslant e^{-m\cdot 2^{-A}}=e^{-n^{1-a+o(1)}} $$
If you are interested in the longest run of 0's in the i.i.d. setting, see this paper: http://gato-docs.its.txstate.edu%2Fmathworks%2FDistributionOfLongestRun.pdf&usg=AFQjCNE8shEgVJmaWNEVSYv5YNRIs088CA&sig2=OTB5H3mF7NVoEwIZs_foJw
Also this:
L. Gordon, M.F. Schilling, M.S. Waterman (1986)
An extreme value theory for long head runs.
Probab. Theory Relat. Fields 72, 279-287.
