Stochastická matice - Stochastic matrix

V matematice, stochastické matice je čtvercová matice se používá k popisu přechody na Markov řetězu . Každý z jeho záznamů je nezáporné reálné číslo představující pravděpodobnost . Nazývá se také matice pravděpodobnosti , přechodová matice , substituční matice nebo Markovova matice . Stochastická matice byla poprvé vyvinuta Andrey Markovem na počátku 20. století a našla uplatnění v celé řadě vědeckých oborů, včetně teorie pravděpodobnosti , statistiky, matematických financí a lineární algebry , stejně jako počítačové vědy a populační genetiky . Existuje několik různých definic a typů stochastických matic:

Přímo stochastické matice je skutečný čtvercová matice, kde každý řádek součet činí 1.

Vlevo stochastické matice je skutečný čtvercová matice, kde každý sloupec součtové 1.

Dvojnásobně stochastické matice je čtvercová matice nezáporných reálných čísel se každý řádek a sloupců součet 1.

Ve stejném duchu lze definovat stochastický vektor (nazývaný také vektor pravděpodobnosti ) jako vektor, jehož prvky jsou nezáporná reálná čísla, jejichž součet je 1. Každý řádek pravé stochastické matice (nebo sloupce levé stochastické matice) je tedy stochastický vektor. Běžnou konvencí v matematické literatuře v angličtině je používat řádkové vektory pravděpodobností a pravé stochastické matice spíše než sloupcové vektory pravděpodobností a levé stochastické matice; tento článek dodržuje tuto konvenci.

Dějiny

Andrey Markov v roce 1886

Stochastickou matici vytvořil podél Markovova řetězce Andrey Markov , ruský matematik a profesor na univerzitě v Petrohradě, který na toto téma poprvé publikoval v roce 1906. Jeho původní zamýšlené použití bylo pro lingvistickou analýzu a další matematické předměty, jako je míchání karet , ale oba Markovovy řetězce a matice rychle našly uplatnění v jiných oborech.

Stochastické matice byly dále rozvíjeny učenci jako Andrey Kolmogorov , kteří rozšířili své možnosti tím, že umožnili kontinuální Markovovy procesy. V padesátých letech se v oblastech ekonometrie a teorie obvodů objevily články používající stochastické matice . V šedesátých letech se stochastické matice objevily v ještě širší paletě vědeckých prací, od behaviorální vědy přes geologii až po bytové plánování . Během těchto desetiletí bylo navíc provedeno mnoho matematické práce, aby se zlepšil rozsah použití a funkčnost stochastické matice a Markovianových procesů obecněji.

Od 70. let minulého století našly stochastické matice využití téměř v každé oblasti, která vyžaduje formální analýzu, od strukturální vědy přes lékařskou diagnostiku až po personální management . Navíc stochastické matice našly široké uplatnění v modelování pozemkových změn , obvykle pod pojmem Markovova matice.

Definice a vlastnosti

Stochastic matrice popisuje Markov řetězec $X t$ nad konečným stavového S s mohutnost $S$ .

Pokud je pravděpodobnost přechodu z $i$ do $j$ v jednom časovém kroku $Pr (j | i) = P i, j$ , stochastická matice $P$ je dána použitím $P i, j$ jako $i$ -tého řádku a $j$ -tého sloupcového prvku např.

{\ 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} & \ tečky & P_ {i, j} & \ tečky & P_ {i, S} \\\ vdots & \ vdots & \ ddots & \ vdots & \ ddots & \ vdots \\ P_ { S, 1} & P_ {S, 2} & \ dots & P_ {S, j} & \ dots & P_ {S, S} \\\ end {matrix}} \ right].}

Protože celková pravděpodobnost přechodu ze stavu $i$ do všech ostatních stavů musí být 1,

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

tato matice je tedy správná stochastická matice.

Výše uvedený elementární součet v každém řádku $i$ z $P$ může být výstižněji zapsán jako $P 1 = 1$ , kde $1$ je $S$ -dimenzionální vektor všech jedniček. Pomocí toho je vidět, že součin dvou pravých stochastických matic $P'$ a $P' '$ je také pravou stochastickou: $P' P' ' 1 = P' (P' ' 1) = P' 1 = 1$ . Obecně platí, že $k$ -tá síla $P k$ pravé stochastické matice $P$ je také pravá stochastická. Pravděpodobnost přechodu z $i$ do $j$ ve dvou krocích je pak dána $(i, j)$ -tým prvkem druhé mocniny $P$ :

