Mr George Young
Honours graduate


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.