5
$\begingroup$

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$

  • 0
    Maybe it's so. I've added my partial solution.2012-05-01

1 Answers 1

2

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

  • 0
    hm Seems like I understood your solution. Thank you. You was right.2012-05-02