Véletlenszerű Fibonacci szekvencia

A véletlenszerű Fibonacci szekvencia a Fibonacci szekvencia sztochasztikus analógja , amelyet a rekurzív képlet határoz meg :

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

ahol a "+" vagy "-" jelet véletlenszerűen választjuk minden n-hez, egyenlő valószínűséggel 1/2. Harry Kesten és Hillel Furstenberg tétele szerint az ilyen véletlenszerűen ismétlődő sorozatok bizonyos geometriai progresszióban nőnek, de növekedési ütemüket nehéz kiszámítani. 1999-ben Diwakar Viswanath kimutatta, hogy egy véletlenszerű Fibonacci-sorozat növekedési sebessége 1,1319882487943…, egy matematikai állandó, amelyet később Wiswanath-állandónak neveztek [1] [2] [3] .

Leírás

A véletlenszerű Fibonacci sorozat egy véletlenszerű egész sorozat , ahol a következő tagokat egy véletlenszerű rekurzív képlet határozza meg: ${\displaystyle \left\{f_{n}\right\))$ $f_{1}=f_{2}=1$

${\displaystyle f_{n}={\begin{cases}f_{n-1}+f_{n-2},&{\text{1/2 valószínűséggel))\\f_{n-1}-f_ {n-2},&{\text{1/2}}\end{esetek}}} valószínűséggel$ .

Így a véletlenszerű Fibonacci-sorozat 1-es, 1-es számokkal kezdődik, és a sorozat minden következő tagja vagy az előző két tag összege, vagy azok különbsége, 1/2 valószínűséggel.

Ha váltogatja a jeleket: -, +, +, -, +, +, -, +, +, ..., akkor az eredmény egy sorozat lesz:

1, 1, 0, 1, 1, 0, 1, 1, 0,…

Ebben az esetben azonban a véletlen befolyása eltűnik. A sorozat tagjai általában nem követnek előre megjósolható mintát. Példa véletlenszerű sorrendre:

1, 1, 2, 3, 1, -2, -3, -5, -2, -3…

karaktersorozathoz:

+, +, +, -, -, +, -, -, …

A véletlenszerű Fibonacci sorozat mátrixokkal írható le:

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

ahol a "+" vagy "-" jelet véletlenszerűen választjuk minden n-hez, egyenlő valószínűséggel 1/2. Akkor

${\begin{pmatrix}f_{n-1}\\f_{n}\end{pmatrix}}=M_{n}M_{n-1}...M_{3}{\begin{pmatrix }f_{1}\\f_{2}\end{pmatrix}}$ ,

ahol mátrixok véletlenszerű sorozata, amelyek A vagy B értéket veszik fel 1/2 valószínűséggel $\left\{M_{k}\right\}$

$A={\begin{pmatrix}0&1\\1&1\end{pmatrix)),B={\begin{pmatrix}0&1\\-1&1\end{pmatrix}}$

Lásd még

Jegyzetek

↑ D. Viswanath. Véletlenszerű Fibonacci sorozatok és az 1,13198824 szám... // Számítási matematika. - 1999. - 1. évf. 69 , sz. 231 . - P. 1131-1155 .
↑ ÁLLÁS Oliveira, LH De Figueiredo. A Viswanath-konstans intervallum számítása // Megbízható számítás. - 2002. - 20. évf. 8 , sz. 2 . — 131. o .
↑ E. Makover, J. McGowan. Egy elemi bizonyíték arra, hogy a véletlenszerű Fibonacci sorozatok exponenciálisan nőnek // Journal of Number Theory. - 2006. - 20. évf. 121 . — 40. o .