Stokastik matris - Stochastic matrix

Matematikte, bir stokastik matris , bir Markov zincirinin geçişlerini tanımlamak için kullanılan bir kare matristir . Girişlerinin her biri, bir olasılığı temsil eden negatif olmayan bir gerçek sayıdır . Ayrıca olasılık matrisi , geçiş matrisi , ikame matrisi veya Markov matrisi olarak da adlandırılır . Stokastik matris ilk tarafından geliştirilen Andrey Markov , 20. yüzyılın başında ve dahil bilimsel alanlarda, geniş bir yelpazede boyunca kullanım alanı bulmuş olan olasılık teorisi , istatistik, matematiksel finans ve lineer cebir , hem de bilgisayar bilimi ve nüfus genetiği . Stokastik matrislerin birkaç farklı tanımı ve türü vardır:

Bir sağ stokastik matris 1'e toplayarak her satırın, gerçek kare matristir.

Bir sol stokastik matris 1'e toplanmasıyla her bir sütun ile gerçek kare bir matristir.

Bir çift stokastik matris her satır ve sütun 1 toplanmasıyla ile negatif olmayan bir sayı kare matrisidir.

Aynı şekilde, bir stokastik vektör ( olasılık vektörü olarak da adlandırılır ) öğeleri toplamı 1 olan negatif olmayan gerçek sayılar olan bir vektör olarak tanımlanabilir. stokastik bir vektör. İngiliz dili matematik literatüründe yaygın bir kural , olasılıkların sütun vektörleri ve sol stokastik matrisler yerine olasılıkların satır vektörlerini ve sağ stokastik matrisleri kullanmaktır; bu makale bu sözleşmeyi takip ediyor.

Tarih

1886 yılında Andrey Markov

Stokastik matris tarafından Markov zinciri yanında geliştirilen Andrey Markov , bir Rus matematikçi de ve profesörü Petersburg Üniversitesi dilsel analiz ve benzeri diğer matematiksel konularda vardı ilk 1906 Onun ilk amaçlanan kullanımları için konuyla ilgili yayınlanan kart karıştırması , ancak her iki Markov zincirleri ve matrisleri diğer alanlarda hızla kullanım buldu.

Stokastik matrisler, sürekli zamanlı Markov süreçlerine izin vererek olanaklarını genişleten Andrey Kolmogorov gibi bilim adamları tarafından daha da geliştirildi . 1950'lerde, ekonometri ve devre teorisi alanlarında stokastik matrisleri kullanan makaleler ortaya çıktı . 1960'larda, stokastik matrisler, davranış biliminden jeolojiye ve yerleşim planlamasına kadar çok daha geniş bir bilimsel çalışma yelpazesinde ortaya çıktı . Buna ek olarak, bu on yıllar boyunca, stokastik matrisin ve daha genel olarak Markovian süreçlerinin kullanım alanlarını ve işlevselliğini geliştirmek için çok sayıda matematiksel çalışma yapıldı .

Günümüze 1970'lerden itibaren, stokastik matrisler gelen, biçimsel analiz gerektiren hemen her alanda kullanım bulmuşlardır yapısal bilim için tıbbi tanı için personel yönetimi . Ek olarak, stokastik matrisler, arazi değişimi modellemesinde , genellikle Markov matrisi terimi altında geniş bir kullanım alanı bulmuştur .

Tanım ve özellikler

Rastgele bir matris açıklanmaktadır Markov zinciri X _t aşkın bir sonlu durum uzay S ile önem düzeyi S .

Eğer olasılık geçişin i için j bir kez adımda olduğu P ( j | i ) = p _{i , j} , stokastik matris P kullanılarak elde edilir P _{i , j} olarak i -inci satır ve j -inci kolon elemanı , Örneğin,

