The University of Adelaide
You are here » Home » People directory
Text size: S | M | L
Printer Friendly Version
August 2019
MTWTFSS
   1234
567891011
12131415161718
19202122232425
262728293031 
       

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.