Meghatározás. Egy Markov-láncot homogénnek nevezünk, ha a feltételes valószínűség (állapotból állapotba való átmenet) nem függ a próbaszámtól. Ezért egyszerűen csak írnak helyette.

1. példa Véletlenszerű séta. Legyen egy egész koordinátájú pontban egy anyagrészecske egy egyenesen. Bizonyos időpillanatokban a részecske sokkhatást tapasztal. Lökés hatására a részecske egy egységgel jobbra, egy egységgel balra való valószínűséggel mozog. Nyilvánvaló, hogy egy részecske helyzete (koordinátája) sokk után attól függ, hogy a részecske hol volt a közvetlenül megelőző sokk után, és nem attól függ, hogyan mozgott más korábbi sokkok hatására.

Szóval véletlen séta? Példa egy homogén diszkrét idejű Markov-láncra.

Az átmenet valószínűsége annak a feltételes valószínűsége, hogy abból az állapotból (amelyben a rendszer valamilyen teszt eredményeként került, függetlenül attól, hogy hányszor) a következő teszt eredményeként a rendszer abba az állapotba kerül.

Így a megjelölésben az első index az előző számát jelöli, a második pedig? következő államszám. Például - a második állapotból a harmadikba való átmenet valószínűsége.

Legyen az állapotok száma véges és egyenlő.

Egy rendszer átmeneti mátrixa egy olyan mátrix, amely tartalmazza a rendszer összes átmeneti valószínűségét:

Mivel a mátrix minden sora tartalmazza azoknak az eseményeknek a valószínűségét (azonos állapotból bármely lehetséges állapotba való átmenet), amelyek egy teljes csoportot alkotnak, ezen események valószínűségeinek összege eggyel egyenlő. Más szóval, az átmeneti mátrix minden sorában az átmeneti valószínűségek összege eggyel egyenlő:

Adjunk példát egy olyan rendszer átmeneti mátrixára, amely három állapotú lehet; az állapotból állapotba való átmenet egy homogén Markov-lánc séma szerint történik; Az átmenet valószínűségét a mátrix adja meg:

Itt azt látjuk, hogy ha a rendszer állapotban volt, akkor egy lépésben az állapot megváltoztatása után 0,5 valószínűséggel ugyanabban az állapotban marad, 0,5 valószínűséggel ugyanabban az állapotban marad, állapotba kerül 0,2 valószínűséggel, akkor az átmenet után állapotokba kerülhet; állapotból nem tud költözni. A mátrix utolsó sora azt mutatja, hogy egy állapotból ugyanazzal a 0,1-es valószínűséggel bármelyik lehetséges állapotba juthatunk.

A rendszer átmeneti mátrixa alapján elkészíthető a rendszer úgynevezett állapotgráfja, amelyet címkézett állapotgráfnak is neveznek. Ez kényelmes az áramkör vizuális megjelenítéséhez. Nézzük meg a gráfok felépítésének sorrendjét egy példa segítségével.

2. példa A megadott átmeneti mátrix segítségével készítsünk állapotgráfot.

Mert negyedrendű mátrix, akkor ennek megfelelően a rendszernek 4 lehetséges állapota van.

A grafikon nem mutatja a rendszer egyik állapotból ugyanabba a helyzetbe való átmenetének valószínűségét. Konkrét rendszerek mérlegelésekor célszerű először állapotgráfot készíteni, majd meghatározni a rendszer egyik állapotból ugyanabba a helyzetbe való átmenetének valószínűségét (a mátrixsorok elemeinek összege eggyel). ), majd készítse el a rendszer átmeneti mátrixát.

Markov láncok

Bevezetés

§ 1. Markov-lánc

2. § Homogén Markov-lánc. Átmeneti valószínűségek. Átmeneti mátrix

§3. Markov egyenlőség

4. §. Helyhez kötött elosztás. Határvalószínűség-tétel

§5. A Markov-lánc valószínűségeinek korlátozására vonatkozó tétel bizonyítása

6. §. Markov-láncok alkalmazásai

Következtetés

Felhasznált irodalom jegyzéke

Bevezetés

