Where a base-β orbit spends its time

The doubling map spends equal time everywhere. Start almost anywhere, double and keep the fractional part a million times, and the orbit visits each tenth of the interval a tenth of the time — because the map carries every interval onto something twice as long, sending exactly its share of mass to each part, so the uniform distribution is left unchanged.

The base-β map $x \mapsto \beta x \bmod 1$ looks almost the same. It stretches by $\beta$ everywhere, and for $\beta$ between 1 and 2 it has two straight pieces. But its second piece is cut short, and that one defect changes the answer to the question where does an orbit spend its time? The time is not spread evenly. It is spread according to a staircase, and the staircase is built from the same object that decided which digits are allowed: the orbit of the number 1.

A million steps in base φ #

The histogram has two levels. Every bin to the left of $1/\varphi$ is visited at the same rate, about $1.17$ times the average, and every bin to the right at about $0.72$ times it. The line drawn over it is a formula, not a fit: the density

$$h(x) = \begin{cases} \dfrac{5 + 3\sqrt 5}{10} \approx 1.171 & x < 1/\varphi \\[2mm] \dfrac{5 + \sqrt 5}{10} \approx 0.724 & x \ge 1/\varphi \end{cases}$$

which integrates to 1. The bars match it to within the noise of two million samples in every bin that does not straddle the step.

The shape is not an artefact of where the orbit started, nor of how long it ran. Start anywhere else — any of the random points the figures use, or almost any other — and the same two levels appear, to the same accuracy. The density belongs to the map, not to the orbit, and it is the answer to a question every orbit asks and almost every orbit answers identically.

Why should the left part be favoured? Because it is reached from both pieces of the map. A point on the left piece is sent anywhere in $[0, 1)$; a point on the right piece is sent only into $[0, 1/\varphi)$, since the right piece is cut short at height $\varphi - 1 = 1/\varphi$. So the part of the interval below $1/\varphi$ receives mass from both pieces, and the part above it receives mass from the left piece alone. More arrives on the left, and the density there is higher.

The balance that fixes the density #

A density $h$ is invariant when the map sends it to itself: the mass arriving in each small interval equals the mass already there. For a map made of straight pieces of slope $\beta$ that is a balance equation. The mass arriving near $y$ comes from every point $x$ that lands on $y$ — one on each piece of the graph whose range includes $y$ — and a piece of slope $\beta$ compresses its mass by $\beta$ as it arrives. So

$$h(y) = \frac{1}{\beta} \sum_{x \,:\, T(x) = y} h(x).$$

For the golden map, a point $y$ below $1/\varphi$ has two preimages and a point above has one. Guess that $h$ is constant on each side, with value $a$ on the left and $b$ on the right. A point $y$ on the left has one preimage on each side — $y/\varphi$ on the left and $(y + 1)/\varphi$ on the right — so the balance says $a = (a + b)/\varphi$. A point on the right has a single preimage, $y/\varphi$, which lies on the left, so $b = a/\varphi$. Those two equations are consistent because $\varphi^2 = \varphi + 1$, and they give $a/b = \varphi$ — the ratio $1.171/0.724$ in the figure. Normalising to total mass 1 gives the numbers above.

There is a second route to the same numbers, through the finite graph of base φ. Its two states correspond to the two parts of the interval — “last digit 0” to the left part, “last digit 1” to the right — and its matrix is the same $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ whose powers counted the returns of another map. The matrix’s largest eigenvalue is $\varphi$, and its eigenvector, weighted by the lengths of the two parts, gives the relative time spent in each: the Parry density is, for a system of finite type, the Perron–Frobenius eigenvector of its graph in disguise. The balance equations above are the eigenvector equation written out.

The equations close up with two unknowns because the map’s pieces start and end at only two special heights, 0 and $1/\varphi$. The cut-off height of the second piece is $T(1)$, the image of 1, and it is the only place a new step could arise. That is the whole mechanism, and it generalises.

Parry’s staircase #

For any base $\beta > 1$, William Parry in 1960 and Alexander Gelfond independently in 1959 found the invariant density in closed form:

$$h(x) \ \propto \ \sum_{n \,:\, x < T^n(1)} \beta^{-n},$$

