15
$\begingroup$

For an integer $n$, let $\ell(n)$ denote the maximal number of consecutive $1$s in the binary expansion of $n$. For instance, $$ \ell(71_{10}) = \ell(1000111_2) = 3. $$ Consider the set $E$ of all integers $n \in \mathbb{N}$ such that $\ell(n)$ is even.

It seems intuitively obvious that $E$ should have natural density $1/2$: $$ d(E) = \lim_{N\to \infty} \frac{|E \cap [0,N)|}{N} = 1/2.$$ Can one prove that this is actually the case?

Less ambitiously, can one show that $$ \bar{d}(E) = \limsup_{N\to \infty} \frac{|E \cap [0,N)|}{N} > 0?$$


Edit to add: The following sketch of an argument seeems to show that $$1/3 \leq \underline{d}(E) \leq \bar{d}(E) \leq 2/3.$$

Note that the binary expansion of any integer $n$ can be written as $(n)_2 = u 1^{\ell(n)}v$, where $u,v \in \{0,1\}^*$, $u$ is either empty or ends with a $0$, $v$ is either empty or begins with a zero, and the longest block of consecutive $1$s in $u$ has length strictly less than $\ell(n)$.

Divide $E$ into three sets, depending on $v$ in the decomposition above: $E_{bad}$ consists of $n\in E$ for which $|v| \leq 1$, $E_{0}$ consists of $n\in E$ for which $v = 00v'$, and $E_1$ consists of $n \in E$ for which $v = 01v'$. The set $E_{bad}$ is small enough that we don't need to worry about it.

Now, define the map $\phi_0 \colon\ E_0 \to \mathbb{N} \setminus E$ by (using the expansion above): $$ (\phi_0(n))_2 = u1^{\ell(n)+1}0v'.$$ Similarly, define $\phi_1 \colon\ E_1 \to \mathbb{N} \setminus E$ by $$ (\phi_1(n))_2 = u1^{\ell(n)+1}0v'.$$

It is not hard to show that these maps are both injective. Additionally, for almost all $n$, $\phi_0(n)/n$ is close to $1$, and likewise for $\phi_1$. From here, one can infer that $$ \bar d(E) \leq 2(1 -\bar d(E)), $$ and consequently $\bar d(E) \leq 2/3$. A symmetric argument shows that $\underline d(E) \geq 1/3$.

$\endgroup$
1
  • 2
    $\begingroup$ You might want to look up to distribution of the length of the longest run in $n$ (fair) Bernoulli trials. You essentially ask about the parity of such a run. See e.g. this thread: math.stackexchange.com/q/59738/10312 $\endgroup$ Aug 5 at 13:40

2 Answers 2

24
$\begingroup$

Perhaps surprisingly, the random variable $\ell(n)$ (with $n$ drawn uniformly from $[0,N)$) concentrates too much around $\log_2\log_2 N$ (where $\log_2$ denotes the logarithm to base $2$) to have a limiting parity probability - the variance stays bounded as $N \to \infty$, as opposed to growing to infinity. One only recovers a limiting law when the fractional part $\{\frac{1}{2} \log_2 \log_2 N \}$ of half the double logarithm of $N$ converges to a limit, and when one does so the parity probability will usually converge to a limit that deviates slightly from $1/2$.

