La longitud de máxima subsequence de una secuencia al azar

Question

Estoy haciendo mi tarea y realmente atascado con un problema.

Tengo una secuencia aleatoria de 1 y 0 de longitud $n$. Vamos a $m$ la longitud máxima de larga que consta sólo de 1. Por ejemplo, para la secuencia

0011010

$m=2$

Así que la tarea es demostrar que

$$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}\} \a 1$ as $n \to \infty$), however, I can't prove the first one ($P\left\{\frac{\log_2{n}}{2} < m\right\} \a 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$$

Answer 1

Si $K = \lfloor \log_2(n)/2 \rfloor$, podemos dividir $\{1,2,\ldots,n\}$ en bloques separados de $M = \lfloor n/K \rfloor$ $K$ enteros consecutivos (y quizás algunos sobran). La probabilidad de que su secuencia aleatoria tiene todas las %#% de #% en cualquier bloque dado es $1$. La probabilidad de que ninguno de ellos son los %#% de #% es $2^{-K}$. Pensar en multicelular de este $1$.