Periodicita a ergodicita

Periodicita je důležitý koncept v teorii Markovových řetězců, který nám pomáhá pochopit, jak se systém chová v čase. Stav je periodický, pokud se Markovův řetězec vrátí do tohoto stavu v pravidelných intervalech. Konkrétně řečeno, stav i má periodu k, pokud jakákoli sekvence přechodů vedoucích zpět do stavu i trvá množství kroků, které je násobkem k.

Periodicita nám může pomoci předpovědět, kdy se systém vrátí do určitého stavu. Například, pokud má stav periodu 3, víme, že po vrácení se do tohoto stavu se systém vrátí zpět do tohoto stavu přesně za 3 kroky.

Příkladem může být systém, kde máme tři stavy A, B a C, a pravděpodobnosti přechodu jsou takové, že A vždy přechází na B, B vždy přechází na C a C vždy přechází na A. Potom má každý stav periodu 3, protože se systém vrátí do jakéhokoli stavu po třech krocích.

Nicméně v mnoha reálných případech je aperiodicita preferovaná, protože umožňuje systému, aby se volněji pohyboval mezi stavy, což umožňuje dosáhnout stacionárního rozdělení rychleji. Pokud je systém periodický, může to znamenat, že jeho dlouhodobé chování je pravidelné a předvídatelné, což nemusí být vždy žádoucí.

Příklad výpočtu periodicity:

Představte si jednoduchý Markovův řetězec se třemi stavy: {A, B, C}. Předpokládejme, že pravděpodobnosti přechodu jsou následující:

A -> B: 1, B -> C: 1, C -> A: 1,

A potom zpět na A. Zde můžeme vidět, že perioda pro každý stav je 3, protože systém se vrací do stejného stavu každé tři kroky. A -> B -> C -> A.

Z toho plyne, že periodicitu lze považovat za formu "cyklického" chování v Markovově řetězci. Pamatujte, že ne všechny Markovovy řetězce mají periodické stavy. Například, pokud existuje pravděpodobnost zůstat ve stejném stavu (tj. pravděpodobnost přechodu je menší než 1), bude tento stav aperiodický, protože existuje několik možných cest zpět do tohoto stavu s různou délkou.

V kontextu Markovových řetězců je perioda definována pro jednotlivé stavy, nikoliv pro celý systém jako takový. Výpočet periody stavu spočívá v určení NSD (největšího společného dělitele) všech délek cyklů, které začínají a končí v daném stavu. Pokud má nějaký stav periodu k, pak to znamená, že jakmile se systém ocitne v tomto stavu, bude se do něj vracet každých k kroků, za předpokladu, že se systém pohybuje v cyklech. To je důvod, proč může mít každý stav svou vlastní periodu.

Například, pokud vezmeme v úvahu nějaké stavy M, O, P, třeba jako oddělení v obchodě, můžeme sledovat různé cesty, které zákazníci mohou absolvovat a které začínají a končí v oddělení O. Například O-M-O, O-M-P-O, O-P-O atd. NSD délek těchto cyklů pak určuje periodu stavu O. Pokud existuje nějaká cesta, která se do daného stavu vrací v každém kroku (jako například O-O-O...), pak je perioda tohoto stavu 1 a říkáme, že stav je aperiodický. To znamená, že zákazník se do daného oddělení může vrátit v libovolném časovém kroku, a ne pouze po určitém počtu kroků.

Ve skutečnosti to znamená, že pokud systém někdy navštíví daný stav a následně se začne pohybovat v cyklech (tj. se opakujícími trajektoriemi), pak se do tohoto stavu vrátí po počtu kroků, který je násobkem periody tohoto stavu.

To však neznamená, že systém se nutně musí pohybovat v cyklech. Není zaručeno, že se systém "zacyklí". Je to pouze charakteristika toho, co by se stalo, kdyby systém začal cyklicky opakovat své trajektorie.

Takže pokud má stav periodu 2, neznamená to, že kdykoliv navštívíme položku, musíme se vrátit zpět po dvou krocích. To pouze znamená, že pokud se zákazník začne pohybovat v cyklech, můžeme očekávat, že se vrátí do oddělení O každé dvě kroky.

Poslední poznámku je, že čísla - velikosti pravděpodobností v přechodové matici nijak nesouvisí s periodou. Velikosti pravděpodobností v přechodové matici ovlivňují to, jaký je pravděpodobný průběh markovova řetězce (tj. jaké stavy budou navštěvovány a jak často), ale nerozhodují o periodicitě stavů.

Představme si, že systém má 6 stavů s přechodovou maticí:

Nyní, abychom našli periodu jednotlivých stavů, musíme sledovat všechny možné cykly, které může systém podstoupit, začínající a končící ve stejném stavu.

Pro stav A můžeme mít následující cykly: A-B-D-C-D-B-A (6 kroků), A-B-D-E-F-A (5 kroků)
Pro stav B: B-D-C-D-B (4 kroky), B-D-E-F-A-B (5 kroků), B-A-B (1 krok)
Pro stav C: C-D-B-A-B-D-C (6 kroků), C-D-B-D-C (3 kroky)
Pro stav D: D-C-D (2 kroky), D-B-A-B-D (4 kroky)
Pro stav E: E-F-A-B-D-C-D-B-A-B-D-E (12 kroků), E-F-A-B-D-E (5 kroků)
Pro stav F: F-A-B-D-C-D-B-A-F (8 kroků), F-A-B-D-E-F (5 kroků)

Když máme všechny tyto délky cyklů, musíme najít jejich největšího společného dělitele (největší číslo, které všechny tyto délky dělí beze zbytku), což je perioda daného stavu.

A: gcd(6,5) = 1
B: gcd(4,5,1) = 1
C: gcd(6,3) = 3
D: gcd(2,4) = 2
E: gcd(12,5) = 1
F: gcd(8,5) = 1

Z tohoto můžeme vidět, že stavy A, B, E a F mají periodu 1 (jsou aperiodické), zatímco stav C má periodu 3 a stav D periodu 2 (jsou periodické). Samozřejmě to ale nebudeme nikdy počítat ručně. Nejsme ve škole. Tolhe za nás spočítá statistický software.

Příklad 1.

Mějme robustní matici 10 na 10.

Rádi bychom určili, jestli se v ní nacházejí nějaké periody. Takhle od oka to je problematické, museli bychom si vypisovat všechny cesty. V tomto případě by to sice nebylo složité, ale není nic jednoduššího, než za nás nechat pracovat software.

Pokračování brzy:)