To simplify the calculations a little let us assume that $N$ is of the form $N = 2^{2^{2k+1}}$ (I'll leave it as an exercise to the reader to handle the general case) in the asymptotic regime $k \to \infty$. Then the binary expansion of a randomly chosen element $n$ of $[0,N)$ consists of $2^{2k+1}$ independent Bernoulli variables (each taking $0$ and $1$ with values $1/2$). We think of this as the initial segment of an infinite sequence of Bernoulli variables. Now we perform the standard trick of viewing this sequence as a renewal process. After each $0$, the number of $1$s one encounters before one reaches the next $0$ is $a-1$ where $a$ is distributed according to a geometric distribution of expectation $2$. One can thus interpret this sequence as $a_1-1$ zeroes followed by a one, then $a_2-1$ zeroes followed by a one, and so forth ad infinitum, where $a_1,a_2,\dots$ are iid geometric distributions of expectation $2$. By the law of large numbers, we see with probability $1-o(1)$ that the first $t$ for which $a_1+\dots+a_t$ exceeds $2^{2k+1}$ will lie in the range $[2^{2k}-2^{4k/3},2^{2k}+2^{4k/3}]$ (say). Also, by symmetry we see that with probability $1-o(1)$, the maximum value of the $a_i$ for $i \leq 2^{2k}+2^{4k/3}$ will already be attained for $i \leq 2^{2k}-2^{4k/3}$. Putting these two together, we see that with probability $1-o(1)$, $\ell(n)$ will equal $\sup_{1 \leq i \leq 2^{2k}} a_i-1$. So asymptotically we just need to understand the distribution of $\sup_{1 \leq i \leq 2^{2k}} a_i-1$. We have the exact formula $$ {\bf P}( \sup_{1 \leq i \leq 2^{2k}} a_i-1 < t ) = \prod_{i=1}^{2^{2k}} {\bf P}(a_i-1 < t)$$ $$ = (1-2^{-t})^{2^{2k}}$$ for any positive integer $t$, so in particular $$ {\bf P}( \sup_{1 \leq i \leq 2^{2k}} a_i-1 - 2k < s ) = \exp( - 2^{-s} ) + o(1)$$ for any fixed $s$. Thus in the limit $k \to \infty$, $\ell(n) - 2k$ converges in distribution to a discrete random variable $X$ with distribution function $$ {\bf P}( X < s ) = \exp( - 2^{-s} ).$$ (Is there a name for this sort of random variable? EDIT: it is a discrete Gumbel distribution, see update below.) The quantity $\frac{|E \cap [0,N)|}{N}$ then converges to the probability that $X$ is even, which is $$ \sum_{j \in {\bf Z}} \exp(-2^{-2j-1}) - \exp(-2^{-2j}) = 0.4998402\dots$$ which is very slightly less than $1/2$. (If one picked a different subsequence of $N$ one would obtain a different limit; for instance if $N = 2^{2^{2k}}$ then the same analysis would ultimately give the complementary limiting probability of $0.500157\dots$.)

UPDATE: after a tip in the comments, I'll remark that a refinement of the above analysis will eventually show that the distribution of $\ell(n)$ is asymptotic to the integer part $\lfloor \mathrm{Gumbel}(\log_2 \log_2 N, \log_2 e)\rfloor$ of a Gumbel distribution, in the sense that the Levy metric (for instance) between the two distributions goes to zero as $N \to \infty$ (without any further restriction on the natural number $N$). In retrospect this sort of answer was a natural guess, given the usual role of the Gumbel distribution in extreme value theory.

Some references for further reading (gathered from following links in the comments):

Gordon, Louis; Schilling, Mark F.; Waterman, Michael S., An extreme value theory for long head runs, Probab. Theory Relat. Fields 72, 279-287 (1986). ZBL0587.60031.

Chakraborty, Subrata; Chakravarty, Dhrubajyoti; Mazucheli, Josmar; Bertoli, Wesley, A discrete analog of Gumbel distribution: properties, parameter estimation and applications, ZBL07482747.

$\endgroup$
4
  • $\begingroup$ oh using probability to prove a number theory result? or did the question already have some probability in it? $\endgroup$
    – BCLC
    Aug 6 at 0:39
  • 3
    $\begingroup$ On the name of that random variable, it looks like a discrete version of Gumbel and is discussed in arxiv.org/abs/1410.7568 as a candidate extreme-value distribution for data taking integer values. $\endgroup$
    – user196574
    Aug 6 at 7:07
  • 5
    $\begingroup$ @BCLC Probabilistic number theory has been a thing for almost a century. en.wikipedia.org/wiki/Probabilistic_number_theory $\endgroup$
    – Terry Tao
    Aug 6 at 12:48
  • 3
    $\begingroup$ I am reminded of the Dance Marathon Problem, which also features a kind of extreme value problem, and a limit that seems like it should exist, but doesn't. $\endgroup$ Aug 6 at 20:58
7
$\begingroup$

Here is a small visualisation of the values of this function.

I have taken $n \in \{1,2,\ldots,512\}$ and calculated the proportion of the numbers $0 \leqslant x < 2^n$ that have a maximum 1-run of even length.

enter image description here

Obviously I can't compute directly the longest run for each of the integers smaller than $2^{512}$ but luckily the values can be computed symbolically.

The number of compositions (i.e., ordered partitions) of $n$ with largest part odd is equal to the number of integers in the range $0 \leqslant x < 2^{n-1}$ with largest 1-run of even length (via the "McMahon Graph" of a composition).

These values are listed in the OEIS at https://oeis.org/A103421 along with a generating function that can be computed symbolically by Mathematica for a reasonable range of values.

$\endgroup$
1
  • 2
    $\begingroup$ That generating function probably permits an asymptotic analysis, though it's a bit tricky. I have to restrain myself due to too many other things to do, but maybe someone else will have a go. $\endgroup$ Aug 6 at 13:35

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.