A threshold no average can see

The random Fibonacci sequence starts with $1, 1$ and at each step either adds or subtracts the last two terms, choosing by a fair coin. It wanders, it shrinks, it passes near nought, and with probability one it grows in the long run like $1.13198824^k$ — a rate that no single step contains and that Divakar Viswanath computed exactly in 2000 by a method special to the matrices involved.

In 1999 Mark Embree and Nick Trefethen had asked what happens if the term before last is weakened. Their sequence is

$$t_{k+1} = t_k \pm \beta\, t_{k-1},$$

with the sign still chosen by a fair coin and $\beta$ a fixed number. At $\beta = 1$ it is the random Fibonacci sequence. At $\beta = 0$ it never changes. In between, the growth rate falls as $\beta$ falls, and at some value it must fall through one — the point where the sequence stops growing and starts to decay. Embree and Trefethen located that value at $\beta^* \approx 0.70258$.

The hero figure shows three values of $\beta$ and what they do. Below the threshold, at $0.6$, every run shrinks — not steadily, since each step can add or subtract, but on average by about three per cent a step, so that after four hundred steps a typical run is a millionth of where it started. Above the threshold, at $0.8$, every run grows by about four per cent a step. At the threshold the runs neither grow nor shrink; they wander up and down over many powers of ten with no tendency either way. The whole story turns on a parameter changing from $0.6$ to $0.8$, and the essay is about why the one number that decides it is so hard to see.

Two step matrices and a coin #

The sequence is easiest to think about as a pair of numbers moving together. Write the current state as the vector $(t_k, t_{k-1})$. One step takes it to $(t_k \pm \beta t_{k-1},\; t_k)$, which is multiplication by one of two matrices,

$$P = \begin{pmatrix} 1 & \beta \\ 1 & 0 \end{pmatrix} \quad\text{or}\quad M = \begin{pmatrix} 1 & -\beta \\ 1 & 0 \end{pmatrix},$$

each chosen with probability one half. After $k$ steps the state is the product of $k$ randomly chosen matrices applied to the start. So the question is how fast a random product of two fixed matrices grows.

For a single matrix multiplied by itself the answer is its largest eigenvalue: a matrix with eigenvalue $1.2$ stretches long vectors by $1.2$ per step in the long run. For a random product there is no single eigenvalue to consult. Hillel Furstenberg and Harry Kesten proved in 1960 that the product still has a definite growth rate, the same for almost every sequence of coin tosses — a Lyapunov exponent, the logarithm of the factor per step — and Furstenberg proved later that it is positive under conditions these matrices satisfy. What neither theorem supplies is the value.

Why a minus sign shrinks things #

It helps to see, before measuring anything, why a minus step is the dangerous one. A plus step $t_{k+1} = t_k + \beta t_{k-1}$, applied when the last two terms have the same sign, adds them: the sequence grows the way Fibonacci’s does. A minus step applied to the same pair subtracts them, and if $t_k$ and $\beta t_{k-1}$ are close, the result is small — a cancellation. After a cancellation the next step starts from a pair in which one term is much smaller than the other, and whatever sign comes next, the pair has lost most of its size.

So the sequence’s fate is a race between steady modest growth from the plus steps and occasional deep cancellations from the minus steps. Lowering $\beta$ weakens both — the plus steps add less, and the minus steps cancel less exactly — but it weakens the growth more, and below $\beta^*$ the cancellations win on average. The first essay on this subject watched two orbits of a deterministic map separate from a starting difference too small to draw; here a single sequence’s size is pushed up and down by a coin, and the question is only which way the push tends.

The cancellations also explain why the average is misleading. A run that happens to avoid cancellations for a long stretch grows like the plus-only sequence, at nearly $1.48$ per step at the threshold, and although such stretches are rare, they are not exponentially rare enough to stop dominating the average of the squares. The average is a statement about the luckiest runs, and the typical rate is a statement about all of them.

The rate, measured, and the average, computed #

The figure below measures the growth factor at seventeen values of $\beta$, each from four hundred thousand steps, and sets beside it a second quantity that can be computed exactly.

The measured rate rises smoothly with $\beta$ and crosses one between $0.70$ and $0.71$. The exact line above it is the growth of the root-mean-square, the square root of the average of $t_k^2$ over all possible sequences of coin tosses, and its formula takes one line to derive. Square the recurrence and average over the coin:

