Slumpmässig Fibonacci-sekvens

Den slumpmässiga Fibonacci-sekvensen är en stokastisk analog till Fibonacci-sekvensen , som definieras av den rekursiva formeln :

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

där tecknet "+" eller "-" väljs slumpmässigt för varje n, med lika sannolikhet 1/2. Enligt Harry Kestens och Hillel Furstenbergs sats växer slumpmässiga återkommande sekvenser av detta slag i en viss geometrisk progression, men det är svårt att beräkna deras tillväxthastighet. 1999 visade Diwakar Viswanath att tillväxthastigheten för en slumpmässig Fibonacci-sekvens är 1,1319882487943…, en matematisk konstant som senare kallades Wiswanath-konstanten [1] [2] [3] .

Beskrivning

Den slumpmässiga Fibonacci-sekvensen är en slumpmässig heltalssekvens , där de efterföljande termerna bestäms av en slumpmässig rekursiv formel: ${\displaystyle \left\{f_{n}\right\))$ $f_{1}=f_{2}=1$

$f_{n}={\begin{cases}f_{n-1}+f_{n-2},&{\text{med sannolikhet 1/2))\\f_{n-1}-f_ {n-2},&{\text{med sannolikhet 1/2}}\end{fall}}$ .

Således börjar den slumpmässiga Fibonacci-sekvensen med siffrorna 1, 1, och varje efterföljande medlem av sekvensen är antingen summan av de två föregående medlemmarna, eller deras skillnad, med sannolikhet 1/2.

Om du alternerar tecknen: -, +, +, -, +, +, -, +, +, ..., så blir resultatet en sekvens:

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

Men i detta fall försvinner slumpens inflytande. Typiskt kommer medlemmarna i en sekvens inte att följa ett förutsägbart mönster. Exempel på slumpmässig sekvens:

1, 1, 2, 3, 1, -2, -3, -5, -2, -3...

för en sekvens av tecken:

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

Den slumpmässiga Fibonacci-sekvensen kan beskrivas med hjälp av matriser:

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

där tecknet "+" eller "-" väljs slumpmässigt för varje n, med lika sannolikhet 1/2. Sedan

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

där är en slumpmässig sekvens av matriser som tar värdet A eller B med sannolikhet 1/2 $\left\{M_{k}\right\}$

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

Se även

Anteckningar

↑ D. Viswanath. Slumpmässiga Fibonacci-sekvenser och numret 1.13198824... // Mathematics of Computation. - 1999. - Vol. 69 , nr. 231 . - P. 1131-1155 .
↑ JOBB Oliveira, LH De Figueiredo. Intervallberäkning av Viswanaths konstanta // Reliable Computing. - 2002. - Vol. 8 , nr. 2 . — S. 131 .
↑ E. Makover, J. McGowan. Ett elementärt bevis på att slumpmässiga Fibonacci-sekvenser växer exponentiellt // Journal of Number Theory. - 2006. - Vol. 121 . — S. 40 .