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



The parity of the maximal number of consecutive 1s in the binary expansion of an integer
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](https://en.wikipedia.org/wiki/Renewal_theory). 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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Gumbel_distribution), in the sense that the [Levy metric](https://en.wikipedia.org/wiki/L%C3%A9vy_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](https://en.wikipedia.org/wiki/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**](http://dx.doi.org/10.1007/BF00699107), Probab. Theory Relat. Fields 72, 279-287 (1986). [ZBL0587.60031](https://zbmath.org/?q=an:0587.60031).


*Chakraborty, Subrata; Chakravarty, Dhrubajyoti; Mazucheli, Josmar; Bertoli, Wesley*, A discrete analog of Gumbel distribution: properties, parameter estimation and applications, [ZBL07482747](https://zbmath.org/?q=an:07482747).