a sum over the orbit of 1 — $T^0(1) = 1$, $T(1)$, $T^2(1)$, and so on — adding $\beta^{-n}$ for every point of that orbit that lies to the right of $x$. Each term is a step function, 1 to the left of $T^n(1)$ and 0 to its right, weighted by $\beta^{-n}$. The density is their sum: a staircase that steps down at every point of the orbit of 1, the steps shrinking geometrically.

This connects the density directly to the digits of 1. When the expansion of 1 stops, the orbit of 1 hits 0 after finitely many steps and the staircase has finitely many steps — one for the golden ratio, two for the tribonacci constant. When the expansion of 1 never ends, neither does its orbit, and neither does the staircase. The same dichotomy that separated systems of finite type from the rest separates densities with finitely many steps from those with infinitely many.

In every case the density is bounded away from zero and from infinity. Each term is at most $\beta^{-n}$ and the $n = 0$ term is 1 everywhere, so the unnormalised density lies between 1 and $1/(1 - 1/\beta)$ — which is why every stretch of the interval is visited, and no stretch is visited disproportionately.

Infinitely many steps #

In base 1.8 the staircase is visibly more complicated. The first few steps are clear in the line and in the bars — a drop at 0.8, another near 0.44 — and the rest are smaller than the bin width and the sampling noise, piling up where the orbit of 1 happens to fall. The density is continuous from the right, discontinuous at every point of the orbit of 1 — an infinite set — and bounded between two fixed levels. None of that is visible in the histogram, which shows only the first few steps; the formula shows all of them.

The orbit of 1 is worth seeing in its own right, because it is where the steps are.

So one orbit, the orbit of the single point 1, determines where every other orbit spends its time. The digits it writes are the rulebook for which strings are allowed; the points it visits are the edges of the staircase that says how often each part of the interval is visited. Both descriptions are consequences of one fact: the right-hand piece of the graph ends at height $T(1)$, and everything about the system is decided by where that end lands and where it goes next.

Time averages that settle #

The density is an invariant measure, and the map is ergodic for it: an orbit started at almost any point spends, in the long run, a share of its time in each region equal to that region’s measure. That is Birkhoff’s ergodic theorem, the same theorem that makes almost every binary expansion fair, and it can be watched converging.

The frequency of the digit 1 in a typical base-$\varphi$ expansion is the measure of $[1/\varphi, 1)$, the piece that writes a 1. Integrating the staircase over it gives $(1 - 1/\varphi) \times 0.724 = 1/(1 + \varphi^2) \approx 0.2764$. In binary, a typical number has half its digits equal to 1. In base $\varphi$ a typical number has a little over a quarter — fewer than half, because every 1 must be followed by a 0, and well below the half that the pattern $1010\dots$ would give, because a typical orbit also writes runs of several 0s.

The three runs in the figure are three random starting points, and the ergodic theorem says their averages converge for all starting points outside a set of measure zero. The exceptions exist — every number whose orbit is periodic, for a start, and many others — and they are invisible to any experiment that picks its start at random.

Why the steps follow the orbit of 1 #

The balance equation explains why the steps sit exactly at the orbit of 1 and nowhere else. A step in the density at a point $y$ means that the number of preimages, or the density at those preimages, changes as $y$ crosses it. The number of preimages changes only where a piece of the graph begins or ends, and the only piece that ends in the middle of the interval is the last one, at height $T(1)$. So $T(1)$ is a step.

Once there is a step at $T(1)$, the balance equation transports it. A point just to the left of $T^2(1)$ has a preimage just to the left of $T(1)$, and a point just to the right has a preimage just to the right; the density at the preimage jumps, so the density at $T^2(1)$ jumps too, reduced by the factor $1/\beta$ that every transfer applies. And so on along the orbit: each step creates the next, a factor $\beta$ smaller. The formula $\sum_{x < T^n(1)} \beta^{-n}$ is that cascade written out, and when the orbit of 1 reaches 0 the cascade ends, because a step at 0 is no step at all.

Seen this way, the doubling map’s uniform density is the case with no cascade: its second piece reaches all the way to the top, $T(1)$ is 0 at once, and nothing ever starts. Every integer base is the same, which is why ordinary positional notation, in any base, treats all digits evenly in a typical number; the unevenness of base $\varphi$ is the price of a base whose last piece does not fit.

The measure every other measure loses to #

