Satunnainen Fibonacci-sekvenssi

Satunnainen Fibonacci - sekvenssi on Fibonacci - sekvenssin stokastinen analogi , joka määritellään rekursiivisella kaavalla :

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

jossa merkki "+" tai "-" valitaan satunnaisesti jokaiselle n:lle yhtä suurella todennäköisyydellä 1/2. Harry Kestenin ja Hillel Furstenbergin lauseen mukaan tällaiset satunnaiset toistuvat sekvenssit kasvavat tietyssä geometrisessa progressiossa, mutta niiden kasvunopeutta on vaikea laskea. Vuonna 1999 Diwakar Viswanath osoitti, että satunnaisen Fibonacci-sekvenssin kasvunopeus on 1,1319882487943…, matemaattinen vakio, jota myöhemmin kutsuttiin Wiswanath-vakioksi [1] [2] [3] .

Kuvaus

Satunnainen Fibonacci-sekvenssi on satunnainen kokonaislukusarja , jossa seuraavat termit määritetään satunnaisella rekursiivisella kaavalla: ${\displaystyle \left\{f_{n}\right\))$ $f_{1}=f_{2}=1$

$f_{n}={\begin{cases}f_{n-1}+f_{n-2},&{\teksti{todennäköisyydellä 1/2))\\f_{n-1}-f_ {n-2},&{\teksti{todennäköisyydellä 1/2}}\loppu{tapaukset}}$ .

Näin ollen satunnainen Fibonacci-sarja alkaa luvuilla 1, 1, ja jokainen sekvenssin seuraava jäsen on joko kahden edellisen jäsenen summa tai niiden erotus todennäköisyydellä 1/2.

Jos vaihdat merkkejä: -, +, +, -, +, +, -, +, +, ..., tuloksena on sarja:

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

Tässä tapauksessa sattuman vaikutus kuitenkin katoaa. Tyypillisesti sekvenssin jäsenet eivät seuraa ennustettavaa kaavaa. Esimerkki satunnaisesta järjestyksestä:

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

merkkijono:

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

Satunnainen Fibonacci-sekvenssi voidaan kuvata matriiseilla:

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

jossa merkki "+" tai "-" valitaan satunnaisesti jokaiselle n:lle yhtä suurella todennäköisyydellä 1/2. Sitten

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

jossa on satunnainen sarja matriiseja, jotka saavat arvon A tai B todennäköisyydellä 1/2 $\left\{M_{k}\right\}$

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

Katso myös

Muistiinpanot

↑ D. Viswanath. Satunnaiset Fibonacci-sekvenssit ja luku 1.13198824... // Laskennan matematiikka. - 1999. - Voi. 69 , ei. 231 . - s. 1131-1155 .
↑ TYÖ Oliveira, LH De Figueiredo. Viswanathin vakion intervallilaskenta // Luotettava laskenta. - 2002. - Voi. 8 , ei. 2 . - s. 131 .
↑ E. Makover, J. McGowan. Perustodiste siitä, että satunnaiset Fibonacci-sekvenssit kasvavat eksponentiaalisesti // Journal of Number Theory. - 2006. - Voi. 121 . - s. 40 .