Markov lánc

A matematika , a Markov-lánc egy diszkrét idejű Markov-folyamat , vagy a folytonos idejű és diszkrét állapottér. A Markov-folyamat egy sztochasztikus folyamat, amely a Markov tulajdonsággal rendelkezik : a jövő előrejelzéséhez hasznos információ teljes egészében a folyamat jelenlegi állapotában található, és nem függ a korábbi állapotoktól (a rendszernek nincs "memóriája"). A Markov-folyamatokat feltalálójukról, Andrej Markovról nevezik el .

A diszkrét idejű Markov-folyamat egy sorozata a valószínűségi változók értékek az állam teret , amely azt fogja megjegyezni a következőket. Az érték az állam a folyamat abban a pillanatban. Az alkalmazások, ahol az állapottér véges vagy megszámlálható számtalan: az egyik beszél, majd a Markov-lánc , illetve a Markov-láncok diszkrét állapottér . Az általános Markov-folyamatok alapvető tulajdonságait , például a megismétlődés és az ergodicitás tulajdonságait egyszerűbben megfogalmazzák vagy bemutatják a diszkrét állapottérbeli Markov-láncok esetében . Ez a cikk pontosan a Markov diszkrét állapottérről szól . ${\ displaystyle X_ {0},}$ ${\ displaystyle X_ {1},}$ ${\ displaystyle X_ {2},}$ ${\ displaystyle X_ {3}, \ \ pöttyök$ $E$ $X_ {n}$ $nem.$ $E$

Andrej Markov 1906-ban publikálta az első eredményeket a véges állapotú űrbeli Markov-láncokról . A általánosítás megszámlálható végtelen állapottér tette közzé Kolmogorov a 1936 . A Markov-folyamatok összefüggenek a Brown-mozgással és az ergodikus hipotézissel , a statisztikai fizika két témájával, amelyek a XX . Század elején nagyon fontosak voltak .

Gyenge Markov-ingatlan

Definíciók

Ez a Markov-lánc jellemző tulajdonsága: a jövőnek a jelenből való előrejelzését nem pontosítják a múltat érintő további információk, mert a jövő előrejelzéséhez hasznos összes információ a jelenlegi állapotban található. a folyamat. A gyenge Markov-tulajdonságnak számos ekvivalens formája van, amelyek mind azt a megfigyelést jelentik, hogy a múlt idő ismeretének feltételes törvénye , vagyis a tudás csak a következő függvénye : $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) & \ E ^ {{n + 2}} , \\ {\ mathbb {P}} {\ Nagy (} X _ {{n + 1}} = j & \ közepes, X_ {0} = i_ {0}, X_ {1} = i_ {1} , \ ldots, X _ {{n-1}} = i _ {{n-1}}, X_ {n} = i {\ Big)} = {\ mathbb {P}} \ balra (X _ {{ n + 1}} = j \ X X közepe {n} = i \ jobb). \ end {igazítva}}$

A Markov-láncok egyik gyakori változata a homogén Markov-lánc , amelynél az átmenet valószínűsége független : $nem$ ${\ displaystyle \ forall n \ geq 1, \ forall (i, j) \ in E ^ {2}, \ quad \ mathbb {P} (X_ {n + 1} = j \ X X közepe {n} = i) = \ mathbb {P} (X_ {n} = j \ X X közepe {n-1} = i)}$

A cikk további részében csak homogén Markov-láncokat veszünk figyelembe. Egy érdekes alkalmazása nem homogén Markov-láncok a kombinatorikus optimalizálás , lásd a cikk szimulált hűtés . Van egy erős Markov-tulajdonság , amely az idő leállításának fogalmához kapcsolódik : ez az erős Markov-tulajdonság kulcsfontosságú a fontos eredmények igazolásához (különböző megismétlődési kritériumok, a Markov-láncok nagy számának erős törvénye). A " Markov tulajdonság " című cikkben szerepel .

Kritérium

Alapvető kritérium - Legyen ugyanazon törvény független, véletlen változóinak sorozata , térbeli értékekkel , és vagy mérhető térképpel . Tegyük fel, hogy a szekvenciát a megismétlődés relációja határozza meg: ${\ displaystyle Y = (Y_ {n}) _ {n \ geq 1}}$ $F$ $f$ $E \ -szer F$ ${\ displaystyle E.}$ ${\ displaystyle X = (X_ {n}) _ {n \ geq 0}}$ $\ forall n \ geq 0, \ qquad X _ {{n + 1}} = f \ bal (X_ {n}, Y _ {{n + 1}} \ jobb),$ és tegyük fel, hogy a szekvencia független azután Homogén Markov-lánc. $Y$ ${\ displaystyle X_ {0}.}$ $x$

Példa: a miniatűrök gyűjtőjének problémája :

Petit Pierre összegyűjti a labdarúgó-válogatott tizenegy játékosának portréját, amelyeket a csokoládé csomagolásának belsejében található matricákon talál; minden alkalommal, amikor tabletet vásárol, 1/11-es esélye van megtalálni a játékos (mindenre nézve ) portréját . Vegye figyelembe Pierre Petit gyűjteményének állapotát, miután kinyitotta e csokoládéjának csomagolását . egy Markov-lánc, amely indul , mivel az előző keretbe illeszkedik a választás óta $k$ $k$ ${\ displaystyle X_ {n} \ in {\ mathcal {P}} ([\! [1,11] \!])}$ $nem$ ${\ displaystyle X = (X_ {n}) _ {n \ geq 0}}$ ${\ displaystyle X_ {0} = \ emptyyset}$ ${\ displaystyle F = [\! [1,11] \!], \ E = {\ mathcal {P}} (F), \ f (x, y) = x \ csésze \ {y \},}$ $X _ {{n + 1}} = X_ {n} \ csésze \ {Y _ {{n + 1}} \},$ ahol a véletlenszerű változók egymástól függetlenek és egységesek : ezek a csokoládéból vett matricák egymás utáni számai. Az átlagos idő kell tölteniük a gyűjtemény (itt a tabletták számát, hogy Petit Pierre kell vásárolni átlagosan a teljes gyűjteménye) is, mert a gyűjtemény matrica összesen ahol a th harmonikus szám . Például csokoládé. ${\ displaystyle Y_ {n}}$ ${\ displaystyle [\! [1,11] \!]}$ $NEM$ ${\ displaystyle N \, H_ {N},}$ ${\ displaystyle H_ {N}}$ $NEM$ ${\ displaystyle 11 \, H_ {11} = 33,2 \ dots \ quad}$

