Markovův řetězec

V matematiky , je Markov řetěz je diskrétní Markov proces nebo kontinuální i diskrétní stavový prostor. Markovův proces je stochastický proces mající Markovovu vlastnost : informace užitečné pro předpovídání budoucnosti jsou zcela obsaženy v současném stavu procesu a nejsou závislé na předchozích stavech (systém nemá žádnou „paměť“). Markovské procesy jsou pojmenovány podle jejich vynálezce Andreje Markova .

Diskrétní časové Markov proces je sekvence z náhodných proměnných s hodnotami ve státní prostoru , který budeme poznámka v následujícím textu. Hodnota je stav procesu v daném okamžiku. Aplikace, kde je stavový prostor konečný nebo spočetný, jsou nespočetné: mluvíme pak o Markovových řetězcích nebo o diskrétních stavových prostorových Markovových řetězcích . Základní vlastnosti obecných Markovových procesů , například vlastnosti rekurence a ergodicity , lze uvést nebo dokázat jednodušeji v případě diskrétních stavových prostorových Markovových řetězců . Tento článek se týká přesně Markovových řetězců s diskrétním stavovým prostorem . ${\ displaystyle X_ {0},}$ ${\ displaystyle X_ {1},}$ ${\ displaystyle X_ {2},}$ ${\ displaystyle X_ {3}, \ \ tečky}$ $E$ $X_ {n}$ $ne.$ $E$

Andrei Markov zveřejnil první výsledky v markovských řetězcích konečného stavu prostoru v roce 1906 . Zobecnění na spočetný nekonečný stavový prostor publikoval 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í .

Slabý majetek Markov

Definice

Toto je charakteristická vlastnost markovského řetězce: predikce budoucnosti ze současnosti není zpřesněna dalšími informacemi o minulosti, protože všechny informace užitečné pro predikci budoucnosti jsou obsaženy v současném stavu proces. Slabá Markovova vlastnost má několik ekvivalentních forem, které všechny znamenají pozorování, že podmíněný zákon poznání minulého času, tj. Poznání, je funkcí pouze: $X _ {{n + 1}}$ ${\ displaystyle \ left (X_ {k} \ right) _ {0 \ leq k \ leq n},}$ $X_ {n}$ ${\ begin {aligned} \ forall n \ geq 0, \ forall (i_ {0}, \ ldots, i _ {{n-1}}, i, j) & \ in E ^ {{n + 2}} , \\ {\ mathbb {P}} {\ Big (} X _ {{n + 1}} = j & \ mid \, X_ {0} = i_ {0}, X_ {1} = i_ {1} , \ ldots, X _ {{n-1}} = i _ {{n-1}}, X_ {n} = i {\ Big)} = {\ mathbb {P}} \ vlevo (X _ {{ n + 1}} = j \ mid X_ {n} = i \ right). \ end {zarovnáno}}$

Běžnou variantou Markovových řetězců je homogenní Markovův řetězec , u kterého je pravděpodobnost přechodu nezávislá na : $ne$ ${\ displaystyle \ forall n \ geq 1, \ forall (i, j) \ v E ^ {2}, \ quad \ mathbb {P} (X_ {n + 1} = j \ mid X_ {n} = i) = \ mathbb {P} (X_ {n} = j \ mid X_ {n-1} = i)}$

Ve zbytku článku budou uvažovány pouze homogenní Markovovy řetězce. Zajímavou aplikaci nehomogenních Markovových řetězců na kombinatorickou optimalizaci najdete v článku Simulované žíhání . Existuje silná vlastnost Markov , spojená s představou času zastavení : tato silná vlastnost Markov je zásadní pro důkaz důležitých výsledků (různá kritéria opakování, silný zákon velkého počtu pro řetězce Markov). Je to uvedeno v článku „ Markovský majetek “.

Kritérium

Základní kritérium - Dovolme být posloupností nezávislých náhodných proměnných stejného zákona s hodnotami v prostoru a buď měřitelnou mapou v Předpokládejme, že posloupnost je definována relací opakování: ${\ displaystyle Y = (Y_ {n}) _ {n \ geq 1}}$ $F$ $F$ $E \ krát F.$ ${\ displaystyle E.}$ ${\ displaystyle X = (X_ {n}) _ {n \ geq 0}}$ $\ forall n \ geq 0, \ qquad X _ {{n + 1}} = f \ left (X_ {n}, Y _ {{n + 1}} \ right),$ a předpokládejme, že sekvence je nezávislá na Then je homogenní Markovův řetězec. $Y$ ${\ displaystyle X_ {0}.}$ $X$

Příklad: problém sběrače nálepek :

Petit Pierre sbírá portréty jedenácti hráčů národního fotbalového týmu, které najde na samolepkách uvnitř obalu čokoládových tyčinek; pokaždé, když si koupí tablet, má šanci 1 z 11 najít portrét hráče č. (pro všechno ). Poznámka: stav kolekce Pierre Petit, po otevření obalu svého e čokoládové tyčinky. je Markov řetěz od , protože se vejde do předchozího rámce pro volbu od $k$ $k$ ${\ displaystyle X_ {n} \ in {\ mathcal {P}} ([\! [1,11] \!])}$ $ne$ ${\ displaystyle X = (X_ {n}) _ {n \ geq 0}}$ ${\ displaystyle X_ {0} = \ emptyset}$ ${\ displaystyle F = [\! [1,11] \!], \ E = {\ mathcal {P}} (F), \ f (x, y) = x \ pohár \ {y \},}$ $X _ {{n + 1}} = X_ {n} \ cup \ {Y _ {{n + 1}} \},$ kde náhodné proměnné jsou nezávislé a jednotné náhodné proměnné jsou : jsou to po sobě jdoucí čísla viněty čerpané z čokoládových tyčinek. Průměrná doba potřebná k dokončení kolekce (zde je počet tablet, které si Petit Pierre musí v průměru koupit, aby mohla dokončit svou sbírku), je u kolekce vinět celkem, kde je th harmonické číslo . Například čokoládové tyčinky. ${\ displaystyle Y_ {n}}$ ${\ displaystyle [\! [1,11] \!]}$ $NE$ ${\ displaystyle N \, H_ {N},}$ ${\ displaystyle H_ {N}}$ $NE$ ${\ displaystyle 11 \, H_ {11} = 33,2 \ tečky \ quad}$

