Markov proces

V matematice , je Markov proces je stochastický proces s majetkem Markov . V takovém procesu není předpovědi budoucnosti ze současnosti zpřesňována informacemi o minulosti. Markovské procesy jsou pojmenovány podle jejich vynálezce Andreje Markova .

Diskrétní čase Markov proces je sekvence z náhodných proměnných . Soubor jejich možných hodnot se nazývá stavový prostor , přičemž hodnotou je stav procesu v daném okamžiku. Podle autorů termín „ Markovův řetězec “ označuje diskrétní Markovovy procesy nebo pouze diskrétní Markov procesy. Markovův proces v diskrétním čase a diskrétním stavovém prostoru, tj. diskrétní Markovovy procesy, jejichž stavový prostor je konečný nebo spočetný . $\ scriptstyle \ X_ {1},$ $\ scriptstyle \ X_ {2},$ $\ scriptstyle \ X_ {3}, \ \ tečky$ $\ scriptstyle \ X_ {n} \$ $\ scriptstyle \ n.$

Pokud je podmíněný zákon poznání minulého času, tj. Poznání, funkcí osamoceného, pak: $\ scriptstyle \ X _ {{n + 1}} \$ $\ scriptstyle \ \ left (X_ {k} \ right) _ {{0 \ leq k \ leq n}} \$ $\ scriptstyle \ X_ {n} \$

P (X _ {{n + 1}} = x \ mid X_ {0}, X_ {1}, X_ {2}, \ ldots, X_ {n}) = P (X _ {{n + 1}} = x \ mid X_ {n}). \,

kde je jakýkoli stav procesu. Výše uvedená identita identifikuje Markovianovu pravděpodobnost . $X$

Andrej Markov zveřejnil první výsledky těchto procesů v roce 1906 .

Zobecnění na spočetný nekonečný stavový prostor dal Kolmogorov v roce 1936 .

Markov procesy jsou spojeny s Brownova pohybu a ergodické hypotézy , dvě tématech statistické fyziky , které byly na počátku velmi důležitá XX th století.

Typy Markovových procesů

Diskrétní stavový prostor

Když jsou po sobě jdoucí náhodné proměnné diskrétní proměnné vybavené pravděpodobnostní funkcí, mluvíme o Markovově řetězci .

Ačkoli se Markovovy řetězce vztahují na jevy, jejichž dočasný aspekt je obecně nezajímavý, je možné spojit postupné hodnoty s okamžiky . Markovianova vlastnost, podle které pravděpodobnost stavu systému závisí pouze na jeho předchozím stavu prostřednictvím podmíněné pravděpodobnosti nazývané pravděpodobnost přechodu, je vyjádřena: $x_i \,$ $t_ {i} \,$

P (x_ {n}, t_ {n} | x _ {{n-1}}, t _ {{n-1}}; x _ {{n-2}}, t _ {{n-2} }; ...; x_ {1}, t_ {1}; x_ {0}, t_ {0}) = P (x_ {n}, t_ {n} | x _ {{n-1}}, t _ {{n-1}}) \ quad t_ {n}> t _ {{n-1}}> ...> t_ {1}> t_ {0} \,

Markovův řetězec je zcela definován pravděpodobností prvního řádu a pravděpodobností přechodu. Například pravděpodobnost druhého řádu získáme takto: $P (x, t) \,$

P (x_ {1}, t_ {1}; x_ {2}, t_ {2}) = P (x_ {1}, t_ {1}) P (x_ {2}, t_ {2} | x_ {1 }, t_ {1}) \ quad t_ {2}> t_ {1} \,

Je proto také definována pravděpodobností druhého řádu. Nakonec jej lze definovat počátečním stavem a pravděpodobností přechodu.

Kontinuální stavový prostor

Markovovy řetězce nacházejí uplatnění v nejrůznějších oblastech, ale procesy uvažované v dynamických problémech, zejména ve vibracích, se obecně vztahují k spojitým náhodným proměnným.

Za těchto podmínek je pravděpodobnost získání dané hodnoty obecně nulová a pravděpodobnosti výskytu musí být nahrazeny hustotami pravděpodobnosti ve vzorci Markovianovy vlastnosti:

p (x_ {n}, t_ {n} | x _ {{n-1}}, t _ {{n-1}}; x _ {{n-2}}, t _ {{n-2} }; ...; x_ {1}, t_ {1}; x_ {0}, t_ {0}) = p (x_ {n}, t_ {n} | x _ {{n-1}}, t _ {{n-1}}) \ quad t_ {n}> t _ {{n-1}}> ...> t_ {1}> t_ {0} \,

