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$
6
  • 1
    $\begingroup$ Just to clarify: $\ell_{0101}(0101010101010101)$ is 4 or 7? $\endgroup$ Aug 20, 2016 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$ Aug 20, 2016 at 1:57
  • $\begingroup$ @AnthonyQuas that would be 4 $\endgroup$ Aug 20, 2016 at 3:13
  • $\begingroup$ @AnthonyQuas Yes, I mean simultaneously for all $\sigma$, although a restriction to only short $\sigma$'s might make sense $\endgroup$ Aug 20, 2016 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$ Aug 20, 2016 at 10:39

1 Answer 1

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

$\endgroup$
5
  • $\begingroup$ I think the tightest constraint is 2^L << n^\epsilon. $\endgroup$ Aug 21, 2016 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$ Aug 21, 2016 at 3:01
  • $\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$ Aug 21, 2016 at 13:48
  • 1
    $\begingroup$ My Forum of Mathematics Sigma paper (published 2021) answered a 20-year old question of Jeff Shallit and cites this answer. $\endgroup$ Oct 27, 2021 at 7:10
  • $\begingroup$ That's great! Thanks for letting me know. $\endgroup$ Oct 27, 2021 at 15:39

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.