Cesko.wiki Stochastická matice
Author
Albert FloresStochastická matice je čtvercová nezáporná matice jejíž řádkové součty jsou rovny jedné, tedy
S = \left[\begin{array}{ccccc} s_{1,1}&s_{1,2}&s_{1,3}&\cdots&s_{1,n}\\ s_{2,1}&s_{2,2}&s_{2,3}&\cdots&s_{2,n}\\ s_{3,1}&s_{3,2}&s_{3,3}&\cdots&s_{3,n}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ s_{n,1}&s_{n,2}&s_{n,3}&\cdots&s_{n,n} \end{array}\right]\in\mathbb{R}^{n\times n},
pro kterou platí
\forall j=1,2,3,\ldots,n:\qquad \sum_{k=1}^n s_{j,k} = \sum_{k=1}^n |s_{j,k}| = 1.
(Nezaměňovat se zcela nesouvisejícím pojmem náhodná matice.)
Terminologie
Stochastickou matici někdy nazýváme též pravou stochastickou maticí přičemž transpozici takové matice, tedy čtvercovou nezápornou matici se sloupcovými součty rovnými jedné, pak nazýváme levou stochastickou maticí.
Matici, která je zároveň pravou i levou stochastickou maticí, nazýváme dvojitě stochastická matice.
Souvislost s Markovovými řetězci
Stochastické matice jsou přirozené maticové reprezentanty Markovových řetězců, neboť j-tý řádek (v případě pravé stochastické matice) můžeme ztotožnit s j-tým stavem nějakého systém a prvky v tomto řádku s pravděpodobnostmi přechodu do jiných stavů. Tedy s_{j,k} je pravděpodobnost, že systém přejde ze stavu j do stavu k.
Typickým představitelem takového řetězce a jednou z nejznámějších aplikací stochastických matic je tzv. PageRank algoritmus ohodnocující např. +more relevanci webových stránek pro vyhledávač Google.
Základní spektrální vlastnosti
Stochastická matice má vlastní číslo \lambda=1 spektrální poloměr \sigma{}(S)=1, jednotkové vlastní číslo je tedy největším vlastním číslem. Odpovídá mu pravý vlastní vektor
x=\left[\begin{array}{c} 1\\1\\1\\\vdots\\1\end{array} \right].
Zřejmě totiž platí S x = x\,1.
V analýze chování Markovových řetězců je pak klíčový levý vlastní vektor y odpovídající vlastnímu číslu \lambda=1, tj. vektor splňující y^T S = 1\,y^T . +more Ten je vždy možné zvolit kladný, za jistých dodatečných předpokladů na matici S (ireducibilita, imprimitivita) je přitom dán (až na násobek číslem) jednoznačně.
Např. v PageRank algoritmu jsou složky tohoto již jednoznačně daného vhodně normovaného levého vlastního vektoru y právě rovny PageRankům jednotlivých stránek.