Markovovské řetězce - základní charakteristika a vlastnosti

Markovovy řetězce jsou nástrojem používaným v teorii pravděpodobnosti k modelování různých typů náhodných procesů. Mají široké uplatnění v mnoha oblastech, včetně statistiky, ekonomie, sociologie, fyziky, informatiky a dalších.

Základní myšlenkou Markovových řetězců je to, co se nazývá "Markovova vlastnost" nebo "bezpaměťová vlastnost". Tato vlastnost říká, že budoucí stav náhodného procesu závisí pouze na současném stavu a je nezávislý na předchozí historii. Jinými slovy, vše, co potřebujeme vědět k předpovědi budoucnosti, je aktuální stav, minulé události nemají žádný vliv.

Když hodíte kostkou, výsledek každého hodu je náhodný a nezávisí na tom, co se stalo při předchozích hodech. To je příklad Markovova procesu. Formálněji, Markovův řetězec je sekvence náhodných proměnných {X0, X1, X2,...}, kde každá proměnná Xn představuje stav systému v čase n. Pro každé n a pro jakýkoli výběr stavů i0, i1,..., in, in+1, máme:

P(Xn+1 = in+1 | X0 = i0, X1 = i1, ..., Xn = in) = P(Xn+1 = in+1 | Xn = in),

což je matematická formulace vlastnosti Markova.

Přechodová matice

Důležitým pojmem v Markovových řetězcích je přechodová matice. Tato matice, kterou značíme P, obsahuje pravděpodobnosti přechodů mezi jednotlivými stavy. Pokud máme tři stavy (1, 2, 3), pak prvek Pij v přechodové matici P je pravděpodobnost přechodu ze stavu i do stavu j v jednom kroku.

V pochopení Markovových řetězců je klíčový koncept přechodových pravděpodobností. Přechodové pravděpodobnosti popisují, jak pravděpodobné je, že proces se přesune z jednoho stavu do druhého. Tyto pravděpodobnosti jsou základním kamenem dynamiky Markovových řetězců a jsou zaznamenány v takzvané přechodové matici.

Představme si jednoduchý příklad. Máme počasí, které se může nacházet v jednom ze tří stavů: slunečno, zamračeno nebo deštivé. Na základě dlouhodobých meteorologických dat víme, jak pravděpodobné je, že se počasí změní z jednoho stavu na druhý za jeden den. Toto jsou naše přechodové pravděpodobnosti.

Tyto pravděpodobnosti zapisujeme do matice, kterou nazýváme přechodová matice. Každý řádek v matici představuje počáteční stav a každý sloupec představuje konečný stav. Prvek na pozici (i, j) v matici je pravděpodobnost, že systém přejde ze stavu i do stavu j v jednom kroku. V našem příkladu by přechodová matice mohla vypadat nějak takto.

Tato matice nám říká, například, že pokud je dnes slunečno, je pravděpodobnost, že zítra bude také slunečno, 0.6. Je pravděpodobnost 0.3, že bude zamračeno, a pravděpodobnost 0.1, že bude deštivé.

V přechodové matici musí součet pravděpodobností v každém řádku být roven 1, protože popisují všechny možné stavy, do kterých může systém přejít.

V kontextu Markovových řetězců hovoříme často také o jednokrokových a vícekrokových přechodových pravděpodobnostech. Jednokroková pravděpodobnost je pravděpodobnost přechodu ze stavu i do stavu j v jednom kroku (jako v našem příkladu počasí). Vícekroková pravděpodobnost je pravděpodobnost přechodu ze stavu i do stavu j v n krocích. Tyto pravděpodobnosti můžeme vypočítat pomocí přechodové matice a metody zvané "exponenciál matice". Do toho bych se tu teď ale nepouštěl.

Stavový prostor

Stavový prostor je základní koncept Markovových řetězců. Definuje možné stavy, ve kterých se může systém nacházet. Jednoduše řečeno, je to množina všech možných stavů, které může Markovův řetězec přijmout.

