Ireducibilní Markovovy retezce

Reducibilní a ireducibilní jsou dva důležité pojmy v kontextu Markovových řetězců a hrají klíčovou roli v určování jejich dlouhodobého chování.

Markovův řetězec se nazývá ireducibilní, pokud existuje nenulová pravděpodobnost, že systém může přejít z libovolného stavu do libovolného jiného stavu v konečném počtu kroků. Jinými slovy, z každého stavu se dá dostat do každého jiného stavu (ne nutně přímo, ale skrze sérii přechodů). V praxi to znamená, že ireducibilní Markovův řetězec nakonec navštíví každý stav nekonečněkrát, bez ohledu na počáteční stav.

Na druhou stranu, Markovův řetězec se nazývá reducibilní, pokud existují stavy, mezi kterými nemůže dojít k přechodu. Jinými slovy, pokud existuje stav (nebo skupina stavů), do kterého se můžeme dostat z jiných stavů, ale nemůžeme se z něj dostat zpět do ostatních stavů, pak je takový řetězec reducibilní.

Pokud máme matici přechodových pravděpodobností, můžeme určit, zda je Markovův řetězec reducibilní nebo ireducibilní, tím, že zkontrolujeme, zda existuje cesta mezi každými dvěma stavy. Pokud taková cesta existuje, pak je Markovův řetězec ireducibilní. Pokud ne, je reducibilní.

Určení, zda je Markovův řetězec ireducibilní, může mít v praxi mnoho důležitých důsledků, zejména pokud se snažíme předvídat dlouhodobé chování systému, který je tímto řetězcem modelován. 

Pokud je Markovův řetězec ireducibilní, znamená to, že systém nakonec dosáhne jakéhokoli stavu nezávisle na svém počátečním stavu. Tedy z dlouhodobého hlediska, ireducibilní Markovovy řetězce mají tendenci "zapomenout" na svůj počáteční stav. To je důležité například při predikci počasí - bez ohledu na to, jaké je dnes počasí, můžeme se v budoucnu dostat do jakéhokoli jiného stavu počasí.

Vedle toho, ireducibilní Markovovy řetězce konvergují k unikátní stacionární (nebo rovnovážné) distribuci. Tato distribuce nám říká pravděpodobnost, že systém se bude v dlouhodobém horizontu nacházet v daném stavu, bez ohledu na jeho počáteční stav. Tato vlastnost je velmi užitečná, například při modelování burzovních cen - můžeme předpovědět pravděpodobnost, že cena bude v určitém rozmezí, bez ohledu na to, jaká byla cena při našem začátku pozorování.

Pokud je Markovův řetězec naopak reducibilní, znamená to, že existují stavy, které systém nemůže dosáhnout z jiných stavů. Tedy existují "izolované" oblasti v prostoru stavů, kde se systém může zacyklit a nikdy nedosáhne ostatních stavů. To může být problematické například při modelování front v počítačové síti - pokud se síť dostane do stavu, kdy je některá fronta přeplněná a nemůže se z tohoto stavu dostat ven, může to vést k "zaseknutí" sítě.

Příklad 1.

Představte si, že máme server, který obsluhuje požadavky od klientů. Server může zpracovávat jeden požadavek za jednotku času a nové požadavky přicházejí s určitou pravděpodobností. Pokud je server zaneprázdněn zpracováním požadavku a přijde nový požadavek, je tento požadavek přidán do fronty.

Předpokládejme, že kapacita fronty je 3 požadavky a stav systému je dán počtem požadavků ve frontě (0, 1, 2 nebo 3). Každý stav může přejít do následujícího stavu (pokud přijde nový požadavek a fronta není plná) nebo do předchozího stavu (pokud server dokončí zpracování požadavku a fronta není prázdná).

Můžeme vytvořit přechodovou matici Markovova řetězce, která popisuje pravděpodobnosti přechodů mezi stavy. Ta může vypadat např. následovně. 

Teď potřebujeme určit, jestli je Markovovský řetězec ireducibilní. Můžeme to učinit samozřejmě i pohledem. Je zřejmé, že ze stavu 1 (první řádek) můžeme přejít do stavu 2 (druhý řádek), ze stavu 2 do stavu 3 a ze stavu 3 do stavu 4. Zároveň ze stavu 4 můžeme přejít zpět do stavu 3 a tak se můžeme dostat zpět do jakéhokoli stavu. Tedy pro každý pár stavů existuje cesta z jednoho stavu do druhého. Toto je v souladu s definicí silně souvislého grafu, a tedy i s definicí ireducibilního Markovova řetězce. Tedy váš Markovův řetězec je ireducibilní.

Jenže někdy to může být takhle vizuálně posoudit poměrně složité. Budeme to pak dále provádět softwarem. R je super, ale míval jsem s tím trochu problém, tak tohle dělám v Pythonu. Ale já Vám to pak ukážu. Teď se naučíme, jak to určit manuálně. Ukážeme si postup, který vlastně ty programy prováději. Třeba funkce nx.is_strongly_connected() v pythonu to dělá stejně. Nejprve by bylo fajn si udělat graf nebo si prostě vypsat cesty s nenulovou pravděpodobností.

1 -> 1 (protože prvek na pozici 1,1 je nenulový) 
1 -> 2 (protože prvek na pozici 1,2 je nenulový)
2 -> 1 (protože prvek na pozici 2,1 je nenulový)
2 -> 2 (atd. pořád stejně)
2 -> 3 
3 -> 2 
3 -> 3 
3 -> 4
4 -> 3 
4 -> 4 

Při pohledu na výše uvedené hrany můžete vidět následující:

• Ze stavu 1 můžete přejít přímo do stavu 2 (1 -> 2), a odtud do stavu 3 (2 -> 3), a odtud do stavu 4 (3 -> 4). Takže je možné se dostat z 1 do jakéhokoli jiného stavu.
• Ze stavu 2 můžete přejít přímo do stavu 1 (2 -> 1), 3 (2 -> 3), a 4 (2 -> 3 a pak 3 -> 4). Je tedy možné se dostat z 2 do jakéhokoli jiného stavu.
• Ze stavu 3 můžete přejít přímo do stavu 2 (3 -> 2) a 4 (3 -> 4), a z 2 do 1 (2 -> 1). Takže se můžeme dostat z 3 do všech ostatních stavů.
• Ze stavu 4 můžete přejít přímo do stavu 3 (4 -> 3), a odtud do stavu 2 (3 -> 2) a 1 (2 -> 1). Čili je možné se dostat z 4 do jakéhokoli jiného stavu.

Na základě těchto hran v grafu můžeme konstatovat, že je možné se dostat z jakéhokoli stavu do jakéhokoli jiného stavu, pak tento Markovův řetězec je ireducibilní. Jenže u větších matic s celou řadou stavů je tohle šíleně pracné. Existují na to, jak jsem již zmínil, softwarové metody. které si v dalším příkladu ukážeme.