4
$\begingroup$

For numbers between $2^{k-1}$ and $2^{k}-1$, how many have a maximum run of $n$ identical digits in base $2$? For instance, $1000110101111001$ in base $2$ has a maximum run of 4.

See picture below showing the number of numbers with a maximum run equal to $2$, between $1$ and $2^{k}-1$, for various values of $k$. Clearly, it is a simple function of Fibonacci numbers. This seems to generalize to maximum run equal to $3, 4, 5$ and so on. See this previous question on the subject. However, the people who answered that question provide no reference and no explanation. It is also said (in that same question) that in a random string of $0/1$ of length $k$, one expects the longest sequence of zeros to be roughly of length $\log k$. I am also very interested in that statement (if you replace "longest sequence of zero" by "longest sequence whether zero or one"), but where can I find a proof?

enter image description here

The goal is to construct a sub-sequence of integers that has a max run less than (say) $\sqrt{k}$ for all $k$ so that as $k$ increases, and you divide the numbers in the sub-sequence by a power of two so that each number becomes a fraction between $0.5$ and $1$, you end up at the limit with an irrational number that has a specific proportion of zero and one in its binary expansion. The final goal is to find a mathematical constant that we know for sure, based on the aforementioned construction, to be either normal or not normal.

$\endgroup$
  • 1
    $\begingroup$ I've no way to help toward an answer, but +1 for including the source of the question. $\endgroup$ – Ethan Bolker Aug 10 at 15:28
  • 1
    $\begingroup$ An interesting link in the previous question referenced in my post, is broken. I was able to find the correct URL: csun.edu/~hcmth031/tlroh.pdf (title: The longest run of heads). $\endgroup$ – Vincent Granville Aug 10 at 15:53
2
$\begingroup$

That is the same as asking about max number of runs (of consecutive 1's) in a binary string of length $n=k-1$.

In this related post it is explained that the
Number of binary strings, with $s$ "$1$"'s and $m$ "$0$"'s in total, that have up to $r$ consecutive $1$s
is given by $$ N_b (s,r,m + 1)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s}{r+1}\, \leqslant \,m + 1} \right)} { \left( { - 1} \right)^k \binom{m+1}{k} \binom {s + m - k\left( {r + 1} \right) }{s - k\left( {r + 1} \right) } } $$

So, the cumulative number we are looking for is: $$ \bbox[lightyellow] { \eqalign{ & C(n,r) = \sum\limits_{\left( {0\, \le } \right)\,\,m\,\,\left( { \le \,n} \right)} { N_b (n - m,r,m + 1)} = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,m\,\,\left( { \le \,n} \right)} { \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{s \over {r + 1}}\, \le \,m + 1} \right)} {\left( { - 1} \right)^k \binom{m+1}{k} \binom{ n - k\left( {r + 1} \right)} {n - m - k\left( {r + 1} \right) } } } \cr} } \tag{1}$$

Of course it is $C(n,n)=2^n$. It is also OEIS seq. A126198.

Consec_1_1

By splitting the first binomial in $m+1$ and applying $$ \eqalign{ & {{z^{\,m} } \over {m!}}\left( {{d \over {dz}}} \right)^{\,m} \left( {1 + z} \right)^{\,n} = \sum\limits_{k\, \ge \,0} {\left( \matrix{ n \cr k \cr} \right)\left( \matrix{ k \cr m \cr} \right)\,\;z^{\,k} } = \cr & = {{n^{\underline {\,m\,} } z^{\,m} } \over {m!}}\left( {1 + z} \right)^{\,n - m} = \left( \matrix{ n \cr m \cr} \right)z^{\,m} \left( {1 + z} \right)^{\,n - m} \cr} $$ we can express $C(n,r)$ also as $$ \bbox[lightyellow] { \eqalign{ & C(n,r) = \sum\limits_{0\, \le \,m\, \le \,n} {N_m (n,r,m)} \quad \left| {\;0 \le {\rm integers }m,n,r} \right.\quad = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{n \over {r + 2}} \le \,{n \over {r + 1}}} \right)} {\left( { - 1} \right)^k \left( \matrix{ n - k\left( {r + 1} \right) \cr n - k\left( {r + 2} \right) \cr} \right)2^{\,n - k\left( {r + 2} \right)} } + 2\sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( {{{n + 1} \over {r + 2}} \le \,{n \over {r + 1}}} \right)} {\left( { - 1} \right)^k \left( \matrix{ n - k\left( {r + 1} \right) \cr n + 1 - k\left( {r + 2} \right) \cr} \right)2^{\,n - k\left( {r + 2} \right)} } = \cr & = \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{{n + 1} \over {r + 2}} \le \,{n \over {r + 1}}} \right)} {\left( { - 1} \right)^k \left( {\left( \matrix{ n + 1 - k\left( {r + 1} \right) \cr n + 1 - k\left( {r + 2} \right) \cr} \right) + \left( \matrix{ n - k\left( {r + 1} \right) \cr n + 1 - k\left( {r + 2} \right) \cr} \right)} \right)2^{\,n - k\left( {r + 2} \right)} } \cr} } \tag{2}$$

