Stochastická matice

Stochastická 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ř. 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í $Sx=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}$ . 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.

Odkazy

Související články