Almost every orbit is fair

The histogram an orbit leaves found that a long orbit of the logistic map at four settles into a fixed distribution, the same whichever starting point is chosen — and quoted, without proving it, the property that makes that true. The property is called ergodicity, and the essay named where its proof lives: in the doubling map, $x \mapsto 2x \bmod 1$, which the logistic map is carried onto by a change of coordinates, and whose ergodicity is “a genuinely provable statement about binary expansions”.

This is that proof. Its conclusion is simple to state. Take almost any starting point, run the doubling map, and record how often the orbit lands in a given interval. In the long run the share of time spent there is exactly the interval’s length — a quarter for each quarter, an eighth for each eighth — so the orbit is fair to every part of the interval. The word almost is the whole subtlety, and the exceptions it allows are numerous, interesting and impossible to see.

The orbit is written in the digits #

Doubling a number in binary shifts its digits one place left; taking the fractional part deletes the digit that crossed the point. So if $x = 0.d_1 d_2 d_3 \ldots$ in binary, the orbit is $0.d_2 d_3 d_4 \ldots$, then $0.d_3 d_4 \ldots$, and so on. The orbit written as a word built this correspondence; here it is the tool.

Which quarter the $n$-th point lies in is decided by its first two digits — $00$ for the bottom quarter, $01$, $10$, $11$ for the others — which are digits $d_{n+1}$ and $d_{n+2}$ of the starting point. So the share of time the orbit spends in the bottom quarter is the frequency of the block $00$ among consecutive pairs of digits of $x$, and similarly for every other quarter, and for eighths with blocks of three digits.

That is also why every orbit in these figures is computed from digits and never by doubling a number on a computer. The orbit a computer draws explained what goes wrong: a floating-point number has 53 binary digits, doubling discards one each step, and after 53 steps every computed orbit reaches zero and stays there. The digits are the map’s own definition, and reading them is exact.

The figure’s four orbits are four kinds of digit sequence. A seeded sequence of fair coin tosses gives the random point, and its pairs $00$, $01$, $10$, $11$ each occur about a quarter of the time. The digits of $\tfrac13$ are $0101\ldots$, whose pairs are only $01$ and $10$. The point with no two 1s together never has the pair $11$. Champernowne’s number strings together the binary numerals $1, 10, 11, 100, 101, \dots$ and so contains every block of digits eventually.

Almost every number is balanced #

Émile Borel proved in 1909 that almost every number is normal: every block of $k$ binary digits occurs among its digits with frequency exactly $2^{-k}$. By the correspondence above, that is the statement that almost every orbit of the doubling map spends in every dyadic interval a share of time equal to the interval’s length.

“Almost every” has a precise meaning. The set of exceptions has length zero: it can be covered by intervals whose total length is as small as desired. The reason is the law of large numbers, applied to digits. If digits were chosen by fair coin tosses — and choosing a point uniformly at random from the interval is exactly that — the fraction of 1s among the first $n$ digits would concentrate ever more tightly around one half.

The curves narrow as $n$ grows. At a thousand digits, all but about a tenth of one per cent of strings have a fraction of 1s within $0.05$ of a half, and the remaining strings — the unbalanced ones — occupy a correspondingly tiny share of the interval, since each string of $n$ digits is an interval of length $2^{-n}$. Push $n$ further and the unbalanced share goes to zero; do the same for every block length and every tolerance, and the exceptions shrink to a set of length zero. That is Borel’s theorem, and it is the bell curve built out of coin flips read as a statement about points instead of about coins.

Invariant sets are all or nothing #

Normality of almost every point is one statement. Ergodicity is a stronger-sounding and in fact equivalent one: every set that the doubling map carries into itself, in both directions, has length zero or length one. There is no way to split the interval into two pieces of positive length that the map keeps apart.

Why this implies the fairness of orbits is Birkhoff’s ergodic theorem of 1931: for a map that preserves length and has no such splitting, the time an orbit spends in a set equals the set’s length, for almost every starting point. The theorem is general and hard. What is specific to the doubling map, and short, is the proof that there is no splitting — and the cleanest version of it runs through Fourier series.