Megjegyzések:

A Markov-tulajdonság a függetlenségéből származik, akkor is igaz marad, ha a különböző törvények vannak, és amikor a "megismétlődési viszony" függ. A függetlenség mellett tett feltételezések csak azért vannak, hogy biztosítsák a lánc Markogen általi homogenitását . ${\ displaystyle Y_ {i} \;}$ $Y_ {i}$ ${\ displaystyle X_ {n + 1} = f_ {n} \ bal (X_ {n}, Y_ {n + 1} \ jobb)}$ $nem.$
A kritérium alapvető, mivel bármely homogén Markov-lánc szimulálható a forma megismétlődésével egy jól megválasztott funkcióhoz . Akár független és egységes változókat is választhatunk és választhatunk a [0,1] intervallum felett, ami kényelmes Markov-láncok tanulmányozásához Monte-Carlo módszerekkel . ${\ displaystyle X_ {n + 1} = f \ bal (X_ {n}, Y_ {n + 1} \ jobb),}$ $f$ ${\ displaystyle F = [0,1],}$ ${\ displaystyle Y_ {j}}$

Átmenet valószínűségei

Meghatározás

Meghatározás - A számot nevezzük a valószínűsége állami to- állapotátmenet egy lépésben , vagy a valószínűsége állami to- állapotátmenet ha nincs kétértelműség. Gyakran megjegyezzük ezt a számot ${\ displaystyle \ mathbb {P} \ bal (X_ {1} = j \ X X közepe {0} = i \ jobb)}$ $én$ $j$ $én$ ${\ displaystyle j,}$ ${\ displaystyle p_ {i, j}:}$ $p _ {{i, j}} = {\ mathbb {P}} \ balra (X _ {{1}} = j \ X X közepe {0} = i \ jobbra).$

A családszámokat átmeneti mátrixnak , átmeneti magnak vagy a Markov-lánc átmenet-operátorának nevezzük . ${\ displaystyle P = \ left (p_ {i, j} \ right) _ {(i, j) \ in E ^ {2}}}$

A terminológia átmeneti mátrixa a leggyakrabban használt, de szigorúan véve csak akkor megfelelő, ha például egy egész szám esetén, amikor a véges, például a bíboros , mindig tetszőlegesen 1-től számozhatja az elemeket a problémát meghatározó elemekhez , de tökéletlenül mert ez az újraszámozás számos példában ellentmondásos. ${\ displaystyle n \ geq 1,}$ ${\ displaystyle E = \ {1,2, \ ldots, n \}.}$ $E$ ${\ displaystyle n,}$ $E$ ${\ displaystyle n,}$

Ehrenfest modell: a két kutya és bolháik:

Két kutya osztja a bolhákat az alábbiak szerint: minden pillanatban az egyik bolhát véletlenszerűen választják ki, majd egyik kutyáról a másikra ugrik. A rendszer állapotát egy olyan elem írja le, ahol $NEM$ $NEM$ ${\ displaystyle x = (x_ {1}, x_ {2}, \ pontok, x_ {N}) \ {0,1 \} ^ {N},}$ $x _ {{i}} = 0 {\ text {vagy}} 1 {\ text {attól függően, hogy a chip n}} ^ {{\ \}} \ i {\ text {az 1. vagy a 2. kutyán van-e .}}$

Így vannak elemei, de számozásuk 1-ről kényelmetlen lenne követni a rendszer evolúcióját, amely abból áll, hogy véletlenszerűen kiválasztjuk az egyik koordinátáját és megváltoztatjuk annak értékét. Ha kevésbé részletesen akarjuk megérteni a rendszert (mivel nem vagyunk képesek felismerni az egyik chipet a másiktól), akkor egyszerűen tanulmányozhatjuk az 1. számú kutya chipjeinek számát, ami annyit jelent, hogy újra meg kell választanunk , a megértéshez kár újraszámozni az állapotokat 1-ről Megjegyezzük, hogy ennek az új $E$ $2 ^ {N}$ $2 ^ {N}$ $NEM$ $x$ ${\ displaystyle E = \ {0,1,2, \ pont, N \}.}$ ${\ displaystyle N + 1.}$ $p _ {{k, k + 1}} = {\ tfrac {Nk} N} {\ text {et}} p _ {{k, k-1}} = {\ tfrac {k} N},$ mivel például az 1. számú kutya hátulján lévő zsetonok száma k- ről k-1- re halad, ha ezek közül a k zsetonok közül az egyiket választják ugrásra, a „rendszerben” található N zseton között . Ezt a modellt gyakrabban „ Ehrenfest Urns Model ” -nek nevezik . 1907-ben Tatiana és Paul Ehrenfest vezette be a kialakulóban lévő statisztikai mechanika alapjaiban felmerült "paradoxonok" szemléltetésére és a rózsaszínű zaj modellezésére . Az Ehrenfest urnamodellt Mark Kac matematikus úgy vélte , hogy "valószínűleg az egyik legtanulságosabb modell az egész fizikában".

