Random Fibonacci

Run the Fibonacci recurrence, but flip a fair coin for each sign:

The cancellations look like they should tame the growth. They do not. Viswanath (1999) proved that almost surely

exponential growth with a deterministic rate — every run of coin flips, outside a measure-zero set, produces the same constant.1

The right frame is matrix products: $\bigl(\begin{smallmatrix}x_{n+1}\\ x_n\end{smallmatrix}\bigr) = A_n\cdots A_1 \bigl(\begin{smallmatrix}x_1\\ x_0\end{smallmatrix}\bigr)$ with each $A_i$ a random signed Fibonacci matrix. Norms of random matrix products grow at a Lyapunov exponent $\gamma$; here $\nu = e^{\gamma}$, and no closed form for it is known or expected.

Why simulation stalls, and what worked

import math, random
a, b, shift = 1.0, 1.0, 0.0
for _ in range(10**7):
    a, b = b, random.choice((-1.0, 1.0)) * b + random.choice((-1.0, 1.0)) * a
    if abs(b) > 1e100:
        a, b, shift = a / 1e100, b / 1e100, shift + 100 * math.log(10)
print(math.exp((shift + math.log(abs(b))) / 10**7))

Ten million steps, with renormalization standing in for the overflow the naive version hits — and the answer is still only good to about three digits, because the running exponent fluctuates like a random walk: accuracy improves as $1/\sqrt n$. Viswanath sidestepped simulation entirely. The slopes $x_n/x_{n-1}$ form a Markov chain whose invariant measure is a fractal supported on the Stern–Brocot intervals; he computed that measure with rigorously bounded floating-point error and integrated against it, extracting eight certified digits. When Monte Carlo saturates, compute the measure, not the samples.

Damping generalizes the question: for $x_{n+1} = x_n \pm \beta x_{n-1}$, growth switches to decay at the Embree–Trefethen threshold $\beta^* \approx 0.70258$ — random recurrences carry phase transitions.