Poznámky:

Vlastnost Markov pochází z nezávislosti , zůstává pravdou, když mají různé zákony a kdy závisí „relace opakování“ . Předpoklady provedené kromě nezávislosti existují pouze k zajištění homogenity řetězce Markovem. ${\ displaystyle Y_ {i} \;}$ $Y_ {i}$ ${\ displaystyle X_ {n + 1} = f_ {n} \ vlevo (X_ {n}, Y_ {n + 1} \ vpravo)}$ $ne.$
Kritérium je zásadní v tom, že jakýkoli homogenní Markovův řetězec lze simulovat pomocí opakování formy pro dobře zvolenou funkci . Můžeme si dokonce vybrat a zvolit nezávislé a jednotné proměnné v intervalu [0,1], což je vhodné pro studium Markovových řetězců metodami Monte Carlo . ${\ displaystyle X_ {n + 1} = f \ vlevo (X_ {n}, Y_ {n + 1} \ vpravo),}$ $F$ ${\ displaystyle F = [0,1],}$ ${\ displaystyle Y_ {j}}$

Pravděpodobnosti přechodu

Definice

Definice - Číslo se nazývá pravděpodobnost státně to- přechodu stavu v jednom kroku , nebo pravděpodobnost státně to- přechodu stavu , pokud není dvojznačnost. Toto číslo si často všimneme ${\ displaystyle \ mathbb {P} \ doleva (X_ {1} = j \ mid X_ {0} = i \ right)}$ $i$ $j$ $i$ ${\ displaystyle j,}$ ${\ displaystyle p_ {i, j}:}$ $p _ {{i, j}} = {\ mathbb {P}} \ vlevo (X _ {{1}} = j \ mid X_ {0} = i \ vpravo).$

Rodinná čísla se nazývají přechodová matice , přechodové jádro nebo přechodový operátor Markovova řetězce. ${\ displaystyle P = \ left (p_ {i, j} \ right) _ {(i, j) \ in E ^ {2}}}$

Terminologická přechodová matice je nejpoužívanější, ale je vhodné, přísně vzato, pouze když pro celé číslo When je konečné, například kardinál, lze vždy číslovat prvky libovolně od 1 do toho, co určuje problém, ale nedokonale, protože toto přečíslování je v mnoha příkladech protiintuitivní. ${\ displaystyle n \ geq 1,}$ ${\ displaystyle E = \ {1,2, \ ldots, n \}.}$ $E$ ${\ displaystyle n,}$ $E$ ${\ displaystyle n,}$

Model Ehrenfest: dva psi a jejich blechy:

Dva psi sdílejí blechy následujícím způsobem: v každém okamžiku je náhodně vybrána jedna z blech a poté skočí z jednoho psa na druhého. Stav systému je popsán prvkem kde $NE$ $NE$ ${\ displaystyle x = (x_ {1}, x_ {2}, \ tečky, x_ {N}) \ v \ {0,1 \} ^ {N},}$ $x _ {{i}} = 0 {\ text {or}} 1 {\ text {podle toho, zda je čip n}} ^ {{\ circ}} \ i {\ text {na 1. nebo na 2. psu .}}$

Stejně tak má prvky, ale jejich číslování od 1 do by bylo nepříjemné sledovat vývoj systému, který spočívá v náhodném výběru jedné ze souřadnic a změně jeho hodnoty. Pokud chceme systému porozumět méně podrobně (protože nejsme schopni rozeznat čip od jiného), můžeme jednoduše prostudovat počet čipů u psa č. 1, což znamená zvolit znovu, pro pochopení by bylo škoda přečíslovat stavy z 1 na Všimněte si, že pro tuto novou modelování $E$ $2 ^ {N}$ $2 ^ {N}$ $NE$ $X$ ${\ displaystyle E = \ {0,1,2, \ tečky, N \}.}$ ${\ displaystyle N + 1.}$ $p _ {{k, k + 1}} = {\ tfrac {Nk} N} {\ text {et}} p _ {{k, k-1}} = {\ tfrac {k} N},$ protože například počet žetonů na zadní straně psa č. 1 se změní z k na k-1, pokud je vybrán jeden z těchto k žetonů mezi N čipy přítomnými v „systému“. Tento model se častěji označuje jako „ model Ehrenfest Urny “. To bylo představeno v roce 1907 Tatianou a Paulem Ehrenfestem pro ilustraci některých „paradoxů“, které vznikly v základech rodící se statistické mechaniky, a pro modelování růžového šumu . Ehrenfest Model urna byla zvažována matematik Mark Kac, aby byl „pravděpodobně jedním z nejvíce poučných modelů v celé fyziky.“

Spíše než přečíslování stavů od 1 je proto v mnoha případech ergonomičtější přijímat konečné nebo nekonečné matice, jejichž řádky a sloupce jsou „číslovány“ pomocí prvků Součin dvou takových „matic“, a je pak definován velmi přirozeně podle ${\ displaystyle E.}$ ${\ displaystyle A = \ left (a_ {i, j} \ right) _ {(i, j) \ v E ^ {2}}}$ ${\ displaystyle B = \ left (b_ {i, j} \ right) _ {(i, j) \ in E ^ {2}}}$ $(AB) _ {{i, j}} = \ sum _ {{\ ell \ in E}} a _ {{i, \ ell}} b _ {{\ ell, j}},$ analogicky s klasičtějším vzorcem součinu dvou čtvercových matic velikosti ${\ displaystyle n,}$ $(AB) _ {{i, j}} = \ sum _ {{k = 1}} ^ {n} a _ {{i, k}} b _ {{k, j}}.$

Vlastnosti

Tvrzení - Matice přechodu je stochastická : součet členů kteréhokoli řádku vždy dává 1. ${\ displaystyle P = \ left (p_ {i, j} \ right) _ {(i, j) \ in E ^ {2}}}$ $P$ $\ forall i \ in E, \ quad \ sum _ {{j \ in E}} p _ {{i, j}} = 1.$

