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

В математике случайная последовательность Фибоначчи является стохастическим аналогом Последовательность Фибоначчи определяется отношение повторения ж_п = ж_п−1 ± ж_п−2, где выбраны знаки + или - наугад с равной вероятностью 1/2, независимо для разных п. По теореме Гарри Кестен и Гилель Фюрстенберг, случайные рекуррентные последовательности такого типа растут при определенном экспоненциальная скорость, но вычислить скорость явно сложно. В 1999 году, Дивакар Вишванатх показали, что скорость роста случайной последовательности Фибоначчи равна 1,1319882487943… (последовательность A078416 в OEIS ), а математическая константа это было позже названо Постоянная Вишваната.^[1][2][3]

Описание

Случайная последовательность Фибоначчи - это целая случайная последовательность {ж_п}, куда ж₁ = ж₂ = 1, а последующие члены определяются из случайного рекуррентного соотношения

${\displaystyle f_{n}={\begin{cases}f_{n-1}+f_{n-2},&{\text{ with probability 1/2}};\\f_{n-1}-f_{n-2},&{\text{ with probability 1/2}}.\end{cases}}}$

Прогон случайной последовательности Фибоначчи начинается с 1,1, и значение каждого последующего члена определяется честная монета бросок: учитывая два последовательных элемента последовательности, следующий элемент является либо их суммой, либо их разностью с вероятностью 1/2, независимо от всех ранее сделанных выборов. Если в случайной последовательности Фибоначчи на каждом шаге выбирается знак плюс, то соответствующий прогон будет Последовательность Фибоначчи {F_п},

${\displaystyle 1,1,2,3,5,8,13,21,34,55,\ldots .}$

Если знаки чередуются по образцу минус-плюс-плюс-минус-плюс-плюс -..., результатом будет последовательность

${\displaystyle 1,1,0,1,1,0,1,1,0,1,\ldots .}$

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

${\displaystyle 1,1,2,3,1,-2,-3,-5,-2,-3,\ldots {\text{ for the signs }}+,+,+,-,-,+,-,-,\ldots .}$

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

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

где знаки выбираются независимо для разных п с равными вероятностями для + или -. Таким образом

${\displaystyle {f_{n-1} \choose f_{n}}=M_{n}M_{n-1}\ldots M_{3}{f_{1} \choose f_{2}},}$

куда {M_k} представляет собой последовательность независимые одинаково распределенные случайные матрицы принимая ценности А или же B с вероятностью 1/2:

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

Скорость роста

Иоганн Кеплер обнаружил, что как п увеличивается, отношение последовательных членов последовательности Фибоначчи {F_п} приближается к Золотое сечение ${\displaystyle \varphi =(1+{\sqrt {5}})/2,}$ что составляет примерно 1,61803. В 1765 г. Леонард Эйлер опубликовал явную формулу, известную сегодня как Формула Бине,

${\displaystyle F_{n}={{\varphi ^{n}-(-1/\varphi )^{n}} \over {\sqrt {5}}}.}$

Он демонстрирует, что числа Фибоначчи растут с экспоненциальной скоростью, равной золотому сечению. φ.

В 1960 г. Гилель Фюрстенберг и Гарри Кестен показал, что для общего класса случайных матрица продукты, норма растет как λ^п, куда п это количество факторов. Их результаты применимы к широкому классу процессов генерации случайной последовательности, который включает случайную последовательность Фибоначчи. Как следствие, п-й корень из |ж_п| сходится к постоянному значению почти наверняка, или с вероятностью один:

${\displaystyle {\sqrt[{n}]{|f_{n}|}}\to 1.1319882487943\dots {\text{ as }}n\to \infty .}$

Явное выражение для этой константы было найдено Дивакаром Вишванатом в 1999 году. Оно использует формулу Фюрстенберга для Показатель Ляпунова случайного матричного произведения и интегрирования по некоторой фрактальная мера на Стерн – Броко. Более того, Вишванат вычислил числовое значение выше, используя плавающая точка арифметика подтверждена анализом ошибка округления.

Связанных с работой

В Постоянная Эмбри – Трефетена описывает качественное поведение случайной последовательности с рекуррентным соотношением

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

для разных значений β.^[4]

Рекомендации

1. Вишванат, Д. (1999). «Случайные последовательности Фибоначчи и число 1.13198824 ...» Математика вычислений. 69 (231): 1131–1155. Дои:10.1090 / S0025-5718-99-01145-X.
2. Oliveira, J.O.B .; Де Фигейредо, Л. Х. (2002). «Интервальное вычисление константы Вишваната». Надежные вычисления. 8 (2): 131. Дои:10.1023 / А: 1014702122205.
3. Маковер, Э .; Макгоуэн, Дж. (2006). «Элементарное доказательство того, что случайные последовательности Фибоначчи растут экспоненциально». Журнал теории чисел. 121: 40. arXiv:math.NT / 0510159. Дои:10.1016 / j.jnt.2006.01.002.
4. Эмбри, М.; Трефетен, Л.Н. (1999). «Рост и распад случайных последовательностей Фибоначчи» (PDF). Труды Королевского общества A: математические, физические и инженерные науки. 455 (1987): 2471. Bibcode:1999RSPSA.455.2471T. Дои:10.1098 / rspa.1999.0412.

внешняя ссылка

• Вайсштейн, Эрик В. «Случайная последовательность Фибоначчи». MathWorld.
• OEIS последовательность A078416 (десятичное разложение константы Вишваната)
• Случайные числа Фибоначчи. Numberphile Видео о случайной последовательности Фибоначчи.