Tanfolyamunk témája a Markov-lánc. A Markov-láncokat a kiváló orosz matematikusról, Andrej Andrejevics Markovról nevezték el, aki sokat dolgozott véletlenszerű folyamatokon, és jelentős mértékben hozzájárult e terület fejlődéséhez. A közelmúltban számos területen lehet hallani a Markov-láncok használatáról: a modern webes technológiákban, irodalmi szövegek elemzésekor vagy akár egy futballcsapat taktikáinak kidolgozásakor. Aki nem ismeri a Markov-láncokat, annak az az érzése lehet, hogy ez valami nagyon összetett és szinte érthetetlen.

Nem, ennek éppen az ellenkezője. A Markov-lánc a véletlenszerű események sorozatának egyik legegyszerűbb esete. De egyszerűsége ellenére gyakran még meglehetősen összetett jelenségek leírásánál is hasznos lehet. A Markov-lánc véletlenszerű események sorozata, amelyben az egyes események valószínűsége csak az előzőtől függ, de nem függ a korábbi eseményektől.

Mielőtt mélyebbre ásnánk, mérlegelnünk kell néhány általánosan ismert, de a további kifejtéshez feltétlenül szükséges segédkérdést.

Tantárgyi munkám célja a Markov-láncok alkalmazásai, a problémafelvetés és a Markov-problémák részletesebb tanulmányozása.

§1. Markov lánc

Képzeljük el, hogy tesztsorozatot hajtanak végre.

Meghatározás. A Markov-lánc próbák sorozata, amelyek mindegyikében az alábbiak közül csak egy jelenik meg.

a teljes csoport inkompatibilis eseményei, és annak feltételes valószínűsége, hogy az esemény a 2. kísérletben bekövetkezik , feltéve, hogy az esemény a próba során történt , nem függ a korábbi tesztek eredményeitől.

Például, ha a kísérletek sorozata Markov-láncot alkot, és a teljes csoport négy összeférhetetlen eseményből áll

, és ismert, hogy az esemény a hatodik kísérletben jelent meg, akkor annak feltételes valószínűsége, hogy az esemény bekövetkezik a hetedik kísérletben, nem függ attól, hogy milyen események jelentek meg az első, második, ..., ötödik kísérletben.

Vegye figyelembe, hogy a független tesztek a Markov-lánc speciális esetei. Valójában, ha a tesztek függetlenek, akkor egy bizonyos esemény bekövetkezése egyetlen tesztben sem függ a korábban elvégzett tesztek eredményeitől. Ebből következik, hogy a Markov-lánc fogalma a független vizsgálatok fogalmának általánosítása.

A Markov-láncok elméletének bemutatásakor gyakran más terminológiához ragaszkodnak, és egy bizonyos fizikai rendszerről beszélnek.

, amely minden időpillanatban a következő állapotok valamelyikében van: , és csak külön időpontokban változtatja állapotát, vagyis a rendszer egyik állapotból a másikba lép (például -ból -ba). A Markov-láncok esetében annak a valószínűsége, hogy bármely állapotba kerül pillanatnyilag csak attól függ, hogy a rendszer éppen milyen állapotban volt, és nem változik, mert a korábbi pillanatok állapotai ismertté válnak. Továbbá különösen a teszt után a rendszer ugyanabban az állapotban maradhat ("mozgat" állapotról állapotra).

Szemléltetésképpen vegyünk egy példát.

1. példa Képzeljük el, hogy egy egyenes vonalon elhelyezkedő részecske mozog ezen az egyenes mentén pillanatnyi véletlenszerű lökés hatására

. Egy részecske egész koordinátájú pontokban is elhelyezhető: ; A fényvisszaverő falak a pontokon helyezkednek el. Minden egyes nyomás a részecskét valószínûséggel jobbra, valószínûséggel balra mozgatja, hacsak a részecske nem fal közelében van. Ha a részecske a fal közelében van, akkor minden nyomás egy egységgel a falak közötti résen belül mozgatja. Itt azt látjuk, hogy a részecskejárásnak ez a példája egy tipikus Markov-lánc.

Így az eseményeket a rendszer állapotainak, a teszteket pedig állapotváltozásoknak nevezzük.

Definiáljunk most egy Markov-láncot új terminológiával.

A diszkrét idejű Markov-lánc olyan áramkör, amelynek állapotai bizonyos meghatározott időpontokban változnak.

A folytonos idejű Markov-lánc olyan lánc, amelynek állapotai az idő bármely lehetséges pillanatában megváltoznak.