Tvrzení - Zákon Markovova řetězce je charakterizován dvojicí tvořenou jeho přechodovou maticí a jeho počátečním zákonem (zákonem ): pro všechny společné právo je dáno ${\ displaystyle X = \ vlevo (X_ {n} \ vpravo) _ {n \ geq 0}}$ ${\ displaystyle P,}$ $X_ {0}$ $n \ geq 1$ ${\ displaystyle (X_ {0}, X_ {1}, \ ldots, X_ {n})}$ ${\ mathbb {P}} \ left (X _ {{0}} = i_ {0}, X _ {{1}} = i_ {1}, \ ldots, X _ {{n-1}} = i _ {{n -1}}, X _ {{n}} = i_ {n} \ right) = {\ mathbb {P}} \ left (X _ {{0}} = i_ {0} \ right) \ p _ {{i_ {{0}}, i_ {1}}} \, p _ {{i _ {{1}}, i_ {2}}} \, \ ldots \, p _ {{i _ {{n-2}}, i _ {{n-1}}}} \, p _ {{i _ {{n-1}}, i_ {n}}}.$

Demonstrace

Indukcí, na hodnosti 0, ${\ mathbb {P}} \ left (X _ {{0}} = i_ {0} \ right) = {\ mathbb {P}} \ left (X _ {{0}} = i_ {0} \ right ).$

V řadě pózováním ${\ displaystyle n,}$ ${\ displaystyle P_ {k} = \ mathbb {P} \ vlevo (X_ {0} = i_ {0}, X_ {1} = i_ {1}, \ ldots, X_ {k-1} = i_ {k- 1}, X_ {k} = i_ {k} \ vpravo),}$ ${\ frac {P_ {n}} {P _ {{n-1}}}} = {\ mathbb {P}} {\ Big (} X _ {{n}} = i_ {n} \ mid \, X_ {0} = i_ {0}, X_ {1} = i_ {1}, \ ldots, X _ {{n-1}} = i _ {{n-1}} {\ Big)} = p _ {{i _ {{n-1}}, i_ {n}}},$ díky slabé Markovově vlastnosti, takže pokud má očekávaný výraz, pak také. ${\ displaystyle P_ {n-1}}$ $P_ {n}$

Když studujeme konkrétní Markovův řetězec, jeho přechodová matice je obecně dobře definovaná a fixovaná během celé studie, ale počáteční zákon se může během studia změnit a notace musí odrážet původní zákon uvažovaný v daném okamžiku: pokud v okamžiku ve studii považujeme Markovův řetězec počáteční distribuce definovaný do té doby jsou zaznamenány pravděpodobnosti a očekávání jsou zaznamenána Zejména pokud řekneme, že Markovův řetězec začíná od pravděpodobností jsou zaznamenány a očekávání jsou zaznamenána ${\ displaystyle \ forall i \ in E, \ quad \ mathbb {P} \ left (X_ {0} = i \ right) = \ mu _ {i}, \ quad}$ ${\ displaystyle \ mathbb {P} _ {\ mu} \ vlevo (\ tečky \ vpravo), \ quad}$ ${\ displaystyle \ mathbb {E} _ {\ mu} \ doleva [\ tečky \ doprava]. \ quad}$ ${\ displaystyle \ mathbb {P} \ vlevo (X_ {0} = j \ vpravo) = 1, \ quad}$ ${\ displaystyle j, \ quad}$ ${\ displaystyle \ mathbb {P} _ {j} \ vlevo (\ tečky \ vpravo), \ quad}$ ${\ displaystyle \ mathbb {E} _ {j} \ vlevo [\ tečky \ vpravo]. \ quad}$

Síly přechodové matice

Pro pravděpodobnosti přechodu v kroku, není závislá na : ${\ displaystyle k \ geq 1,}$ $k$ ${\ displaystyle \ mathbb {P} \ vlevo (X_ {n + k} = j \ mid X_ {n} = i \ vpravo),}$ $ne$

Tvrzení - matice přechodu ve stupních , se rovná výkonu th přechodného matice Poznamenáváme, $k$ ${\ displaystyle \ left (\ mathbb {P} \ left (X_ {n + k} = j \ mid X_ {n} = i \ right) \ right) _ {(i, j) \ v E ^ {2} },}$ $k$ $P.$ $p _ {{i, j}} ^ {{(k)}} = {\ mathbb {P}} \ vlevo (X _ {{n + k}} = j \ mid X_ {n} = i \ vpravo) ,$ a $P ^ {k} = \ left (p _ {{i, j}} ^ {{(k)}} \ right) _ {{(i, j) \ in E ^ {2}}}.$

Demonstrace

Opakováním. Na 1. úrovni je to důsledek homogenity markovského řetězce již zmíněného v sekci Slabá markovská vlastnost : ${\ mathbb {P}} \ left (X _ {{n + 1}} = j \ mid X_ {n} = i \ right) = {\ mathbb {P}} \ left (X _ {{1}} = j \ mid X_ {0} = i \ right).$

Hodnost ${\ displaystyle k,}$ ${\ begin {aligned} {\ mathbb {P}} \ left (X_ {n} = i {\ text {and}} X _ {{n + k}} = j \ right) & = \ sum _ {{ \ ell \ in E}} {\ mathbb {P}} \ left (X_ {n} = i, \, X _ {{n + k-1}} = \ ell {\ text {and}} X _ { {n + k}} = j \ right) \\ & = \ sum _ {{\ ell \ in E}} {\ mathbb {P}} \ left (X_ {n} = i, \, X _ {{ n + k- 1}} = \ ell \ right) \ {\ mathbb {P}} \ left (X _ {{n + k}} = j \ mid X_ {n} = i, \, X _ {{ n + k-1}} = \ ell \ right) \\ & = \ sum _ {{\ ell \ in E}} {\ mathbb {P}} \ left (X_ {n} = i, \, X _ {{n + k-1}} = \ ell \ right) \ p _ {{\ ell, j}} \\ & = {\ mathbb {P}} \ left (X_ {n} = i \ right) \ \ sum _ {{\ ell \ in E}} p _ {{i, \ ell}} ^ {{(k-1)}} \ p _ {{\ ell, j}} \\ & = {\ mathbb {P}} \ left (X_ {n} = i \ right) \ p _ {{i, j}} ^ {{(k)}}, \ end {zarovnáno}}$ nebo

