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:

    “Once a child has demonstrated his capacity for independent functioning in any area, his lapses into dependent behavior, even though temporary, make the mother feel that she is being taken advantage of....What only yesterday was a description of the child’s stage in life has become an indictment, a judgment.”
    —Elaine Heffner (20th century)

    “I was here first introduced to Joe.... He was a good-looking Indian, twenty-four years old, apparently of unmixed blood, short and stout, with a broad face and reddish complexion, and eyes, methinks, narrower and more turned up at the outer corners than ours, answering to the description of his race. Besides his underclothing, he wore a red flannel shirt, woolen pants, and a black Kossuth hat, the ordinary dress of the lumberman, and, to a considerable extent, of the Penobscot Indian.”
    —Henry David Thoreau (1817–1862)

    “It is possible—indeed possible even according to the old conception of logic—to give in advance a description of all ‘true’ logical propositions. Hence there can never be surprises in logic.”
    —Ludwig Wittgenstein (1889–1951)