A growth rate no step contains

The Fibonacci numbers start 1, 1 and add the last two to get the next: 1, 1, 2, 3, 5, 8, 13. They grow like powers of the golden ratio, $\varphi \approx 1.618$, so each is about 1.618 times the one before. Change one thing. At every step toss a fair coin, and on heads add the last two numbers as before, but on tails subtract them:

$$t_1 = t_2 = 1, \qquad t_{k+1} = t_k \pm t_{k-1}.$$

A run might go 1, 1, 2, 1, 3, −2, 1, −1, 0, −1 — and it can shrink, change sign, even land on zero for a moment. The question is what happens in the long run. It is not obvious that the sequence grows at all, since each subtraction can undo an addition. It does grow, almost surely, and at a definite rate: $|t_k|^{1/k}$ tends to $1.13198824\ldots$ for almost every sequence of coin tosses. That number, Viswanath’s constant, is the subject of this essay, and the reason it is hard to compute is the reason it belongs beside the Lyapunov exponent.

Five runs, one slope #

A run is easy to generate. The numbers grow too large for ordinary arithmetic after a few thousand steps, so the logarithm of their size is carried separately, but nothing else is needed.

Each run is jagged. There are stretches where it falls, and moments where $|t_k|$ comes close to zero before recovering. But all five climb at the same average slope, well below the golden ratio’s and well above zero. After a thousand steps their growth rates, $|t_{1000}|^{1/1000}$, are all within a few per cent of $1.132$.

The coin makes the sequence random and the rate makes it predictable, and the combination is the same one a random walk shows: individual paths are unpredictable, and a statistic of the path is almost certain. What is different here is that the statistic is a growth rate of a product, not an average of a sum, and that difference is the whole difficulty.

Why the rate exists #

Write the sequence as a vector. The pair $(t_{k+1}, t_k)$ is obtained from $(t_k, t_{k-1})$ by multiplying by one of two matrices,

$$A_+ = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}, \qquad A_- = \begin{pmatrix} 1 & -1 \\ 1 & 0 \end{pmatrix},$$

chosen by the coin. After $k$ steps the vector is a product of $k$ random matrices applied to $(1, 1)$, and the size of $t_k$ grows like the size of that product.

Hillel Furstenberg and Harry Kesten proved in 1960 that a product of independent random matrices has a definite exponential growth rate almost surely: the size of the product, to the power $1/k$, converges to a constant that does not depend on the particular coin tosses. The proof is an ergodic theorem, the matrix version of the law of large numbers, and the constant is the top Lyapunov exponent of the product. Furstenberg proved in 1963 that the exponent is strictly positive under conditions these two matrices satisfy, so the random Fibonacci sequence really does grow exponentially. Neither theorem says what the rate is.

The estimates from short runs spread widely, because a few early subtractions can hold a sequence down for a long time. As the runs lengthen the spread narrows, and by 3,000 steps the middle ninety per cent of runs agree to within about one per cent. The narrowing is slow — the width falls roughly in proportion to one over the square root of the length, as a law of large numbers would suggest — so simulation pins the constant to two or three decimal places in reasonable time and no further.

Mark Embree and Nick Trefethen introduced the random Fibonacci sequence in 1999 and estimated the constant by simulation. Divakar Viswanath computed it in 2000 to eight decimal places by a quite different method, exact rather than statistical, and the method is the most interesting part of the story.

Averages that miss #

For a single map, the Lyapunov exponent is the average of the logarithm of the derivative along an orbit: stretch by stretch, the local rates multiply and their logarithms add. It is tempting to do the same here and average something about the two matrices.

The average of the two matrices is $\begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix}$, whose largest eigenvalue is 1: averaging the steps says the sequence does not grow at all. The average of the matrices’ own growth rates — $\varphi$ for $A_+$, and 1 for $A_-$, whose eigenvalues are complex numbers of size one — is about 1.309. And the root-mean-square size of $t_k$ grows like $\sqrt{\varphi} \approx 1.272$, because averaging $t_{k+1}^2 = t_k^2 + t_{k-1}^2 \pm 2 t_k t_{k-1}$ over the coin kills the cross term and leaves the Fibonacci recurrence itself. The true rate, which one long run puts at $1.1324$ and Viswanath’s calculation at $1.13199$, lies strictly between the first guess and the other two.

