Doğrusal Cebir · Markov zinciri

Markov zinciri

Markov zinciri durumlar arasında rastgele geçer. Bir sonraki durumun olasılıkları yalnızca mevcut duruma bağlıdır. Geçiş matrisi P ise yarının dağılımı bugünkü dağılımın sağdan P ile çarpımıdır. Bu işlem tekrarlandığında çoğu zaman πP = π koşulunu sağlayan durağan dağılım π’ye, yani özdeğeri 1 olan bir sol özvektöre yaklaşılır.

Bu görselleştirmede Markov zinciri

Bir Markov zincirinde sonraki durumun olasılıklarını yalnızca mevcut durum belirler. Burada durumlar güneş, bulut ve yağmurdur. Geçiş matrisi PP içindeki ii numaralı satır, bugünkü durum ii ise yarının olasılıklarını verir; her satır bir olasılık vektörüdür. Bugünün dağılımı pp satır vektörüyse yarın pPpP, nn gün sonra pn=p0Pnp_n = p_0 P^n olur. Üç durumda her dağılım üçgende bir noktadır. Her köşede tek bir durum kesindir ve olasılıklar köşelerin ağırlıklarıdır. Koyu noktalar PP matrisinin satırları, mavi nokta başlangıçtır; kırmızı yol p0,p1,p2,…p_0, p_1, p_2, \dots noktalarını birleştirir.

Bir adımda ne olur?

Bir adım her köşeyi ilgili satıra taşır: bugün kesinlikle güneşliyse yarının dağılımı ilk satırdır. Diğer her pp dağılımı köşelerin ağırlıklı ortalamasıdır, dolayısıyla pPpP aynı ağırlıklarla satırların ortalamasıdır. Tüm üçgen satırların gerdiği üçgenin, iki adımda ise P2P^2 satırlarının gerdiği üçgenin içine gider. PP matrisinin bir kuvvetinde bütün girdiler pozitifse bu iç içe üçgenler tek bir noktaya, durağan dağılım π\pi noktasına daralır.

π neden özvektördür ve pₙ ona ne hızla yaklaşır?

Sabit nokta πP=π\pi P = \pi eşitliğini sağlar: π\pi, özdeğeri 1 olan bir sol özvektördür (sütunlarla PTπT=πTP^{\mathsf T}\pi^{\mathsf T} = \pi^{\mathsf T}). p0−πp_0 - \pi farkının bileşenleri toplamı 0’dır. Bu altuzayda PP matrisinin özdeğerleri diğer iki özdeğer λ2,λ3\lambda_2, \lambda_3 olur. Her adım bir özdoğrultudaki vektörü ilgili özdeğerle çarpar. İkisinin de modülü 1’den küçükse pnp_n, π\pi değerine yaklaşır; büyük modül ∣λ2∣|\lambda_2| hızı belirler. Hava zincirinde ∣λ2∣≈0.462|\lambda_2| \approx 0.462 olduğundan, başlangıcın λ2\lambda_2 yönünde bileşeni varsa büyük nn için her adımda uzaklığın yarısından biraz azı kalır. Karmaşık özdeğerlerde yol daralırken döner.

Dağılım ne zaman yakınsamaz?

Döngüde güneş, bulut ve yağmur birbirini izler. Diğer iki özdeğerin modülü 1’dir; π\pi noktasından başlamadıkça pnp_n dönmeyi sürdürür. İki yutucu durumda güneş ve yağmur kalıcıdır. Özdeğer 1 iki katlıdır ve bunların her karışımı sabit kalır; pnp_n yakınsar ancak limit başlangıca bağlıdır. Sonlu bir zincirde pnp_n her başlangıçtan aynı π\pi değerine ancak ve ancak bir tek kapalı iletişim sınıfı varsa ve bu sınıf periyotsuzsa yakınsar. Sınıfın her durumundan diğerlerine gidilebilir ama dışına çıkılamaz. Örneğin bir PmP^m kuvvetinin tüm girdilerinin pozitif olması yeterlidir.

Dikkat edilecekler

  • Hava zincirinin durağan dağılımı, başlangıç ne olursa olsun uzak gelecekteki bir günün hava olasılıklarını verir. Havanın kendisi günden güne değişmeyi sürdürür.
  • Üçten fazla durumda dağılımlar üçgenin daha yüksek boyutlu karşılığı olan bir simpleksi doldurur. Aynı akıl yürütme geçerlidir.

Kontroller

  • Bir matris satırını değiştirmek için koyu noktayı, başlangıcı değiştirmek için mavi noktayı sürükleyin. Ok tuşları odaktaki noktayı 0.01 kaydırır.

İlgili konular