Pro konkrétní příklady bychom mohli uvažovat o Markovově řetězci, který modeluje počasí. Stavový prostor v tomto případě by mohl zahrnovat stavy jako "slunečno", "zataženo", "déšť" atd.

Pokud bychom měli Markovův řetězec modelující stav počítačového serveru, stavový prostor by mohl zahrnovat stavy jako "volný", "zaneprázdněný" a "vypnutý".

Stavový prostor může být konečný nebo nekonečný. Konečný stavový prostor má pevný počet stavů. Například, stav počasí (viz výše) může být popsán konečným počtem stavů. Nekonečný stavový prostor na druhou stranu má nekonečný počet stavů, ačkoli každý jednotlivý stav je stále jednoznačně definován. Příkladem může být model popisující pohyb částic, kde stav může být definován jako poloha a rychlost částice.

Další důležitou vlastností stavového prostoru je skutečnost, zda jsou stavy přístupné z jiných stavů. Některé stavy mohou být "absorpční", což znamená, že pokud do nich systém jednou vstoupí, už z nich nemůže vyjít. Například, v modelu životního cyklu organismu by mohl být "stav smrti" absorpčním stavem.

V kontextu matematické notace, stavový prostor je často označován pomocí S nebo Ω. Pokud je stavový prostor konečný, můžeme jej zapsat jako S = {s1, s2, ..., sn}, kde s1, s2, ..., sn jsou jednotlivé stavy.

Důležité je si uvědomit, že stavový prostor je definován na základě konkrétního problému, který se snažíme modelovat, a může se velmi lišit v závislosti na tomto problému. Výběr správného stavového prostoru je často klíčovým krokem při vytváření účinného modelu pomocí Markovových řetězců.

Markovova vlastnost

Markovova vlastnost, někdy nazývaná také "bezpaměťovostí", je klíčovým rysom Markovových řetězců. Ve své nejjednodušší formě, Markovova vlastnost říká, že budoucí chování Markovova řetězce závisí pouze na jeho současném stavu a je nezávislé na tom, jak se do tohoto stavu dostal.

Formálně, Markovův řetězec splňuje Markovovu vlastnost, pokud pro všechny stavy s1, s2, ..., sn a t v sekvenci platí:

P(St+1 = s | St = s1, St-1 = s2, ..., S1 = sn) = P(St+1 = s | St = s1)

Tedy pravděpodobnost, že systém se přesune do stavu s v následujícím kroku, závisí pouze na současném stavu St a nezávisí na předchozí historii.

Tato vlastnost je klíčová pro praktickou aplikaci Markovových řetězců. Díky ní se Markovovy řetězce staly populárními v mnoha oblastech, včetně statistiky, ekonomie, informatiky, fyziky a mnoha dalších.

Například, pokud byste chtěli modelovat chování zákazníků na webové stránce pomocí Markovova řetězce, můžete předpokládat, že stránka, na kterou zákazník přejde dále, závisí pouze na stránce, na které se právě nachází, a ne na tom, jak se na tuto stránku dostal. Toto je velmi silné zjednodušení, ale může být dostatečné pro některé účely.

Je důležité si uvědomit, že ačkoli Markovova vlastnost je silným zjednodušením, nemusí být vždy přesná. Existují systémy, které nevykazují Markovovy vlastnosti, a pro modelování takových systémů může být třeba použít složitější metody. V těchto případech Markovovy řetězce poskytují pouze přibližné modely. Nicméně, pokud je Markovova vlastnost splněna, Markovovy řetězce poskytují silné a efektivní nástroje pro modelování a analýzu systémů.

Klasifikace stavů