§2. Homogén Markov lánc. Átmeneti valószínűségek. Átmeneti mátrix

Meghatározás. Egy Markov-láncot homogénnek mondunk, ha a feltételes valószínűség

(állapotból állapotba való átmenet) nem függ a tesztszámtól. Ezért ahelyett, hogy egyszerűen írna .

1. példa Véletlenszerű séta. Legyen egyenes vonalon

egy egész koordinátájú pontban van egy anyagrészecske. Bizonyos időpillanatokban a részecske sokkot ér. Lökés hatására a részecske egy egységnyi valószínűséggel jobbra és egy egységgel balra mozdul el. Nyilvánvaló, hogy egy részecske helyzete (koordinátája) sokk után attól függ, hogy a részecske hol volt a közvetlenül megelőző sokk után, és nem attól függ, hogyan mozgott más korábbi sokkok hatására.

Így egy véletlenszerű séta egy homogén Markov-lánc példája, diszkrét idővel.

2016. június 1-jén 16:31-kor

Osztály fejlesztése a Markov-láncokkal való munkavégzéshez

• C++
• Algoritmusok

Ma egy osztály megírásáról szeretnék beszélni, amely megkönnyíti a Markov-láncokkal való munkát.

Kérem a kat.

Alapismeretek:

Gráfok ábrázolása szomszédsági mátrix formájában, gráfokkal kapcsolatos alapfogalmak ismerete. C++ ismerete a gyakorlati részhez.

Elmélet

A Markov-lánc véletlenszerű események sorozata, véges vagy megszámlálható számú végkifejlettel, amelyet az a tulajdonság jellemez, hogy lazán szólva, rögzített jelen mellett a jövő független a múlttól. A. A. Markov (idősebb) tiszteletére nevezték el.

Egyszerűen fogalmazva, a Markov-lánc egy súlyozott gráf. A csúcsaiban események vannak, és az A és B csúcsokat összekötő él súlya annak a valószínűsége, hogy A eseményt B esemény követi.

Elég sok cikk született a Markov láncok használatáról, de továbbra is fejlesztjük az osztályt.

Mondok egy példát egy Markov-láncra:

A jövőben ezt a sémát példaként fogjuk figyelembe venni.

Nyilvánvaló, hogy ha csak egy kimenő él van az A csúcsból, akkor annak súlya 1 lesz.

Megnevezések

A csúcsokon események vannak (A, B, C, D, E...). A széleken annak a valószínűsége, hogy az i-edik esemény után j > i esemény lesz. Az egyszerűség és a kényelem kedvéért a csúcsokat számoztam (1., 2. stb.).

A mátrix egy orientált súlyozott gráf szomszédsági mátrixa, amelyet egy Markov-lánc ábrázolására használunk. (erről később). Ebben a konkrét esetben ezt a mátrixot átmeneti valószínűségi mátrixnak vagy egyszerűen átmeneti mátrixnak is nevezik.

Egy Markov-lánc mátrixábrázolása

A Markov-láncokat egy mátrix segítségével fogjuk ábrázolni, pontosan azzal a szomszédsági mátrixszal, amellyel a gráfokat ábrázoljuk.

Hadd emlékeztesselek:

Egy véges számú n csúcsú (1-től n-ig számozott) G gráf szomszédsági mátrixa egy n méretű A négyzetmátrix, amelyben az aij elem értéke egyenlő az i-edik csúcsból származó élek számával. a gráf j-edik csúcsához.

Olvasson többet a szomszédsági mátrixokról a diszkrét matematika kurzusban.

Esetünkben a mátrix 10x10 méretű lesz, írjuk fel:

0 50 0 0 0 0 50 0 0 0
0 0 80 20 0 0 0 0 0 0
0 0 0 0 100 0 0 0 0 0
0 0 0 0 100 0 0 0 0 0
0 0 0 0 0 100 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 70 30 0
0 0 0 0 0 0 0 0 0 100
0 0 0 0 0 0 0 0 0 100
0 0 0 0 0 100 0 0 0 0

Ötlet

Nézze meg közelebbről mátrixunkat. Minden sorban vannak nem nulla értékek azokban az oszlopokban, amelyek száma egybeesik a következő eseménnyel, és maga a nem nulla érték az esemény bekövetkezésének valószínűsége.

