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

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

$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{array}{cc}{f}_{n-1}+f_{n-2},& \text{с вероятностью 1/2}\\ f_{n-1}-f_{n-2},& \text{с вероятностью 1/2}\end{array}$.

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

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

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

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

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

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

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

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

$\left(\begin{array}{c}{f}_{n-1}\\ f_n\end{array}\right)=\left(\begin{array}{cc}0& 1\\ \pm 1& 1\end{array}\right)\left(\begin{array}{c}{f}_{n-2}\\ f_{n-1}\end{array}\right)$,

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

$\left(\begin{array}{c}{f}_{n-1}\\ f_n\end{array}\right)=M_n{M}_{n-1}...M_3\left(\begin{array}{c}{f}_1\\ f_2\end{array}\right)$,

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

$A=\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right),B=\left(\begin{array}{cc}0& 1\\ -1& 1\end{array}\right)$

См. также

• Числа Фибоначчи
• Обобщение чисел Фибоначчи