Using the o.g.f. for $Nb$ provided in the post above, it is possible to provide quite a neat o.g.f. for $C(n,r)$ as $$ \bbox[lightyellow] { \eqalign{ & F(z,r) = \sum\limits_{0\, \le \,n} {C(n,r)z^{\,n} } = \cr & = \sum\limits_{0\, \le \,n} {\sum\limits_{\left( {0\, \le } \right)\,\,m\,\,\left( { \le \,n} \right)} {z^{\,m} N_b (n - m,r,m + 1)z^{\,n - m} } } = \cr & = \sum\limits_{0\, \le \,\,m} {z^{\,m} \left( {{{1 - z^{\,r + 1} } \over {1 - z}}} \right)^{m + 1} } = \left( {{{1 - z^{\,r + 1} } \over {1 - z}}} \right){1 \over {1 - z{{1 - z^{\,r + 1} } \over {1 - z}}}} = \cr & = {{1 - z^{\,r + 1} } \over {1 - 2z + z^{\,r + 2} }} \cr} } \tag{3}$$

Concerning the asymptotic expression for large $n$, in this other post it is shown that for large values of the number of zeros $m$, and thus for large $n$, the Probability $N_b(s,r,m)/(r+1)^m$ tends to the probability distribution of the sum of $m$ continuous random variables uniformly distributed on $[-1/2,r+1/2]$, which is known as Irwin Hall Distribution, and which in turn becomes asymptotic to a normal distribution with mean and variance equal to $m$ times the mean and variance of the uniform random variable on $[-1/2,r+1/2]$, i.e. $$ \eqalign{ & P_{\,b} (s,r,m) = {{N_{\,b} (s,r,m)} \over {\left( {r + 1} \right)^{\,m} }} \approx \cr & \approx {1 \over {\sqrt {2\pi m\sigma ^{\,2} } }}e^{\, - \,{{\left( {s - m\mu } \right)^{\,2} } \over {2m\sigma ^{\,2} }}} = {{\sqrt {6/\pi } } \over {\sqrt {m\left( {\left( {r + 1} \right)^{\,2} } \right)} }}e^{\, - \,6{{\left( {s - mr/2} \right)^{\,2} } \over {m\left( {\left( {r + 1} \right)^{\,2} } \right)}}} \cr} $$

Adapting the above to our case, we get $$ \eqalign{ & {{C(n,r)} \over {2^{\,n} }} = {1 \over {2^{\,n} }}\sum\limits_{\left( {0\, \le } \right)\,\,m\,\,\left( { \le \,n} \right)} {\left( {r + 1} \right)^{\,m + 1} P_{\,b} (n - m,r,m + 1)} = \cr & \approx {1 \over {2^{\,n} }}\sum\limits_{\left( {0\, \le } \right)\,\,m\,\,\left( { \le \,n} \right)} {\left( {r + 1} \right)^{\,m + 1} {{\sqrt {6/\pi } } \over {\sqrt {\left( {m + 1} \right)\left( {\left( {r + 1} \right)^{\,2} } \right)} }}e^{\, - \,6{{\left( {n - m - \left( {m + 1} \right)r/2} \right)^{\,2} } \over {\left( {m + 1} \right)\left( {\left( {r + 1} \right)^{\,2} } \right)}}} } = \cr & = \sqrt {6/\pi } \sum\limits_{\left( {0\, \le } \right)\,\,m\,\,\left( { \le \,n} \right)} {\exp \left( {\, - \,6{{\left( {n - m - \left( {m + 1} \right)r/2} \right)^{\,2} } \over {\left( {m + 1} \right)\left( {\left( {r + 1} \right)^{\,2} } \right)}} + m\ln \left( {1 + r} \right) - n\ln 2 - 1/2\ln \left( {1 + m} \right)} \right)} \cr} $$ which is not of much help and shall be refined though other approaches.