Így a számmal megegyező számmal rendelkező esemény bekövetkezésének valószínűsége van oszlop számmal egyenlő esemény után vonalak.

Azok, akik ismerik a valószínűségszámítást, sejthetik, hogy minden sor valószínűségeloszlási függvény.

Markov-lánc bejárási algoritmus

1) inicializáljuk a kezdeti k pozíciót a nulla csúcsponttal.
2) Ha a csúcs nem végleges, akkor a mátrix k sorában lévő valószínűségi eloszlás alapján generálunk egy m számot 0...n-1-ből, ahol n a csúcsok száma, m pedig a következő esemény (!). Különben elmegyünk
3) Az aktuális k pozíció száma megegyezik a generált csúcs számával
4) A 2. lépéshez

Megjegyzés: egy csúcs véges, ha a valószínűségi eloszlás nulla (lásd a mátrix 6. sorát).

Elég elegáns algoritmus, igaz?

Végrehajtás

Ebben a cikkben külön szeretném feltüntetni a leírt bypass megvalósítási kódját. A Markov-lánc inicializálása és feltöltése nem különösebben érdekes (a teljes kódot lásd a végén).

A bejárási algoritmus megvalósítása

sablon Elem *Markov ::Next(int Kezdőelem = -1) ( if (Markov ::Initiated) // ha a szomszédsági mátrix létrejön ( if (StartElement == -1) // ha az alapértelmezett kezdőelem StartElement = Markov ::Jelenlegi; // majd folytatjuk (a Current = 0 konstruktorban) std::random_device rd;<>std::mt19937 gen(rd()); std::diszkrét_elosztás ::AdjacencyMatrix.at(Current).end()); // inicializálja a tárolót egy szám generálásához a valószínűségi eloszlás alapján in next = dicr_distr(gen); // generálja a következő csúcsot if (next == Markov ::size()) // a generátor finomságai, ha a valószínűségi eloszlás nulla, akkor az elemek számát adja vissza NULL; Markov ::Aktuális = következő; // az aktuális csúcsérték megváltoztatása &(Markov

::elems.at(next)); // a csúcsban lévő érték visszaadása ) return NULL; ) Ez az algoritmus különösen egyszerűnek tűnik a tároló jellemzői miatt diszkrét_elosztás

0 50 0 0 0 0 50 0 0 0

. Elég nehéz szavakkal leírni, hogyan működik ez a konténer, ezért vegyük példának a mátrixunk 0. sorát:

A generátor működése eredményeként 1-et vagy 6-ot ad vissza, mindegyikre 0,5 valószínűséggel. Azaz azt az oszlopszámot adja vissza (amely megegyezik a lánc csúcsának számával), ahol a mozgásnak folytatódnia kell.

Egy példaprogram, amely az osztályt használja:

Egy olyan program megvalósítása, amely a Markov-lánc bejárását végzi a példából #beleértve #include "Markov.h" #include #beleértve névtér használata std; int main() (Markov< num; i++) { getline(ins, str); chain.AddElement(str); // добавляем вершину } if (chain.InitAdjacency()) // инициализируем матрицу нулями { for (int i = 0; i < chain.size(); i++) { for (int j = 0; j < chain.size(); j++) { (ins >lánc; folyamon kívüli kivezetések;<< "Adjacency matrix write error" << endl; } } } outs << chain.At(0) << " "; // выводим 0-ю вершину for (int i = 0; i < 20 * chain.size() - 1; i++) // генерируем 20 цепочек { string *str = chain.Next(); if (str != NULL) // если предыдущая не конечная outs << (*str).c_str() << " "; // выводим значение вершины else { outs << std::endl; // если конечная, то начинаем с начала chain.Current = 0; outs << chain.At(0) << " "; } } chain.UninitAdjacency(); // понятно } else cerr << "Can not initialize Adjacency matrix" << endl;; ins.close(); outs.close(); cin.get(); return 0; }

outs.open("out.txt");

ifstream ins; ins.open("mátrix.txt"); int szám; double Prob = 0;
(ins >> szám).get(); // csúcsok száma string str;
.

for (int i = 0; i
> Prob).get();

if (!chain.PushAdjacency(i, j, Prob)) // írja be a mátrixot ( cerr

Példa a program által generált kimenetre:

