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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

,

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

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

.

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

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

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

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

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

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

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

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

,

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

,

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

Примечания

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