The reason every per-step average fails is that the matrices do not commute. $A_+$ stretches some directions and shrinks others, and how much it stretches the current vector depends on which way the vector is pointing — which depends on all the previous steps. A single map on a line has only one direction, so its local stretching is a number that can be averaged; the essay on how fast orbits part does exactly that. Two matrices acting on a plane have a stretch that depends on the direction, and the direction is itself a random process. The mean square grows faster than the typical size because it is dominated by rare runs that happen to keep adding, and that is the same gap between the typical and the average that a random walk’s return times show.

Three steps worked by hand #

The dependence on direction can be seen in the first few steps. Start from the vector $(1, 1)$, of length $\sqrt{2}$. Adding gives $(2, 1)$, of length $\sqrt{5}$, a stretch by a factor of about $1.58$. Subtracting gives $(0, 1)$, of length one, a shrink by a factor of about $0.71$. The two outcomes are equally likely, and on the logarithmic scale that the growth rate is measured on they average to a small gain.

Now suppose the first step added, so the vector is $(2, 1)$. Adding again gives $(3, 2)$, a stretch of about $1.61$; subtracting gives $(1, 2)$, which has exactly the same length as $(2, 1)$, so the step neither stretches nor shrinks. From $(2, 1)$ the average gain is larger than it was from $(1, 1)$. And if the first step subtracted, so the vector is $(0, 1)$, then adding gives $(1, 0)$ and subtracting gives $(-1, 0)$: both have length one, and neither step changes the size at all.

So the same coin toss is worth a different amount of growth depending on where the vector points. From $(0, 1)$ a step gains nothing whatever the coin says; from $(2, 1)$ a step gains a lot on average; and the direction after the step depends on the coin as well. The growth rate is an average over this chain of directions, and the chain does not visit directions evenly. That is why the naive averages above failed in both directions: the average matrix ignored the stretching entirely, and the averages of the matrices’ own rates assumed each matrix always meets its most favourable direction.

Where the vector points #

So the growth rate is an average after all — of the stretch $\log |A v| / |v|$, over the matrix $A$ chosen by the coin and over the direction $v$ — but the directions are not spread evenly. They are distributed according to a measure that the random process itself selects: the distribution of directions that is unchanged by applying a random step. Furstenberg called it the stationary measure, and the growth rate is the average stretch against it.

For random Fibonacci the stationary measure is far from even. The direction spends most of its time in narrow bands and almost none elsewhere, and zooming into any band reveals more bands inside it. The measure is singular: it gives no weight to any interval in the way a smooth density would, and its structure is tied to continued fractions, because the steps act on the ratio $t_k / t_{k-1}$ as $r \mapsto 1 \pm 1/r$, a map from the family that builds the Stern–Brocot enumeration of fractions.

That connection is what Viswanath used. He described the stationary measure exactly in terms of the Stern–Brocot tree, computed the average stretch against it with rigorous error bounds, and obtained $1.13198824\ldots$ with every digit certified — an exact calculation of a constant defined by a random process, by replacing the randomness with its invariant distribution.

The rate as the coin changes #

The fair coin is one choice. If the plus sign is chosen with chance $p$, the product still has a definite growth rate, now a function of $p$.

At $p = 0$ the rule is always subtract, and the sequence is $1, 1, 0, -1, -1, 0, 1, 1, \ldots$ — periodic with period six, bounded, with growth rate exactly one. At $p = 1$ it is the Fibonacci sequence and grows like $\varphi$. Between them the rate rises steadily, and it rises immediately: with only one step in ten an addition, the rate is already about $1.015$. A system that on its own never grows becomes exponentially growing as soon as a little randomness is mixed in.

That is the random counterpart of sensitive dependence. The subtraction-only rule is a rotation — $A_-$ has order six — and a rotation neither stretches nor shrinks. Occasional additions interrupt the rotation, and because the additions stretch some directions and the rotation carries the vector through all of them, the interruptions compound. Furstenberg’s positivity theorem is the general statement, roughly: for matrices that do not share a common invariant direction and do not all preserve some fixed notion of length, the random product grows exponentially.

Sensitivity without a map #

