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.

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

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
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
1  
@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

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.