Random Fibonacci Numbers

I just finished watching the latest Numberphile video on YouTube titled Random Fibonacci Numbers:

To produce these random Fibonacci numbers, what happens is that the previous two members of the sequence are added (as in the normal sequence) OR subtracted (the smaller from the larger) RANDOMLY. 

In the case of the normal Fibonacci sequence, we know that the \(n\)-th root of the \(n\)-th term approaches the golden ratio (1.6180339887…). In the randomised Fibonacci sequence, the \(n\)-th root of the \(n\)-th term approaches 1.319882487943… and this is as accurate as can currently be determined. Interestingly, as \(n\) gets larger, the \(n\)-th term can be a very large positive OR negative number. The SageMath code shown in Figure 1 calculates for 1000 terms and determines positivity or negativity:

Figure 1

Figure 2 shows an example of typical output:

Figure 2

As shown in Figure 3, a simple modification of the code , so that \(a\) must be zero, produces the standard Fibonacci sequence. 

Figure 3

Figure 4 shows an example of typical output:

Figure 4

Now in the normal Fibonacci sequence, the ratio of successive terms approaches \( \phi \) but that doesn't really work for the random Fibonacci sequence which is why the \(n\)-th root of the \(n\)-th term was chosen instead. This gets a little technical and I don't pretend to understand it but I'll quote from Wikipedia:

Johannes Kepler discovered that as \(n\) increases, the ratio of the successive terms of the Fibonacci sequence \(F_n\) approaches the golden ratio \( \phi=(1+\sqrt{5})/2\) which is approximately 1.61803. In 1765, Leonhard Euler published an explicit formula, known today as the Binet formula: $$F_n = \frac{\phi^n-(-1/\phi)^n}{\sqrt 5}$$It demonstrates that the Fibonacci numbers grow at an exponential rate equal to the golden ratio \( \phi \).

In 1960, Hillel Furstenberg and Harry Kesten showed that for a general class of random matrix products, the matrix norm grows as \( \lambda^n\), where \(n\) is the number of factors. Their results apply to a broad class of random sequence generating processes that includes the random Fibonacci sequence. As a consequence, the \(n\)-th root of |\(f_n\)| converges to a constant value almost surely, or with probability one:$$\sqrt[n]{|f_n|} \text{ --> 1.1319882487943 ...  as } n \text{ --> } \infty$$An explicit expression for this constant was found by Divakar Viswanath in 1999. It uses Furstenberg's formula for the Lyapunov exponent of a random matrix product and integration over a certain fractal measure on the Stern–Brocot tree. Moreover, Viswanath computed the numerical value above using floating point arithmetics validated by an analysis of the rounding error.