# The length of maximum subsequence in a random sequence

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

0011010


$m=2$

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

11111XXXXX


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.

XX11111XXX


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

And

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

• Perhaps you should explain better how you solved the other half- it seems that the approach should be similar. – leonbloy May 1 '12 at 1:58
• Maybe it's so. I've added my partial solution. – 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$.
• When you disjoin blocks you have to do smth like XXX0XXX0XXX so your estimate doesn't take into account the sequences like 0011100000. – Ximik May 1 '12 at 2:49
• @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.. – Robert Israel May 1 '12 at 5:31
• 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$$ – Ximik May 1 '12 at 5:46
• @Ximik: No, that is, as Robert correctly wrote, "The probability that none of them are all 1's". That's what goes to $0$. – joriki May 1 '12 at 6:03
• 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. – Ximik May 1 '12 at 6:30