Write a function on the interval as a sum of waves, a square wave built out of round ones, with a coefficient $c_m$ for the wave of frequency $m$. Composing the function with the doubling map replaces $x$ by $2x$, which turns the wave of frequency $m$ into the wave of frequency $2m$. So the coefficients do not change size; they move, each one from $m$ to $2m$. The figure shows the energy of a step function marching outwards: after three doublings nothing is left below frequency eight.

Now suppose a function is unchanged by the doubling map — as the indicator of an invariant set would be. Then its coefficient at frequency $m$ must equal its coefficient at $2m$, and at $4m$, and at $2^j m$ for every $j$. But a function whose square has a finite integral has coefficients whose squares add up to something finite, so the coefficients must shrink to zero at high frequencies. A sequence that is constant along $m, 2m, 4m, \ldots$ and tends to zero is zero. So every coefficient except the constant one vanishes, and the function is constant — up to a set of length zero. An invariant set’s indicator is then constantly $0$ or constantly $1$: the set has length zero or length one.

Mixing: stripes that spread evenly #

The Fourier picture says more than ergodicity. Energy does not just fail to stay put; it runs off to infinity, and that is a stronger property called mixing.

The points sent into the left half by $k$ doublings are those whose $(k+1)$-th binary digit is $0$, and they form $2^k$ stripes of equal width, evenly spaced. However the interval $A$ is placed, once the stripes are much narrower than $A$ it is cut into almost equal shares, and the length of $A$ inside the stripes approaches half the length of $A$. In general, the chance of starting in $A$ and landing in $B$ after $k$ steps approaches the product of their lengths: after enough doublings, where the orbit is tells nothing about where it started.

That is the precise sense in which the doubling map forgets. It is also a sharper form of the sensitivity of a difference too small to draw: two points close together separate, but mixing says that sets spread out evenly over the whole interval, not merely that points drift apart.

The exceptions, which are everywhere #

The set of numbers that are not normal has length zero, and it is nonetheless large and everywhere. Every rational number is an exception, since its digits eventually repeat a fixed block and so cannot contain every block with the right frequency — $\tfrac13$ is the figure’s example. There are also uncountably many irrational exceptions.

The numbers whose binary digits never have two 1s together form such a set. Doubling one of them deletes its first digit and leaves the rest, which still has no two 1s together, so the map carries the set onto itself. At level $k$ the admissible addresses number a Fibonacci number, and their share of the interval falls like $(\varphi/2)^k$, so the set has length zero. It is nonetheless uncountable — there are as many ways to choose digits avoiding $11$ as there are infinite paths through the Fibonacci tree — and it has a fractional dimension, $\log\varphi/\log 2 \approx 0.694$, in the sense of a dimension that is not a whole number.

This is the same shape as the middle-thirds Cantor set in almost none of it left, and still uncountably many: a set of length zero, invisible to any statement that holds “almost everywhere”, and yet containing as many points as the whole interval. The doubling map has infinitely many invariant sets of this kind, one for every rule forbidding some blocks of digits, and every one of them is an exception to Borel’s theorem.

Four running averages #

Birkhoff’s theorem is about limits, and the limits are approached at very different speeds.

The random point’s average wanders early and settles near $\tfrac14$ within a few thousand steps. The orbit of $\tfrac13$ never enters the bottom quarter, so its average is zero throughout: a periodic orbit’s averages are fixed by its period. The point avoiding $11$ also settles, but at $0.429$, the frequency of the block $00$ that its own digit rule produces; it is a perfectly regular orbit for a different invariant distribution, one that lives on its set of length zero. And Champernowne’s number, which provably is normal, approaches a quarter so slowly that twenty thousand steps leave it well short, because every numeral it concatenates begins with a $1$ and the bias fades only as the numerals grow long.

Being normal is a statement about the limit and says nothing about the rate. Champernowne’s number was constructed to be normal, and is; it is also a poor example of what normal looks like at any length a computer can reach.

From the doubling map to the logistic map #