1 st rovnost je třetí axiom pravděpodobnosti ,
2 nd rovnost je definice podmíněné pravděpodobnosti ,
3 th rovnost je kvůli tvaru nízkého majetku Markov,
4 th rovnost je opakování vlastnost není ${\ displaystyle k-1,}$
5 th rovnost je vzorec produktu ze dvou „pole“, aplikován na produkt s ${\ displaystyle P ^ {k-1}}$ $P.$

Na závěr dělíme dva krajní členy této posloupnosti rovností, pokud není tento poslední člen nulový, v takovém případě můžeme libovolně definovat , tedy například rovno ${\ displaystyle \ mathbb {P} \ doleva (X_ {n} = i \ doprava),}$ ${\ displaystyle \ mathbb {P} \ vlevo (X_ {n + k} = j \ mid X_ {n} = i \ vpravo)}$ ${\ displaystyle p_ {i, j} ^ {(k)}.}$

Jednoduchou aplikací vzorce pro celkovou pravděpodobnost odvodíme mezní zákony Markovova řetězce.

Dodatek - Zákon je dán ${\ displaystyle X_ {n + k}}$ ${\ mathbb {P}} \ left (X _ {{n + k}} = j \ right) = \ sum _ {{i \ in E}} {\ mathbb {P}} \ left (X _ {{ n}} = i \ right) p _ {{i, j}} ^ {{(k)}}.$

Zejména, ${\ mathbb {P}} \ left (X _ {{n}} = j \ right) = \ sum _ {{i \ in E}} {\ mathbb {P}} \ left (X _ {{0} } = i \ right) p _ {{i, j}} ^ {{(n)}}.$

Při psaní matice, je-li právem se považuje za line-vektoru s tím, že upravené, do: ${\ displaystyle X_ {n}}$ ${\ displaystyle \ mu _ {n} = (\ mu _ {n, i}) _ {i \ v E},}$ ${\ displaystyle \ mu _ {n, i} = \ mathbb {P} \ vlevo (X_ {n} = i \ vpravo),}$ $\ mu _ {{n + k}} = \ mu _ {{n}} P ^ {k} \ quad {\ text {a}} \ quad \ mu _ {{n}} = \ mu _ {{0 0 }} P ^ {n}.$

Klasifikace států

Pro říkáme, že je přístupný z tehdy a jen tehdy, pokud existuje taková, že jsme se označují: ${\ displaystyle (i, j) \ v E ^ {2}}$ $j$ $i$ $n \ geq 0$ ${\ displaystyle \ mathbb {P} (X_ {n} = j \ mid X_ {0} = i)> 0.}$ $\ {j \ leftarrow i \} \ quad \ Leftrightarrow \ quad \ left \ {\ existuje n \ geq 0 {\ text {jako například}} p _ {{i, j}} ^ {{(n)}}> 0 \ doprava \}.$

Říkáme to a komunikujeme tehdy a jen tehdy, pokud takové existují a označujeme: $i$ $j$ ${\ displaystyle (n, m) \ v \ mathbb {N} ^ {2}}$ ${\ displaystyle \ mathbb {P} (X_ {n} = j \ mid X_ {0} = i)> 0}$ ${\ displaystyle \ mathbb {P} (X_ {m} = i \ střední X_ {0} = j)> 0.}$ $\ {j \ leftrightarrow i \} \ quad \ Leftrightarrow \ quad \ left \ {j \ leftarrow i {\ text {and}} i \ leftarrow j \ right \}.$

Vztah ke komunikaci , známý je vztah ekvivalence . Když mluvíme o třídě, když hovoříme o stavech Markovova řetězce, obecně se jedná o třídy ekvivalence pro vztah , o kterém mluvíme. Pokud všechny státy komunikují, říká se, že markovský řetězec je neredukovatelný . ${\ displaystyle \ leftrightarrow,}$ $\ leftrightarrow$

Vztah, který má být přístupný , se vztahuje na třídy ekvivalence: pro dvě třídy a , máme ${\ displaystyle \ leftarrow,}$ $VS$ ${\ displaystyle C ^ {\ prime}}$ $\ {C \ leftarrow C ^ {{\ prime}} \} \ quad \ Leftrightarrow \ quad \ left \ {\ existuje (i, j) \ v C \ krát C ^ {{\ prime}}, \ qquad i \ leftarrow j \ right \} \ quad \ Leftrightarrow \ quad \ left \ {\ forall (i, j) \ in C \ times C ^ {{\ prime}}, \ qquad i \ leftarrow j \ right \}.$

Relace je relační řád mezi třídami ekvivalence. $\ šipka vlevo$

Třída je považována za konečnou, pokud nevede k žádné jiné, tj. Pokud je třída pro vztah minimální , jinak se říká, že je přechodná . Příslušnost k finální nebo přechodné třídě má důsledky na pravděpodobnostní vlastnosti státu v Markovově řetězci, zejména na jeho stav jako opakující se stav nebo přechodný stav . Počet a povaha závěrečných tříd diktují strukturu souboru stacionárních pravděpodobností , které přesně shrnují asymptotické chování Markovova řetězce, jak je vidět v následující části a ve dvou příkladech podrobně popsaných na konci této stránky. ${\ displaystyle \ leftarrow.}$

Je $M _ {{ij}} = \ left \ {n \ geq 1 \ | \ p _ {{i, j}} ^ {{(n)}}> 0 \ right \}.$

Období o stavu je GCD sady li oba státy komunikují, mají stejnou periodu: proto můžeme hovořit o období třídy stavů. Pokud je perioda rovna 1, říká se, že třída je neperiodická . Aperiodicita stavů Markovova řetězce podmíňuje konvergenci zákona směrem ke stacionární pravděpodobnosti, viz stránka Stacionární pravděpodobnost Markovova řetězce . $i$ ${\ displaystyle M_ {ii}.}$ $X_ {n}$

