WikiSort.ru - Не сортированное

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

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

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

Описание

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

${\displaystyle 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…

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

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

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

${\displaystyle {\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. Тогда

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

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

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

См. также

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

Примечания