Interested Article - Случайная последовательность Фибоначчи

Случайная последовательность Фибоначчи — это стохастический аналог последовательности Фибоначчи , который определяется рекуррентной формулой :

$f_{n}=f_{n-1}\pm f_{n-2}$ ,

где знак «+» или «-» выбирается для каждого n случайно, с равной вероятностью 1/2. Согласно теореме Гарри Кестен и Гилель Фюрстенберга, случайные рекуррентные последовательности этого вида растут в определённой геометрической прогрессии, но трудно вычислить скорость их роста. В 1999 году Дивакар Висванат показал, что скорость роста случайной последовательности Фибоначчи равна 1,1319882487943…, математической константе, которая позже была названа .

Описание

Случайная последовательность Фибоначчи — это случайная целочисленная последовательность $\left\{f_{n}\right\}$ , где $f_{1}=f_{2}=1$ и последующие члены определяются случайной рекуррентной формулой:

$f_{n}={\begin{cases}f_{n-1}+f_{n-2},&{\text{с вероятностью 1/2}}\\f_{n-1}-f_{n-2},&{\text{с вероятностью 1/2}}\end{cases}}$ .

Таким образом, случайная последовательность Фибоначчи начинается с чисел 1, 1, и каждый последующий член последовательности является либо суммой двух предшествующих членов, либо их разностью, с вероятностью 1/2.

Если чередовать знаки: -, +, +, -, +, +, -, +, +, …, то в результате получится последовательность:

1, 1, 0, 1, 1, 0, 1, 1, 0, …

Однако, в этом случае пропадает влияние случайности. В типичном случае, члены последовательности не будут следовать по предсказуемой схеме. Пример случайной последовательности:

1, 1, 2, 3, 1, −2, −3, −5, −2, −3…

для последовательности знаков:

+, +, +, -, -, +, -, -, …

Случайная последовательность Фибоначчи может быть описана с помощью матриц:

${\begin{pmatrix}f_{n-1}\\f_{n}\end{pmatrix}}={\begin{pmatrix}0&1\\\pm 1&1\end{pmatrix}}{\begin{pmatrix}f_{n-2}\\f_{n-1}\end{pmatrix}}$ ,

где знак «+» или «-» выбирается для каждого n случайно, с равной вероятностью 1/2. Тогда

${\begin{pmatrix}f_{n-1}\\f_{n}\end{pmatrix}}=M_{n}M_{n-1}...M_{3}{\begin{pmatrix}f_{1}\\f_{2}\end{pmatrix}}$ ,

где $\left\{M_{k}\right\}$ — случайная последовательность матриц, принимающих значение A или B с вероятностью 1/2

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

См. также

Примечания

D. Viswanath. Random Fibonacci sequences and the number 1.13198824... (англ.) // Mathematics of Computation. — 1999. — Vol. 69 , no. 231 . — P. 1131—1155 .
J. O. B. Oliveira, L. H. De Figueiredo. Interval Computation of Viswanath's Constant (англ.) // Reliable Computing. — 2002. — Vol. 8 , no. 2 . — P. 131 .
E. Makover, J. McGowan. An elementary proof that random Fibonacci sequences grow exponentially (англ.) // Journal of Number Theory. — 2006. — Vol. 121 . — P. 40 .