Ahelyett, hogy az állapotokat újraszámozzuk 1-ről, ezért ergonómikusabb sok esetben elfogadni azokat a véges vagy végtelen mátrixokat, amelyek sorait és oszlopait "számozzuk" a két ilyen "mátrix" szorzata segítségével , és ezt aztán nagyon természetes módon definiáljuk. által ${\ displaystyle E.}$ ${\ displaystyle A = \ bal (a_ {i, j} \ jobb) _ {(i, j) \ E ^ -ban {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}},$ két négyzet alakú mátrix szorzatának klasszikusabb képletével analóg módon ${\ displaystyle n,}$ $(AB) _ {{i, j}} = \ sum _ {{k = 1}} ^ {n} a _ {{i, k}} b _ {{k, j}}.$

Tulajdonságok

Állítás - Az átmenet mátrix van sztochasztikus : az összege szempontjából minden sorban mindig ad 1. ${\ displaystyle P = \ left (p_ {i, j} \ right) _ {(i, j) \ in E ^ {2}}}$ $P$ $\ forall i \ E, \ quad \ sum _ {{j \ E}} p _ {{i, j}} = 1.$

Tétel - A törvény a Markov-lánc jellemzi a páros alkotja annak átmeneti mátrix és annak kezdeti joga (a törvény ): az összes közös törvénye adják ${\ displaystyle X = \ bal (X_ {n} \ jobb) _ {n \ geq 0}}$ ${\ displaystyle P,}$ $X_ {0}$ $n \ geq 1$ ${\ displaystyle (X_ {0}, X_ {1}, \ ldots, X_ {n})}$ ${\ mathbb {P}} \ balra (X _ {{0}} = i_ {0}, X _ {{1}} = i_ {1}, \ ldots, X _ {{n-1}} = i _ {{n -1}}, X _ {{n}} = i_ {n} \ jobbra) = {\ mathbb {P}} \ balra (X _ {{0}} = i_ {0} \ jobbra) \ p _ {{i_ {{0}}, i_ {1}}} \, p _ {{i _ {{1}}, i_ {2}}} \, \ ldots \, p _ {{i _ {{n-2}}, i _ {{n-1}}}} \, p _ {{i _ {{n-1}}, i_ {n}}}.$

Demonstráció

Indukcióval, a 0. rangban, ${\ mathbb {P}} \ left (X _ {{0}} = i_ {0} \ right) = {\ mathbb {P}} \ left (X _ {{0}} = i_ {0} \ right ).$

Sorban pózolva ${\ displaystyle n,}$ ${\ displaystyle P_ {k} = \ mathbb {P} \ balra (X_ {0} = i_ {0}, X_ {1} = i_ {1}, \ ldots, X_ {k-1} = i_ {k- 1}, X_ {k} = i_ {k} \ jobb),}$ ${\ frac {P_ {n}} {P _ {{n-1}}}} = {\ mathbb {P}} {\ Nagy (} X _ {{n}} = i_ {n} \ közepes \, X_ {0} = i_ {0}, X_ {1} = i_ {1}, \ ldots, X _ {{n-1}} = i _ {{n-1}} {\ Nagy)} = p _ {{i _ {{n-1}}, i_ {n}}},$ a gyenge Markov-tulajdonság miatt, tehát ha megvan a várt kifejezés, akkor is. ${\ displaystyle P_ {n-1}}$ $P_ {n}$

Amikor egy adott Markov-láncot vizsgálunk, annak átmeneti mátrixa általában jól meghatározott és rögzített a vizsgálat során, de a kezdeti törvény a vizsgálat során megváltozhat, és a jelöléseknek tükrözniük kell a pillanatban figyelembe vett kezdeti törvényt: ha a a tanulmány a Markov kezdeti eloszlásának láncolatát veszi figyelembe, amelyet akkor meghatározunk, a valószínűségeket és az elvárásokat figyelembe vesszük. Különösen, ha azt mondjuk, hogy a Markov-lánc a valószínűségekből indul ki , és az elvárásokat megjegyezzük ${\ displaystyle \ forall i \ E, \ quad \ mathbb {P} \ bal (X_ {0} = i \ right) = \ mu _ {i}, \ quad}$ ${\ displaystyle \ mathbb {P} _ {\ mu} \ bal (\ pöttyök \ jobb), \ quad}$ ${\ displaystyle \ mathbb {E} _ {\ mu} \ balra [\ dots \ right]. \ quad}$ ${\ displaystyle \ mathbb {P} \ bal (X_ {0} = j \ jobb) = 1, \ quad}$ ${\ displaystyle j, \ quad}$ ${\ displaystyle \ mathbb {P} _ {j} \ bal (\ pöttyök \ jobb), \ quad}$ ${\ displaystyle \ mathbb {E} _ {j} \ bal [\ dots \ right]. \ quad}$

Az átmeneti mátrix hatáskörei

A lépésben történő átmenet valószínűsége nem függ a következőktől : ${\ displaystyle k \ geq 1,}$ $k$ ${\ displaystyle \ mathbb {P} \ bal (X_ {n + k} = j \ X X közepe {n} = i \ jobb),}$ $nem$

Tétel - A átmenet mátrix lépéseket , egyenlő a teljesítmény -én az átmeneti mátrix Megjegyezzük $k$ ${\ displaystyle \ left (\ mathbb {P} \ left (X_ {n + k} = j \ X X közepe {n} = i \ right) \ right) _ {(i, j) \ E ^ -ban {2} },}$ $k$ $P.$ $p _ {{i, j}} ^ {{(k)}} = {\ mathbb {P}} \ bal (X _ {{n + k}} = j \ X X közepe {n} = i \ jobb) ,$ és $P ^ {k} = \ balra (p _ {{i, j}} ^ {{(k)}} \ jobbra) _ {{(i, j) \ E ^ {2}}} -ban.$

Demonstráció

Megismétlődéssel. Az 1. rangban ez a Markov-lánc homogenitásának következménye, amelyet a gyenge Markov-tulajdonság részben már említettünk : ${\ mathbb {P}} \ balra (X _ {{n + 1}} = j \ X közepére {n} = i \ jobbra) = {\ mathbb {P}} \ balra (X _ {{1}} = j \ X X közepe {0} = i \ right).$

Rang ${\ displaystyle k,}$ ${\ begin {aligned} {\ mathbb {P}} \ balra (X_ {n} = i {\ text {és}} X _ {{n + k}} = j \ right) & = \ sum _ {{ \ ell \ itt E}} {\ mathbb {P}} \ balra (X_ {n} = i, \, X _ {{n + k-1}} = \ ell {\ text {és}} X _ { {n + k}} = j \ jobbra) \\ & = \ sum _ {{\ \ \ \ E}}} {\ mathbb {P}} \ balra (X_ {n} = i, \, X _ {{ n + k- 1}} = \ ell \ jobb) \ {\ mathbb {P}} \ bal (X _ {{n + k}} = j \ X X közepe {n} = i, \, X _ {{ n + k-1}} = \ ell \ right) \\ & = \ sum _ {{\ ell \ E}}} {\ mathbb {P}} \ bal oldalon (X_ {n} = i, \, X _ {{n + k-1}} = \ ell \ jobb) \ p _ {{\ ell, j}} \\ & = {\ mathbb {P}} \ bal (X_ {n} = i \ jobb) \ \ sum _ {{\ ell \ in E}} p _ {{i, \ ell}} ^ {{(k-1)}} \ p _ {{\ ell, j}} \\ & = {\ mathbb {P}} \ balra (X_ {n} = i \ jobbra) \ p _ {{i, j}} ^ {{(k)}}, \ end {igazítva}}$ vagy

Az 1 -jén az egyenlőség a harmadik axióma a valószínűség ,
A 2 nd egyenlőség az a meghatározás, a feltételes valószínűség ,
A 3 -én egyenlőség miatt egyfajta alacsony Markov tulajdonság,
A 4 -én az egyenlőség a kiújulás tulajdonság nem ${\ displaystyle k-1,}$
Az 5 -én egyenlőség a képlet a termék két „tömbök”, alkalmazva a termék a ${\ displaystyle P ^ {k-1}}$ $P.$

