Náhodná Fibonacciho sekvence

Náhodná Fibonacciho posloupnost je stochastickým analogem Fibonacciho posloupnosti , která je definována rekurzivním vzorcem :

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

kde znaménko "+" nebo "-" je vybráno náhodně pro každé n, se stejnou pravděpodobností 1/2. Podle teorému Harryho Kestena a Hillela Furstenberga náhodné rekurentní sekvence tohoto druhu rostou v určité geometrické progresi, ale je obtížné vypočítat rychlost jejich růstu. V roce 1999 Diwakar Viswanath ukázal, že rychlost růstu náhodné Fibonacciho sekvence je 1,1319882487943…, matematická konstanta, která byla později nazvána Wiswanathova konstanta [1] [2] [3] .

Popis

Náhodná Fibonacciho posloupnost je náhodná celočíselná posloupnost , kde následující členy jsou určeny náhodným rekurzivním vzorcem: ${\displaystyle \left\{f_{n}\right\))$ $f_{1}=f_{2}=1$

$f_{n}={\begin{cases}f_{n-1}+f_{n-2},&{\text{s pravděpodobností 1/2))\\f_{n-1}-f_ {n-2},&{\text{s pravděpodobností 1/2}}\end{cases}}$ .

Náhodná Fibonacciho posloupnost tedy začíná čísly 1, 1 a každý následující člen posloupnosti je buď součtem dvou předchozích členů, nebo jejich rozdílem s pravděpodobností 1/2.

Pokud střídáte znaménka: -, +, +, -, +, +, -, +, +, ..., výsledkem bude sekvence:

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

V tomto případě však vliv náhody mizí. Typicky se členové sekvence nebudou řídit předvídatelným vzorem. Příklad náhodné sekvence:

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

pro posloupnost znaků:

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

Náhodnou Fibonacciho sekvenci lze popsat pomocí matic:

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

kde znaménko "+" nebo "-" je vybráno náhodně pro každé n, se stejnou pravděpodobností 1/2. Pak

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

kde je náhodná posloupnost matic, které nabývají hodnoty A nebo B s pravděpodobností 1/2 $\left\{M_{k}\right\}$

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

Viz také

Poznámky

↑ D. Viswanath. Náhodné Fibonacciho posloupnosti a číslo 1,13198824... // Matematika počítání. - 1999. - Sv. 69 , č. 231 . - S. 1131-1155 .
↑ JOB Oliveira, LH De Figueiredo. Intervalový výpočet Viswanathovy konstanty // Spolehlivé počítání. - 2002. - Sv. 8 , č. 2 . — S. 131 .
↑ E. Makover, J. McGowan. Elementární důkaz, že náhodné Fibonacciho sekvence rostou exponenciálně // Journal of Number Theory. - 2006. - Sv. 121 . — S. 40 .