$$\mathbb{E}\,t_{k+1}^2 = \mathbb{E}\,t_k^2 \pm 2\beta\,\mathbb{E}\,t_k t_{k-1} + \beta^2\,\mathbb{E}\,t_{k-1}^2.$$

The middle term carries the sign of the newest coin, which is independent of everything before it, so it averages to nought. What is left, $m_{k+1} = m_k + \beta^2 m_{k-1}$, is a deterministic Fibonacci-like recurrence for the mean squares, and it grows like the larger root of $x^2 = x + \beta^2$, which is $(1 + \sqrt{1 + 4\beta^2})/2$. That root is bigger than one for every positive $\beta$. The average of $t_k^2$ grows without bound whatever $\beta$ is.

So there are two growth rates, and they disagree completely about where the threshold is. The rate of a typical run says $0.70258$. The rate of the average says there is no threshold at all. Only the first is right about what a run actually does.

The average grows while the runs decay #

At $\beta = 0.6$ the disagreement can be watched directly.

The median run — the run that half the runs are bigger than — shrinks steadily, to about two hundredths by step 120. The exact root-mean-square climbs by six orders of magnitude over the same steps. Both statements are true at once, and the reconciliation is in the tails. A very few runs, by an unusual excess of plus signs, grow enormously, and the average of the squares is dominated by them: a run a million times larger than the median contributes a trillion times more to the average of squares. The sampled root-mean-square, from twenty thousand runs, follows the exact line for a while and then begins to fall short of it, because twenty thousand samples no longer contain enough of the rare runs that carry the average.

That is a general lesson about growth under randomness, and it reaches well beyond this sequence — it is a cousin of the average that never settles, where rare enormous values keep moving the mean. Whenever quantities multiply rather than add, the average and the typical value obey different laws: the average follows the logarithm of the average factor, the typical value follows the average of the logarithm. A gamble that multiplies a stake by $1.5$ or $0.6$ with equal chance has an average factor of $1.05$ and makes its expected value grow, while the average of the logarithms is negative and almost every player is ruined. The damped random Fibonacci sequence is the same phenomenon in two dimensions, with matrices in place of numbers, and the threshold $\beta^*$ is the point where the average logarithm changes sign — a point that no average of the quantities themselves can locate, because none of them change sign anywhere.

At the threshold, a random walk #

Exactly at $\beta^*$ the typical growth is nil, and the figure below shows what is left.

The logarithm of $|t_k|$ is a sum of the logarithms of the stretch factors at each step, and those are correlated only weakly and briefly — each step’s stretch depends on the direction the state vector happens to point in, and that direction forgets its past within a few steps. A sum of many such terms obeys a central limit theorem, proved for products of random matrices by Émile Le Page in 1982: the logarithm is approximately normally distributed, centred at $k$ times the exponent, with spread proportional to $\sqrt{k}$. At the threshold the centre is fixed at nought and only the spread remains, so the runs fan out symmetrically on the logarithmic scale like a random walk — some growing for a while, some shrinking, none committed.

That gives the threshold an operational meaning. Slightly above it, a drift of $\varepsilon$ per step eventually beats a spread of $\sqrt{k}$, but only after about $1/\varepsilon^2$ steps; below it, the same. Near $\beta^*$ the fate of a run is decided late, and any finite simulation that stops early will mistake a slow drift for none — which is exactly why the threshold is known to five decimal places and not to fifteen.

Fixed patterns grow; the mixture does not #

The two matrices behave very differently when either is used alone. $P$, all plus signs, has largest eigenvalue $(1 + \sqrt{1 + 4\beta^2})/2$, about $1.48$ at the threshold, and repeated alone it grows fast. $M$, all minus signs, has eigenvalues of size $\sqrt\beta$, about $0.84$, and repeated alone it decays. Any fixed repeating pattern of signs is a single matrix product with its own largest eigenvalue, and it either grows or decays.

At the threshold, roughly half of all repeating patterns grow when repeated, at every length from one to ten. The coin is not choosing between growing and decaying patterns in some balanced way; it is producing sequences that are not periodic at all, and their growth is not an average of the patterns’ growth rates. A random sequence of signs is a different object from every periodic one, and its exponent is a property of the mixing — of how the state vector’s direction is distributed when the signs are random — rather than of any pattern the mixing contains.

