V matematice je Markovův řetězec, pojmenovaný po Andreji Markovovi, diskrétním časoprostorovým stochastickým procesem s Markovovou vlastností. Mít Markovovu vlastnost znamená, že vzhledem k současnému stavu jsou budoucí stavy nezávislé na minulých stavech. Jinými slovy, popis současného stavu plně zachycuje všechny informace, které mohou ovlivnit budoucí vývoj procesu. Vzhledem k současnosti je tedy budoucnost podmíněně nezávislá na minulosti.
V každém okamžiku může systém změnit svůj stav z aktuálního stavu do jiného stavu nebo zůstat ve stejném stavu podle určitého rozdělení pravděpodobnosti. Změny stavu se nazývají přechody a pravděpodobnosti spojené s různými změnami stavu se nazývají pravděpodobnosti přechodu. Viz také sekvenční analýza.
Markovův řetězec je posloupnost náhodných veličin X1, X2, X3, … s vlastností Markov, tedy že vzhledem k současnému stavu jsou budoucí a minulé stavy nezávislé. Formálně,
Možné hodnoty Xi tvoří počitatelnou množinu S nazývanou stavový prostor řetězu.
Markovovy řetězce jsou často popsány směrovaným grafem, kde jsou hrany označeny pravděpodobností přechodu z jednoho stavu do druhého.
Kontinuální Markovovy procesy mají kontinuální index.
Časově homogenní Markovovy řetězce (nebo, Markovovy řetězce s časově homogenní pravděpodobností přechodu) jsou procesy, kde
Markovův řetězec řádu m (nebo Markovův řetězec s pamětí m), kde m je konečný, je kde
pro všechna n. Je možné sestavit řetězec (Yn) z (Xn), který má ‚klasickou‘ Markovovu vlastnost takto:
Nechť Yn = (Xn, Xn−1, …, Xn−m+1), uspořádaná m-tuple hodnot X. Pak Yn je Markovův řetězec se stavovým prostorem Sm a má klasickou Markovovu vlastnost.
Stroj s konečným stavem může být použit jako reprezentace Markovova řetězce. Pokud je stroj ve stavu y v čase n, pak pravděpodobnost, že se přesune do stavu x v čase n + 1, závisí pouze na aktuálním stavu.
Důkladný vývoj a mnoho příkladů naleznete v on-line monografii
Meyn & Tweedie 2005
Dodatek Meyn 2007 , rovněž dostupný on-line, obsahuje zkrácený Meyn & Tweedie.
Vlastnosti Markovových řetězců
Definovat pravděpodobnost přechodu ze stavu i do stavu j v n časových krocích jako
a jednofázový přechod jako
Přechod n-kroku vyhovuje Chapmanově-Kolmogorovově rovnici, že pro každé k taková, že 0 < k < n,
Mezní rozdělení Pr (Xn = x) je rozdělení mezi stavy v čase n. Počáteční rozdělení je Pr (X0 = x). Vývoj procesu prostřednictvím jednoho časového kroku je popsán
Horní index má být pouze celočíselný popisek; pokud je však Markovův řetězec časově stacionární, pak tento horní index může být také interpretován jako „zvyšování na mocninu“, o čemž je dále pojednáno níže.
O stavu j se říká, že je přístupný z jiného stavu i (psaný i → j), pokud vzhledem k tomu, že jsme ve stavu i, existuje nenulová pravděpodobnost, že někdy v budoucnu budeme ve stavu j. Formálně je stav j přístupný ze stavu i, pokud existuje celé číslo n≥0 takové, že
Dovolit, aby n bylo nula, znamená, že každý stát je definován tak, aby byl přístupný sám od sebe.
O stavu i se říká, že komunikuje se stavem j (psáno i ↔ j), pokud je pravda, že obojí i je přístupné z j a že j je přístupné z i. Sada stavů C je komunikující třída, pokud každá dvojice stavů v C spolu komunikuje, a žádný stav v C nekomunikuje s žádným stavem mimo C. (Lze ukázat, že komunikace v tomto smyslu je ekvivalenční relace). Komunikující třída je uzavřená, pokud je pravděpodobnost opuštění třídy nulová, tedy pokud i je v C, ale j není, pak j není přístupný z i.
Konečně, Markovův řetězec je prý neredukovatelný, pokud je jeho stavový prostor komunikující třídou; to znamená, že v neredukovatelném Markovově řetězci je možné se dostat do jakéhokoli stavu z jakéhokoli stavu.
Stav i má periodu k, pokud k návratu do stavu i musí dojít v násobcích k časových kroků. Pokud je například možné vrátit se do stavu i pouze v sudém počtu kroků, pak i je periodické s periodou 2. Formálně je perioda stavu definována jako
(kde „gcd“ je největší společný dělitel). Všimněte si, že i když má stav periodu k, nemusí být možné dosáhnout stavu v krocích k. Například předpokládejme, že je možné vrátit se do stavu v časových krocích {6,8,10,12,…}; pak k bude 2, i když 2 se v tomto seznamu neobjevuje.
Pokud k = 1, pak stav je prý aperiodický; jinak (k>1), stav je prý periodický s periodou k.
Lze ukázat, že každý stát v komunikující třídě musí mít stejnou dobu.
Konečný stav neredukovatelný Markovův řetěz je prý ergodický, pokud jsou jeho stavy aperiodické.
O stavu i se říká, že je pomíjivý, pokud vzhledem k tomu, že začínáme ve stavu i, existuje nenulová pravděpodobnost, že se nikdy nevrátíme zpět do stavu i. Formálně nechť je náhodná proměnná Ti dalším návratovým časem do stavu i („návratový čas“):
Pak, stav i je přechodné MFF existuje konečný Ti taková, že:
Pokud stav i není přechodný (má konečný čas úderu s pravděpodobností 1), pak se říká, že je opakovaný nebo trvalý. Ačkoli je čas úderu konečný, nemusí mít konečný průměr. Nechť Mi je očekávaný (průměrný) čas návratu,
Pak je stav i kladný rekurentní, pokud je Mi konečný; jinak je stav i nulový rekurentní (používají se také termíny non-null persistent a null persistent).
To může být prokázáno, že stav se opakuje tehdy a jen tehdy, pokud
Stav i se nazývá absorbující, pokud není možné tento stav opustit. Proto
stav i absorbuje tehdy a jen tehdy, pokud
Stav i je prý ergodický, pokud je aperiodický a pozitivní rekurentní. Pokud jsou všechny stavy v Markovově řetězci ergodické, pak je řetězec prý ergodický.
Analýza rovnovážného stavu a limitující rozdělení
Pokud je Markovův řetězec časově homogenní Markovův řetězec, takže proces je popsán jedinou, časově nezávislou maticí pij, pak vektor π je stacionární rozdělení (také nazývané rovnovážné rozdělení nebo invariantní míra), pokud jeho položky πj součet k 1 a splňovat
Nezvratný řetězec má stacionární rozdělení tehdy a jen tehdy, jsou-li všechny jeho stavy pozitivní-opakující se. V takovém případě je π jedinečné a souvisí s očekávanou dobou návratnosti:
Dále, pokud řetězec je jak irreducible a aperiodic, pak pro jakékoliv i a j,
Všimněte si, že není žádný předpoklad o počátečním rozdělení; řetězec konverguje ke stacionárnímu rozdělení bez ohledu na to, kde začíná.
Není-li řetězec neredukovatelný, jeho stacionární distribuce nebudou jedinečné (uvažujme jakoukoli uzavřenou komunikující třídu v řetězci; každá z nich bude mít vlastní unikátní stacionární distribuci. Každá z nich se rozšíří na stacionární distribuci pro celý řetězec, kde je pravděpodobnost mimo třídu nastavena na nulu). Je-li však stav j aperiodický, pak
a pro každý jiný stav i, ať fij je pravděpodobnost, že řetěz někdy navštíví stav j, pokud to začíná na i,
Markovovy řetězy s konečným stavovým prostorem
Je-li stavový prostor konečný, rozdělení pravděpodobnosti přechodu může být reprezentováno maticí, nazývanou přechodová matice, přičemž (i, j)’tý prvek P se rovná
P je stochastická matice. Dále, když Markovův řetězec je časově homogenní Markovův řetězec, takže přechodová matice P je nezávislá na značce n, pak k-kroková přechodová pravděpodobnost může být vypočtena jako k-tá mocnina přechodové matice, Pk.
Stacionární rozdělení π je (řádek) vektor, který splňuje rovnici
Jinými slovy, stacionární rozdělení π je normalizované levé vlastní číslo přechodové matice spojené s vlastní číslicí 1.
Jako každá spojitá transformace v jednotce simplex má pevný bod, stacionární rozdělení vždy existuje, ale není zaručeno, že bude unikátní, obecně. Pokud je však Markovův řetězec neredukovatelný a aperiodický, pak existuje unikátní stacionární rozdělení π. Kromě toho Pk konverguje k řadové matici, ve které je každý řádek stacionární rozdělení π, tedy,
kde 1 je sloupcový vektor se všemi položkami rovnými 1. To je dáno Perronovou-Frobeniovou větou. To znamená, že jak čas plyne, Markovův řetězec zapomíná, kde začal (jeho počáteční rozdělení) a konverguje ke svému stacionárnímu rozdělení.
Myšlenka reverzibilního Markovova řetězce pochází ze schopnosti „invertovat“ podmíněnou pravděpodobnost pomocí Bayesova pravidla:
Nyní se zdá, že čas byl obrácený. Tedy, Markov řetězec je řekl, že je vratný, pokud existuje π taková, že
Tato podmínka je také známá jako podrobná podmínka vyvážení.
takže pro vratné Markovovy řetězce, π je vždy stacionární distribuce.
Bernoulliho schéma je speciální případ Markovova řetězce, kde matice pravděpodobnosti přechodu má shodné řádky, což znamená, že další stav je dokonce nezávislý na aktuálním stavu (kromě toho, že je nezávislý na minulých stavech). Bernoulliho schéma s pouze dvěma možnými stavy je známé jako Bernoulliho proces.
Markovovy řetězy s celkovým stavovým prostorem
Mnohé výsledky pro Markovovy řetězce s konečným stavovým prostorem lze zobecnit na řetězce s nespočetným stavovým prostorem prostřednictvím Harrisových řetězců. Hlavní myšlenkou je zjistit, zda existuje bod ve stavovém prostoru, do kterého řetězec narazí s pravděpodobností jedna. Obecně to neplatí pro spojitý stavový prostor, nicméně můžeme definovat množiny A a B spolu s kladným číslem ε a pravděpodobností
opatření ρ, takové, že
Pak bychom mohli množiny zhroutit do pomocného bodu α a opakující se Harrisův řetězec by mohl být upraven tak, aby obsahoval α. A konečně, kolekce Harrisových řetězů je pohodlnou úrovní obecnosti, která je dostatečně široká, aby obsahovala velké množství zajímavých příkladů, a přitom dostatečně restriktivní, aby umožnila bohatou teorii.
Markovianovy systémy se ve fyzice, zejména ve statistické mechanice, objevují extenzivně vždy, když se pro reprezentaci neznámých nebo nekódovaných detailů systému používají pravděpodobnosti, pokud lze předpokládat, že dynamika je časově invariantní a že není třeba brát v úvahu žádnou relevantní historii, která již není zahrnuta v popisu stavu.
Několik teoretiků navrhlo myšlenku Markovova řetězového statistického testu, metody spojení Markovových řetězců do „Markovovy přikrývky“, uspořádání těchto řetězců do několika rekurzivních vrstev („wafering“) a vytvoření účinnějších testovacích sad – vzorků – jako náhrady za vyčerpávající testování. MCSTs mají také využití v sítích založených na časových stavech; Chilukuriho a spol. práce s názvem „Temporal Uncertainty Reasoning Networks for Evidence Fusion with Applications to Object Detection and Tracking“ (ScienceDirect) poskytuje vynikající podklady a případovou studii pro aplikaci MCSTs na širší spektrum aplikací.
Markovovy řetězce mohou být také použity k modelování různých procesů v teorii řazení a statistice. Slavná práce Clauda Shannona z roku 1948 Matematická teorie komunikace, která v jediném kroku vytvořila oblast teorie informace, se otevírá zavedením konceptu entropie prostřednictvím Markovova modelování anglického jazyka. Takové idealizované modely mohou zachytit mnoho statistických zákonitostí systémů. I bez dokonalého popisu celé struktury systému mohou takové modely signálu umožnit velmi účinnou kompresi dat prostřednictvím entropických kódovacích technik, jako je aritmetické kódování. Umožňují také efektivní odhad stavu a rozpoznávání vzorů. Světové systémy mobilních telefonů jsou závislé na Viterbiho algoritmu pro opravu chyb, zatímco skryté Markovovy modely jsou hojně využívány v rozpoznávání řeči a také v bioinformatice, například pro kódování oblasti/genové predikce. Markovovy řetězce také hrají důležitou roli v učení se posilováním.
Pořadí Stránek, jak je používá Google, je definováno Markovovým řetězcem. Je to pravděpodobnost, že bude na stránce ve stacionárním rozdělení na následujícím Markovově řetězci na všech (známých) webových stránkách. Pokud je počet známých webových stránek a stránka má odkazy, pak má přechodovou pravděpodobnost pro všechny stránky, které jsou propojeny a pro všechny stránky, které nejsou propojeny. Parametr je brán jako cca 0.15.
Markovovy modely byly také použity k analýze chování webových navigací uživatelů. Přechod webového odkazu uživatele na konkrétní webové stránce může být modelován pomocí Markovových modelů prvního nebo druhého řádu a může být použit k predikci ohledně budoucí navigace a k personalizaci webové stránky pro jednotlivého uživatele.
Markovovy řetězové metody se také staly velmi důležitými pro generování posloupností náhodných čísel, aby přesně odrážely velmi komplikovaná požadovaná rozdělení pravděpodobnosti, a to prostřednictvím procesu nazvaného Markovův řetěz Monte Carlo (MCMC). V posledních letech to způsobilo revoluci v praktičnosti bayesovských inferenčních metod, což umožnilo simulovat širokou škálu zadních rozdělení a nalézt jejich parametry numericky.
Markovovy řetězce mají také mnoho aplikací v biologickém modelování, zejména populačních procesů, které jsou užitečné v modelovacích procesech, které jsou (alespoň) analogické k biologickým populacím. Jedním takovým příkladem je Leslieho matice, i když některé její položky
nejsou pravděpodobnosti (mohou být větší než 1). Dalším důležitým příkladem je modelování tvaru buňky v dělicích listech epiteliálních buněk]. Rozložení tvarů — převážně šestiúhelníkových — bylo dlouho trvající záhadou, dokud nebylo vysvětleno jednoduchým Markovovým modelem, kde stav buňky je její počet stran. Empirické důkazy od žab, octomilek a hydry dále naznačují, že stacionární rozložení tvaru buňky vykazují téměř všichni mnohobuněční živočichové.
Markovovy řetězy mohou být použity k modelování mnoha hazardních her. Například dětské hry Snakes and Ladders a „Hi Ho! Cherry-O“ jsou reprezentovány přesně Markovovými řetězy. Na každém tahu hráč začíná v daném stavu (na daném čtverci) a odtud má pevně stanovenou pravděpodobnost přesunu do určitých jiných stavů (čtverců).
Markovovy řetězce se používají v algoritmické hudební kompozici, zejména v softwarových programech, jako je CSound nebo Max. V řetězci prvního řádu se stavy systému stávají hodnotami noty nebo výšky tónu a pro každou notu je konstruován vektor pravděpodobnosti, který dokončuje matici pravděpodobnosti přechodu (viz níže). Algoritmus je konstruován tak, aby vytvářel a vypouštěl hodnoty noty na základě váhy přechodové matice, což mohou být hodnoty noty MIDI, frekvence (Hz) nebo jiná žádoucí metrika.
Markovův řetězec druhého řádu může být zaveden s ohledem na aktuální stav a také předchozí stav, jak je uvedeno ve druhé tabulce. Vyšší řetězy n-tého řádu mají tendenci „seskupovat“ jednotlivé noty dohromady, zatímco se příležitostně „lámou“ do jiných vzorů a sekvencí. Tyto řetězy vyššího řádu mají tendenci generovat výsledky se smyslem pro frázovou strukturu, spíše než „bezcílné bloudění“ produkované systémem prvního řádu.
Modely Markovových řetězů se používají v pokročilé baseballové analýze od roku 1960, i když jejich použití je stále vzácné. Každá půlsměna baseballového zápasu odpovídá stavu Markovova řetězu, kdy se bere v úvahu počet běžců a outů. Pro každou půlsměnu existuje 24 možných run-out kombinací. Modely Markovových řetězů lze použít k vyhodnocení běhů vytvořených jak pro jednotlivé hráče, tak i pro tým. .
Markovovy procesy mohou být také použity ke generování povrchně „reálně vypadajícího“ textu daného ukázkovým dokumentem: jsou použity v různých rekreačních „generátorech parodií“ software (viz disociovaný tisk, Jeff Harrison, Mark V Shaney,
a)
).
Andrey Markov vyrobené první výsledky (1906) pro tyto procesy, čistě teoreticky.
A zobecnění na počítatelně nekonečné stavových prostorů byla dána Kolmogorovovův (1936).
Markovovy řetězce jsou spojené s Brownův pohyb a ergodické hypotézy, dvě témata ve fyzice, které byly důležité v prvních letech dvacátého století, ale Markov se zdá, že sledovali to z matematické motivace, a to rozšíření zákona velkých čísel na závislé události. V roce 1913, on aplikoval své poznatky poprvé, a to, na prvních 20.000 dopisů Puškin je „Evžen Oněgin“.