3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Just to clarify: $\ell_{0101}(0101010101010101)$ is 4 or 7? $\endgroup$ – Anthony Quas Aug 20 '16 at 1:53
  • 1
    $\begingroup$ 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$? $\endgroup$ – Anthony Quas Aug 20 '16 at 1:57
  • $\begingroup$ @AnthonyQuas that would be 4 $\endgroup$ – Bjørn Kjos-Hanssen Aug 20 '16 at 3:13
  • $\begingroup$ @AnthonyQuas Yes, I mean simultaneously for all $\sigma$, although a restriction to only short $\sigma$'s might make sense $\endgroup$ – Bjørn Kjos-Hanssen Aug 20 '16 at 3:14
  • 1
    $\begingroup$ 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$? $\endgroup$ – Douglas Zare Aug 20 '16 at 10:39
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Cool, I hope we can bound $n_0$ as a function of $L $... $\endgroup$ – Bjørn Kjos-Hanssen Aug 21 '16 at 2:24
  • $\begingroup$ I think the tightest constraint is 2^L << n^\epsilon. $\endgroup$ – Anthony Quas Aug 21 '16 at 2:29
  • $\begingroup$ 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. $\endgroup$ – Anthony Quas Aug 21 '16 at 3:01
  • $\begingroup$ Perhaps for most $x$ we have that for all $\sigma$, if $|\sigma|\le \log_2 n$ then your displayed equation holds, and if $|\sigma|> \log_2 n$ (maybe replace $>$ by $\gg$) then $\ell_\sigma(x)\le 1$? That would be great. $\endgroup$ – Bjørn Kjos-Hanssen Aug 21 '16 at 6:18
  • $\begingroup$ 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. $\endgroup$ – Anthony Quas Aug 21 '16 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.