Összegzésképpen felosztjuk ennek az egyenlőségsorozatnak a két szélső tagját , hacsak ez az utolsó tag nulla, ebben az esetben tetszőlegesen definiálhatjuk , ezért például egyenlő: ${\ displaystyle \ mathbb {P} \ bal (X_ {n} = i \ jobb),}$ ${\ displaystyle \ mathbb {P} \ bal (X_ {n + k} = j \ X X közepe {n} = i \ jobb)}$ ${\ displaystyle p_ {i, j} ^ {(k)}.}$

A teljes valószínűségi képlet egyszerű alkalmazásával levezetjük a Markov-lánc határtörvényeit.

Következmény - A törvény az adja ${\ displaystyle X_ {n + k}}$ ${\ mathbb {P}} \ balra (X _ {{n + k}} = j \ jobbra) = \ sum _ {{i \ E} -ben} {\ mathbb {P}} \ balra (X _ {{ n}} = i \ right) p _ {{i, j}} ^ {{(k)}}.$

Különösen, ${\ mathbb {P}} \ balra (X _ {{n}} = j \ jobbra) = \ sum _ {{i \ in E}} {\ mathbb {P}} \ balra (X _ {{0} } = i \ right) p _ {{i, j}} ^ {{(n)}}.$

A mátrixírásban, ha a törvényét vonalvektornak tekintjük , akkor az a következõvé formálódik: ${\ displaystyle X_ {n}}$ ${\ displaystyle \ mu _ {n} = (\ mu _ {n, i}) _ {i \ E} -ban,}$ ${\ displaystyle \ mu _ {n, i} = \ mathbb {P} \ bal (X_ {n} = i \ jobb),}$ $\ mu _ {{n + k}} = \ mu _ {{n}} P ^ {k} \ quad {\ text {és}} \ quad \ mu _ {{n}} = \ mu _ {{0 }} P ^ {n}.$

Az állapotok osztályozása

Mert azt mondjuk, hogy ez elérhető távolságra akkor és csak akkor létezik olyan, hogy jelöljük: ${\ displaystyle (i, j) \ E ^ nyelven {2}}$ $j$ $én$ $n \ geq 0$ ${\ displaystyle \ mathbb {P} (X_ {n} = j \ X X közepe {0} = i)> 0.}$ $\ {j \ leftarrow i \} \ quad \ Leftightrow \ quad \ left \ {\ pastāv n \ geq 0 {\ text {például}} p _ {{i, j}} ^ {{(n)}}> 0 \ jobb \}.$

Azt mondjuk, hogy és kommunikálni akkor és csak akkor, ha létezik olyan, hogy és mi jelöljük: $én$ $j$ ${\ displaystyle (n, m) \ in \ mathbb {N} ^ {2}}$ ${\ displaystyle \ mathbb {P} (X_ {n} = j \ X X közepe {0} = i)> 0}$ ${\ displaystyle \ mathbb {P} (X_ {m} = i \ X X közepe {0} = j)> 0.}$ $\ {j \ balra nyíl i \} \ quad \ balra nyíl \ quad \ balra \ {j \ balra nyíl i {\ text {és}} i \ balra nyílra \ jobbra \}.$

A kapcsolatban közli , megjegyezte egy ekvivalencia reláció . Amikor Markov-lánc állapotairól beszélünk osztályról, akkor általában az általunk hivatkozott reláció ekvivalenciaosztályaira vonatkozik. Ha minden állam kommunikál, akkor azt mondják, hogy a Markov-lánc nem olvasható . ${\ displaystyle \ leftrightarrow,}$ $\ leftrightarrow$

A hozzáférhető , megjelölt reláció kiterjed az egyenértékűségi osztályokra: két osztályra, és megvan ${\ displaystyle \ leftarrow,}$ $VS$ ${\ displaystyle C ^ {\ prime}}$ $\ {C \ balra nyíl C ^ {{\ prime}} \} \ quad \ Balra mutató nyíl \ quad \ balra \ {\ létezik (i, j) \ C-szer C ^ {{\ prime}}, \ qquad i \ balra nyíl j \ jobb \} \ quad \ Balra nyíl \ quad \ balra \ {\ összes (i, j) \ C-szer C ^ C {{\ prime}}, \ qquad i \ balra nyíl \ jobb \}.$

A reláció egy megbízás kapcsán az ekvivalencia osztályok. $\ bal nyíl$

Egy osztály akkor mondható véglegesnek, ha nem vezet máshoz, azaz ha az osztály minimális a relációhoz, ellenkező esetben átmenetinek mondják . A végső vagy átmeneti osztályhoz való tartozás következményekkel jár a Markov-lánc egy állapotának valószínűségi tulajdonságaira, különös tekintettel a visszatérő vagy átmeneti állapot állapotára . Az utolsó osztályok száma és jellege diktálja az álló valószínűségek halmazának felépítését , amely pontosan összefoglalja a Markov-lánc aszimptotikus viselkedését, amint az a következő szakaszban és az oldal végén részletezett két példában is látható . ${\ displaystyle \ leftarrow.}$

Is $M _ {{ij}} = \ bal \ {n \ geq 1 \ | \ p _ {{i, j}} ^ {{(n)}}> 0 \ jobb \}.$

Az időszak az állam a legnagyobb közös osztója a készlet. Ha két állam közli, ezek ugyanabban az időszakban: tudjuk, ezért beszélünk az időszak egy osztály államok. Ha a periódus 1, akkor az osztály aperiodikusnak mondható . A Markov-lánc állapotainak aperiodicitása feltételezi a törvény konvergenciáját az álló valószínűség felé, lásd a Markov-lánc stacionárius valószínűsége című oldalt . $én$ ${\ displaystyle M_ {ii}.}$ $X_ {n}$

Az állapotok osztályozása és periódusuk könnyen olvasható a Markov-lánc grafikonon . Ha azonban az átmeneti mátrix minden eleme szigorúan pozitív, akkor a Markov-lánc nem redukálható és aperiodikus: a Markov-lánc grafikonjának megrajzolása felesleges.

Helyhez kötött törvény

Meghatározás

Egy vagy több mérés lehet az állapottérben , például: ${\ displaystyle \ pi = (\ pi _ {i}) _ {i \ E} -ban,}$ ${\ displaystyle E,}$ $\ pi = \ pi \, P,$ vagy akár $\ for j j E-ben, \ qquad \ pi _ {j} = \ sum _ {{i \ E}} \ pi _ {i} \, p _ {{i, j}}.$