Vratný a nevratný stav: V Markovově řetězci se stav jmenuje "vratný", pokud existuje nenulová pravděpodobnost, že se systém do něj někdy vrátí, bez ohledu na to, kde se právě nachází. Naopak, pokud je pravděpodobnost návratu do daného stavu nulová, říkáme, že je stav "nevratný". Formálně, pokud pro stav i platí, že existuje n takové, že P(St+n = i | St = i) > 0, pak je stav i vratný. Pokud takové n neexistuje, je stav i nevratný.
Přechodný a rekurentní stav: Tyto pojmy jsou těsně spjaty s vratností. Stav se nazývá "přechodný", pokud je pravděpodobnost, že se systém do něj vrátí, menší než 1, i když začal v tomto stavu. Naopak, pokud je pravděpodobnost návratu do daného stavu rovna 1, říkáme, že je stav "rekurentní". Tedy, pokud pro stav i platí, že ∑n P(St+n = i | St = i) = 1, pak je stav i rekurentní. Pokud tento součet je menší než 1, je stav i přechodný.
Periody stavů: Periody stavů jsou užitečné pro rozumění, jak se Markovův řetězec vrací do určitých stavů. Perioda stavu je největší společný dělitel všech n takových, že P(St+n = i | St = i) > 0. Jinými slovy, je to největší počet kroků, které systém může udělat mezi návraty do daného stavu. Pokud je tento největší společný dělitel roven 1, říkáme, že je stav "aperiodický". Pokud je větší než 1, je stav "periodický" s periodou rovnou tomuto největšímu společnému děliteli.

Zkusme příklad, ať tomu lépe porozumíte. Máme přechodovou matici.

Stav 0 je vratný. Vidíme to na tom, že z něj existuje přechod zpět do sebe (s pravděpodobností 0,5). Je také rekurentní, protože pravděpodobnost návratu do tohoto stavu je rovna 1 (můžeme se do něj vrátit buď přímo, nebo přes stav 1). Tento stav je také aperiodický, protože je možné se do něj vrátit po různém počtu kroků a největší společný dělitel těchto počtů je 1.

Stav 1 je také vratný a rekurentní. Z tohoto stavu existuje cesta zpět do sebe přes stav 0 a možnost návratu do tohoto stavu je rovna 1. Také je tento stav aperiodický, protože existuje více různých cest, které vedou zpět do tohoto stavu, a největší společný dělitel těchto počtů kroků je 1.

Stav 2 je nevratný. Z tohoto stavu neexistuje žádná cesta zpět do jiného stavu. Je také rekurentní, protože pokud se jednou do tohoto stavu dostaneme, zůstaneme v něm navždy (pravděpodobnost návratu do tohoto stavu je rovna 1). Tento stav je také aperiodický, protože se do něj můžeme vrátit po libovolném počtu kroků.

Zkusím ještě objasnit některé možné neintuitivní věci, které uvádím výše. Pravděpodobnost návratu do stavu 0 je rovna 1, protože existuje jistota (pravděpodobnost 1), že se do stavu 0 vrátíme buď přímo (s pravděpodobností 0.5) nebo můžeme jít přes stav 1 a zpět do stavu 0. Proto se stav 0 považuje za rekurentní.

Pojem "aperiodický" stav se vztahuje na pravidelnost návratu do daného stavu. Pokud je možné se do stavu vrátit v různých časech, které nemají společný faktor větší než 1, nazýváme tento stav aperiodický. V našem příkladu můžeme návrat do stavu 0 pozorovat buď po jednom kroku (přímo) nebo po dvou krocích (přes stav 1 a zpět). Největší společný dělitel těchto dvou čísel (1 a 2) je 1, takže stav 0 je aperiodický.

Pokud by existoval jen jeden způsob, jak se vrátit do stavu (například pouze po dvou krocích), nebo pokud by všechny možné způsoby návratu měly nějaký společný faktor větší než 1 (například by bylo možné se vrátit pouze po 2, 4, 6 atd. krocích), potom by tento stav byl periodický s danou periodou.