{\ Displaystyle \ left (P^{2} \ right) _ {i, j}.}

Obecně je pravděpodobnostní přechod z jakéhokoli stavu do jiného stavu v konečném Markovově řetězci daný maticí $P$ v $k$ krocích dán $P k$ .

Počáteční rozdělení pravděpodobnosti stavů určující, kde může být systém zpočátku a s jakými pravděpodobnostmi, je uvedeno jako řádkový vektor .

Stacionární pravděpodobnost vektor $π$ je definována jako distribuce, psaný jako řádkového vektoru, které se nemění za použití přechodové matice; to znamená, že je definováno jako rozdělení pravděpodobnosti na množině ${1,\dots, n},$ což je také řádkový vlastní vektor matice pravděpodobnosti spojený s vlastní hodnotou 1:

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

Lze ukázat, že spektrální poloměr jakékoli stochastické matice je jeden. Podle Gershgorinovy kruhové věty mají všechna vlastní čísla stochastické matice absolutní hodnoty menší nebo rovné jedné. Kromě toho má každá pravá stochastická matice „vlastní“ sloupcový vlastní vektor spojený s vlastní hodnotou 1: vektor $1$ , jehož souřadnice jsou všechny rovny 1 (stačí si uvědomit, že vynásobení řádku $A$ krát $1 se$ rovná součtu záznamů v řádku a proto se rovná 1). Protože jsou levá a pravá vlastní čísla čtvercové matice stejná, má každá stochastická matice přinejmenším řádkový vlastní vektor spojený s vlastní hodnotou 1 a největší absolutní hodnota všech jejích vlastních čísel je také 1. Nakonec je Brouwerova věta o pevných bodech ( aplikováno na kompaktní konvexní množinu všech rozdělení pravděpodobnosti konečné množiny ${1,\dots, n}$ ) znamená, že existuje nějaký vlastní vlastní vektor, který je také stacionárním vektorem pravděpodobnosti.

Na druhé straně Perronova – Frobeniusova věta také zajišťuje, že každá neredukovatelná stochastická matice má takový stacionární vektor a že největší absolutní hodnota vlastního čísla je vždy 1. Tuto větu však nelze použít přímo na takové matice, protože potřebují nebýt neredukovatelný.

Obecně může být takových vektorů několik. Avšak pro matici s přísně kladnými vstupy (nebo obecněji pro neredukovatelnou aperiodickou stochastickou matici) je tento vektor jedinečný a lze jej vypočítat pozorováním, že pro libovolné $i$ máme následující limit,

{\ Displaystyle \ lim _ {k \ rightarrow \ infty} \ left (P^{k} \ right) _ {i, j} = {\ boldsymbol {\ pi}} _ {j},}

kde $π$ $j$ je $j$ -tý prvek řádkového vektoru $π$ . Mimo jiné to říká, že dlouhodobá pravděpodobnost pobytu ve stavu $j$ je nezávislá na počátečním stavu $i$ . Že oba tyto výpočty dávají stejný stacionární vektor, je forma ergodické věty , která obecně platí v celé řadě disipativních dynamických systémů : systém se postupem času vyvíjí do stacionárního stavu .

Intuitivně představuje stochastická matice Markovův řetězec; aplikace stochastické matice na rozdělení pravděpodobnosti přerozdělí pravděpodobnostní hmotnost původního rozdělení při zachování její celkové hmotnosti. Pokud se tento proces aplikuje opakovaně, distribuce konverguje ke stacionární distribuci pro Markovův řetězec.

Příklad: kočka a myš

