Random Fibonacci sequence: Difference between revisions

Revision as of 10:42, 23 December 2003

Revision as of 10:44, 23 December 2003

Line 5:

The constant is defined as the [[exponential]] rate at which the average absolute value of a random [[Fibonacci sequence]] increases. A "random Fibonacci sequence" is a sequence of Fibonacci numbers that have the following recursive definition.

'''TerminatingInitial conditions :'''

:<math>f(0)=1</math>

:<math>f(1)=1</math>

'''Recursive step :'''

:<math>

f(n)=\left\{\begin{matrix} ff_+(n), & \mbox{with probability 0.5}\\ ff_-(n), & \mbox{with probability 0.5}\end{matrix}\right.

</math>

where,

:<math>ff_+(n)=f(n-1) + f(n-2)</math>

:<math>ff_-(n)=f(n-1) - f(n-2)</math>

or in other words, the decision whether to add or subtract the previous two elements of the sequence to get the next element, is taken at random with a probability of 0.5 favouring each decision (say with a toss of a fair coin.)