Случайная последовательность Фибоначчи
Рандомизированная математическая последовательность, основанная на последовательности Фибоначчи

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

Описание

Случайная последовательность Фибоначчи — это целочисленная случайная последовательность, заданная числами для натуральных чисел , где и последующие члены выбираются случайным образом в соответствии со случайным рекуррентным соотношением. Пример случайной последовательности Фибоначчи начинается с 1,1, а значение каждого последующего члена определяется честным подбрасыванием монеты : если даны два последовательных элемента последовательности, следующим элементом является либо их сумма, либо их разность с вероятностью 1/2, независимо от всех выборов, сделанных ранее. Если в случайной последовательности Фибоначчи на каждом шаге выбирается знак плюс, соответствующий экземпляр — это последовательность Фибоначчи ( F n ), Если знаки чередуются в шаблоне минус-плюс-плюс-минус-плюс-плюс-..., результатом является последовательность ф н {\displaystyle f_{n}} н {\displaystyle n} ф 1 = ф 2 = 1 {\displaystyle f_{1}=f_{2}=1} ф н = { ф н − 1 + ф н − 2 ,  с вероятностью  1 2 ; ф н − 1 − ф н − 2 ,  с вероятностью  1 2 . {\displaystyle f_{n}={\begin{cases}f_{n-1}+f_{n-2},&{\text{ с вероятностью }}{\tfrac {1}{2}};\\f_{n-1}-f_{n-2},&{\text{ с вероятностью }}{\tfrac {1}{2}}.\end{cases}}} 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , … . {\displaystyle 1,1,2,3,5,8,13,21,34,55,\ldots .} 1 , 1 , 0 , 1 , 1 , 0 , 1 , 1 , 0 , 1 , … . {\displaystyle 1,1,0,1,1,0,1,1,0,1,\ldots .}

Однако такие закономерности возникают с исчезающей вероятностью в случайном эксперименте. В типичном прогоне условия не будут следовать предсказуемой закономерности: 1 , 1 , 2 , 3 , 1 , − 2 , − 3 , − 5 , − 2 , − 3 , …  для знаков  + , + , + , − , − , + , − , − , … . {\displaystyle 1,1,2,3,1,-2,-3,-5,-2,-3,\ldots {\text{ для знаков }}+,+,+,-,-,+,-,-,\ldots .}

Подобно детерминированному случаю, случайную последовательность Фибоначчи можно с пользой описать с помощью матриц : ( ф н − 1 ф н ) = ( 0 1 ± 1 1 ) ( ф н − 2 ф н − 1 ) , {\displaystyle {f_{n-1} \choose f_{n}}={\begin{pmatrix}0&1\\\pm 1&1\end{pmatrix}}{f_{n-2} \choose f_{n-1}},}

где знаки выбираются независимо для разных n с равными вероятностями для + или −. Таким образом, где ( M k ) — последовательность независимых одинаково распределенных случайных матриц, принимающих значения A или B с вероятностью 1/2: ( ф н − 1 ф н ) = М н М н − 1 … М 3 ( ф 1 ф 2 ) , {\displaystyle {f_{n-1} \выберите f_{n}}=M_{n}M_{n-1}\ldots M_{3}{f_{1} \выберите f_{2}},} А = ( 0 1 1 1 ) , Б = ( 0 1 − 1 1 ) . {\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 году Леонард Эйлер опубликовал явную формулу, известную сегодня как формула Бине , φ = ( 1 + 5 ) / 2 , {\displaystyle \varphi =(1+{\sqrt {5}})/2,} Ф н = φ н − ( − 1 / φ ) н 5 . {\displaystyle F_{n}={{\varphi ^{n}-(-1/\varphi )^{n}} \over {\sqrt {5}}}.}

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

В 1960 году Хиллел Фюрстенберг и Гарри Кестен показали, что для общего класса случайных матричных произведений норма растет как λ n , где n — число факторов. Их результаты применимы к широкому классу процессов генерации случайных последовательностей, включая случайную последовательность Фибоначчи. Как следствие, корень n-й степени из | f n | сходится к постоянному значению почти наверняка или с вероятностью единица: | ф н | н → 1.1319882487943 …  как  н → ∞ . {\displaystyle {\sqrt[{n}]{|f_{n}|}}\to 1.1319882487943\dots {\text{ как }}n\to \infty .}

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

Обобщение

Марк Эмбри и Ник Трефетен показали в 1999 году, что последовательность ф н = ± ф н − 1 ± β ф н − 2 {\displaystyle f_{n}=\pm f_{n-1}\pm \beta f_{n-2}}

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

Ссылки

  1. ^ Вишванат, Д. (1999). «Случайные последовательности Фибоначчи и число 1,13198824...» Математика вычислений . 69 (231): 1131– 1155. doi : 10.1090/S0025-5718-99-01145-X .
  2. ^ Оливейра, РАБОТА; Де Фигейредо, Л.Х. (2002). «Интервальное вычисление постоянной Вишваната». Надежные вычисления . 8 (2): 131. doi :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. ^ Embree, M. ; Trefethen, LN (1999). "Рост и распад случайных последовательностей Фибоначчи" (PDF) . Труды Королевского общества A: Математические, физические и инженерные науки . 455 (1987): 2471. Bibcode :1999RSPSA.455.2471T. doi :10.1098/rspa.1999.0412. S2CID  16404862.
  • Вайсштейн, Эрик В. «Случайная последовательность Фибоначчи». Математический мир .
  • Последовательность OEIS A078416 (Десятичное разложение константы Вишваната)
  • Случайные числа Фибоначчи. Видео Numberphile о случайной последовательности Фибоначчи.
Взято с "https://en.wikipedia.org/w/index.php?title=Случайная_последовательность_Фибоначчи&oldid=1150580949"