The same distinction appears in the joint spectral radius, the fastest growth any sequence of the two matrices can achieve. Among all the patterns the figure tries, the fastest is all plus signs every time, at $1.476$ per step at the threshold; choosing the signs at random gives exactly one. The random exponent sits somewhere strictly between the worst case and the best case, and no formula places it.

Every starting direction is forgotten #

There is a second reason the damped sequence belongs beside the chaotic maps of this subject, and it points the other way. In a chaotic map, two nearby starting points separate; the system remembers the tiny difference and magnifies it. A random product of matrices does something close to the opposite with directions. Start two runs from different initial pairs — $(1, 1)$ and $(1, -3)$, say — and feed them the same coin tosses. Their sizes may differ by a constant factor, but their directions converge: after a few dozen steps the two state vectors point the same way, and they stay aligned for ever.

The reason is that the random product stretches one direction more than the other, and repeated stretching aligns everything with the most-stretched direction, whatever the start. Oseledets’ theorem of 1968 makes this precise: almost every starting vector grows at the same rate, the top Lyapunov exponent, and the direction of the state forgets where it began exponentially fast, at a rate given by the gap between the two exponents — the same pair of stretching rates that sets a strange attractor’s dimension when the matrices come from a map’s derivative instead of a coin. A product of random matrices is sensitive to the coin and insensitive to the start. That loss of memory is what makes the exponent a single number rather than a number for each initial condition — and it is the same mechanism by which two chaotic systems, driven by a common signal, can be made to forget their differences, which is where this subject goes next.

The surprising connection: waves trapped by disorder #

Products of random two-by-two matrices are not a curiosity of sequences. They are how a wave travels through a disordered medium.

A wave moving along a chain of sites, each with a slightly different random property — an electron in an impure crystal, light in a randomly layered material — obeys a recurrence that relates its amplitude at three neighbouring sites, and the step from one pair of sites to the next is multiplication by a random two-by-two matrix. Philip Anderson argued in 1958 that disorder can trap a wave: if the random product grows with a positive exponent, a wave that is to stay bounded must decay away from where it started, exponentially, with the exponent as its rate. Every state is localised. In one dimension the Furstenberg exponent of the transfer matrices is positive for any disorder, so every wave is trapped — Anderson localisation — and the localisation length is the reciprocal of the exponent.

So the number that decides whether the damped random Fibonacci sequence grows is, in a physical setting, the number that decides how far an electron can move through a disordered wire. And the lesson of the mean-square figure carries over intact: averaged quantities, which are what a calculation can most easily compute, can miss the localisation entirely, because they are dominated by rare configurations through which the wave happens to pass.

A threshold measured to four places and derived to none #

The threshold’s value is measured, not derived. The dots in the rate figure are averages over long simulated runs, each with an error of a few parts in ten thousand, and the crossing at $0.70258$ is read from the measured curve. Embree and Trefethen located it by a more careful computation, and no closed form for $\beta^*$ is known. The figures establish that the crossing is between $0.70$ and $0.71$ and consistent with $0.70258$; the last digits are theirs.

The mean-square formula is exact; its sampled version is not. The line in the third figure is computed from the recurrence and is exact for every step. The open circles are averages over twenty thousand runs and become unreliable precisely where the figure says they do, so the visible gap between them and the line at late steps is a sampling effect, and it is the point of the figure rather than a defect in it.

The random-walk picture at the threshold is a limit theorem. The histograms show the spread doubling as the steps quadruple, as the central limit theorem predicts, but at a few thousand steps the distributions still carry visible traces of the start, and a figure at finite times cannot show that the limiting distribution is exactly normal.

Still open: a formula for the threshold #

For $\beta = 1$ the exponent is known to eight places by Viswanath’s method, which uses the fact that the two matrices then have integer entries and generate a group closely tied to the Stern–Brocot tree. For other $\beta$ that structure is absent, and the exponent is computed by simulation or by numerical approximation of the stationary distribution of the state vector’s direction, which for these matrices is singular and fractal. The value of $\beta^*$ is therefore a number defined by a clean condition — the exponent equals nought — with no known expression and no known proof of its irrationality.

More generally, no method is known that computes the Lyapunov exponent of a random product of two given matrices exactly, except in special families; it is not even known in general whether such exponents are rational when the matrices are. The theorems guarantee the number exists and say when it is positive. How fast two orbits part was a question with an answer once the derivative was known; for random products, knowing every matrix and every probability still leaves the answer to computation.