Klasifikaci stavů a jejich období lze snadno přečíst na Markovově řetězovém grafu . Pokud jsou však všechny prvky přechodové matice přísně pozitivní, je Markovův řetězec neredukovatelný a neperiodický: kreslení grafu Markovova řetězce je potom nadbytečné.

Stacionární zákon

Definice

Ve stavovém prostoru může být jedno nebo více měření , například: ${\ displaystyle \ pi = (\ pi _ {i}) _ {i \ v E},}$ ${\ displaystyle E,}$ $\ pi = \ pi \, P,$ nebo dokonce $\ forall j \ in E, \ qquad \ pi _ {j} = \ sum _ {{i \ in E}} \ pi _ {i} \, p _ {{i, j}}.$

Takové měření se nazývá stacionární měření . Stacionární míra je vlastní funkce transpozice přechodové matice spojená s vlastní hodnotou 1. Nazývá se stacionární pravděpodobnost nebo stacionární zákon, pokud splňuje další podmínky: $\ pi$

$\ forall i \ in E, \ qquad \ pi _ {i} \ \ geq \ 0,$
$\ sum _ {{i \ in E}} \ pi _ {i} \ = \ 1.$

Pojem „ stacionární “ je odůvodněn následujícím návrhem:

Tvrzení - Pokud je původní zákon Markovova řetězce (tj. Zákon ) stacionární pravděpodobnost, pak pro celý zákon je $X_ {0}$ ${\ displaystyle \ pi,}$ ${\ displaystyle n \ geq 0,}$ $X_ {n}$ ${\ displaystyle \ pi.}$

Demonstrace

To vyplývá z vlastností sil přechodové matice uvedených výše: zákon μ n z X n je vyjádřen jako funkce zákona μ 0 z X 0 takto: nebo znamená ${\ displaystyle \ mu _ {n} = \ mu _ {0} P ^ {n} = \ pi P ^ {n},}$ ${\ displaystyle \ pi P = \ pi}$ ${\ displaystyle \ pi P ^ {n} = \ pi. \}$

Obecněji řečeno, Markovův řetězec je stacionární proces právě tehdy, je-li jeho počátečním zákonem stacionární pravděpodobnost .

Existence a jedinečnost

V případě diskrétních stavových prostorových Markovových řetězců určují určité vlastnosti procesu, zda existuje stacionární pravděpodobnost a zda je jedinečná nebo ne:

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é.

Pokud má Markovův řetězec alespoň jeden pozitivní rekurentní stav, pak existuje stacionární pravděpodobnost. Pokud existuje stacionární pravděpodobnost taková , pak je stav pozitivní rekurentní a naopak. $\ pi$ ${\ displaystyle \ pi _ {i}> 0}$ $i$

Věta - Pokud má Markovův řetězec pouze jednu závěrečnou třídu, existuje maximálně jedna stacionární pravděpodobnost. Pak máme ekvivalenci mezi 3 tvrzeními: ${\ displaystyle C,}$

existuje jedinečná stacionární pravděpodobnost ${\ displaystyle \ pi,}$
existuje pozitivní opakující se stav,
všechny stavy konečné třídy jsou pozitivní opakující se.

Máme také rovnocennost $\ {\ pi _ {i}> 0 \} \ Leftrightarrow \ {i \ v C \} \ Leftrightarrow \ {i {\ text {je opakující se pozitivní}} \}.$

Tato věta platí zejména pro neredukovatelné Markovovy řetězce, protože tyto mají pouze jednu třídu (což je tedy nutně konečná třída); ověřují se zejména neredukovatelné Markovovy řetězce ${\ displaystyle C = E.}$

Silný zákon velkého počtu a ergodicity

V případě neredukovatelného a opakujícího se pozitivního Markovova řetězce platí silný zákon velkého počtu : průměr funkce nad instancemi Markovova řetězce se rovná jeho průměru podle jeho stacionární pravděpodobnosti. Přesněji řečeno, za předpokladu $F$ $\ sum _ {{i \ in E}} | f (i) | \, \ pi _ {i} \ <+ \ infty,$ budeme mít téměř jistě : $\ lim _ {{n}} \; {\ frac {1} {n}} \; \ sum _ {{k = 0}} ^ {{n-1}} f (X_ {k}) \ = \ \ sum _ {{i \ in E}} f (i) \, \ pi _ {i} \ = \ \ pi f.$

Průměr hodnoty instancí se tedy dlouhodobě rovná očekávání podle stacionární pravděpodobnosti. Zejména tato rovnocennost s prostředky platí, pokud je indikátorová funkce podmnožiny stavového prostoru: $F$ $NA$ $\ lim _ {{n}} \; {\ frac {1} {n}} \; \ sum _ {{k = 0}} ^ {{n-1}} \ chi _ {A} (X_ {k }) \ = \ \ sum _ {{i \ v A}} \ \ pi _ {i} \ = \ \ pi (A).$

To umožňuje přiblížit se stacionární pravděpodobnosti empirickým rozložením (což je histogram sestrojený z konkrétní sekvence), jako v případě náhodné chůze s bariérou .

Zejména pokud je proces sestaven tak, že se jako počáteční zákon použije stacionární pravděpodobnost, je posun definován $\ theta$ $x = (x_ {0}, x_ {1}, x_ {2}, \ dots) \ in E ^ {{{\ mathbb {N}}}} \ quad \ rightarrow \ quad \ theta \, x = (x_ {1}, x_ {2}, x_ {3}, \ tečky)$ zachovává míru, díky níž je Markovův řetězec měřeným dynamickým systémem . Silný zákon velkého počtu vede k tomu, že Markovův řetězec je ergodický dynamický systém . Ergodicita je silnější než silný zákon velkého počtu, protože můžeme odvodit například to, že má téměř určitou hranici, ale je také slabší, protože v zásadě vyžaduje stacionaritu markovského řetězce, což u silných zákon velkých čísel. ${\ displaystyle {\ frac {1} {n}} \; \ součet _ {k = 0} ^ {n-1} f (X_ {k}, X_ {k + 1}),}$ ${\ displaystyle \ sum _ {i, j \ v E} f (i, j) \, \ pi _ {i} p_ {i, j},}$

