You can certainly prove the following: for each $L>0$, for all $\epsilon>0$, there exists an $n_0$ such that if $n>n_0$, then with probability at least $1-\epsilon$,
$$
\Big|\frac{\ell_\sigma(x_1\ldots x_n)}{\log_2 n/|\sigma|}-1\Big|<\epsilon
\text{ for each $\sigma$ such that $|\sigma|\le L$.}
$$
I wouldn't say this is a concentration of measure result, though. There is a simple proof just
by simple probability estimates. The above is a simultaneous convergence in probability
of the run lengths of all small sequences normalized by $\log n/\sigma$. No doubt, more
refined estimates can be obtained.

The proof I have in mind is the following:
for each $\sigma$ with $|\sigma|\le L$, let $k=|\sigma|$ and
consider the probability that there are
$m=\lfloor (1-\epsilon)\log_2 n/|\sigma|\rfloor $ consecutive copies of $\sigma$ in the positions
$(j-1)k+1,\ldots,jk$ for some $1\le j\le n/(km)$. Since these `slots' are disjoint,
the probability of seeing $\sigma^m$ in each of these slots is the same, and
is $2^{-m|\sigma|}\approx 2^{-(1-\epsilon)\log_2 n}=n^{-(1-\epsilon)}$.
The probability of
not seeing $\sigma^m$ in any of these slots is approximately $(1-n^{-(1-\epsilon)})^n\approx
e^{-n^\epsilon}$. Since there are $2^L$ possible $\sigma$'s, the probability of failure
for one of the $\sigma$'s is (by the union bound) at most $2^Le^{-n^\epsilon}$.
That is: we've shown with (very) high probability that $\ell_\sigma(x_1\ldots x_n)
\ge (1-\epsilon)\log_2 n/|\sigma|$ for each short (that is of length $\le L$) $\sigma$.

The upper bound is also a consequence of the union bound.
Let $M=\lceil (1+\epsilon)\log_2 n/|\sigma|\rceil$.
Consider the probability that there is a copy of $\sigma^M$ in any
of the positions $1,\ldots,n-M|\sigma|$. Using the union bound,
the probability is at most $n2^{-|\sigma|M}\approx n\cdot n^{-(1+\epsilon)}
=n^{-\epsilon}$. The probability that $x_1\ldots x_n$ has an excessive run
of $\sigma$'s for some $\sigma$ with $|\sigma|\le L$ is at most
$2^Ln^{-\epsilon}$, so that with high probability, there is
are no more than $(1+\epsilon)\log_2 n/|\sigma|$ consecutive
$\sigma$'s in $x_1\ldots x_n$ for each short $\sigma$.

all$\sigma$, $\big|\ell_\sigma(x)-\log_2 n/|\sigma|\big|$ is something small depending only on $n$? $\endgroup$ – Anthony Quas Aug 20 '16 at 1:571more comment