The Parry density has a second characterisation that explains why it is the natural one. The system has topological entropy $\log \beta$: the number of distinguishable digit strings of length $n$ grows like $\beta^n$. Every invariant measure has its own entropy, measuring how unpredictable a typical orbit is under that measure, and each is at most $\log \beta$. Parry’s measure is the unique invariant measure that attains the maximum. It spreads its weight over the allowed strings as evenly as the constraints permit — each allowed string of length $n$ getting roughly $\beta^{-n}$ of the mass — and that evenness is exactly what makes a typical orbit as unpredictable as the system allows.

That coincidence — the density that Lebesgue measure converges to is also the one of maximal entropy — is special to maps of constant slope. For a map whose slope varies, such as the logistic map at its top parameter, the density that typical orbits follow and the measure of maximal entropy can differ, and the arcsine density there is shaped by the slope, crowding near the ends where the map is flattest. Here the slope is the same everywhere, the only source of unevenness is the short piece, and the staircase is the whole of it.

For the doubling map the measure of maximal entropy is the uniform one, since every binary string is allowed and every one of length $n$ gets $2^{-n}$. For the golden map it cannot be uniform, because the strings are constrained, and the staircase is what “as even as possible” looks like under the constraint that no two 1s touch.

What the histograms cannot certify #

Floating-point orbits are not true orbits. Multiplying by $\varphi$ in double precision loses a digit or so of accuracy every few steps, and after a few dozen steps the computed orbit has no relation to the true orbit of its starting point. What it is, is a pseudo-orbit — a sequence that follows the map to within rounding at each step — and for expanding maps like these a pseudo-orbit stays close to some true orbit, which is why its statistics are still meaningful. The figures also nudge the orbit by $10^{-9}$ every thousand steps, so that rounding cannot trap it on a short cycle.

The bars are samples of the density, not measurements of it. Two million steps in fifty bins leave about forty thousand in each, and the relative noise is about half a percent — matched by the check, which requires agreement to within five hundredths away from the steps. Steps smaller than that noise, which is all but the first few in base 1.8, cannot be seen in any histogram and are shown only by the formula.

Ergodicity is a theorem the figure illustrates. Three orbits settling on the same frequency is consistent with it, and would be consistent with many other things; the proof that almost every orbit behaves this way is Rényi’s and Parry’s, not the picture’s.

Still open: which particular numbers are typical #

The ergodic theorem says almost every number has digit frequencies given by the Parry measure — is normal in base $\beta$, in the natural sense. As with ordinary normality, almost nothing is known about specific numbers. It is not known whether $\sqrt 2 - 1$ is normal in base $\varphi$, or whether $1/\pi$ is. For integer bases the corresponding questions about $\sqrt 2$ and $\pi$ are famous and open; in non-integer bases they are equally open and less studied.

There are also questions about how normality in different bases interacts. For integer bases, a number can be normal in base 2 and not in base 3, and normality in bases $b$ and $b^k$ is equivalent; for non-integer bases the corresponding relations between $\beta$ and $\beta'$ are understood only in special cases, and whether a number can be normal in base $\varphi$ and not in base $\varphi^2$ is the kind of question where results exist and a full picture does not.

A third question concerns the density itself as $\beta$ varies. For each base there is one staircase; as $\beta$ moves continuously, the orbit of 1 moves, the steps slide, and at bases where the orbit of 1 happens to hit 0 the infinite staircase collapses to a finite one. How the density depends on $\beta$ — continuously in an averaged sense, discontinuously at every base of finite type — has been studied, and its fine structure, including the entropy of the Parry measure restricted to parts of the interval, is still being worked out.

One orbit that governs the rest #

The doubling map spends its time evenly because both its pieces are complete. Cut the second piece short, as every non-integer base does, and the interval is no longer treated evenly: the region reached from both pieces is visited more, and the boundary between the favoured and unfavoured parts is where the short piece ends. Follow that boundary under the map and it generates the whole staircase. The orbit of 1 — a single, specific orbit — dictates both which digit strings every other number may have and how often each part of the interval is visited, and in bases where it never closes up, it dictates infinitely many of each.

That is an unusual amount of control for one orbit to have. In most dynamical systems no single orbit is privileged; here the edge of the interval is, because it is where the map’s graph is cut, and a cut is a place where information about the whole system is concentrated. The cobweb of that one point, drawn for a few steps, already contains the first steps of the staircase every other orbit follows.