# 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?

• Just to clarify: $\ell_{0101}(0101010101010101)$ is 4 or 7? – Anthony Quas Aug 20 '16 at 1:53
• Also can you make the question a bit more precise - on the face of it, it looks as though you're asking is it true that for most $x=x_1\ldots x_n$ that simultaneously for all $\sigma$, $\big|\ell_\sigma(x)-\log_2 n/|\sigma|\big|$ is something small depending only on $n$? – Anthony Quas Aug 20 '16 at 1:57
• @AnthonyQuas that would be 4 – Bjørn Kjos-Hanssen Aug 20 '16 at 3:13
• @AnthonyQuas Yes, I mean simultaneously for all $\sigma$, although a restriction to only short $\sigma$'s might make sense – Bjørn Kjos-Hanssen Aug 20 '16 at 3:14
• What is the set of all $\sigma$ you are considering, $\{0,1,01,10,001,...\}$? Do you want to exclude only powers since they are redundant? Or do you want to consider only $0$ and sequences of $0$s preceded by a $1$ or followed by a $1$? – Douglas Zare Aug 20 '16 at 10:39

## 1 Answer

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$.

• I think the tightest constraint is 2^L << n^\epsilon. – Anthony Quas Aug 21 '16 at 2:29
• That is: n0 >> 2^{L/epsilon}. Maybe you could fix epsilon as a function of L also in advance if you want something depending only on L. – Anthony Quas Aug 21 '16 at 3:01
• I think asking for the displayed equation to hold up to $|\sigma|=\log n$ is too much. At that point, you would be saying (for example) that the repetition number of a block of length $\frac 23\log_2 n$ is between $\frac 32(1-\epsilon)$ and $\frac 32(1+\epsilon)$ for example, which makes no sense (but the true repetition number is probably 1 in this range). A more serious issue arises if you look for blocks of length $\frac 12\log_2 n$. What probably happens here is that the repetition number is either 1 or 2 with vhp. – Anthony Quas Aug 21 '16 at 13:48