I'm doing my homework and really stuck with one problem.

I have a random sequence of 1 and 0 of length $n$. Let's $m$ the maximum lenght of subsequence consisting only of 1. For example for the sequence



So task is to prove that

$$P\left\{\frac{\log_2{n}}{2} < m < 2\log_2{n}\right\} \to 1\text{ as }n \to \infty$$

I've proved the second part ($P\{m < 2\log_2{n}\} \to 1$ as $n \to \infty$), however, I can't prove the first one ($P\left\{\frac{\log_2{n}}{2} < m\right\} \to 1$ as $n \to \infty$). Can you get me some ideas about how can I do this? Thank you.

Maybe it will be helpful. The second part I've proved with combinatorial method.

Let's estimate $P\{m \ge k\}$. This means that we have at least subsequence with length $k$. So let's make sequence like this


Here we have $k$ of 1 and $n-k$ arbitrary values. We can fill this XXXXX in $2^{n-k}$ ways. Also we can place the beginning of the sequence in $n-k+1$ ways. E.g.


There are $2^{n-k}(n-k+1)$ ways (and some of them we calculeted twice or more). All there are $2^{n}$ ways. So

$$P\{m \ge k\} \le 2^{-k}(n-k+1)$$


$$P\{m \ge 2\log_2{n}\} \le \frac{n-2\log_2{n}+1}{n^2} \to 0\text{ as }n \to \infty$$

  • $\begingroup$ Perhaps you should explain better how you solved the other half- it seems that the approach should be similar. $\endgroup$ – leonbloy May 1 '12 at 1:58
  • $\begingroup$ Maybe it's so. I've added my partial solution. $\endgroup$ – Ximik May 1 '12 at 2:17

If $K = \lfloor \log_2(n)/2 \rfloor$, we can split $\{1,2,\ldots,n\}$ into $M = \lfloor n/K \rfloor$ disjoint blocks of $K$ consecutive integers (plus perhaps some left over). The probability that your random sequence has all $1$'s in any given block is $2^{-K}$. The probability that none of them are all $1$'s is $(1 - 2^{-K})^M = \exp(M \log(1-2^{-K}))$. Think about asymptotics of this as $n \to \infty$.

  • $\begingroup$ When you disjoin blocks you have to do smth like XXX0XXX0XXX so your estimate doesn't take into account the sequences like 0011100000. $\endgroup$ – Ximik May 1 '12 at 2:49
  • 1
    $\begingroup$ @Ximik: This is for a lower bound. You could certainly have a run of $K$ ones that overlaps more than one block, but that's OK: the probability of at least one run of $K$ ones $\ge$ the probability of at least one block of ones, so if the latter $\to 1$ as $n \to \infty$ you're done.. $\endgroup$ – Robert Israel May 1 '12 at 5:31
  • $\begingroup$ But $$P\{m \ge K\} \gt (1-2^{-K})^M \sim \exp(\frac{2n}{\log_2{n}}\log(1-n^{-1/2})) \sim \exp(-\frac{2n^{1/2}}{\log_2{n}}) \to 0$$ $\endgroup$ – Ximik May 1 '12 at 5:46
  • $\begingroup$ @Ximik: No, that is, as Robert correctly wrote, "The probability that none of them are all 1's". That's what goes to $0$. $\endgroup$ – joriki May 1 '12 at 6:03
  • $\begingroup$ So do you mean $P\{m < K\} \lt (1-2^{-K})^M$? But this is not true. Because there are much more ways to have K 1's. My first comment is an example. $\endgroup$ – Ximik May 1 '12 at 6:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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