Random Fibonacci Sequence

The surprising behaviour of a random Fibonacci sequence

Description

This routine shows the surprising behaviour of a random Fibonacci sequence.
As reported by Divakar Viswanath - "RANDOM FIBONACCI SEQUENCES AND THE NUMBER 1:13198824..." - in MATHEMATICS OF COMPUTATION, 1999; 69(231): 1131-1155:
"For the familiar Fibonacci sequence (defined by f1 = f2 = 1, and fn = fn1 + fn2 for n > 2), fn increases exponentially with n at a rate given by the golden ratio (1 + sqrt(5))/2 = 1:61803398.... But for a simple modification with both additions and subtractions - the random Fibonacci sequences defined by t1 = t2 = 1, and for n > 2, tn = ±tn-1 ±tn-2, where each ± sign is independent and either + or - with probability 1/2 - it is not even obvious if |tn| should increase with n. Our main result is that:
|tn|^(1/n) -> 1:13198824... as n->Inf
with probability 1."

More details are available on http://www.advancedmcode.org/rndfibseq.html

You can visit my homepage http://home.tele2.it/cardillo
My profile on XING http://www.xing.com/go/invita/13675097
My profile on LinkedIN http://it.linkedin.com/in/giuseppecardillo

• MATLAB release: MATLAB 7.3 (R2006b)