${\displaystyle P=\left[{\begin{matrix}P_{1,1}&P_{1,2}&\dots &P_{1,j}&\dots &P_{1,S}\\P_{2, 1}&P_{2,2}&\dots &P_{2,j}&\dots &P_{2,S}\\\vdots &\vdots &\ddots &\vdots &\ddots &\vdots \\P_{i ,1}&P_{i,2}&\dots &P_{i,j}&\dots &P_{i,S}\\\vdots &\vdots &\ddots &\vdots &\ddots &\vdots \\P_{ S,1}&P_{S,2}&\dots &P_{S,j}&\dots &P_{S,S}\\\end{matris}}\sağ].}$

Bir i durumundan diğer tüm durumlara geçiş olasılığının toplamı 1 olması gerektiğinden,

${\displaystyle \sum _{j=1}^{S}P_{i,j}=1;\,}$

dolayısıyla bu matris bir doğru stokastik matristir.

Her bir satır boyunca yukarıda elementwise toplamı i arasında P daha öz olarak yazılabilir P 1 = 1 , 1 olduğu S tüm olanların boyutlu vektör. Bunu kullanarak, iki sağ stokastik matrisin P ′ ve P ′′ çarpımının da sağ stokastik olduğu görülebilir : P ′ P ′′ 1 = P ′ ( P ′′ 1 ) = P ′ 1 = 1 . Genel olarak, bir sağ stokastik matris P'nin k -inci kuvveti P ^k aynı zamanda sağ stokastiktir. Geçiş olasılığı i için j iki adımda aşağıdaki formülle verilir: ( i , j ) karesinin inci elemanının P :

${\displaystyle \sol(P^{2}\sağ)_{i,j}.}$

Genel olarak, bir matris tarafından verilen sonlu Markov zincirinin başka bir duruma herhangi bir durumdan olacak olasılığı geçiş P içinde k adımları ile verilir p ^k .

Sistemin başlangıçta nerede olabileceğini ve hangi olasılıklarla olabileceğini belirten durumların bir başlangıç ​​olasılık dağılımı, bir satır vektörü olarak verilir .

Bir sabit olasılık vektörü π geçiş matrisinde uygulaması altında değişmeyen bir sıra vektörü olarak yazılmış bir dağılım olarak tanımlanır; yani, aynı zamanda olasılık matrisinin bir satır özvektörü olan {1, …, n } kümesindeki bir olasılık dağılımı olarak tanımlanır ve özdeğer 1 ile ilişkilendirilir :

${\displaystyle {\boldsymbol {\pi }}P={\boldsymbol {\pi }}.}$

