Secvența Fibonacci aleatorie

Sirul aleatoriu Fibonacci este un analog stocastic al secvenței Fibonacci , care este definită prin formula recursivă :

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

unde semnul „+” sau „-” este ales aleatoriu pentru fiecare n, cu probabilitate egală 1/2. Conform teoremei lui Harry Kesten și Hillel Furstenberg, secvențele recurente aleatorii de acest fel cresc într-o anumită progresie geometrică, dar este dificil de calculat rata de creștere a acestora. În 1999, Diwakar Viswanath a arătat că rata de creștere a unei secvențe aleatoare de Fibonacci este 1,1319882487943..., o constantă matematică care a fost numită mai târziu constanta Wiswanath [1] [2] [3] .

Descriere

Secvența aleatorie de Fibonacci este o secvență de numere întregi aleatoare , în care termenii următori sunt determinați printr-o formulă recursivă aleatorie: $\stanga\{f_{n}\dreapta\}$ $f_{1}=f_{2}=1$

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

Astfel, șirul aleatoriu Fibonacci începe cu numerele 1, 1 și fiecare membru ulterior al șirului este fie suma celor doi membri anteriori, fie diferența lor, cu probabilitate 1/2.

Dacă alternați semnele: -, +, +, -, +, +, -, +, +, ..., atunci rezultatul va fi o secvență:

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

Totuși, în acest caz, influența întâmplării dispare. De obicei, membrii unei secvențe nu vor urma un model previzibil. Exemplu de secvență aleatorie:

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

pentru o secvență de caractere:

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

Secvența aleatorie Fibonacci poate fi descrisă folosind matrici:

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

unde semnul „+” sau „-” este ales aleatoriu pentru fiecare n, cu probabilitate egală 1/2. Apoi

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

unde este o succesiune aleatorie de matrici care iau valoarea A sau B cu probabilitate 1/2 $\stanga\{M_{k}\dreapta\}$

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

Vezi și

Note

↑ D. Viswanath. Secvențe aleatorii Fibonacci și numărul 1,13198824... // Matematica calculului. - 1999. - Vol. 69 , nr. 231 . - P. 1131-1155 .
↑ JOB Oliveira, LH De Figueiredo. Calcul interval al constantei lui Viswanath // Calcul fiabil. - 2002. - Vol. 8 , nr. 2 . — P. 131 .
↑ E. Makover, J. McGowan. O dovadă elementară că secvențele aleatoare ale lui Fibonacci cresc exponențial // Journal of Number Theory. - 2006. - Vol. 121 . — P. 40 .