The essay on the orbit’s histogram needed ergodicity for the logistic map at four, not for the doubling map, and the transfer is the point of doing the doubling map first. The same map in different coordinates showed that the logistic map at four and the tent map are one map seen through a change of variable, and the tent map is carried onto the doubling map in the same way, up to a symmetry that folds the interval in half. Changes of coordinates carry invariant sets to invariant sets, and sets of length zero to sets of length zero in the right measure. So a splitting of the logistic map’s interval into two invariant pieces of positive size would give one for the doubling map, and there is none.

What changes under the transfer is the measure. The doubling map preserves length; the logistic map preserves the arcsine density, which piles up at the ends of the interval. Birkhoff’s theorem then says that almost every orbit of the logistic map spends time in each interval in proportion to that density — which is exactly the histogram the earlier essay drew and could not justify. The fairness of doubling orbits, pushed through a sine squared, becomes the U-shaped unfairness of logistic orbits.

Balanced in one base, and not in another #

Normality depends on the base. A number can be normal in base two and not in base ten, and Wolfgang Schmidt showed in 1960 that this happens as freely as it can: for any two bases that are not powers of a common whole number — two and three, say, or two and ten — there are numbers normal in one and not in the other. Bases two and four cannot disagree, because a base-four digit is just a pair of binary digits.

Borel’s theorem holds in every base at once, and a countable union of sets of length zero still has length zero, so almost every number is absolutely normal, normal in every base simultaneously. Constructing one explicitly is harder than constructing a number normal in one base. Wacław Sierpiński gave the first explicit absolutely normal number in 1916, by a construction so involved that computing its digits was impractical for most of a century; efficient algorithms came only in the 2010s.

In dynamical terms each base is a different map — $x \mapsto 10x \bmod 1$ for base ten — and each is ergodic for length, by the same Fourier argument with ten in place of two. Their exceptional sets are all of length zero and all different, and Schmidt’s theorem says the differences are genuine: escaping one map’s exceptions does not mean escaping another’s.

What the digits cannot show #

Which numbers are normal. The figures draw orbits of four specific points, three of which were constructed to have known digit patterns. Borel’s theorem says almost every point behaves like the first, and gives no way to recognise one: a point chosen by any explicit rule is a point with a pattern, and the theorem is silent about points with patterns.

The limit itself. Every running average is drawn for twenty thousand steps and every histogram for four thousand. The ergodic theorem is about the limit as the number of steps grows without bound, and no finite run can distinguish a point that is normal from one that behaves normally for a billion steps and then stops.

The set of length zero. The figure of the set avoiding $11$ draws eight levels of a set that is only reached in the limit, and at the last level drawn it still covers a fifth of the interval. The actual set is a dust with no interval in it at all, and no finite level shows that.

Still open: whether the square root of two is normal #

Almost every number is normal in base two. Champernowne’s number is, and so are a few other numbers built for the purpose. For no naturally occurring constant — $\sqrt2$, $\pi$, $e$, $\log 2$ — is it known whether its binary digits are normal, or even whether the digit $1$ occurs in them with frequency one half. The digits of $\sqrt2$ have been computed to many billions of places and every block frequency looks exactly as it should; that is evidence and not proof.

The difficulty is the one the ergodic theorem cannot help with. The theorem says the exceptions have length zero; the constants are single points, and a single point is a set of length zero too. Nothing that holds almost everywhere can decide anything about a particular point, and the techniques that do decide things about particular points — the arithmetic of algebraic numbers, the continued fractions of irrationality proofs — have so far said nothing about their digits in any base.

Fair to every interval, and silent about every name #

The doubling map shifts binary digits, so the time an orbit spends in an interval is the frequency of a block among the starting point’s digits. For almost every point those frequencies are exactly the interval lengths — Borel’s theorem — and the reason, stated as ergodicity, is that doubling pushes every Fourier coefficient off to higher frequencies, so no function except a constant survives it unchanged. Sets forget where they started and spread evenly.

The exceptions have length zero and are everywhere: every fraction, and uncountable dusts like the numbers with no two 1s together, each carried onto itself by the map. Whether $\sqrt2$ is among them is unknown, because a theorem about almost every point has nothing to say about any point in particular. The typical case is completely understood, and every case anyone can write down is not — the same division that runs through the rest of this subject, from random walks to continued fractions.