Herhangi bir stokastik matrisin spektral yarıçapının bir olduğu gösterilebilir . Tarafından Gershgorin daire teoremi , stokastik matrisin özdeğerler tüm az mutlak değerlere sahiptir veya birine eşittir. Vektör: Ayrıca, her doğru stokastik matris özvektörü Özdeğer 1 ilişkili bir "bariz" sütunu vardır 1 , koordinatları hepsi 1 (eşittir sadece bir sıra çarparak olduğunu gözlemlemek, A zamanlarda 1 sıranın girişlerin toplamına eşittir ve dolayısıyla, 1'e eşittir. Bir kare matrisin sol ve sağ özdeğerleri aynı olduğundan, her stokastik matrisin en azından özdeğer 1 ile ilişkili bir satır özvektörü vardır ve tüm özdeğerlerinin en büyük mutlak değeri de 1'dir. Son olarak, Brouwer Sabit Nokta Teoremi ( {1, …, n } ) sonlu kümesinin tüm olasılık dağılımlarının kompakt dışbükey kümesine uygulanması , aynı zamanda durağan bir olasılık vektörü olan bir sol özvektör olduğunu ima eder.

Öte yandan, Perron-Frobenius teoremi , indirgenemez her stokastik matrisin böyle durağan bir vektöre sahip olmasını ve bir özdeğerin en büyük mutlak değerinin her zaman 1 olmasını sağlar. indirgenemez olmasın.

Genel olarak, bu tür birkaç vektör olabilir. Bununla birlikte, kesinlikle pozitif girişleri olan bir matris için (veya daha genel olarak, indirgenemez bir periyodik olmayan stokastik matris için), bu vektör benzersizdir ve herhangi bir i için aşağıdaki limite sahip olduğumuzu gözlemleyerek hesaplanabilir ,

${\displaystyle \lim _{k\rightarrow \infty }\sol(P^{k}\sağ)_{i,j}={\boldsymbol {\pi }}_{j},}$

burada π _j , π satır vektörünün j -inci öğesidir . Diğer şeylerin yanı sıra, bu, uzun vadeli bir j durumunda olma olasılığının , ilk i durumundan bağımsız olduğunu söyler . Bu hesaplamaların her ikisinin de aynı durağan vektörü vermesi , genellikle çok çeşitli enerji tüketen dinamik sistemlerde doğru olan ergodik bir teoremin bir biçimidir : sistem zamanla durağan bir duruma dönüşür .

Sezgisel olarak, bir stokastik matris bir Markov zincirini temsil eder; olasılık dağılımına stokastik matrisin uygulanması, toplam kütlesini korurken orijinal dağılımın olasılık kütlesini yeniden dağıtır. Bu işlem tekrar tekrar uygulanırsa, dağılım Markov zinciri için durağan bir dağılıma yakınsar.

Örnek: kedi ve fare

Sıfır zamanında birinci kutuda bir kedi ve beşinci kutuda bir fare bulunan bir zamanlayıcı ve bitişik beş kutudan oluşan bir sıra olduğunu varsayalım. Zamanlayıcı ilerlediğinde hem kedi hem de fare rastgele bitişik kutuya atlar . Örneğin, kedi ikinci kutuda ve fare dördüncü kutudaysa, zamanlayıcı ilerledikten sonra kedinin birinci kutuda ve farenin beşinci kutuda olma olasılığı dörtte birdir . Kedi birinci kutuda ve fare beşinci kutudaysa, zamanlayıcı ilerledikten sonra kedinin ikinci kutuda ve farenin dördüncü kutuda olma olasılığı birdir. Her ikisi de aynı kutuya düşerse kedi fareyi yer ve oyun o anda biter. Rasgele değişken K zaman sayısı oyununda fare kalır adımları verir.

Markov zinciri bu oyunu temsil pozisyonların birleşimi (kedi, fare) ile belirtilen aşağıdaki beş durumlarını içerir. Saf bir durum sayımı 25 durumu listeleyecek olsa da, birçoğunun ya farenin asla kediden daha düşük bir indekse sahip olamayacağı (bu, farenin kedinin kutusunu işgal ettiği ve onu geçmek için hayatta kaldığı anlamına gelir) veya bunun nedeninin imkansız olduğuna dikkat edin. iki indeksin toplamı her zaman çift pariteye sahip olacaktır . Ek olarak, farenin ölümüne yol açan 3 olası durum tek bir durumda birleştirilir:

• Durum 1: (1,3)
• Durum 2: (1,5)
• Durum 3: (2,4)
• Durum 4: (3,5)
• Durum 5: oyun bitti: (2,2), (3,3) ve (4,4).

Bu sistemin geçiş olasılıklarını temsil etmek için (aşağıda) bir stokastik matris kullanıyoruz ( bu matristeki satırlar ve sütunlar, geçiş öncesi durum satır ve geçiş sonrası durum olarak yukarıda listelenen olası durumlar tarafından indekslenir. kolon). Örneğin durum 1 – 1. satırdan başlayarak sistemin bu durumda kalması imkansızdır, yani ; sistem ayrıca durum 2'ye geçemez – çünkü kedi aynı kutuda kalırdı – bu nedenle ve fare için benzer bir argümanla, . Durum 3 veya 5'e geçişlere izin verilir ve bu nedenle . ${\görüntüleme stili P}$${\displaystyle P_{11}=0}$${\displaystyle P_{12}=0}$${\displaystyle P_{14}=0}$${\displaystyle P_{13},P_{15}\neq 0}$

${\displaystyle P={\begin{bmatrix}0&0&1/2&0&1/2\\0&0&1&0&0\\1/4&1/4&0&1/4&1/4\\0&0&1/2&0&1/2\\0&0&0&0&1\end{bmatrix}}.}$

Uzun vadeli ortalamalar

Başlangıç ​​durumu ne olursa olsun, kedi sonunda fareyi yakalayacaktır (1 olasılıkla) ve durağan bir duruma π = (0,0,0,0,1) limit olarak yaklaşılır. Stokastik bir değişkenin uzun vadeli ortalamasını veya beklenen değerini hesaplamak için , her durum ve zaman için bir katkı vardır . Hayatta kalma, hayatta kalan bir durum ve sonlandırılan durum için ikili bir değişken olarak ele alınabilir . olan eyaletler uzun vadeli ortalamaya katkıda bulunmaz. ${\görüntüleme stili Y}$${\ Displaystyle S_{j}}$${\görüntüleme stili t_{k}}$${\displaystyle Y_{j,k}\cdot P(S=S_{j},t=t_{k})}$${\görüntüleme stili Y=1}$${\görüntüleme stili Y=0}$${\görüntüleme stili Y=0}$

Faz tipi gösterimi

Farenin hayatta kalma işlevi. Fare en azından ilk zaman adımında hayatta kalacaktır.

Durum 5 bir soğurucu durum olduğundan, soğurulmaya kadar geçen sürenin dağılımı ayrık faz tipi dağıtılır . Sistemin vektör ile temsil edilen durum 2'de başladığını varsayalım . Farenin yok olduğu durumlar, hayatta kalma ortalamasına katkıda bulunmaz, bu nedenle durum beş göz ardı edilebilir. Başlangıç ​​durumu ve geçiş matrisi şuna indirgenebilir, ${\görüntüleme stili [0,1,0,0,0]}$

${\displaystyle {\boldsymbol {\tau }}=[0,1,0,0],\qquad T={\begin{bmatrix}0&0&{\frac {1}{2}}&0\\0&0&1&0\\{ \frac {1}{4}}&{\frac {1}{4}}&0&{\frac {1}{4}}\\0&0&{\frac {1}{2}}&0\end{bmatrix} },}$

ve

${\displaystyle (BT)^{-1}{\boldsymbol {1}}={\begin{bmatrix}2.75\\4.5\\3.5\\2.75\end{bmatrix}},}$

burada bir birim matris ve durumları uzerinden bir toplam olarak hareket hepsinin bir kolon matrisini temsil eder. ${\görüntüleme stili I}$${\görüntüleme stili \mathbf {1} }$

Her durum bir zaman adımı için işgal edildiğinden, farenin hayatta kalması için beklenen süre, hayatta kalan tüm durumlar üzerindeki işgal olasılığının ve zaman adımlarının toplamıdır ,

${\displaystyle E[K]={\boldsymbol {\tau }}\left(I+T+T^{2}+\cdots \right){\boldsymbol {1}}={\boldsymbol {\tau }} (BT)^{-1}{\boldsymbol {1}}=4.5.}$

Daha yüksek dereceli anlar tarafından verilir

${\displaystyle E[K(K-1)\dots (K-n+1)]=n!{\boldsymbol {\tau }}(I-{T})^{-n}{T}^{n -1}\mathbf {1} \,.}$

Ayrıca bakınız

• yoğunluk matrisi
• Markov çekirdeği , sürekli bir durum uzayı üzerinde stokastik bir matrisin eşdeğeri
• Matris farkı denklemi
• DNA evrimi modelleri
• Muirhead eşitsizliği
• olasılıklı otomat

Referanslar