Longest runs and concentration of measure Consider the longest runs $\ell_\sigma(x)$ of the pattern $\sigma$ for $\sigma\in \{0, 1, 01, 10, 001,\dots\}$ etc. in a binary sequence $x=x_1\dots x_n$.
For example, $\ell_{001}(0001110010011001)=2$ since 001001 is a contiguous subsequence of that sequence but 001001001 is not.
And $\ell_0$ is approximately $\log_2 n$ by a result of Boyd (1972).
Is there a way to use concentration of measure to show that for most $x$, we have that all these $\ell_\sigma(x)$'s are fairly close to their mean or median?
 A: 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$. 
