🔢 mathematics

The martingale evolution of probability measures defined via the sum-of-digits functions

This paper investigates the properties of probability measures defined by the asymptotic density of sum-of-digits differences by reindexing odd integers to model their evolution as a nonautonomous dynamical system on planar binary trees, thereby providing a structural description of these measures via a stopped random walk and framing the Cusick conjecture as a specific instance of a broader claim about asymmetric tree evolution.

Original authors: Dawid Tarłowski

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Dawid Tarłowski

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, infinite row of natural numbers: 1, 2, 3, 4, and so on. Now, imagine a game where you look at the "binary code" of these numbers (the string of 0s and 1s that computers use to count).

For any number, we count how many 1s are in its binary code. Let's call this the "pop count."

The paper asks a simple but tricky question: If you take a number $n$ , add a specific amount $t$ to it, and look at the new pop count, how does it change?

Does the number of 1s usually go up?
Does it usually go down?
Does it stay the same?

The author, Dawid Tarłowski, investigates a famous guess (the Cusick Conjecture) which suggests that for any starting number $t$ , the result of this addition will increase the number of 1s more often than it decreases it. Specifically, the chance of the number of 1s going up is always greater than 50%.

The Problem: A Messy Sequence

At first glance, this seems like a chaotic mess. The relationship between adding numbers and their binary 1s is complicated. The paper notes that while we know the answer is "mostly yes" for most numbers, proving it for every number is incredibly hard.

The Solution: A Growing Tree

The author's big idea is to stop looking at the numbers as a flat list and start looking at them as a growing family tree.

The Family Tree of Numbers:
Imagine a tree where the root is the number 1. From any number on the tree, you can grow two new branches:
- Left Branch: A rule that creates a new number (roughly doubling and subtracting 1).
- Right Branch: A rule that creates a new number (roughly doubling and adding 1).
Every odd number you can think of appears exactly once on this tree. By organizing the numbers this way, the author turns a messy list into a structured hierarchy.
The "Random Walker" (The Martingale):
To understand how the "pop count" changes as we move down this tree, the author imagines a drunkard's walk (a random walk).
- Imagine a person standing at position 0 on a number line.
- Every time they take a step, they flip a coin. Heads = step right (+1), Tails = step left (-1).
- The "tree" tells this walker when to stop.
The paper shows that the probability of the pop count changing by a certain amount is exactly the same as the probability of this walker ending up at a certain spot when they are forced to stop by the rules of the tree.

The "Martingale" Magic

In math, a "martingale" is like a fair game where your expected future winnings are exactly what you have right now. The author proves that this "stopped random walk" behaves like a perfectly fair game.

Because it's a fair game, we can predict its behavior:

Symmetry: The walk is balanced. It's just as likely to go left as right, on average.
Variance (Wobble): We can measure how "wobbly" the walk is. The paper shows that if the tree grows in a very specific, alternating pattern (Left-Right-Left-Right), the walk gets very wobbly (variance increases). If the tree grows in a straight line (Left-Left-Left), the walk stays very calm (variance stays low).
The Limit: If the tree grows forever in a straight line, the walker eventually settles down at a specific spot. The paper calculates exactly where they settle.

The Big Claim: The "Asymmetric Growth"

Here is the paper's main contribution to the Cusick Conjecture:

The author suggests that once the tree starts growing, it develops a bias.

If you start the tree by going Left, the "weight" of the probability shifts to the positive side (more 1s).
If you start by going Right, the weight shifts to the negative side.
Crucially, the author claims this bias never disappears. Even as the tree grows huge and complex, that initial "heaviness" on one side persists.

The Conclusion:
The paper argues that the Cusick Conjecture (that the number of 1s increases more than 50% of the time) is just a special case of this broader rule: "Once a tree leans one way, it stays leaning that way."

The author supports this with computer simulations, checking millions of numbers. They found that the "worst-case" scenarios (where the probability is closest to 50%) still stay just above the 50% line, and these worst cases happen at very specific, predictable spots on the tree.

Summary in a Nutshell

The paper takes a confusing problem about binary numbers and reorganizes it into a family tree. By viewing the problem as a random walk that stops according to the tree's shape, the author shows that the system has a built-in "memory" of its direction. This structural insight provides a powerful new way to look at the Cusick Conjecture, suggesting that the "upward bias" in binary sums is a fundamental property of how these mathematical trees grow.

Technical Summary: The Martingale Evolution of Probability Measures Defined via the Sum-of-Digits Functions

Problem Statement
The paper investigates the properties of the family of probability measures $\{\mu_t\}_{t \in \mathbb{N}}$ defined on the integers $\mathbb{Z}$ . For a natural number $n$ , let $s(n)$ denote the number of ones in its binary expansion. The measure $\mu_t(d)$ represents the asymptotic density of natural numbers $n$ such that $s(n+t) - s(n) = d$ . While it is known that $\mu_t$ is a well-defined probability measure with mean zero, the central open problem motivating this work is the Cusick conjecture, which posits that $\mu_t(\mathbb{N}) > 1/2$ for all $t \in \mathbb{N}$ . Previous results have established this inequality for asymptotic density one of $t$ , or for specific classes of $t$ (e.g., those with many blocks of ones in binary), but a full structural proof remains elusive.

