The Growth of Random Fibonacci Sequences

It is a well known fact that the Fibonacci sequence grows exponentially at a rate given by the golden ratio, &phis; = 1.61803398... We can generate a "random Fibonacci sequence" by starting with the terms 1, 1 but instead of forming new terms by adding the previous two, we can either add or subtract them with probability ½. This process can be represented as a linear matrix recurrence. An infinite number of random Fibonacci sequences can occur, and it has been shown by Divakar Viswanath that with probability one, not only does the absolute value of terms in the sequence grow exponentially, but it does so at a fixed rate of 1.13198824. . ., Viswanath's constant. Among the tools used to reach this end are the theory of products of random matrices, measure theory, use of the Stern-Brocot tree and a computer assisted calculation.

It is a well known fact that the Fibonacci sequence grows exponentially at a rate given by the golden ratio, &phis; = 1.61803398.