Mr George Young

Honours thesis

Random Fibonacci Sequences

The random Fibonacci sequences are introduced as the sequences defined by a0 = 1, a1 = 1, an = an−2 ± an−1 , n ≥ 2, where the + sign or − sign is chosen independently for every n, both with probability 1/2. The behaviour of random Fibonacci sequences is analysed using two fundamentally different approaches, by considering the sequences as random walks in a binary tree and as products of random matrices. Using trees, it is proved that the variance of an grows exponentially with growth rate equal to 1+2 5 , and that the sequence (E[|an |]) also grows exponentially, with growth rate approximately 1.20556943. This constant is the only real root of a certain cubic polynomial. Using random matrices, it is proved that for an individual random Fibonacci sequence, its absolute value will almost surely grow exponentially with growth rate approximately 1.13198824. A method is given to approximate this constant numerically.