Homogén
egy Markov-lánc, amelyre az állapotból való átmenet feltételes valószínűsége olyan állapotban nem függ a tesztszámtól. Helyette homogén láncokhoz használja a jelölést A homogén Markov-láncra példa a véletlenszerű séták. Legyen egy anyagrészecske az Ox egyenesen egy x=n egész koordinátájú pontban. Bizonyos időpontokban

a részecske hirtelen megváltoztatja helyzetét (például p valószínűséggel jobbra, 1 –p– valószínűséggel balra mozoghat). Nyilvánvaló, hogy a részecske koordinátája az ugrás után attól függ, hogy a részecske hol volt a közvetlenül megelőző ugrás után, és nem attól függ, hogyan mozgott az előző pillanatokban. A rendszerek egy mátrixot hívnak, amely tartalmazza a rendszer összes átmeneti valószínűségét:

, Hol egy lépésben ábrázolják az átmenet valószínűségét.

Vegyük észre az átmeneti mátrix néhány jellemzőjét.

Markov egyenlőség

Jelöljük azzal
annak a valószínűsége, hogy n lépés (teszt) eredményeként a rendszer kimozdul az állapotból int szám; . Például,
- a harmadik állapotból a hatodik állapotba való átmenet valószínűsége 10 lépésben. Vegye figyelembe, hogy ha n= 1, ez a valószínűség egyszerűen az átmenet valószínűségére redukálódik
.

Felmerül a kérdés, hogy az átállási valószínűségek ismeretében hogyan
, keresse meg az állapotátmenet valószínűségét int szám; lépésről lépésre Erre a célra egy köztes (között És ) állapot. Más szóval, úgy gondolják, hogy az eredeti állapotból M lépés után a rendszer nagy valószínűséggel átmegy egy köztes állapotba
, ami után a fennmaradó n–m lépésben a köztes állapotból a végső állapotba kerül valószínűséggel
.

A teljes valószínűségi képlet segítségével megmutathatjuk, hogy a képlet érvényes Ezt a képletet ún .

Markov egyenlőség
Az összes átmeneti valószínűség ismeretében , azaz az átmeneti mátrix ismeretében
állapotról állapotra egy lépésben megtalálhatja a valószínűségeket átmenet állapotból állapotba két lépésben, és ezért maga az átmeneti mátrix , akkor - az ismert mátrix szerint - találni

stb.

Valóban, ha n= 2,m= 1-et teszünk a Markov-egyenlőségbe, azt kapjuk
vagy
.

. Mátrix formában ez így írható fel
Feltéve, hogy n=3,m=2, kapjuk
.

. Általános esetben az összefüggés igaz Példa . Legyen az átmeneti mátrix

egyenlő
.

Meg kell találnunk az átmeneti mátrixot Szorzómátrix
.

önmagában kapjuk

A gyakorlati alkalmazások szempontjából rendkívül fontos annak a valószínűsége, hogy egy rendszer egy adott időpontban egy adott állapotba kerül. Ennek a kérdésnek a megoldásához szükség van a kezdeti feltételek ismeretére, pl. annak valószínűsége, hogy a rendszer a kezdeti időpontban bizonyos állapotokban van. Egy Markov-lánc kezdeti valószínűségi eloszlása ​​a folyamat elején lévő állapotok valószínűségi eloszlása.
Itt keresztül jelzi annak valószínűségét, hogy a rendszer állapotba kerül
az idő kezdeti pillanatában. Speciális esetben, ha a rendszer kezdeti állapota pontosan ismert (pl
), akkor a kezdeti valószínűség

, és az összes többi egyenlő nullával.
Ha egy homogén Markov-láncra adott a kezdeti valószínűségi eloszlás és az átmeneti mátrix, akkor a rendszerállapotok valószínűségei az n-edik lépésben

.

A szemléltetés kedvéért mondjunk egy egyszerű példát. Tekintsük egy bizonyos rendszer (például egy eszköz) működési folyamatát. Hagyja, hogy a készülék egy napig két állapot egyikében legyen - üzemképes ( ) és hibás ( ). A készülék működésének tömeges megfigyelései eredményeként a következő átmeneti mátrixot állítottuk össze
,

Ahol - annak valószínűsége, hogy az eszköz jó állapotban marad;