A further step is that, taking $p(n,r)$ as the
probability of having one (or more) runs with exactly $r$ consecutive ones in a string of lenght $n$ $$ p(n,r) = {{C(n,r) - C(n,r - 1)} \over {2^{\,n} }} $$ then from (3) we obtain $$ \bbox[lightyellow] { \eqalign{ & F_{\,p} (z,r) = \sum\limits_{0\, \le \,n} {p(n,r)z^{\,n} } = \cr & = \sum\limits_{0\, \le \,n} {\left( {C(n,r) - C(n,r - 1)} \right)\left( {{z \over 2}} \right)} ^{\,n} = \cr & = F_{\,C} (z/2,r) - F_{\,C} (z/2,r - 1) = \cr & = {{\left( {1 - \left( {z/2} \right)} \right)^{\,2} \left( {z/2} \right)^{\,r} } \over {\left( {1 - z + \left( {z/2} \right)^{\,r + 2} } \right)\left( {1 - z + \left( {z/2} \right)^{\,r + 1} } \right)}} \cr & = {{\left( {1 - z/2} \right)^{\,2} \left( {z/2} \right)^{\,r} } \over {\left( {1 - z} \right)^{\,2} }}\sum\limits_{0\, \le \,k} {\left( { - 1} \right)^{\,k} {{\left( {z/2} \right)^{\,k\,\left( {r + 1} \right)} } \over {\left( {1 - z} \right)^{\,k} }}} \sum\limits_{0\, \le \,j} {\left( { - 1} \right)^{\,j} {{\left( {z/2} \right)^{\,j\,\left( {r + 2} \right)} } \over {\left( {1 - z} \right)^{\,j} }}} = \cr & = {{\left( {1 - z/2} \right)} \over {\left( {1 - z} \right)^{\,2} }}\sum\limits_{0\,\, \le \,k} {\left( { - 1} \right)^{\,k} {{\left( {1 - \left( {z/2} \right)^{\,k + 1} } \right)\left( {z/2} \right)^{\,k} } \over {\left( {1 - z} \right)^{\,k} }}\left( {z/2} \right)^{\,\left( {k + 1} \right)\,r} } \cr} } \tag{4}$$

Defining by $$ \overline r (n) = \sum\limits_{0\, \le \,r\,\left( { \le \,n} \right)} {r\,p(n,r)} $$ the expected run length, then we can get the o.g.f. of it as $$ \eqalign{ & \sum\limits_{0\, \le \,n} {\overline r (n)z^{\,n} } = \sum\limits_{0\, \le \,n} {\sum\limits_{0\, \le \,r\,\left( { \le \,n} \right)} {r\,p(n,r)z^{\,n} } } = \cr & = \sum\limits_{0\, \le \,r} {r\sum\limits_{\left( {r\, \le } \right)\,n\,} {\,p(n,r)z^{\,n} } } = \sum\limits_{0\, \le \,r} {rF_{\,p} (z,r)} \cr & = \left. {\sum\limits_{0\, \le \,r} {rF_{\,p} (z,r)y^{\,r} } \,} \right|_{\,y = 1} = y{\partial \over {\partial y}}\left. {\sum\limits_{0\, \le \,r} {F_{\,p} (z,r)y^{\,r} } \,} \right|_{\,y = 1} \cr} $$ and we arrive, omitting here the algebraic manipulations, to $$ \bbox[lightyellow] { \eqalign{ & \sum\limits_{0\, \le \,n} {\overline r (n)z^{\,n} } = \cr & = {{\left( {1 - z/2} \right)\left( {z/2} \right)} \over {\left( {1 - z} \right)^{\,2} }}\sum\limits_{0\,\, \le \,k} {\left( { - 1} \right)^{\,k} {{\left( {z/2} \right)^{\,2k} } \over {\left( {1 - z} \right)^{\,k} }}{1 \over {\left( {1 - \left( {z/2} \right)^{\,\left( {k + 1} \right)\,} } \right)}}} = \cr & = {{\left( {1 - z/2} \right)\left( {z/2} \right)} \over {\left( {1 - z} \right)^\, }}\sum\limits_{0\,\, \le \,j} {{{\left( {z/2} \right)^{\,j} } \over {1 - z + \left( {z/2} \right)^{\,2 + j} }}} \cr} } \tag{5}$$ and discovering that $2^n \overline r (n)$ is OEIS seq. A119706, while $2^n p(n,r)$ is seq. A048004.