The other essays on sensitive dependence measured how fast two nearby starting points separate under one fixed rule. Here there is no fixed rule — the rule is chosen afresh at every step — and there is only one starting point. The analogy is exact nonetheless. The derivative of a product of maps is a product of derivatives, and for maps of the plane those derivatives are matrices; the Lyapunov exponent of a smooth map of the plane, such as the Hénon map, is the growth rate of a product of matrices chosen by the orbit rather than by a coin. Random Fibonacci strips away the orbit and keeps the product, which is why it has become the standard test case for methods that compute Lyapunov exponents of products.

A system that sheds almost every orbit showed the same principle in one dimension: the rate that matters is an average against the distribution the dynamics selects, not against the obvious one. In one dimension that distribution can sometimes be written down. In two dimensions, even for two small integer matrices and a fair coin, it is the singular measure in the figure, and computing an average against it exactly took a new method.

Where random products appear #

The random Fibonacci sequence is a toy, but the object it isolates — the growth rate of a product of random matrices — governs several real systems, and the mistake of averaging the matrices is a real mistake in each.

A population with age classes is described by a matrix that says how many individuals of each age survive and reproduce in a year. In a constant environment the population grows at the rate of that matrix’s largest eigenvalue. In a varying environment — a good year, a bad year, chosen by the weather — the population is multiplied by a random sequence of such matrices, and its long-run growth rate is the top Lyapunov exponent of the product. Shripad Tuljapurkar made this the basis of stochastic demography in the 1980s, and the lesson is the one in the figure above: the growth rate of the average year is not the average growth rate, and it can have the wrong sign.

In physics the same product describes a wave travelling through a disordered medium, such as an electron in a crystal with impurities placed at random. The wave’s amplitude from one site to the next is a two-by-two transfer matrix that depends on the local disorder, and the product of those matrices along the chain has a positive Lyapunov exponent. Its reciprocal is the distance over which the wave dies away: the wave is confined, or localised, by the randomness itself. That is Anderson localisation in one dimension, and Furstenberg’s positivity theorem is one route to proving it.

In both settings the exponent must usually be found by simulation, to a few decimal places, as in the second figure. The random Fibonacci case, where it can be computed exactly, is valuable as a benchmark for exactly that reason.

What the simulations cannot show #

The runs are seeded and every number in the figures is reproducible, but they are samples. The estimates of the growth rate from simulation are good to about three decimal places, which is enough to see that the naive averages are wrong and not enough to confirm the eighth decimal of Viswanath’s constant; that confirmation comes from his calculation, not from these runs. The long run’s $1.1324$ differs from $1.13199$ in the fourth place for exactly this reason.

The histogram of directions is one run of four hundred thousand steps, binned coarsely. It shows that the stationary measure is uneven and suggests that it is singular, but no histogram can show singularity, which is a statement about arbitrarily fine scales. And the curve of growth rate against $p$ is eleven points from single runs; its smoothness between them is assumed, not shown.

Still open: when can such a rate be computed #

Viswanath’s method depends on the special structure of these two matrices — their link to continued fractions and the Stern–Brocot tree. For products of random matrices in general there is no such structure, and the top Lyapunov exponent is known exactly in only a handful of cases. Even for two-by-two matrices with small integer entries, chosen with equal probability, there is no general method for writing the exponent in closed form, and for almost none of them is it known whether the exponent is even rational.

The same gap separates the existence of the rate from its value in the other questions on this subject. Furstenberg and Kesten’s theorem guarantees a number; Furstenberg’s criterion says when it is positive; computing it is a separate problem, solved case by case. The random Fibonacci sequence is the case in which it was solved, and the certified digits $1.13198824$ are among the few Lyapunov exponents of random products known to that precision.

What the coin does to the product #

A coin chooses between two rules. One of them grows like the golden ratio; the other does not grow at all. Chosen at random, together they grow at a rate that is not the average of their rates, not the rate of their average, and not any quantity of a single step. It is the average stretch against the distribution of directions that the product itself creates — and that distribution, for two of the simplest matrices there are, turns out to be a fractal that took a tree of fractions to describe.

The lesson reaches past this one sequence. Whenever growth is compounded from steps that act differently on different states, the rate belongs to the process as a whole, not to its parts, and the honest way to find it is either to run the process for a long time or to find the distribution of states it settles into. Averaging the parts first gives an answer that is easy to compute and wrong.