- a készülék üzemképes állapotból hibás állapotba való átmenetének valószínűsége;

- a készülék hibás állapotból üzemképes állapotba való átmenetének valószínűsége;

- annak a valószínűsége, hogy az eszköz „hibás” állapotban marad.

Adja meg a reláció az eszközállapotok kezdeti valószínűségeinek vektorát

, azaz
(a kezdeti pillanatban a készülék hibás volt). Három nap elteltével meg kell határozni az eszköz állapotának valószínűségét.

Megoldás: Az átmeneti mátrix segítségével meghatározzuk az első lépés utáni állapotok valószínűségét (az első nap után):

A második lépés (második nap) utáni állapotok valószínűsége egyenlő

Végül a harmadik lépés (harmadik nap) utáni állapotok valószínűsége egyenlő

Így annak a valószínűsége, hogy a készülék jó állapotú lesz, 0,819, a hibás állapotnak pedig 0,181.

A rendszer összes lehetséges állapota egy homogén Markov-láncban, és ez a sztochasztikus mátrix, amely meghatározza ezt a láncot, amely átmeneti valószínűségekből áll (lásd 381. oldal).

Jelöljük annak valószínűségével, hogy a rendszer az időpillanatban állapotba kerül, ha ismert, hogy az időpillanatban a rendszer (,) állapotban volt. Nyilvánvalóan, . A valószínűségek összeadásáról és szorzásáról szóló tételek segítségével könnyen megtalálhatjuk:

vagy mátrix jelöléssel

Innen, egymás után megadva az értékeket, megkapjuk a fontos képletet

Ha vannak korlátok

vagy mátrix jelöléssel

majd az értékeket marginális vagy végső átmenetvalószínűségnek nevezzük.

Hogy megtudjuk, milyen esetekben vannak korlátozó átmeneti valószínűségek, és a megfelelő képleteket levezetjük, a következő terminológiát vezetjük be.

Szabályosnak nevezünk egy sztochasztikus mátrixot és a hozzá tartozó homogén Markov-láncot, ha a mátrixban nincsenek az egységtől eltérő karakterisztikus számok, amelyek modulusa eggyel egyenlő, és regulárisnak nevezzük, ha emellett az egység a mátrix karakterisztikus egyenletének egyszerű gyöke.

A reguláris mátrixot az a tény jellemzi, hogy normál formájában (69) (373. o.) a mátrixok primitívek. Szabályos mátrixhoz ezenkívül .

Ezenkívül egy homogén Markov-láncot felbonthatatlannak, felbonthatónak, aciklikusnak, ciklikusnak nevezünk, ha ennek a láncnak a sztochasztikus mátrixa rendre felbonthatatlan, felbontható, primitív, imprimitív.

Mivel a primitív sztochasztikus mátrix a reguláris mátrix egy speciális típusa, az aciklikus Markov-lánc a szabályos lánc speciális típusa.

Megmutatjuk, hogy korlátozó átmeneti valószínűségek csak szabályos homogén Markov-láncok esetén léteznek.

Valóban, legyen egy reguláris mátrix minimális polinomja. Majd

A 10. tétel szerint feltételezhetjük, hogy

A (24) képlet alapján Ch. V (113. oldal)

(96)

Ahol a redukált adjungált mátrix és

Ha reguláris mátrix, akkor

és ezért a (96) képlet jobb oldalán az első kivételével minden tag nullára irányul. Ezért egy reguláris mátrixhoz létezik egy mátrix, amely a korlátozó átmenet valószínűségekből áll, és

Az ellenkező helyzet nyilvánvaló. Ha probléma van