Az ilyen mérést helyhez kötött mérésnek nevezzük . A stacionárius mérték az átmeneti mátrix transzpozíciójának sajátfüggvénye , az 1. sajátértékhez társítva . Stacionárius valószínűségnek vagy stacionárius törvénynek nevezzük, ha megfelel a további feltételeknek: $\ pi$

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

Az " álló " kifejezést a következő javaslat igazolja:

Állítás - Ha a kezdeti törvény a Markov-lánc (azaz a törvény a ) egy helyhez kötött valószínűsége akkor minden törvénye még mindig $X_ {0}$ ${\ displaystyle \ pi,}$ ${\ displaystyle n \ geq 0,}$ $X_ {n}$ ${\ displaystyle \ pi.}$

Demonstráció

Ez következik a tulajdonságok a hatáskörét az átmenet mátrix fent megadott: a törvény μ n az X n függvényében fejezzük a törvény μ 0 a X 0 a következőképpen: vagy maga után vonja ${\ displaystyle \ mu _ {n} = \ mu _ {0} P ^ {n} = \ pi P ^ {n},}$ ${\ displaystyle \ pi P = \ pi}$ ${\ displaystyle \ pi P ^ {n} = \ pi. \}$

Általánosabban fogalmazva, a Markov-lánc akkor és csak akkor helyhez kötött folyamat, ha kezdeti törvénye statikus valószínűségű .

Létezés és egyediség

Diszkrét állapottérbeli Markov-láncok esetén a folyamat bizonyos tulajdonságai meghatározzák, hogy van-e álló valószínűség, és hogy egyedi-e vagy sem:

egy Markov-lánc visszavonhatatlan, ha bármely állam hozzáférhető bármely más államtól;
egy állapot visszatérő pozitív, ha az ebbe az állapotba való első visszatérés idejének várakozása véges.

Ha egy Markov-láncnak van legalább egy pozitív visszatérő állapota, akkor helyhez kötött valószínűség van. Ha van olyan helyhez kötött valószínűség , hogy az állapot pozitív visszatérő, és fordítva. $\ pi$ ${\ displaystyle \ pi _ {i}> 0}$ $én$

Tétel - Ha egy Markov-láncnak csak egy végső osztálya van, akkor legfeljebb egy álló helyzet valószínűsége van. Ekkor ekvivalenciánk van a 3 javaslat között: ${\ displaystyle C,}$

egyedülálló helyhez kötött valószínűség van megállapítva ${\ displaystyle \ pi,}$
pozitív visszatérő állapot van,
a végső osztály összes állapota pozitív visszatérő.

Megvan az egyenértékűség is $\ {\ pi _ {i}> 0 \} \ Balra nyíl \ {i \ a C \} \ Balra nyílra \ {i {\ text {visszatérő pozitív}} \}.$

Ez a tétel különösen érvényes a redukálhatatlan Markov-láncokra, mivel ez utóbbiaknak csak egy osztálya van (ami tehát szükségszerűen végső osztály); a redukálhatatlan Markov-láncok különösen igazolják ${\ displaystyle C = E.}$

Erős törvény a nagy számokról és az ergodicitásról

Redukálhatatlan és visszatérő pozitív Markov- lánc esetén a nagy számok erős törvénye van érvényben: a függvény átlaga a Markov-lánc eseteinél megegyezik az átlagával a helyhez kötött valószínűség szerint. Pontosabban a feltételezés alatt $f$ $\ sum _ {{i \ in E}} | f (i) | \, \ pi _ {i} \ <+ \ infty,$ mi szinte biztos, hogy : $\ lim _ {{n}} \; {\ frac {1} {n}} \; \ sum _ {{k = 0}} ^ {{n-1}} f (X_ {k}) \ = \ \ sum _ {{i \ in E}} f (i) \, \ pi _ {i} \ = \ \ pi f.$

A példányok átlagának átlaga tehát hosszú távon megegyezik az álló valószínűség szerinti várakozással. Különösen ez az egyenértékűség az eszközöket kell alkalmazni, ha az indikátor függvény egy részhalmaza az állapottér: $f$ $NÁL NÉL$ $\ lim _ {{n}} \; {\ frac {1} {n}} \; \ sum _ {{k = 0}} ^ {{n-1}} \ chi _ {A} (X_ {k }) \ = \ \ sum _ {{i \ in A}} \ \ pi _ {i} \ = \ \ pi (A).$

Ez lehetővé teszi az álló helyzet valószínűségének megközelítését az empirikus eloszlás révén (amely egy adott szekvenciából felépített hisztogram ), mint például a véletlenszerű, gáttal történő járás esetén .

Különösen akkor, ha az eljárás épül azáltal, hogy a helyhez kötött valószínűsége, mint az eredeti törvény szerint a váltás által meghatározott $\ theta$ $x = (x_ {0}, x_ {1}, x_ {2}, \ pontok) \ E ^ {{{{\ mathbb {N}}}} \ quad \ rightarrow \ quad \ theta \, x = (x_ {1}, x_ {2}, x_ {3}, \ pont)$ megőrzi a mértéket, ami a Markov-láncot mért dinamikus rendszerré teszi . A nagy számok erős törvénye azt eredményezi, hogy a Markov-lánc ergodikus dinamikus rendszer . Az ergodicitás ugyanakkor erősebb, mint a nagy számok erős törvénye, mert következtethetünk például arra, hogy majdnem egy bizonyos határig van, de gyengébb is, mert elvileg megköveteli a Markov-lánc állékonyságát, ami nem így van a nagy számok erős törvényével. ${\ displaystyle {\ frac {1} {n}} \; \ sum _ {k = 0} ^ {n-1} f (X_ {k}, X_ {k + 1}),}$ ${\ displaystyle \ sum _ {i, j \ E} f (i, j) \, \ pi _ {i} p_ {i, j},}$

Konvergencia az álló törvény felé

Ha a Markov-lánc nem redukálható , pozitív visszatérő és aperiodikus, akkor konvergál egy olyan mátrixhoz, amelynek minden sora az egyedi álló eloszlás . Különösen a konvergencia törvénye konvergál a kezdeti törvénytől függetlenül. Kész állapotállapot esetén ez: a Perron-Frobenius-tétel bizonyítja . Ne feledje, hogy természetes, hogy a reláció által indukcióval meghatározott szekvencia korlátozhatja ennek az átalakításnak egy fix pontját , azaz az egyenlet megoldását ${\ 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.}$

Véges állapottér Markov láncok

Ha egy Markov-lánc nem redukálható, és ha az állapottere véges, akkor az összes állapota pozitív visszatérő. Ekkor a nagy számok erős törvénye van érvényben.

Általánosabban véve a véges végső osztály minden eleme pozitív visszatérő, függetlenül attól, hogy az állapottér véges vagy végtelen megszámolható-e.

Egy abszorbeált Markov-lánc kvázi stacionárius eloszlása

Legyen Markov-lánc a természetes számok halmazán . Tegyük fel, hogy a 0 állapot abszorbeálja, és a lánc szinte biztosan abszorbeálódik 0-nál. Hagy az abszorpciós idő 0. Azt mondjuk, hogy egy valószínűségi on egy kvázi-stacionárius eloszlás, ha minden és mindenki számára , $(X_ {n})$ ${\ displaystyle \ {0,1,2, ... \}}$ ${\ displaystyle T_ {0} = \ inf \ {n \ geq 0, X_ {n} = 0 \}}$ $\meztelen$ ${\ 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}.}

