Losowy ciąg Fibonacciego

W matematyce losowy ciąg Fibonacciego jest stochastycznym odpowiednikiem ciągu Fibonacciego zdefiniowanego przez relację powtarzalności ${\ Displaystyle f_ {n} = f_ {n-1} \ pm f_ { n-2}}$$,$ gdzie znaki + lub - są wybierane losowo z równym niezależnie dla różnych ${\ displaystyle n}$ . Zgodnie z twierdzeniem Harry'ego Kestena i Hillela Furstenberga , losowe powtarzające się sekwencje tego rodzaju rosną w pewnym tempie wykładniczym , ale trudno jest jednoznacznie obliczyć tempo. W 1999 roku Divakar Viswanath wykazał, że tempo wzrostu losowego ciągu Fibonacciego jest równe 1,1319882487943... (sekwencja A078416 w OEIS ), stałej matematycznej , którą później nazwano stałą Viswanatha.

Opis

Losowy ciąg Fibonacciego to $losowy$ ciąg liczb całkowitych określony liczby dla $2$ naturalnych , gdzie ${\ displaystyle f_ {1}$ , a kolejne wyrazy są wybierane losowo zgodnie z losową relacją powtarzalności

$${\ Displaystyle f_ {n} = {\ rozpocząć {przypadki} f_ {n-1} + f_ {n-2}, & {\ tekst {z prawdopodobieństwem}} {\ tfrac {1} {2}}; \\ f_{n-1}-f_{n-2},&{\text{ z prawdopodobieństwem }}{\tfrac {1}{2}}.\end{przypadki}}}$$

Przypadek losowego ciągu Fibonacciego zaczyna się od 1,1, a wartość każdego kolejnego wyrazu jest określana przez uczciwy rzut monetą: biorąc pod uwagę dwa kolejne elementy ciągu, następnym elementem jest albo ich suma, albo różnica z prawdopodobieństwem 1/ 2, niezależnie od wszystkich dokonanych wcześniej wyborów. Jeśli w losowym ciągu Fibonacciego na każdym kroku wybierany jest znak plus, to odpowiednim przypadkiem jest ciąg Fibonacciego ( F _n ),

$${\ Displaystyle 1,1,2,3,5,8,13,21,34,55, \ ldots.}$$

Jeśli znaki zmieniają się we wzór minus-plus-plus-minus-plus-plus-..., wynikiem jest sekwencja

$${\ Displaystyle 1,1,0,1,1,0,1,1,0,1, \ ldots.}$$

Jednak takie wzorce występują z prawdopodobieństwem zniknięcia w losowym eksperymencie. W typowym przebiegu warunki nie będą przebiegać zgodnie z przewidywalnym wzorcem:

$${\ Displaystyle 1,1,2,3,1, -2, -3, -5, -2, -3, \ ldots {\ tekst {dla znaków}} +, +, +, -, -, + ,-,-,\ldkropki .}$$

Podobnie jak w przypadku deterministycznym, losowy ciąg Fibonacciego można z korzyścią opisać za pomocą macierzy :

$${\ Displaystyle {f_ {n-1} \ wybierz f_ {n}} = {\ rozpocząć {pmatrix} 0&1\\\pm 1&1\end{pmacierz}}{f_{n-2} \wybierz f_{n-1}},}$$

gdzie znaki są wybierane niezależnie dla różnych n z równymi prawdopodobieństwami dla + lub -. Zatem

$${\ Displaystyle {f_ {n-1} \ wybierz f_ {n}} = M_ {n} M_ {n -1}\ldots M_{3}{f_{1} \wybierz f_{2}},}$$

gdzie ( M _k ) jest ciągiem niezależnych identycznie rozłożonych macierzy losowych przyjmujących wartości A lub B z prawdopodobieństwem 1/2:

$${\ Displaystyle A = {\ rozpocząć {pmatrix} 0 i 1 \\ 1 i 1 \ koniec {pmatrix}}, \ quad B = {\ rozpocząć {pmatrix} 0 i 1 \\ -1 i 1 \ koniec {pmatrix}}.}$$

Tempo wzrostu

Johannes Kepler odkrył, że wraz ze wzrostem n stosunek kolejnych wyrazów ciągu Fibonacciego ( fa _n ) zbliża się do złotego podziału . ${\ Displaystyle \ varphi = (1 + {\ sqrt {5 }})/2,}$ czyli około 1,61803. W 1765 roku Leonhard Euler opublikował jednoznaczną formułę, znaną dziś jako formuła Bineta ,

$${\ Displaystyle F_ {n} = {{\ varphi ^ {n} - (-1 / \ varphi) ^ {n}} \ ponad {\ sqrt {5}}}.}$$

Pokazuje, że liczby Fibonacciego rosną w tempie wykładniczym równym złotemu podziałowi φ .

W 1960 roku Hillel Furstenberg i Harry Kesten wykazali, że dla ogólnej klasy iloczynów macierzy losowej norma rośnie jako λ ⁿ , gdzie n jest liczbą czynników. Ich wyniki odnoszą się do szerokiej klasy procesów generujących sekwencje losowe, w tym losowej sekwencji Fibonacciego. W konsekwencji n- ty pierwiastek z | f _n | zbiega się do stałej wartości prawie na pewno lub z prawdopodobieństwem jeden:

$${\ Displaystyle {\ sqrt [{n}] {| f_ {n} |}} \ do 1,1319882487943 \ kropki {\ tekst {jak}} n \ do \ infty.}$$

Wyraźne wyrażenie dla tej stałej zostało znalezione przez Divakara Viswanatha w 1999 roku. Wykorzystuje on wzór Fürstenberga na wykładnik Lapunowa iloczynu macierzy losowej i całkowanie po pewnej mierze fraktalnej na drzewie Sterna-Brocota . Ponadto Viswanath obliczył powyższą wartość liczbową za pomocą zmiennoprzecinkowej potwierdzonej analizą błędu zaokrąglenia .

Uogólnienie

Mark Embree i Nick Trefethen wykazali w 1999 roku, że sekwencja

$${\ Displaystyle f_ {n} = f_ {n-1} \ pm \ beta f_ {n-2}}$$

rozpada się prawie na pewno, jeśli β jest mniejsze niż wartość krytyczna β * ≈ 0,70258 , znana jako stała Embree-Trefethena, a poza tym rośnie prawie na pewno. Pokazali również, że asymptotyczny stosunek σ ( β ) między kolejnymi wyrazami jest prawie na pewno zbieżny dla każdej wartości β . Wykres σ ( β ) wydaje się mieć strukturę fraktalną , z globalnym minimum w pobliżu β _min ≈ 0,36747 w przybliżeniu równym σ ( β _min ) ≈ 0,89517 .

Linki zewnętrzne

• Weisstein, Eric W. „Losowy ciąg Fibonacciego” . MathWorld .
• OEIS A078416 (dziesiętne rozwinięcie stałej Viswanatha)
• Losowe liczby Fibonacciego . Film Numberphile o losowym ciągu Fibonnaciego.