# The parity of the maximal number of consecutive 1s in the binary expansion of an integer

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

• 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 Aug 5 at 13:40

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.

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.

• oh using probability to prove a number theory result? or did the question already have some probability in it?
– BCLC
Aug 6 at 0:39
• 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. Aug 6 at 7:07
• @BCLC Probabilistic number theory has been a thing for almost a century. en.wikipedia.org/wiki/Probabilistic_number_theory Aug 6 at 12:48
• 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. Aug 6 at 20:58

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.

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.

• 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. Aug 6 at 13:35