Azt mondjuk, hogy egy valószínűségi on egy Yaglom határt , ha mindent , és mindent , $\ 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}.}

A Yaglom-határ kvázi stacionárius eloszlás . Ha létezik, akkor a Yaglom határérték egyedi. Másrészt több kvázi stacionárius eloszlás is lehet.

Ha kvázi stacionárius eloszlás van, akkor létezik olyan valós szám , amely . $\meztelen$ ${\ displaystyle \ rho (\ nu) \ in] 0,1 [}$ ${\ displaystyle \ sum _ {i} \ nu _ {i} \ mathbb {P} (T_ {0}> n | X_ {0} = i) = \ rho (\ nu) ^ {n}}$

Értékelés

A fenti képletekben, az elem ( ) annak a valószínűsége, a átmenet a . Egy sor elemeinek összege mindig egyenlő 1-vel, és az álló eloszlást az átmeneti mátrix bal sajátvektora adja meg. $i, j$ $én$ $j$

Néha találkozunk mátrixait, amelyben a kifejezést ( ) annak a valószínűsége, átmenet a , amely esetben az átmenet mátrix egyszerűen a transzponáltja az, hogy az itt leírt. Az oszlop elemeinek összege ekkor 1-et ér. Sőt, a rendszer stacionárius eloszlását ezután az átmeneti mátrix jobb oldali sajátvektora adja meg a bal sajátvektor helyett. $i, j$ $j$ $én$

Példa: Doudou a hörcsög

Doudou hörcsög csak három helyet ismer ketrecében: a forgácsot, ahol alszik, az etetőt, ahol eszik, és a kereket, ahol gyakorol. Napjai meglehetősen hasonlítanak egymásra, és tevékenységét könnyen képviseli egy Markov-lánc. Minden percben megváltoztathatja tevékenységét, vagy folytathatja azt, amit végzett. Az emlékezet nélküli névfolyamat egyáltalán nem túlzó, ha Doudou-ról beszélünk.

Amikor alszik, akkor 9 esély van a 10-re, hogy a következő percben nem ébred fel.
Amikor felébred, akkor 1: 2 esély van arra, hogy enni fog, és 1: 2 esély, hogy elmegy edzeni.
Az étkezés csak egy percig tart, utána mást csinál.
Evés után van esély 3-ból 10-be, hogy futni megy a kerekében, de főleg 7-ből 10-re van esély, hogy visszaalszik.
A futás fárasztó Doudou számára; 10-ből van esély arra, hogy egy perc múlva visszaaludjon. Egyébként továbbra is elfelejti, hogy már egy kicsit fáradt.

Diagramok

A diagramok megmutathatják az összes nyilat, mindegyik az átmenet valószínűségét képviseli. Azonban olvashatóbb, ha:

nem rajzoljuk a nulla valószínűségű nyilakat (az átmenet lehetetlen);
nem húzzuk a hurkokat (egy állam nyilát maga felé) . Azonban léteznek; valószínűségük implikált, mert tudjuk, hogy az egyes állapotokból távozó nyilak valószínűségének összegének egyenlőnek kell lennie 1-vel.

Példa implicit hurokkal
Példa rajzolt hurkokkal

Átmeneti mátrix

