Случайная последовательность Фибоначчи
Случайная последовательность Фибоначчи — это стохастический аналог последовательности Фибоначчи, который определяется рекуррентной формулой:
[math]\displaystyle{ f_n = f_{n-1} \pm f_{n-2} }[/math],
где знак «+» или «-» выбирается для каждого n случайно, с равной вероятностью 1/2. Согласно теореме Гарри Кестен и Гилель Фюрстенберга, случайные рекуррентные последовательности этого вида растут в определённой геометрической прогрессии, но трудно вычислить скорость их роста. В 1999 году Дивакар Висванат показал, что скорость роста случайной последовательности Фибоначчи равна 1,1319882487943…, математической константе, которая позже была названа константой Висваната[1][2][3].
Описание
Случайная последовательность Фибоначчи — это случайная целочисленная последовательность [math]\displaystyle{ \left \{ f_n \right \} }[/math], где [math]\displaystyle{ f_1 = f_2 = 1 }[/math] и последующие члены определяются случайной рекуррентной формулой:
[math]\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} }[/math].
Таким образом, случайная последовательность Фибоначчи начинается с чисел 1, 1, и каждый последующий член последовательности является либо суммой двух предшествующих членов, либо их разностью, с вероятностью 1/2.
Если чередовать знаки: -, +, +, -, +, +, -, +, +, …, то в результате получится последовательность:
1, 1, 0, 1, 1, 0, 1, 1, 0, …
Однако, в этом случае пропадает влияние случайности. В типичном случае, члены последовательности не будут следовать по предсказуемой схеме. Пример случайной последовательности:
1, 1, 2, 3, 1, −2, −3, −5, −2, −3…
для последовательности знаков:
+, +, +, -, -, +, -, -, …
Случайная последовательность Фибоначчи может быть описана с помощью матриц:
[math]\displaystyle{ \begin{pmatrix} f_{n-1} \\ f_n \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ \pm1 & 1 \end{pmatrix} \begin{pmatrix} f_{n-2} \\ f_{n-1} \end{pmatrix} }[/math],
где знак «+» или «-» выбирается для каждого n случайно, с равной вероятностью 1/2. Тогда
[math]\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} }[/math],
где [math]\displaystyle{ \left \{ M_k \right \} }[/math] — случайная последовательность матриц, принимающих значение A или B с вероятностью 1/2
[math]\displaystyle{ A = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} , B = \begin{pmatrix} 0 & 1 \\ -1 & 1 \end{pmatrix} }[/math]
См. также
Примечания
- ↑ 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.