Diskrétní čas a spojitý čas

Výše uvedené úvahy zůstávají v platnosti, pokud jsou časové intervaly nekonečně malé. Tato poznámka je zvláště zajímavá v případě diferenciální rovnice . Pokud je to prvního řádu, nastavení konečných rozdílů odhalí markovovský mechanismus. U vyšších řádů a diferenciálních systémů vede rozklad na rovnice prvního řádu k Markovianovu systému s několika dimenzemi.

Vlastnosti Markovových procesů v diskrétním čase

Markovův proces je charakterizován podmíněným rozdělením:

P (X _ {{n + 1}} \ mid X_ {n}) \,

což se také nazývá pravděpodobnost přechodu kroku procesu. Pravděpodobnost přechodu pro dva , tři nebo více kroků se odvodí z pravděpodobnosti přechodu jednoho kroku a z vlastnosti Markov:

P (X _ {{n + 2}} \ mid X_ {n}) = \ int P (X _ {{n + 2}}, X _ {{n + 1}} \ mid X_ {n}) \ , {\ mathrm d} X _ {{n + 1}} = \ int P (X _ {{n + 2}} \ mid X _ {{n + 1}}) \, P (X _ {{n + 1}} \ mid X_ {n}) \, {\ mathrm d} X _ {{n + 1}}

Rovněž,

P (X _ {{n + 3}} \ mid X_ {n}) = \ int P (X _ {{n + 3}} \ mid X _ {{n + 2}}) \ int P (X _ {{n + 2}} \ mid X _ {{n + 1}}) \, P (X _ {{n + 1}} \ mid X_ {n}) \, {\ mathrm d} X _ {{ n + 1}} \, {\ mathrm d} X _ {{n + 2}}

Tyto vzorce jsou zobecněny na libovolně vzdálenou budoucnost vynásobením pravděpodobností přechodu a integračních časů. $n + k$ $k-1$

Zákon marginální distribuce je zákon distribuce států v čase . Počáteční distribuce je . Vývoj procesu po jednom kroku popisuje: $P (X_ {n})$ $ne$ $P (X_ {0})$

P (X _ {{n + 1}}) = \ int P (X _ {{n + 1}} \ mid X_ {n}) \, P (X_ {n}) \, {\ mathrm d} X_ {n}

Toto je verze Frobenius-Perronovy rovnice . Může existovat jedna nebo více distribucí stavu , například: $\ pi$

\ pi (X) = \ int P (X \ mid Y) \, \ pi (Y) \, {\ mathrm d} Y

kde je libovolný název integrační proměnné. Takové rozdělení se nazývá stacionární rozdělení . Stacionární distribuce je vlastní funkce zákona podmíněného rozdělení, spojená s vlastní hodnotou 1. $Y$ $\ pi$

V případě diskrétních stavových prostorových Markovových řetězců určují určité vlastnosti procesu, zda existuje stacionární distribuce či nikoli, a zda je či není jedinečné.

Markovův řetězec je neredukovatelný, pokud je kterýkoli stát přístupný z jiného státu.
stav je rekurentní kladný, pokud je očekávání času prvního návratu do tohoto stavu, počínaje tímto stavem, konečné.

Když stavový prostor Markovova řetězce není neredukovatelný, lze jej rozdělit do sady neredukovatelných komunikujících tříd . Problém klasifikace je důležitý v matematickém studiu Markovových řetězců a stochastických procesů .

Pokud má Markovův řetězec alespoň jeden pozitivní rekurentní stav, pak existuje stacionární distribuce.

Pokud je markovský řetězec pozitivní a neredukovatelný opakující se, pak:

existuje jediný stacionární rozvod;
a proces konstruovaný tak, že stacionární distribuce jako počáteční distribuce je ergodická .

Průměr funkce v instancích Markovova řetězce se tedy rovná jejímu průměru podle jeho stacionárního rozdělení: $F$

\ lim _ {{n \ rightarrow \ infty}} \; {\ frac {1} {n}} \; \ sum _ {{k = 0}} ^ {{n-1}} f (X_ {k} ) = \ int f (X) \, \ pi (X) \, {\ mathrm d} X

To platí zejména, když je funkce identity. $F$

Průměr hodnoty instancí je proto z dlouhodobého hlediska stejný jako očekávání stacionárního rozdělení.

Navíc tato ekvivalence na prostředcích platí také v případě, že je indikátorovou funkcí podmnožiny stavového prostoru: $F$ $NA$