Az átmenet mátrixa ez a rendszer a következő (a sorok és oszlopok megfelelnek annak érdekében, hogy a képviselt Államok a chip , feeder , kerék grafikon ): $P = {\ begin {bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\\ end {bmatrix}}$

Előrejelzések

Tegyük fel, hogy Doudou a vizsgálat első percében alszik. ${\ mathbf {x}} ^ {{(0)}} = {\ elején {bmatrix} 1 és 0 és 0 \ vége {bmatrix}}$

Egy perc múlva megjósolhatjuk: ${\ mathbf {x}} ^ {{(1)}} = {\ mathbf {x}} ^ {{(0)}} P = {\ elején {bmatrix} 1 & 0 és 0 \ vége {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} }$

Így egy perc elteltével 90% az esély arra, hogy Doudou még mindig alszik, 5% -kal eszik és 5% -kal fut.

${\ mathbf {x}} ^ {{(2)}} = {\ mathbf {x}} ^ {{(1)}} P = {\ mathbf {x}} ^ {{(0)}} P ^ {2} = {\ eleje {bmatrix} 1 & 0 & 0 \ vége {bmatrix}} {\ eleje {bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 és 0,2 \\\ vége {bmatrix}} ^ {2} = {\ kezdete {bmatrix} 0,885 és 0,045 és 0,07 \ vége {bmatrix}}$

2 perc elteltével 4,5% az esély, hogy a hörcsög megeszi.

Általánosságban elmondható, hogy percekig: $nem$ ${\ mathbf {x}} ^ {{(n)}} = {\ mathbf {x}} ^ {{(n-1)}} P$ és ${\ mathbf {x}} ^ {{(n)}} = {\ mathbf {x}} ^ {{(0)}} P ^ {n}$

Az elmélet azt mutatja, hogy egy bizonyos idő elteltével a valószínűség törvénye független az eredeti törvénytől. Vegye figyelembe : $q$ ${\ mathbf {q}} = \ lim _ {{n \ to \ infty}} {\ mathbf {x}} ^ {{(n)}}$

A konvergenciát akkor és csak akkor érjük el, ha a lánc aperiodikus és nem redukálható . Példánkban ez a helyzet, így írhatjuk: ${\ 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 {az invariáns törvény a}} P {\ mbox {.)}} \ Vonatkozásában \ & = {\ mathbf {q}} I \\ {\ mathbf {q}} (IP) & = {\ mathbf {0}} \\ & = {\ mathbf {q}} \ balra ({\ begin { 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 és 0 és 0,2 \\\ vége {bmatrix}} \ jobbra) \\ & = {\ mathbf {q}} {\ elején {bmatrix} 0,1 és -0,05 és -0,05 \\ - 0,7 és 1 és -0,3 \ \ - 0.8 és 0 & 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 és 0 \ end {bmatrix}} \ end {aligned}}$

Ennek tudatában megkapjuk: $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 ezért ideje 88,4% -át alvással, 4,42% -át eszik és 7,18% -át futja.

A modell hatásának illusztrációja

Az alábbi példa a rendszer modellezésének fontosságát kívánja bemutatni. A jó modellezés lehetővé teszi az összetett kérdések megválaszolását egyszerű számításokkal.

Tanulmányozunk egy (fiktív) civilizációt, amely több társadalmi osztályból áll, és amelyben az egyének egyik osztályból a másikba mozoghatnak. Minden szakasz egy évet jelent. Az egyén helyett inkább egy vonalat fogunk figyelembe venni, hogy elkerüljük a kétszázéves állampolgárok megszerzését. Négy különböző társadalmi állapot létezik:

rabszolga ;
ingyenes;
polgár;
magas tisztviselő.

Ebben a társaságban:

a rabszolgák rabszolgák maradhatnak, vagy szabad emberekké válhatnak (megvásárolva szabadságukat, vagy azzal, hogy gazdájuk liberálisan kiszabadítja őket);
a szabad férfiak szabadok maradhatnak, vagy eladhatják szabadságukat (adósságaik megfizetéséhez stb.), vagy akár állampolgárokká válhatnak (ismét érdemekből vagy állampolgári cím megvásárlásával);
az állampolgárok egy életre állampolgárok, és átadják állampolgárságukat származásuknak (azt hihetnénk, hogy az állampolgárok száma növekszik, és hogy egy bizonyos idő után mindenki állampolgár, de történelmileg az ezt a mintát követő civilizációkban az állampolgárok a háborúk és az új rabszolgák rendszeresen érkeznek külföldről). Éves választásokon jelöltként is állhatnak magas rangú tisztviselőkké (bírák). Megbízatásuk lejártával újraválaszthatók, vagy újra rendes állampolgárokká válhatnak.

Hogy kissé bonyolítsuk a példát, és így megmutassuk Markov-láncok alkalmazásának mértékét, figyelembe vesszük, hogy a köztisztviselőket több évre választják meg. Ezért az egyes köztisztviselők jövője attól függ, mennyi ideig volt köztisztviselő. Ezért nem homogén Markov-lánc esetében vagyunk. Szerencsére könnyen visszatérhetünk egy homogén lánchoz. Valójában elegendő egy mesterséges állapot hozzáadása a megbízatás minden évéhez. Ahelyett, hogy lenne egy 4-es állapot: Hivatalos , lesz egy államunk:

4 .: köztisztviselő hivatali ideje kezdetén;
5 .: köztisztviselő a megbízatás második évében;
stb.

A két egymást követő mesterséges állapotot összekötő valószínűségek (például a harmadik és a negyedik év) értéke 1, mivel az ember úgy gondolja, hogy bármely megkezdett megbízás véget ér (ennek az ellenkezőjét modellezhetjük a valószínűségek értékének megváltoztatásával). Rögzítsük a megbízások időtartamát két évre, a köztisztviselők kontingensét évente felére megújítva. Ezután a következő grafikon áll rendelkezésünkre:

A nem éves választások modellezéséhez fiktív államok hozzáadására is szükség lenne (választási év, a legutóbbi választások óta eltelt egy év stb.).

Ezután a mátrixot felírják: $P$ ${\ mathbf {P}} = {\ begin {bmatrix} {\ frac {97} {98}} & {\ frac {1} {98}} & 0 & 0 & 0 \\ {\ frac {2} { 73}} és {\ frac {65} {73}} és {\ frac {6} {73}} és 0 és 0 \\ 0 és 0 és {\ frac {12} {13}} és {\ frac { 1} {13}} & 0 \\ 0 & 0 & 0 & 0 & 1 \ \ 0 & 0 & {\ frac {7} {8}} és {\ frac {1} {8}} és 0 \ end {bmatrix}}$

Amint azt fentebb kifejtettük, adja meg az átmenet valószínűségét szakaszokban. Ugyanígy annak valószínűsége, hogy évek múlva államban lehetek egy olyan vonal után , amely a társadalmi osztály része . Ahhoz, hogy tudjuk, mi lesz a rabszolgával évek múlva, elég megírnunk: $P ^ {{n}}$ $nem$ $p _ {{ij}} ^ {{n}}$ $j$ $nem$ $én$ $nem$ ${\ displaystyle {\ begin {bmatrix} 1 & 0 & 0 & 0 & 0 \ end {bmatrix}} \ times \ mathbf {P} ^ {(n)} = {\ begin {bmatrix} p_ {1} ^ { (n)} & p_ {2} ^ {(n)} és p_ {3} ^ {(n)} és p_ {4} ^ {(n)} és p_ {5} ^ {(n)} \ end {bmatrix}}}$

Hol van annak a valószínűsége, hogy társadalmi osztályba kerülünk évek után, ha tudjuk, hogy a vizsgált vonal elhagyta a rabszolgaság állapotát? $p_ {i} ^ {{n}}$ $én$ $nem$

Ha ismerjük az egyes társadalmi osztályok számát a 0. évben, elegendő kiszámítani: ${\ frac 1 {\ mathrm {lign {\ akut e} es}}} \ alkalommal {\ begin {bmatrix} {\ rm {slaves}} & {\ rm {free}} és {\ rm {polgárok}} & {\ rm {{\ akut e} lus_ {1}}} és {\ rm {{\ akut e} lus_ {2}}} \ vég {bmatrix}} \ szor {\ mathbf P} ^ {{n}} = Y$

Így megkapjuk a népesség megoszlását a különböző társadalmi osztályokban ( évek után ). Ha ezt a vektort megszorozzuk a populáció teljes számával, megkapjuk az egyes osztályok számát az évek végén . $nem$ $Y$ $nem$

Tegyük fel magunknak a következő kérdést: "Az évek végén hány sorban lesz már egy magas tisztviselő, aki befejezte mandátumát?" " $nem$

A válasz eltér az évek során elvégzett megbízások számától, mert fennáll az újraválasztás lehetősége. A kérdés megválaszolása nehéznek tűnik (ennek még mindig lehetségesnek kell lennie). Valójában elegendő megváltoztatni a probléma modellezését. Tehát térjünk át egy új modellre, hogy megválaszoljuk ezt a kérdést. (Másrészt ez nem teszi lehetővé az előző kérdések megválaszolását, ezért a két modell bemutatása.) $nem$

Elegendő a grafikont a következőképpen módosítani:

Abszorbeáló felsőt adunk hozzá, mert ha egy sor befejezte a megbízást, akkor azt már nem veszik figyelembe.

Ha egyes olvasók kritikusak, azt mondhatják, hogy a modell téves, mert a megválasztott tisztviselővel folytatott vonalak már nem vesznek részt a választásokon. Nem így van. Valójában a megválasztott tisztviselők száma arányos a polgárok számával. A korábbi magas rangú tisztviselők visszavonása a jelöltek közé tehát nem változtatja meg annak a valószínűségét, hogy egy állampolgárt megválasztanak, mert mivel az állampolgárok száma kisebb, a felajánlott pozíciók száma is megnő. Ez a modell lehetővé teszi a feltett kérdés pontos megválaszolását.

Ezért van egy új átmeneti mátrixunk: ${\ mathbf {Q}} = {\ begin {bmatrix} {\ frac {97} {98}} & {\ frac {1} {98}} & 0 & 0 & 0 & 0 \\ {\ frac {2 } {73}} és {\ frac {65} {73}} és {\ frac {6} {73}} és 0 és 0 és 0 \\ 0 és 0 és {\ frac {12} {13}} és {\ frac {1} {13}} & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \ \ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 0 és 1 \ end {bmatrix}}$

Az előző kérdésekkel megegyező számítások elvégzésével a megoldás vektor utolsó sorában megkapjuk a legalább egy megbízást teljesítő sorok százalékos arányát vagy számát (ha szorozzuk a populáció teljes számával). Más szavakkal, a probléma újbóli modellezése lehetővé teszi a kérdés megválaszolását, amely annyira bonyolultnak tűnt a mátrix teljesítményének egyszerű kiszámításával.

Alkalmazások

A Bernoulli-folyamat a Markov-lánc egyszerű példája.
A markovi rendszerek nagyon jelen vannak a fizikában, különösen a statisztikai fizikában . Általánosságban elmondható, hogy a Markov-féle hipotézisre gyakran hivatkoznak, ha a rendszer állapotának modellezésére valószínűségeket alkalmaznak, feltételezve azonban, hogy a rendszer jövőbeli állapota levezethető a meglehetősen alacsony múltú múltból.
Az információelméletet megalapozó Claude Shannon , a kommunikáció matematikai elmélete 1948-ban készült híres cikke az entrópia fogalmának bevezetésével kezdődik az angol nyelv Markov-modellezéséből . Ez megmutatja az angol nyelv kiszámíthatóságának mértékét, az 1. sorrend egyszerű modelljével ellátva. Bár egyszerűek, az ilyen modellek lehetővé teszik a rendszerek statisztikai tulajdonságainak jó ábrázolását és hatékony előrejelzéseket anélkül, hogy a teljes szerkezetet leírnánk.
A tömörítés során a Markovian-modellezés lehetővé teszi nagyon hatékony entrópia kódolási technikák, például aritmetikai kódolás megvalósítását . Számos algoritmus a mintafelismerésben vagy a mesterséges intelligenciában, mint például a Viterbi algoritmus , amelyet a mobiltelefon-rendszerek túlnyomó többségében hibajavításra használnak, egy alapjául szolgáló Markov-folyamatot feltételez.
A Google által használt weboldal ( PageRank ) népszerűségi indexét egy Markov-lánc határozza meg. Meghatározza annak valószínűsége, hogy ezen az oldalon tartózkodik a Markov lánc bármely, a webet képviselő állapotából. Ha meg van az ismert weboldalak száma, és egy oldalnak vannak linkjei, akkor annak valószínűsége, hogy áttér egy összekapcsolt oldalra (amelyre mutat), és minden más (nem kapcsolódó oldal) esetén. Vegye figyelembe, hogy van . A paraméter körülbelül 0,15. $NEM$ $én$ $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$
A Markov-láncok alapvető eszközök a folyamatok modellezésében a sorelméletben és a statisztikában .
A Markov-láncokat általában a megbízhatóságban használják a műszaki rendszerek megbízhatóságának és elérhetőségének kiszámításához , különösen az eseménysorozatok hibatípusának modellezéséhez, javításához, konfigurációs változtatásaihoz.
A Markov-láncok képezik az autóbiztosító társaságok aktuáriusai által kifejlesztett Bonus / Malus rendszerek alapját (annak valószínűségét, hogy t évben n balesetet szenvedünk, a t-1-ben bekövetkezett balesetek száma függ)
A Markov-láncokat a bioinformatikában is felhasználják az azonos szekvencia egymást követő szimbólumai ( például a nukleotidok ) közötti kapcsolatok modellezésére , túllépve a polinom modellen. A rejtett Markov-modelleknek különféle felhasználási lehetőségeik vannak, például szegmentálás (regionális határok meghatározása különböző kémiai tulajdonságú gének vagy fehérjék szekvenciáin belül ), többszörös illesztés , funkció előrejelzése vagy génfelfedezés (a rejtett Markov-modellek "rugalmasabbak", mint a a start- kodon + több kodon + stop-kodon szigorú meghatározása, ezért alkalmasabbak eukarióták számára (mivel ezek genomjában intronok vannak) vagy álgének felfedezésére.

Megjegyzések és hivatkozások

Lásd is

Kapcsolódó cikkek

Bibliográfia

Bruno Sericola: Markov-láncok - Elmélet, algoritmusok és alkalmazások . Hermes / Lavoisier, 2013.
Sylvie Méléard: Véletlenszerű modellek az ökológiában és az evolúcióban . Springer, 2016.
Paolo Baldi, Laurent Mazliak, Pierre Priouret, Martingales és Markov láncok. Elemi elmélet és javított gyakorlatok , ( ISBN 2-7056-6425-4 ) , Hermann (kiadások) , 2001

Külső linkek

Philippe Gay, " Markov és Csipkerózsika " , a Images des Maths-on ,2014. szeptember 5
(en) [PDF] Charles M. Grinstead és J. Laurie Snell, fej. „ Markov-láncok ”, a Bevezetés a valószínűségbe , AMS
(en) Markov Chain csodálatos
Korrigált gyakorlatok ( wims a University of Nice Sophia Antipolis )