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

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

Описание

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

${\ 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}}}$

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

${\ 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 {для знаков}} +, +, +, -, -, + , -, -, \ ldots.}$

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

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

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

${\ displaystyle {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:

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

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

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

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

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

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

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

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

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

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

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

для разных значений β.

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

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

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