Rastgele Fibonacci dizisi - Random Fibonacci sequence

Matematikte rastgele Fibonacci dizisi bir stokastik analoğudur Fibonacci Dizisi tarafından tanımlanan Tekrarlama ilişkisi f_n = f_n−1 ± f_n−2+ veya - işaretlerinin seçildiği yer rastgele eşit olasılıkla 1/2, bağımsız farklı için n. Teoremi ile Harry Kesten ve Hillel Furstenberg, bu tür rastgele tekrarlayan diziler belirli bir üstel oran, ancak oranı açıkça hesaplamak zordur. 1999 yılında Divakar Viswanath rastgele Fibonacci dizisinin büyüme oranının 1.1319882487943… 'e eşit olduğunu gösterdi (dizi A078416 içinde OEIS ), bir matematik sabiti bu daha sonra adlandırıldı Viswanath sabiti.^[1]^[2]^[3]

Açıklama

Rastgele Fibonacci dizisi, rastgele bir tamsayı dizisidir {f_n}, nerede f₁ = f₂ = 1 ve sonraki terimler rastgele tekrarlama ilişkisinden belirlenir

{ displaystyle f_ {n} = { start {case} f_ {n-1} + f_ {n-2} ve { text {1/2 olasılıkla}}; f_ {n-1} - f_ {n-2} ve { text {1/2 olasılıkla}}. end {durumlar}}}

Rasgele Fibonacci dizisinin bir çalışması 1,1 ile başlar ve sonraki her terimin değeri bir adil para fırlatma: dizinin iki ardışık öğesi verildiğinde, sonraki öğe ya onların toplamıdır ya da önceden yapılan tüm seçimlerden bağımsız olarak 1/2 olasılıkla farklarıdır. Rastgele Fibonacci dizisinde her adımda artı işareti seçilirse, karşılık gelen işlem Fibonacci Dizisi {F_n},

{ displaystyle 1,1,2,3,5,8,13,21,34,55, ldots.}

Eksi-artı-artı-eksi-artı-artı -... biçimindeki işaretler değişiyorsa, sonuç dizidir

{ displaystyle 1,1,0,1,1,0,1,1,0,1, ldots.}

Bununla birlikte, bu tür modeller rastgele bir deneyde kaybolma olasılığı ile ortaya çıkar. Tipik bir çalışmada, terimler tahmin edilebilir bir model izlemeyecektir:

{ displaystyle 1,1,2,3,1, -2, -3, -5, -2, -3, ldots { text {işaretler için}} +, +, +, -, -, + , -, -, ldots.}

Belirleyici duruma benzer şekilde, rastgele Fibonacci dizisi matrisler aracılığıyla karlı bir şekilde tanımlanabilir:

{ displaystyle {f_ {n-1} seç f_ {n}} = { begin {pmatrix} 0 & 1 pm 1 & 1 end {pmatrix}} {f_ {n-2} f_ {n-1'i seç }},}

işaretlerin farklı için bağımsız olarak seçildiği yer n + veya - için eşit olasılıklarla. Böylece

{ displaystyle {f_ {n-1} seçin f_ {n}} = M_ {n} M_ {n-1} ldots M_ {3} {f_ {1} f_ {2}} seçin}

nerede {M_k} bir dizi bağımsız, aynı şekilde dağıtılmış rasgele matrisler değerler almak Bir veya B 1/2 olasılıkla:

{ displaystyle A = { begin {pmatrix} 0 & 1 1 & 1 end {pmatrix}}, quad B = { begin {pmatrix} 0 & 1 - 1 & 1 end {pmatrix}}.}

Büyüme oranı

Johannes Kepler olarak keşfetti n artarsa, Fibonacci dizisinin ardışık terimlerinin oranı {F_n} yaklaşır altın Oran ${ displaystyle varphi = (1 + { sqrt {5}}) / 2,}$ bu yaklaşık 1.61803'tür. 1765'te, Leonhard Euler bugün olarak bilinen açık bir formül yayınladı Binet formülü,

{ displaystyle F_ {n} = {{ varphi ^ {n} - (- 1 / varphi) ^ {n}} { sqrt {5}}} üzerinden.}

Fibonacci sayılarının altın orana eşit üstel bir oranda büyüdüğünü gösterir. φ.

1960 yılında Hillel Furstenberg ve Harry Kesten genel bir rasgele sınıf için matris ürünler, norm olarak büyür λⁿ, nerede n faktörlerin sayısıdır. Sonuçları, rastgele Fibonacci dizisini içeren geniş bir rasgele dizi oluşturma süreçleri sınıfı için geçerlidir. Sonuç olarak, n. kökü |f_n| sabit bir değere yakınsar neredeyse kesin veya olasılıkla bir:

{ displaystyle { sqrt [{n}] {| f_ {n} |}} - 1.1319882487943 nokta { text {as}} n - infty.}

Bu sabit için açık bir ifade 1999'da Divakar Viswanath tarafından bulundu. Bu sabit için Furstenberg'in formülünü kullanır. Lyapunov üssü rastgele bir matris ürünü ve belirli bir fraktal ölçü üzerinde Stern-Brocot ağacı. Dahası, Viswanath yukarıdaki sayısal değeri kullanarak hesapladı. kayan nokta bir analizi ile doğrulanmış aritmetik yuvarlama hatası.

Alakalı iş

Embree-Trefethen sabiti Rastgele dizinin nitel davranışını tekrarlama ilişkisi ile tanımlar

{ displaystyle f_ {n} = f_ {n-1} pm beta f_ {n-2}}

farklı for değerleri için.^[4]

Referanslar

^ Viswanath, D. (1999). "Rastgele Fibonacci dizileri ve 1.13198824 sayısı ..." Hesaplamanın Matematiği. 69 (231): 1131–1155. doi:10.1090 / S0025-5718-99-01145-X.
^ Oliveira, J. O. B .; De Figueiredo, L.H. (2002). "Viswanath Sabitinin Aralık Hesaplaması". Güvenilir Bilgi İşlem. 8 (2): 131. doi:10.1023 / A: 1014702122205.
^ Makover, E .; McGowan, J. (2006). "Rastgele Fibonacci dizilerinin katlanarak büyüdüğünün temel bir kanıtı". Sayılar Teorisi Dergisi. 121: 40. arXiv:matematik.NT / 0510159. doi:10.1016 / j.jnt.2006.01.002.
^ Embree, M.; Trefethen, L.N. (1999). "Rastgele Fibonacci dizilerinin büyümesi ve bozulması" (PDF). Royal Society A: Matematik, Fizik ve Mühendislik Bilimleri Bildirileri. 455 (1987): 2471. Bibcode:1999RSPSA.455.2471T. doi:10.1098 / rspa.1999.0412.

Dış bağlantılar

Weisstein, Eric W. "Rastgele Fibonacci Dizisi". MathWorld.
OEIS dizi A078416 (Viswanath sabitinin ondalık açılımı)
Rastgele Fibonacci Sayıları. Numberphile rastgele Fibonnaci dizisi ile ilgili videosu.

[1] Viswanath, D. (1999). "Rastgele Fibonacci dizileri ve 1.13198824 sayısı ..." Hesaplamanın Matematiği. 69 (231): 1131–1155. doi:10.1090 / S0025-5718-99-01145-X.

[2] Oliveira, J. O. B .; De Figueiredo, L.H. (2002). "Viswanath Sabitinin Aralık Hesaplaması". Güvenilir Bilgi İşlem. 8 (2): 131. doi:10.1023 / A: 1014702122205.

[3] Makover, E .; McGowan, J. (2006). "Rastgele Fibonacci dizilerinin katlanarak büyüdüğünün temel bir kanıtı". Sayılar Teorisi Dergisi. 121: 40. arXiv:matematik.NT / 0510159. doi:10.1016 / j.jnt.2006.01.002.

[4] Embree, M.; Trefethen, L.N. (1999). "Rastgele Fibonacci dizilerinin büyümesi ve bozulması" (PDF). Royal Society A: Matematik, Fizik ve Mühendislik Bilimleri Bildirileri. 455 (1987): 2471. Bibcode:1999RSPSA.455.2471T. doi:10.1098 / rspa.1999.0412.

[1]

[2]

[3]

[4]