В математике случайная последовательность Фибоначчи является стохастическим аналогом последовательности Фибоначчи, определяемой рекуррентным соотношением f n = f n −1 ± f n −2 , где знаки + или - выбираются случайным образом с равной вероятностью 1/2, самостоятельно для разных n . По теореме Гарри Кестена и Хиллеля Фюрстенберга случайные рекуррентные последовательности такого типа растут с определенной экспоненциальной скоростью , но вычислить скорость явно сложно. В 1999 году Дивакар Вишванатхпоказали, что скорость роста случайной последовательности Фибоначчи равна 1,1319882487943… (последовательность A078416 в OEIS ), математической константе, которая позже была названа константой Вишваната. [1] [2] [3]
Описание
Случайная последовательность Фибоначчи представляет собой целочисленную случайную последовательность { f n }, где f 1 = f 2 = 1, а последующие члены определяются из отношения случайной рекуррентности
Прогон случайной последовательности Фибоначчи начинается с 1,1, и значение каждого последующего члена определяется подбрасыванием монеты : для двух последовательных элементов последовательности следующий элемент представляет собой либо их сумму, либо их разность с вероятностью 1 / 2, независимо от всех ранее сделанных выборов. Если в случайной последовательности Фибоначчи знак «плюс» выбирается на каждом шаге, соответствующий прогон является последовательностью Фибоначчи { F n },
Если знаки чередуются по образцу минус-плюс-плюс-минус-плюс-плюс -..., результатом будет последовательность
Однако в случайном эксперименте такие закономерности возникают с исчезающей вероятностью. При типичном запуске условия не будут следовать предсказуемой схеме:
Подобно детерминированному случаю, случайную последовательность Фибоначчи можно описать с помощью матриц:
где знаки выбираются независимо для разных n с равной вероятностью для + или -. Таким образом
где { M k } - последовательность независимых одинаково распределенных случайных матриц, принимающих значения A или B с вероятностью 1/2:
Скорость роста
Иоганн Кеплер обнаружил, что с увеличением n отношение последовательных членов последовательности Фибоначчи { F n } приближается к золотому сечению. что составляет примерно 1,61803. В 1765 году Леонард Эйлер опубликовал явную формулу, известную сегодня как формула Бине :
Это показывает, что числа Фибоначчи растут с экспоненциальной скоростью, равной золотому сечению φ .
В 1960 году Хиллель Фюрстенберг и Гарри Кестен показали, что для общего класса случайных матричных произведений норма растет как λ n , где n - количество факторов. Их результаты применимы к широкому классу процессов генерации случайных последовательностей, которые включают случайную последовательность Фибоначчи. Как следствие, корень n- й степени из | f n | почти наверняка сходится к постоянному значению или с вероятностью единица:
Явное выражение для этой константы было найдено Дивакаром Вишванатом в 1999 году. Оно использует формулу Фюрстенберга для показателя Ляпунова случайного матричного произведения и интегрирования по некоторой фрактальной мере на дереве Штерна – Броко . Более того, Viswanath вычислил числовое значение, указанное выше, с использованием арифметики с плавающей запятой, подтвержденной анализом ошибки округления .
Связанных с работой
Константа Эмбри – Трефетена описывает качественное поведение случайной последовательности с рекуррентным соотношением
для разных значений β. [4]
Рекомендации
- Перейти ↑ Viswanath, D. (1999). «Случайные последовательности Фибоначчи и число 1.13198824 ...» Математика вычислений . 69 (231): 1131–1155. DOI : 10.1090 / S0025-5718-99-01145-X .
- ^ Оливейра, РАБОТА; Де Фигейредо, LH (2002). «Интервальное вычисление константы Вишваната». Надежные вычисления . 8 (2): 131. DOI : 10,1023 / A: 1014702122205 .
- ^ Маковер, Э .; Макгоуэн, Дж. (2006). «Элементарное доказательство того, что случайные последовательности Фибоначчи растут экспоненциально». Журнал теории чисел . 121 : 40. arXiv : math.NT / 0510159 . DOI : 10.1016 / j.jnt.2006.01.002 .
- ^ Эмбри, М .; Trefethen, LN (1999). «Рост и распад случайных последовательностей Фибоначчи» (PDF) . Труды Королевского общества A: математические, физические и инженерные науки . 455 (1987): 2471. Bibcode : 1999RSPSA.455.2471T . DOI : 10,1098 / rspa.1999.0412 .
Внешние ссылки
- Вайсштейн, Эрик В. «Случайная последовательность Фибоначчи» . MathWorld .
- Последовательность OEIS A078416 (десятичное разложение константы Вишваната)
- Случайные числа Фибоначчи . Видео Numberphile о случайной последовательности Фибоначи.