Methodology
The author, Dawid Tarłowski, proposes a structural re-indexing of the odd integers using a specific partial order $\preceq$ to reveal a hierarchical martingale structure underlying the evolution of these measures.

Partial Order and Re-indexing: The set of odd integers $T = 2\mathbb{N} + 1$ is equipped with a partial order generated by two maps, $L(t) = 2t - 1$ and $R(t) = 2t + 1$ . This structure allows the sequence of measures $\mu_t$ to be viewed as trajectories of a non-autonomous dynamical system.
Martingale Construction via Stopped Random Walks: The paper introduces a family of measures $P_t$ $P_{t}$ related to $\mu_t$ $μ_{t}$ by the convolution $\mu_t = \mu_1 * P_t$ $μ_{t} = μ_{1} * P_{t}$ . The evolution of $P_t$ $P_{t}$ is described using a simple symmetric random walk $S_n$ $S_{n}$ on $\mathbb{Z}$ $Z$ .
- A bijection is established between the set of full planar binary trees and bounded stopping times of the random walk.
- The measures $P_t$ are identified as the laws of the random walk stopped at specific times $\tau_t$ determined by the growth of these trees.
- Specifically, for a sequence of choices $w \in \{L, R\}^\mathbb{N}$ , the process $X_t = S_{\tau_{w(t)}}$ forms a martingale.
Dynamics of Tree Growth: The evolution of the measures is modeled as the growth of a binary tree. At each step, determined by the sequence $w$ , one branch of the tree is preserved while the other grows to become a copy of the current tree. This recursive structure defines the non-autonomous dynamics on pairs of probability measures.

Key Contributions and Results

Structural Description: The paper provides a transparent structural description of the measures $\mu_t$ via the associated stopped random walk. This includes explicit characterizations of their support, symmetries, and variance.
Variance Analysis: The author derives explicit bounds for the variance $D^2[P_w]$ $D^{2} [P_{w}]$ of the measures associated with words $w$ $w$ .
- The variance is shown to be monotone with respect to the partial order: $s \preceq t \implies D^2(P_s) \leq D^2(P_t)$ .
- Lower bounds are attained by constant words (e.g., $L^n$ or $R^n$ ), yielding $2 - (1/2)^n$ .
- Upper bounds are related to the number of blocks in the word $w$ , with alternating words (e.g., $LR, LR, \dots$ ) maximizing the variance.
Asymptotic Behavior:
- Bounded Variance: If the sequence of choices $w$ is eventually constant, the martingale converges almost surely. The limiting distributions are shown to be elements of the family $\{\mu_t\} \cup \{\hat{\mu}_t\}$ , where $\hat{\mu}_t$ is the reflection of $\mu_t$ .
- Unbounded Variance: If the number of blocks in the binary representation of $t$ tends to infinity, the measures satisfy a Central Limit Theorem, converging weakly to the standard normal distribution (consistent with prior results by other authors).
Symmetries: The paper establishes that $P_w(d) = P_w(-d)$ and $P_w(d) = P_{\leftarrow w}(d)$ , where $\leftarrow w$ is the reversed word. This implies that the mapping from the tree structure to the measure is not injective.

Relation to the Cusick Conjecture
The paper reframes the Cusick conjecture as a property of the "median preserving" nature of the martingale evolution.

The author proposes a generalized claim: If the tree grows asymmetrically (specifically, if $P_{Lv}(\mathbb{N}) > 1/2$ and $P_{Rv}(-\mathbb{N}) > 1/2$ for any word $v$ ), then the Cusick conjecture holds.
Lemma 24 demonstrates that if the inequality $P_w(\mathbb{N}) > 1/2$ holds for any odd $t$ (represented by a word $w$ ) starting with a specific condition ( $t_2=0$ in binary), it implies $\mu_t(\mathbb{N}) > 1/2$ for all $t$ .
Numerical Evidence: The paper concludes with numerical verification. For odd integers up to $12,000,001$, the global minimum of the function $V(t) = P_t(\mathbb{N})$ was found to be exactly $1/2$ . The minimizers are listed, showing that the inequality is tight but never violated in the tested range.

Significance and Claims
The paper claims that the Cusick conjecture is a special case of a more general statement regarding the asymmetric growth of binary trees associated with the martingale. By shifting the perspective from direct arithmetic properties of $s(n+t) - s(n)$ to the probabilistic evolution of stopped random walks on binary trees, the author provides a new framework for analyzing the measures. The work does not claim to prove the Cusick conjecture but rather reduces it to a property of the tree growth dynamics, which is supported by numerical data. The significance lies in the unification of the problem with martingale theory and the explicit structural bounds on variance and support.

The Problem: A Messy Sequence

The Solution: A Growing Tree

The "Martingale" Magic

The Big Claim: The "Asymmetric Growth"

Summary in a Nutshell

More like this