The graph of $\overline r (n)$ has a strong log resemblance.

$\endgroup$
  • $\begingroup$ Thanks for your answer. The asymptotic formula looks more complicated than I would have expected, but I am sure more accurate than what I had in mind. $\endgroup$ – Vincent Granville Aug 11 at 17:50
  • 2
    $\begingroup$ @VincentGranville as you know, asymptotic expressions can be somewhat simplified depending on the degree of accuracy required. I intend to proceed and dig a bit more on that: will let you know. $\endgroup$ – G Cab Aug 11 at 23:29
  • 1
    $\begingroup$ @VincentGranville: Up to now, I just could find another expression for $C(n,r)$ which I added to my answer. I am looking for a better asymptotics. $\endgroup$ – G Cab Aug 20 at 18:42
  • $\begingroup$ Looking forward to it! Thanks G Cab. $\endgroup$ – Vincent Granville Aug 20 at 19:06
  • 1
    $\begingroup$ @VincentGranville: taken a further step, but the asymptotics remains elusive.. $\endgroup$ – G Cab Aug 22 at 12:54
2
$\begingroup$

Let's analyze a simpler case first, $f_n(k)$: the number of binary strings of length $k$ that do not contain $1^n$.

Obviously $f_1(k) = 1$ for all $k$, as only the all-zero or empty string does not contain $1$.

But $f_2(k)$ is more interesting. We have $f_2(0) = 1$ and $f_2(1) = 2$ by simple counting. But then we can make a simple argument:

$f_2(k) = f_2(k-1) + f_2(k-2)$ because the number of binary strings of length $k$ that avoid $11$ is equal to the amount that avoid $11$ of length $k-1$ with string $0$ prepended plus the amount of length $k-2$ with string $10$ prepended.

You can generalize this argument for a recurrence for $f_n(k)$:

$f_n(k) = f_n(k-1) + f_n(k-2) + \cdots + f_n(k-n)$ because the number of binary strings of length $k$ that avoid string $1^n$ is equal to the amount that avoid $1^n$ of length $k-1$ with string $0$ prepended plus the amount of length $k-2$ with binary digits $10$ prepended to the integer, and so forth, continuing until the amount of strings of length $k - n$ with binary string $1^{n-1}0$ prepended.

To get the starting numbers before the recurrence, we have:

$$\forall k< n:f_n(k) = 2^{k}$$

Now that we have analyzed $f$ we can go back to your problem. First let $g_n(k)$ be the number of binary strings that a maximum sequence of ones exactly equal to $n$. Verify for yourself that:

$$g_n(k) = f_{n+1}(k) - f_n(k)$$

Finally, there is a one-to-one correspondence between the binary strings of length $k$ and and the integers in $[1, 2^k)$ for our problem of counting the maximal sequence of ones.

Unfortunately I don't know where you got the numbers in your post from, as they are not correct. The above formula for $g_2$ yields A000100 which is correct.

$\endgroup$
  • $\begingroup$ I think after editing my explanation, my numbers should be correct. It's the cumulative number for any string with length less or equal to $k$ rather than for length exactly equal to $k$. Anyway for max run equal to 3, I get the same sequence as A000100, and this really answers my question: as it provides the appropriate references. Thank you! $\endgroup$ – Vincent Granville Aug 10 at 17:16
  • $\begingroup$ After reading some references, I realized that his is equivalent to another problem: the number of compositions of $k$ in which the maximal part is specified (2 or 3 in the examples discussed here.) $\endgroup$ – Vincent Granville Aug 10 at 18:15

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.