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

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

Описание

Случайная последовательность Фибоначчи — это целочисленная случайная последовательность, заданная числами $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}$$

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

Внешние ссылки

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