Předpokládejme, že existuje časovač a řada pěti sousedních polí, přičemž v prvním poli je kočka a v pátém poli je v čase nula myš. Když časovač pokročí, kočka i myš skočí do náhodného sousedního pole. Např. Pokud je kočka ve druhém poli a myš ve čtvrtém, je pravděpodobnost jedné čtvrtiny, že kočka bude v prvním poli a myš v pátém po postupu časovače . Pokud je kočka v prvním poli a myš v pátém, je pravděpodobnost taková, že kočka bude v poli dva a myš bude v poli čtyři po postupu časovače. Kočka sežere myš, pokud oba skončí ve stejné krabici, kdy hra končí. Náhodná veličina K dává počet časových kroků na pobyty myši ve hře.

Markov řetěz , který představuje tuto hru obsahuje pět následujících stavů uvedených kombinací poloh (kočka, myš). Všimněte si toho, že zatímco naivní výčet stavů by uváděl 25 stavů, mnoho z nich je nemožných buď proto, že myš nikdy nemůže mít nižší index než kočka (protože to by znamenalo, že myš obsadila kočičí budku a přežila, aby se kolem ní mohla pohybovat), nebo protože součet těchto dvou indexů bude mít vždy sudou paritu . Kromě toho jsou 3 možné stavy, které vedou ke smrti myši, sloučeny do jednoho:

Stav 1: (1,3)
Stav 2: (1,5)
Stav 3: (2,4)
Stav 4: (3,5)
Stav 5: konec hry: (2,2), (3,3) & (4,4).

Ke znázornění přechodových pravděpodobností tohoto systému používáme stochastickou matici (níže) (řádky a sloupce v této matici jsou indexovány možnými stavy uvedenými výše, přičemž stav před přechodem je stav řádku a stav po přechodu je sloupec). Například počínaje stavem 1 - 1. řádek - není možné, aby systém v tomto stavu zůstal, takže ; Systém také nemůže přejít do stavu 2 - proto, že kočka by zůstal ve stejném poli - tak , a podobným argument pro myši . Přechody do stavů 3 nebo 5 jsou povoleny, a tím . ${\ displaystyle 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}}.}

Dlouhodobé průměry

Bez ohledu na počáteční stav kočka nakonec chytí myš (s pravděpodobností 1) a ke stacionárnímu stavu π = (0,0,0,0,1) se přistupuje jako k limitu. Chcete-li vypočítat dlouhodobý průměr nebo očekávanou hodnotu stochastické proměnné , pro každý stav a čas existuje příspěvek . Přežití může být považováno za binární proměnnou s pro přežívající stav a pro ukončený stav. Státy s nepřispívají k dlouhodobému průměru. ${\ displaystyle Y}$ ${\ displaystyle S_ {j}}$ ${\ displaystyle t_ {k}}$ ${\ Displaystyle Y_ {j, k} \ cdot P (S = S_ {j}, t = t_ {k})}$ ${\ displaystyle Y = 1}$ ${\ displaystyle Y = 0}$ ${\ displaystyle Y = 0}$

Zastoupení fázového typu

Funkce přežití myši. Myš přežije alespoň první časový krok.

Protože stav 5 je absorpční stav, distribuce času do absorpce je rozdělena do diskrétních fázových typů . Předpokládejme, že systém začíná ve stavu 2, reprezentovaném vektorem . Stavy, kde myš zahynula, nepřispívají k průměru přežití, takže stav pět lze ignorovat. Počáteční stavovou a přechodovou matici lze redukovat na, ${\ Displaystyle [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} },}

a

{\ Displaystyle (IT)^{-1} {\ boldsymbol {1}} = {\ begin {bmatrix} 2,75 \\ 4,5 \\ 3,5 \\ 2,75 \ end {bmatrix}},}

kde je matice identity a představuje sloupcovou matici všech, která funguje jako součet stavů. ${\ displaystyle I}$ ${\ displaystyle \ mathbf {1}}$

Protože každý stav je obsazen na jeden krok času, očekávaný čas přežití myši je jen součtem pravděpodobnosti obsazení všech přežívajících stavů a kroků v čase,

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

Momenty vyššího řádu jsou dány pomocí

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

Viz také

Hustotní matice
Markovské jádro , ekvivalent stochastické matice v prostoru spojitého stavu
Maticová diferenční rovnice
Modely evoluce DNA
Muirheadova nerovnost
Pravděpodobnostní automat

Languages

In other projects