The University of Adelaide
You are here » Home » People directory
Text size: S | M | L
Printer Friendly Version
April 2014
M T W T F S S
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30        
             

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.