Konvergence k stacionárnímu zákonu

V případě, že Markov řetěz je nesnížitelný , pozitivní recidivující a aperiodické, pak konverguje k matrici, z nichž každá řada je jedinečná pevná distribuce zejména zákon o konverguje k nezávisle na počáteční práva V případě stavového prostoru hotového, to je prokázáno Perron-Frobeniovou větou . Všimněte si, že je přirozené, že posloupnost definovaná indukcí relací má pro limit případně pevný bod této transformace, tj. Řešení rovnice ${\ displaystyle P ^ {k}}$ ${\ displaystyle \ pi.}$ $\ mu _ {n}$ $X_ {n}$ $\ pi$ ${\ displaystyle \ mu _ {0}.}$ ${\ displaystyle \ mu _ {n},}$ ${\ displaystyle \ mu _ {n + 1} = \ mu _ {n} P,}$ ${\ displaystyle \ pi = \ pi P.}$

Markovovy řetězce konečného stavu prostoru

Pokud je Markovův řetězec neredukovatelný a je-li jeho stavový prostor konečný, všechny jeho stavy se pozitivně opakují. Poté platí velký zákon velkého počtu.

Obecněji řečeno, všechny prvky konečné třídy jsou kladné opakující se, ať už je stavový prostor konečný nebo nekonečný spočetný.

Kvazi-stacionární distribuce absorbovaného Markovova řetězce

Nechť je Markovův řetězec přes množinu přirozených čísel . Předpokládejme, že stav 0 pohlcuje a řetězec je téměř jistě pohlcen na 0. Nechť je doba absorpce na 0. Říkáme, že pravděpodobnost zapnutí je kvazi-stacionární rozdělení, pokud pro všechny a pro všechny , $(X_ {n})$ ${\ displaystyle \ {0,1,2, ... \}}$ ${\ displaystyle T_ {0} = \ inf \ {n \ geq 0, X_ {n} = 0 \}}$ $\nahý$ ${\ displaystyle \ {1,2,3, ... \}}$ ${\ displaystyle j \ geq 1}$ $n \ geq 1$

{\ displaystyle \ sum _ {i \ geq 1} \ nu _ {i} \ mathbb {P} (X_ {n} = j | X_ {0} = i, T_ {0}> n) = \ nu _ { j}.}

Říkáme, že pravděpodobnost na je Yaglom omezení , pokud pro všechno a všechno , $\ mu$ ${\ displaystyle \ {1,2,3, ... \}}$ $i \ geq 1$ ${\ displaystyle j \ geq 1}$

{\ displaystyle \ lim _ {n \ to \ infty} \ mathbb {P} (X_ {n} = j | X_ {0} = i, T_ {0}> n) = \ mu _ {j}.}

Yaglomův limit je kvazi-stacionární distribuce . Pokud existuje, je Yaglomův limit jedinečný. Na druhou stranu může existovat několik kvazi-stacionárních distribucí.

Pokud je distribuce kvazi-stacionární, pak existuje reálné číslo takové, že . $\nahý$ ${\ displaystyle \ rho (\ nu) \ in] 0,1 [}$ ${\ displaystyle \ sum _ {i} \ nu _ {i} \ mathbb {P} (T_ {0}> n | X_ {0} = i) = \ rho (\ nu) ^ {n}}$

Hodnocení

Ve výše uvedených vzorcích je prvkem ( ) pravděpodobnost přechodu z do . Součet prvků řady je vždy roven 1 a stacionární rozdělení je dáno levým vlastním vektorem přechodové matice. $já, j$ $i$ $j$

Někdy se setkáváme s přechodovými maticemi, ve kterých je výraz ( ) pravděpodobností přechodu z do , v takovém případě je přechodová matice jednoduše transpozicí zde popsaného. Součet prvků sloupce má pak hodnotu 1. Kromě toho je pak stacionární rozdělení systému dáno pravým vlastním vektorem přechodové matice namísto levého vlastního vektoru. $já, j$ $j$ $i$

Příklad: Doudou křeček

Křeček Doudou zná ve své kleci pouze tři místa: hobliny, kde spí, krmítko, kde jí a kolo, kde cvičí. Jeho dny jsou si navzájem velmi podobné a jeho činnost snadno představuje markovský řetězec. Každou minutu může buď změnit svou činnost, nebo pokračovat v té, kterou dělal. Proces pojmenování bez paměti není vůbec přehnaný, když mluvíme o Doudou.

Když spí, má šanci 9 z 10, že se příští minutu neprobudí.
Když se probudí, je šance 1 ku 2, že půjde jíst, a šance 1 ku 2, že půjde cvičit.
Jídlo trvá jen minutu, po které udělá něco jiného.
Po jídle je šance 3 z 10, že si půjde zaběhat na kole, ale zejména 7 z 10, že se vrátí spát.
Běh je pro Doudou únavný; je šance 8 z 10, že se po minutě vrátí spát. Jinak stále zapomíná, že je už trochu unavený.

Diagramy

Grafy mohou zobrazit všechny šipky, z nichž každá představuje pravděpodobnost přechodu. Je však čitelnější, pokud:

nekreslíme šipky s nulovou pravděpodobností (přechod nemožný);
nebudeme kreslit smyčky (šipka stavu směrem k sobě) . Nicméně existují; jejich pravděpodobnost je naznačena, protože víme, že součet pravděpodobností šipek opouštějících každý stav musí být roven 1.

Příklad s implicitními smyčkami
Příklad s nakreslenými smyčkami

Matice přechodu

