Random Fibonacci Sequence - Description

Description

The random Fibonacci sequence is an integer random sequence {fn}, where f1 = f2 = 1 and the subsequent terms are determined from the random recurrence relation

f_n = \begin{cases} f_{n-1}+f_{n-2}, & \text{ with probability 1/2}; \\ f_{n-1}-f_{n-2}, & \text{ with probability 1/2}. \end{cases}

A run of the random Fibonacci sequence starts with 1,1 and the value of the each subsequent term is determined by a fair coin toss: given two consecutive elements of the sequence, the next element is either their sum or their difference with probability 1/2, independently of all the choices made previously. If in the random Fibonacci sequence the plus sign is chosen at each step, the corresponding run is the Fibonacci sequence {Fn},

If the signs alternate in minus-plus-plus-minus-plus-plus-... pattern, the result is the sequence

However, such patterns occur with vanishing probability in a random experiment. In a typical run, the terms will not follow a predictable pattern:

1, 1, 2, 3, 1, -2, -3, -5, -2, -3, \ldots \text{ for the signs } +, +, -, -, -, +, -, -, \ldots.

Similarly to the deterministic case, the random Fibonacci sequence may be profitably described via matrices:

where the signs are chosen independently for different n with equal probabilities for + or −. Thus

where {Mk} is a sequence of independent identically distributed random matrices taking values A or B with probability 1/2:

A=\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}, \quad B=\begin{pmatrix} 0 & 1 \\ -1 & 1 \end{pmatrix}.

Read more about this topic:  Random Fibonacci Sequence

Famous quotes containing the word description:

    “God damnit, why must all those journalists be such sticklers for detail? Why, they’d hold you to an accurate description of the first time you ever made love, expecting you to remember the color of the room and the shape of the windows.”
    —Lyndon Baines Johnson (1908–1973)

    “As they are not seen on their way down the streams, it is thought by fishermen that they never return, but waste away and die, clinging to rocks and stumps of trees for an indefinite period; a tragic feature in the scenery of the river bottoms worthy to be remembered with Shakespeare’s description of the sea-floor.”
    —Henry David Thoreau (1817–1862)

    “Everything to which we concede existence is a posit from the standpoint of a description of the theory-building process, and simultaneously real from the standpoint of the theory that is being built. Nor let us look down on the standpoint of the theory as make-believe; for we can never do better than occupy the standpoint of some theory or other, the best we can muster at the time.”
    —Willard Van Orman Quine (b. 1908)