\ lim _ {{n \ rightarrow \ infty}} \; {\ frac {1} {n}} \; \ sum _ {{k = 0}} ^ {{n-1}} \ chi _ {A} (X_ {k}) = \ int _ {A} \ pi (X) \, {\ mathrm d} X = \ mu _ {{\ pi}} (A)

kde je míra vyvolaná . $\ mu _ {{\ pi}}$ $\ pi$

To umožňuje aproximovat stacionární distribuci pomocí histogramu konkrétní sekvence.

Pokud je stavový prostor konečný , pak rozdělení pravděpodobnosti může být reprezentováno stochastickou maticí zvanou přechodová matice , jejíž th prvek je: $(i, j)$

P (X _ {{n + 1}} = j \ mid X_ {n} = i) \,

Aplikace

Markovian systémy jsou velmi přítomné ve fyzice, zejména ve statistické fyzice . Zasahují zejména prostřednictvím Fokker-Planckovy rovnice . Obecněji řečeno, Markovova hypotéza je často vyvolána, když jsou k modelování stavu systému použity pravděpodobnosti, avšak za předpokladu, že budoucí stav systému lze odvodit z minulosti s poměrně nízkou historií.
Slavný článek 1948 o Claude Shannon , matematická teorie komunikace , která zakládá informační teorii , začíná tím, že zavádí pojem entropie z modelování Markov z anglického jazyka . Ukazuje tedy míru předvídatelnosti anglického jazyka, který je vybaven jednoduchým modelem řádu 1. I když jsou tyto modely jednoduché, umožňují dobře reprezentovat statistické vlastnosti systémů a provádět efektivní předpovědi bez úplného popisu struktury. .
V kompresi umožňuje Markovianovo modelování realizaci velmi účinných technik kódování entropie , jako je aritmetické kódování . Mnoho algoritmů v rozpoznávání vzorů nebo v umělé inteligenci , jako je Viterbiho algoritmus , používaný v drtivé většině systémů mobilních telefonů pro korekci chyb, předpokládá základní Markovianův proces.
Index popularity webové stránky ( PageRank ) používaný Googlem je definován řetězcem Markov. Je definována pravděpodobností, že se na této stránce vyskytne jakýkoli stav řetězce Markov, který představuje web. Pokud je počet známých webových stránek a stránka má odkazy, pak je její pravděpodobnost přechodu na odkazovanou stránku (na kterou ukazuje) a pro všechny ostatní (nesouvisející stránky). Všimněte si, že máme . Parametr je přibližně 0,15. $NE$ $i$ $k_ {i}$ $p_ {i} ^ {l} = {\ tfrac {1-q} {k_ {i}}} + {\ tfrac qN}$ $p_ {i} ^ {{nl}} = {\ tfrac qN}$ $k_ {i} p_ {i} ^ {l} + (N-k_ {i}) p_ {i} ^ {{nl}} = 1$ $q$
Markovovy řetězce jsou základním nástrojem pro modelování procesů v teorii front a statistikách .
Markov řetězy jsou běžně používané v spolehlivosti pro výpočty spolehlivosti a dostupnosti z technických systémů , zejména pro modelování typ poruchy sekvencí událostí, udržování, změny konfigurace.
Markovovy řetězce se také používají v bioinformatice k modelování vztahů mezi po sobě následujícími symboly stejné sekvence ( například nukleotidů ), které jdou nad rámec polynomiálního modelu. Skryté Markovovy modely mají také různá použití, například segmentaci (definování regionálních hranic v sekvencích genů nebo proteinů s různými chemickými vlastnostmi), vícenásobné zarovnání , predikci funkce nebo objev genů. (Skryté Markovovy modely jsou „pružnější“ než přísné definice typu start kodon + více kodonů + stop kodony, a proto jsou vhodnější pro eukaryoty (kvůli přítomnosti intronů v jejich genomu) nebo pro objevení pseudogenů).

Podívejte se také

Související články

Bibliografie

Étienne Pardoux: Markovovy procesy a aplikace - Algoritmy, sítě, genom a finance . Dunod, 2007
Pierre Désesquelles: Markovovy procesy v biologii, sociologii, geologii, chemii, fyzice a průmyslových aplikacích . Elipsy, 2016.

externí odkazy

(en) [PDF] Charles M. Grinstead a J. Laurie Snell, kap. „ Markovovy řetězce “, v Úvod do pravděpodobnosti , AMS
(en) Markov Chain Marvelous
Opravené cvičení ( wims z University of Nice, Sophia Antipolis )