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
    Perhaps you should explain better how you solved the other half- it seems that the approach should be similar.2012-05-01
  • 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
    When you disjoin blocks you have to do smth like `XXX0XXX0XXX` so your estimate doesn't take into account the sequences like `0011100000`.2012-05-01
  • 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..2012-05-01
  • 0
    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$$2012-05-01
  • 0
    @Ximik: No, that is, as Robert correctly wrote, "The probability that none of them are all 1's". That's what goes to $0$.2012-05-01
  • 0
    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.2012-05-01
  • 0
    No, I mean $P(m \ge K) \ge 1 - (1-2^{-K})^M$.2012-05-01
  • 0
    This is the same. If $P(m \ge K) \ge 1 - \alpha$ then $P(m \lt K) < \alpha$. But the second means that there are more than $2^{n}\alpha$ sequences with $m \lt K$. And this is not true bacause you calculate only one way to do them.2012-05-01
  • 0
    hm Seems like I understood your solution. Thank you. You was right.2012-05-02