Matice přechodu tohoto systému je následující (řádky a sloupce odpovídají stavům znázorněným na čipu , podavači , grafu kola ): $P = {\ begin {bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\\ end {bmatrix}}$

Předpovědi

Předpokládejme, že Doudou spí během první minuty studia. ${\ mathbf {x}} ^ {{(0)}} = {\ begin {bmatrix} 1 & 0 & 0 \ end {bmatrix}}$

Po jedné minutě můžeme předpovědět: ${\ mathbf {x}} ^ {{(1)}} = {\ mathbf {x}} ^ {{(0)}} P = {\ begin {bmatrix} 1 & 0 & 0 \ end {bmatrix}} {\ begin {bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\\ end {bmatrix}} = {\ begin {bmatrix} 0,9 & 0,05 & 0,05 \ end {bmatrix} }$

Po jedné minutě tedy existuje 90% šance, že Doudou stále spí, 5% bude jíst a 5% bude běhat.

${\ mathbf {x}} ^ {{(2)}} = {\ mathbf {x}} ^ {{(1)}} P = {\ mathbf {x}} ^ {{(0)}} P ^ {2} = {\ begin {bmatrix} 1 & 0 & 0 \ end {bmatrix}} {\ begin {bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\\ konec {bmatrix}} ^ {2} = {\ begin {bmatrix} 0,885 & 0,045 & 0,07 \ end {bmatrix}}$

Po 2 minutách existuje 4,5% šance, že křeček sní.

Obecně řečeno, na minuty: $ne$ ${\ mathbf {x}} ^ {{(n)}} = {\ mathbf {x}} ^ {{(n-1)}} P$ a ${\ mathbf {x}} ^ {{(n)}} = {\ mathbf {x}} ^ {{(0)}} P ^ {n}$

Teorie ukazuje, že po určité době je zákon pravděpodobnosti nezávislý na původním zákoně. Všimněme si to : $q$ ${\ mathbf {q}} = \ lim _ {{n \ to \ infty}} {\ mathbf {x}} ^ {{(n)}}$

Konvergenci získáme tehdy a jen tehdy, pokud je řetězec neperiodický a neredukovatelný . To je případ našeho příkladu, abychom mohli napsat: ${\ begin {aligned} P & = {\ begin {bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\\ end {bmatrix}} \\ {\ mathbf {q} } P & = {\ mathbf {q}} \ qquad {\ mbox {(}} {\ mathbf {q}} {\ mbox {je invariantní zákon vzhledem k}} P {\ mbox {.)}} \ \ & = {\ mathbf {q}} I \\ {\ mathbf {q}} (IP) & = {\ mathbf {0}} \\ & = {\ mathbf {q}} \ vlevo ({\ start { bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\\ end {bmatrix}} - {\ begin {bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\\ end {bmatrix}} \ right) \\ & = {\ mathbf {q}} {\ begin {bmatrix} 0,1 & -0,05 & -0,05 \\ - 0,7 & 1 & -0,3 \ \ - 0,8 & 0 a 0, 8 \\\ end {bmatrix}} \\ & = {\ begin {bmatrix} q_ {1} & q_ {2} & q_ {3} \ end {bmatrix}} {\ begin {bmatrix} 0,1 & -0, 05 & -0,05 \\ - 0,7 & 1 & -0,3 \\ - 0,8 & 0 & 0,8 \\\ end {bmatrix}} \\ & = {\ begin {bmatrix} 0 & 0 a 0 \ end {bmatrix}} \ end {zarovnáno}}$

S vědomím toho získáváme: $q_ {1} + q_ {2} + q_ {3} = 1$ ${\ begin {bmatrix} q_ {1} & q_ {2} & q_ {3} \ end {bmatrix}} = {\ begin {bmatrix} 0,884 & 0,0442 & 0,0718 \ end {bmatrix}}$

Doudou proto tráví 88,4% svého času spánkem, 4,42% jídlem a 7,18% běháním.

Ilustrace dopadu modelu

Následující příklad si klade za cíl ukázat důležitost modelování systému. Dobré modelování umožňuje odpovídat na složité otázky pomocí jednoduchých výpočtů.

Studujeme (fiktivní) civilizaci složenou z několika společenských tříd a ve které se jednotlivci mohou pohybovat z jedné třídy do druhé. Každá fáze bude představovat jeden rok. Budeme uvažovat spíše o linii než o jednotlivci, abychom se vyhnuli získání dvoustých občanů. Existují čtyři různé sociální statusy:

otrok;
volný, uvolnit;
občan;
vysoký úředník.

V této společnosti:

otroci mohou zůstat otroky nebo se stát svobodnými muži (koupí svobody nebo svobodným osvobozením od svého pána);
svobodní muži mohou zůstat svobodní nebo jinak prodat svou svobodu (splácet své dluhy atd.) nebo se dokonce stát občany (opět ze zásluh nebo koupí titulu občana);
občané jsou občané na celý život a přenášejí své občanství na svou linii (dalo by se věřit, že počet občanů má tendenci se zvyšovat a že po určité době jsou všichni občané, ale historicky, v civilizacích, které se řídily tímto vzorem, jsou občané zdecimováni války a noví otroci pravidelně přicházejí ze zahraničí). Mohou také kandidovat ve výročních volbách a stát se vyššími úředníky (soudci). Na konci svého mandátu mohou být znovu zvoleni nebo se mohou znovu stát běžnými občany.

Abychom příklad trochu zkomplikovali a ukázali tak rozsah aplikací markovských řetězců, vezmeme v úvahu, že státní zaměstnanci jsou voleni na několik let. Budoucnost jednotlivého státního zaměstnance proto závisí na délce doby, kdy byl státním zaměstnancem. Jsme tedy v případě nehomogenního Markovova řetězce. Naštěstí se můžeme snadno vrátit k homogennímu řetězci. Skutečně stačí přidat umělý stav pro každý rok mandátu. Namísto stavu 4: Official , budeme mít stát:

4: Státní zaměstnanec na začátku svého funkčního období;
5: Státní zaměstnanec ve druhém funkčním období;
atd.

Pravděpodobnosti spojující dva po sobě jdoucí umělé stavy (například třetí a čtvrtý rok) mají hodnotu 1, protože se má za to, že jakýkoli spuštěný mandát končí (změnou hodnoty těchto pravděpodobností by se dal model opakovat). Stanovme dobu trvání mandátů na dva roky, přičemž kontingent státních zaměstnanců lze každý rok prodloužit o polovinu. Pak máme následující graf:

K modelování voleb, které nejsou každoroční, by bylo rovněž nutné přidat fiktivní státy (volební rok, jeden rok od posledních voleb atd.).

Matice se poté zapíše: $P$ ${\ mathbf {P}} = {\ begin {bmatrix} {\ frac {97} {98}} & {\ frac {1} {98}} & 0 & 0 & 0 \\ {\ frac {2} { 73}} & {\ frac {65} {73}} & {\ frac {6} {73}} & 0 & 0 \\ 0 & 0 & {\ frac {12} {13}} & {\ frac { 1} {13}} & 0 \\ 0 & 0 & 0 & 0 & 1 \ \ 0 & 0 & {\ frac {7} {8}} & {\ frac {1} {8}} & 0 \ end {bmatrix}}$

Jak je vysvětleno výše, uveďte pravděpodobnosti přechodu po etapách. Stejně tak je pravděpodobné, že po letech zůstanete ve státě pro linii, která je součástí společenské třídy . Chcete-li vědět, co se po letech stane s otrokem , stačí napsat: $P ^ {{n}}$ $ne$ $p _ {{ij}} ^ {{n}}$ $j$ $ne$ $i$ $ne$ ${\ displaystyle {\ begin {bmatrix} 1 & 0 & 0 & 0 & 0 \ end {bmatrix}} \ times \ mathbf {P} ^ {(n)} = {\ begin {bmatrix} p_ {1} ^ { (n)} & p_ {2} ^ {(n)} & p_ {3} ^ {(n)} & p_ {4} ^ {(n)} & p_ {5} ^ {(n)} \ end {bmatrix}}}$

Kde je pravděpodobnost, že po letech budete v sociální třídě s vědomím, že sledovaná linie opustila stát otroka? $p_ {i} ^ {{n}}$ $i$ $ne$

Pokud známe čísla každé sociální třídy v roce 0, stačí vypočítat: ${\ frac 1 {\ mathrm {lign {\ akutní e} es}}} \ krát {\ begin {bmatrix} {\ rm {otroci}} & {\ rm {zdarma}} & {\ rm {občané}} & {\ rm {{\ akutní e} lus_ {1}}} & {\ rm {{\ akutní e} lus_ {2}}} \ end {bmatrix}} \ times {\ mathbf P} ^ {{n}} = Y$

Získáme tak rozdělení populace v různých sociálních třídách (na konci let). Vynásobením tohoto vektoru celkovým počtem obyvatel získáme počty každé třídy na konci let. $ne$ $Y$ $ne$

Položme si nyní následující otázku: „Na konci let, kolik řádků již bude mít vysoký úředník, který dokončí svůj mandát?“ " $ne$

Odpověď se liší od počtu mandátů vykonaných v letech, protože existuje možnost opětovného zvolení. Odpovědi na tuto otázku se jeví jako obtížné (stále by to mělo být možné). Ve skutečnosti stačí změnit modelování problému. Pojďme tedy k novému modelu, abychom na tuto otázku odpověděli. (Na druhou stranu nám to neumožňuje odpovědět na předchozí otázky, tedy představení těchto dvou modelů.) $ne$

Postačí upravit graf následujícím způsobem:

Přidáme absorpční vršek, protože jakmile linka dokončí mandát, již se to nebere v úvahu.

Pokud jsou někteří čtenáři kritičtí, mohou říci, že model je špatný, protože linky s voleným úředníkem se již voleb neúčastní. Není to tak. Počet zvolených úředníků je ve skutečnosti úměrný počtu občanů. Nepřidělení bývalých vysokých úředníků mezi kandidáty proto nemění pravděpodobnost zvolení občana, protože počet obyvatel je menší a počet nabízených pozic je také. Tento model umožňuje přesně odpovědět na položenou otázku.

Proto máme novou přechodovou matici: ${\ mathbf {Q}} = {\ begin {bmatrix} {\ frac {97} {98}} & {\ frac {1} {98}} & 0 & 0 & 0 & 0 \\ {\ frac {2 } {73}} & {\ frac {65} {73}} & {\ frac {6} {73}} & 0 & 0 & 0 \\ 0 & 0 & {\ frac {12} {13}} & {\ frac {1} {13}} & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \ \ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \ end {bmatrix}}$

Provedením stejných výpočtů jako v předchozích otázkách získáme na posledním řádku vektoru řešení procento řádků, které mají dokončený alespoň jeden mandát, nebo počet (pokud vynásobíme celkovým počtem populace). Jinými slovy, opětovné modelování problému umožňuje odpovědět na otázku, která se zdála tak komplikovaná jednoduchým výpočtem sil matice.

Aplikace

Bernoulliho Proces je jednoduchý příklad Markov řetězce.
Markovian systémy jsou velmi přítomné ve fyzice, zejména ve statistické fyzice . Obecněji se Markovova hypotéza často vyvolává, když se k modelování stavu systému používají 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. Ačkoli jsou tyto modely jednoduché, umožňují dobře reprezentovat statistické vlastnosti systémů a provádět efektivní předpovědi bez popisu celé 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 jsou základem systémů Bonus / Malus vyvinutých pojistnými matematiky automobilových pojišťoven (pravděpodobnost n nehod v roce t je podmíněna počtem nehod v t-1)
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é Markovianovy 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 objev pseudogenů).

Poznámky a odkazy

Podívejte se také

Související články

Bibliografie

Bruno Sericola: Markovovy řetězce - teorie, algoritmy a aplikace . Hermes / Lavoisier, 2013.
Sylvie Méléard: Náhodné modely v ekologii a evoluci . Springer, 2016.
Řetězy Paolo Baldi, Laurent Mazliak, Pierre Priouret, Martingales a Markov. Elementární teorie a opravená cvičení , ( ISBN 2-7056-6425-4 ) , Hermann (edice) , 2001

externí odkazy

Philippe Gay, „ Markov a Šípková Růženka “ , na Images des Maths ,5. září 2014
(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 )