Ciertamente se puede demostrar lo siguiente: para cada $L>0$ para todos $\epsilon>0$ existe un $n_0$ de manera que si $n>n_0$ entonces, con una probabilidad de al menos $1-\epsilon$ , $$ \Big|\frac{\ell_\sigma(x_1\ldots x_n)}{\log_2 n/|\sigma|}-1\Big|<\epsilon \text{ for each $ |sigma $ such that $ |\L $.} $$ Sin embargo, yo no diría que se trata de un resultado de concentración de medidas. Hay una prueba sencilla sólo mediante simples estimaciones de probabilidad. Lo anterior es una convergencia simultánea en probabilidad de las longitudes de carrera de todas las secuencias pequeñas normalizadas por $\log n/\sigma$ . Sin duda, se pueden obtener estimaciones más estimaciones más precisas.
La prueba que tengo en mente es la siguiente para cada $\sigma$ con $|\sigma|\le L$ , dejemos que $k=|\sigma|$ y considerar la probabilidad de que haya $m=\lfloor (1-\epsilon)\log_2 n/|\sigma|\rfloor $ copias consecutivas de $\sigma$ en las posiciones $(j-1)k+1,\ldots,jk$ para algunos $1\le j\le n/(km)$ . Como estas "ranuras" son disjuntas, la probabilidad de ver $\sigma^m$ en cada una de estas ranuras es la misma, y es $2^{-m|\sigma|}\approx 2^{-(1-\epsilon)\log_2 n}=n^{-(1-\epsilon)}$ . La probabilidad de no ver $\sigma^m$ en cualquiera de estas ranuras es aproximadamente $(1-n^{-(1-\epsilon)})^n\approx e^{-n^\epsilon}$ . Dado que hay $2^L$ posible $\sigma$ la probabilidad de fallo para uno de los $\sigma$ es (por el límite de la unión) como máximo $2^Le^{-n^\epsilon}$ . Es decir: hemos demostrado con (muy) alta probabilidad que $\ell_\sigma(x_1\ldots x_n) \ge (1-\epsilon)\log_2 n/|\sigma|$ para cada corto (es decir, de longitud $\le L$ ) $\sigma$ .
El límite superior es también una consecuencia del límite de la unión. Sea $M=\lceil (1+\epsilon)\log_2 n/|\sigma|\rceil$ . Considere la probabilidad de que exista una copia de $\sigma^M$ en cualquiera de los puestos $1,\ldots,n-M|\sigma|$ . Utilizando el límite de la unión la probabilidad es como máximo $n2^{-|\sigma|M}\approx n\cdot n^{-(1+\epsilon)} =n^{-\epsilon}$ . La probabilidad de que $x_1\ldots x_n$ tiene una carrera excesiva de $\sigma$ 's para algunos $\sigma$ con $|\sigma|\le L$ es como máximo $2^Ln^{-\epsilon}$ para que, con alta probabilidad, haya no hay más de $(1+\epsilon)\log_2 n/|\sigma|$ consecutivos $\sigma$ 's en $x_1\ldots x_n$ para cada corto $\sigma$ .