akkor a mátrixnak nem lehet olyan karakterisztikus száma, amelyre , a , mivel akkor nem létezne a határ [Ugyanannak a határnak kell léteznie a határ (97") megléte miatt.]

Bebizonyítottuk, hogy egy szabályos (és csak szabályos) homogén Markov-lánchoz létezik mátrix. Ezt a mátrixot a (97) képlet határozza meg.

Mutassuk meg, hogyan fejezhető ki a mátrix a karakterisztikus polinomon keresztül

és az adjunkt mátrix .

Az identitásból

A (95), (95") és (98) alapján ez a következő:

Ezért a (97) képlet helyettesíthető a képlettel

(97)

Egy szabályos Markov-lánc esetében, mivel ez egy bizonyos típusú szabályos lánc, a mátrix létezik, és a (97), (97") képletek bármelyike ​​határozza meg. Ebben az esetben a (97") képlet alakja is

2. Tekintsünk egy általános típusú (szabálytalan) szabályos láncot. A megfelelő mátrixot normál formában írjuk

(100)

ahol a primitív sztochasztikus mátrixok, és a felbonthatatlan mátrixok maximális karakterisztikus számmal rendelkeznek. hinni

,

írjuk be az űrlapba

(101)

De , mivel a mátrix összes karakterisztikus száma abszolút értékben kisebb egynél. azért

(102)

Mivel primitív sztochasztikus mátrixokról van szó, a (99) és (35) képletek szerinti mátrixok (362. oldal) pozitívak

és ezen mátrixok bármelyik oszlopában minden elem egyenlő egymással:

.

Figyeljük meg, hogy a sztochasztikus mátrix normálalakja (100) megfelel a rendszerállapotok csoportokra osztásának:

A (104) minden csoportja megfelel a (101) saját sorozatainak. L. N. Kolmogorov terminológiája szerint a rendszer állapotait lényegesnek, a többi csoportba tartozó állapotokat pedig lényegtelennek nevezik.

A mátrix (101) alakjából az következik, hogy tetszőleges számú lépésre (pillanatról pillanatra) a rendszer egyetlen lehetséges átmenete a) egy lényeges állapotból egyazon csoport lényegi állapotába, b) lényegtelen állapotból esszenciális állapotba, és c) lényegtelen állapotból ugyanazon vagy előző csoport lényegtelen állapotába.

A mátrix (102) alakjából az következik, hogy az átmenet csak bármely állapotból egy lényeges állapotba lehetséges, azaz a lépések számával nullára hajlik az átmenet valószínűsége bármely lényegtelen állapotba. Ezért az alapvető állapotokat néha határállapotoknak is nevezik.

3. A (97) képletből az következik:

.

Ez azt mutatja, hogy a mátrix minden oszlopa a karakterisztikus szám sztochasztikus mátrixának sajátvektora.

Szabályos mátrix esetén az 1 a karakterisztikus egyenlet egyszerű gyöke, és ez a szám a mátrix egyetlen (legfeljebb skalártényezős) sajátvektorának felel meg. Ezért a mátrix bármelyik oszlopában minden elem azonos nemnegatív számmal:

Így egy szabályos láncban a korlátozó átmenet valószínűségei nem függenek a kezdeti állapottól.

Ezzel szemben, ha valamilyen szabályos homogén Markov-láncban a prodel-átmenet valószínűségei nem függnek a kezdeti állapottól, azaz a (104) képletek teljesülnek, akkor a (102) sémában a mátrixhoz ez szükséges. De akkor szabályos a lánc.

Egy aciklikus lánc esetében, amely egy szabályos lánc speciális esete, ez egy primitív mátrix. Ezért egyesek számára (lásd a 8. tételt a 377. oldalon). De akkor .

Megfordítva, ebből az következik, hogy egyeseknél, és ez a 8. tétel szerint azt jelenti, hogy a mátrix primitív, és ezért az adott homogén Markov-lánc aciklikus.

A kapott eredményeket a következő tétel formájában fogalmazzuk meg:

11. Tétel 1. Ahhoz, hogy egy homogén Markov-láncban minden korlátozó átmenet-valószínűség létezzen, szükséges és elegendő, hogy a lánc szabályos legyen. Ebben az esetben a határátmeneti valószínűségekből álló mátrixot a (95) vagy (98) képlet határozza meg.

2. Ahhoz, hogy egy szabályos homogén Markov-láncban a korlátozó átmeneti valószínűségek függetlenek legyenek a kezdeti állapottól, szükséges és elegendő, hogy a lánc szabályos legyen. Ebben az esetben a mátrixot a (99) képlet határozza meg.

3. Ahhoz, hogy egy szabályos homogén Markov-láncban minden korlátozó átmenet valószínűsége nullától eltérő legyen, szükséges és elegendő, hogy a lánc aciklikus legyen.

4. Vezessük be az abszolút valószínűségek oszlopait

(105)

hol van annak a valószínűsége, hogy a rendszer pillanatnyilag (,) állapotban van. A valószínűségek összeadási és szorzási tételeit felhasználva azt kapjuk, hogy:

(,),

vagy mátrix jelöléssel

ahol a mátrix transzponált mátrixa.

Az összes abszolút valószínűséget (105) a (106) képletből határozzuk meg, ha ismertek a kezdeti valószínűségek és az átmeneti valószínűségek mátrixa

Vezessük be a korlátozó abszolút valószínűségeket

Ha a (106) egyenlőség mindkét oldalát átengedjük a határértékhez, megkapjuk:

Megjegyzendő, hogy a korlátozó átmeneti valószínűségek mátrixának létezése magában foglalja a korlátozó abszolút valószínűségek létezését bármilyen kezdeti valószínűségre és fordítva.

A (107) képletből és a mátrix (102) alakjából az következik, hogy a lényegtelen állapotoknak megfelelő korlátozó abszolút valószínűségek nullával egyenlőek.

A mátrixegyenlőség mindkét oldalát megszorozzuk

a jobb oldalon a (107) alapján megkapjuk:

azaz a határes abszolút valószínűségek oszlopa a mátrix sajátvektora a karakterisztikus számra.

Ha ez a Markov-lánc szabályos, akkor ez a mátrix karakterisztikus egyenletének egyszerű gyöke. Ebben az esetben a korlátozó abszolút valószínűségek oszlopa egyértelműen (108)-ból van meghatározva (mióta és ).

Legyen adott egy szabályos Markov-lánc. Ezután a (104)-ből és a (107)-ből ez következik:

(109)

Ebben az esetben a korlátozó abszolút valószínűségek nem függnek a kezdeti valószínűségektől.

Ezzel szemben nem feltétlenül függ attól, hogy a (107) képlet jelenlétében a mátrix minden sora azonos-e, és csak akkor.

,

és ezért (a 11. tétel szerint) reguláris mátrix.

Ha primitív mátrix, akkor , és így a (109) alapján

Ellenkezőleg, ha minden nem a kezdeti valószínűségektől függ, akkor a mátrix minden oszlopában minden elem azonos és a (109) szerint, és ez a 11. tétel szerint azt jelenti, hogy egy primitív mátrix, azaz ez a lánc aciklikus.

A fentiekből következik, hogy a 11. Tétel a következőképpen fogalmazható meg:

11. Tétel". 1. Ahhoz, hogy egy homogén Markov-láncban minden korlátozó abszolút valószínűség létezzen bármely kezdeti valószínűségre, szükséges és elegendő, hogy a lánc szabályos legyen.

2. Ahhoz, hogy egy homogén Markov-láncban létezzenek korlátozó abszolút valószínűségek bármely kezdeti valószínűségre, és ne ezektől a kezdeti valószínűségektől függjenek, szükséges és elegendő, hogy a lánc szabályos legyen.

3. Ahhoz, hogy egy homogén Markov-lánc pozitív korlátozó abszolút valószínűségekkel rendelkezzen bármely kezdeti valószínűségre, és ezek a korlátozó valószínűségek függetlenek legyenek a kezdeti valószínűségektől, szükséges és elegendő, hogy a lánc aciklikus legyen.

5. Tekintsünk most egy általános típusú homogén Markov-láncot átmeneti valószínűségi mátrixszal.

Vegyük a mátrix normálalakját (69), és jelöljük a (69) mátrixok imprimitivitási indexeivel. Legyen egész számok legkisebb közös többszöröse. Ekkor a mátrixnak nem eggyel azonos modulusú, hanem egytől eltérő karakterisztikus számai vannak, azaz reguláris mátrix; ebben az esetben - a legkisebb mutató, amelynél - a helyes mátrix. A számot egy adott homogén Markov-lánc periódusának nevezzük és... Megfordítva, ha és , amelyet a (110) és (110") képlet határoz meg.

A lényegtelen állapotoknak megfelelő átlagos határvalószínűség mindig nulla.

Ha a mátrix normál alakja egy szám (és csak ebben az esetben), az átlagos korlátozó abszolút valószínűségek nem függenek a kezdeti valószínűségektől, és egyértelműen a (111) egyenletből határozhatók meg.

Előző cikk: Mekkora a fénysebesség Következő cikk: Harmonikus rezgések Az oszcillációs frekvencia fizikai képlete