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

В математике случайная последовательность Фибоначчи является стохастическим аналогом последовательности Фибоначчи, определяемой рекуррентным соотношением. $f_{n}=f_{n-1}\pm f_{n-2}$ , где знаки + или − выбираются случайным образом с равной вероятностью ${\tfrac {1}{2}}$ , независимо для разных $n$ . Согласно теореме Гарри Кестена и Гилеля Фюрстенберга , случайные рекуррентные последовательности такого типа растут с определенной экспоненциальной скоростью , но эту скорость трудно вычислить явно. В 1999 году Дивакар Вишванат показал, что скорость роста случайной последовательности Фибоначчи равна 1,1319882487943... (последовательность A078416 в OEIS ), математической константе , которая позже была названа константой Вишваната. ^[1]^[2]^[3]

Описание [ править ]

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

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

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

1,1,2,3,5,8,13,21,34,55,\ldots .

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

1,1,0,1,1,0,1,1,0,1,\ldots .

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

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

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

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

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

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

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

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

Темпы роста [ править ]

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

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

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

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

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

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

Обобщение [ править ]

Марк Эмбри и Ник Трефетен показали в 1999 году, что последовательность

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

почти наверняка затухает, если β меньше критического значения $β * \approx 0,70258$ , известного как константа Эмбри – Трефетена, и в противном случае почти наверняка растет. Они также показали, что асимптотическое отношение σ ( β ) между последовательными членами почти наверняка сходится для любого значения β . График σ ( β ), по-видимому, имеет фрактальную структуру с глобальным минимумом вблизи $β min \approx 0,36747,$ примерно равным $σ (β min) \approx 0,89517$ . ^[4]

Ссылки [ править ]

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

Внешние ссылки [ править ]

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

[1] Вишванат, Д. (1999). «Случайные последовательности Фибоначчи и число 1,13198824…» Математика вычислений . 69 (231): 1131–1155. дои : 10.1090/S0025-5718-99-01145-X .

[2] Оливейра, РАБОТА; Де Фигейредо, Л.Х. (2002). «Интервальное вычисление постоянной Вишваната». Надежные вычисления . 8 (2): 131. дои : 10.1023/A:1014702122205 . S2CID 29600050 .

[3] Маковер, Э.; Макгоуэн, Дж. (2006). «Элементарное доказательство того, что случайные последовательности Фибоначчи растут экспоненциально». Журнал теории чисел . 121 : 40–44. arXiv : math.NT/0510159 . дои : 10.1016/j.jnt.2006.01.002 . S2CID 119169165 .

[4] Эмбри, М .; Трефетен, Л.Н. (1999). «Рост и распад случайных последовательностей Фибоначчи» (PDF) . Труды Королевского общества A: Математические, физические и технические науки . 455 (1987): 2471. Бибкод : 1999RSPSA.455.2471T . дои : 10.1098/rspa.1999.0412 . S2CID 16404862 .

[1]

[2]

[3]

[4]