Homogén Markov-láncok. Szabályos Markov-láncok Ciklikus Markov-láncok felismerése pdf

Homogén egy Markov-lánc, amelyre az állapotból való átmenet feltételes valószínűsége Egy államban 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 következőkben véges homogén Markov-láncokra szorítkozunk.

Átmeneti valószínűségek. Átmeneti mátrix.

Átmeneti valószínűség
feltételes valószínűségnek nevezzük, hogy az állapotból A következő teszt eredményeként a rendszer állapotba kerül . Tehát az index az előzőhöz kapcsolódik, és - a következő állapotba.

Átmeneti mátrix A rendszerek egy mátrixot hívnak, amely tartalmazza a rendszer összes átmeneti valószínűségét:

, Ahol 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 Egy államban . 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 Egy államban lépésről lépésre Erre a célra egy köztes (között És ) feltétel. 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
. Képlet segítségével teljes valószínűséggel, kimutatható, 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 - megtalálja 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
. BAN BEN általános eset az arány érvényes
.

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 a valószínűsége, hogy a rendszer 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
az ismétlődő képlet segítségével számítják ki

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.

Markov folyamat- a rendszerben lezajló véletlenszerű folyamat, amelynek a tulajdonsága: minden t 0 időpillanatban a rendszer bármely jövőbeli állapotának valószínűsége (t>t 0-nál) csak a jelen állapotától függ. t = t 0), és nem függ attól, hogy a rendszer mikor és hogyan jutott ebbe az állapotba (azaz hogyan alakult a folyamat a múltban).

A gyakorlatban gyakran találkozunk véletlenszerű folyamatokkal, amelyek különböző közelítési fokig markovinak tekinthetők.

Bármely Markov-folyamatot állapotvalószínűség és átmenet-valószínűség segítségével írunk le.

Markov-folyamat P k (t) állapotainak valószínűségei annak a valószínűsége, hogy a véletlenszerű folyamat (rendszer) t időpontban S k állapotban van:

Markov-folyamat átmeneti valószínűségei Egy folyamat (rendszer) egyik állapotból a másikba való átmenetének valószínűsége:

A Markov-folyamatot ún homogén, ha az egységnyi időre eső átmenet valószínűségei nem függenek attól, hogy az időtengelyen hol történik az átmenet.

A legtöbb egyszerű folyamat van Markov lánc– Markov véletlenszerű folyamat diszkrét idővel és diszkréttel véges halmazÁllamok.

Elemezve a Markov-láncok állapotgráf, amelyen a lánc (rendszer) összes állapota és a nullától eltérő valószínűségek egy lépésben meg vannak jelölve.

A Markov-láncot úgy képzelhetjük el, mintha egy rendszert reprezentáló pont véletlenszerűen mozogna az állapotgráfon, egy lépésben húzódva állapotról állapotra, vagy több lépésig ugyanabban az állapotban maradna.

Egy Markov-lánc egy lépésben történő átmeneti valószínűségeit egy P=||P ij || mátrix formájában írjuk fel, amelyet átmeneti valószínűségi mátrixnak vagy egyszerűen csak átmeneti mátrixnak nevezünk.

Példa: a szakos hallgatók állapotkészlete a következő:

S 1 – gólya;

S 2 – másodéves…;

S 5 – 5. éves hallgató;

S 6 – egyetemet végzett szakember;

S 7 – olyan személy, aki egyetemen tanult, de nem végzett.

Az S 1 állapotból egy éven belül az S 2 állapotba való átmenet lehetséges r 1 valószínűséggel; S 1 q 1 valószínűséggel és S 7 p 1 valószínűséggel, és:

r 1 +q 1 + p 1 =1.

Készítsünk állapotgráfot erre a Markov-láncra, és jelöljük átmeneti valószínűségekkel (nem nulla).

Hozzuk létre az átmenet valószínűségeinek mátrixát:

Az átmeneti mátrixok a következő tulajdonságokkal rendelkeznek:

Minden elemük nem negatív;

A sorok összege eggyel egyenlő.

Az ilyen tulajdonságú mátrixokat sztochasztikusnak nevezzük.

Az átmeneti mátrixok lehetővé teszik bármely Markov-láncpálya valószínűségének kiszámítását a valószínűségi szorzási tétel segítségével.

A homogén Markov-láncok esetében az átmeneti mátrixok nem függnek az időtől.

A Markov-láncok tanulmányozása során a legérdekesebbek a következők:

Az átmenet valószínűségei m lépésben;

Eloszlás az állapotok között az m→∞ lépésben;

Egy bizonyos állapotban töltött átlagos idő;

Átlagos idő ahhoz, hogy visszatérjen ehhez az állapothoz.

Tekintsünk egy n állapotú homogén Markov-láncot. Ahhoz, hogy az S i állapotból az S j állapotba m lépésben való átmenet valószínűségét megkapjuk, a teljes valószínűségi képletnek megfelelően össze kell adni az Si állapotból az Sk köztes állapotba való átmenet valószínűségének l lépésben való szorzatát a valószínűséggel. átmenet Sk-ból Sj-be a fennmaradó m-l lépések, azaz

Ez az összefüggés minden i=1, …, n; j=1, …,n mátrixok szorzataként ábrázolható:

P(m)=P(l)*P(m-l).

Így rendelkezünk:

P(2)=P(1)*P(1)=P 2

P(3)=P(2)*P(1)=P(1)*P(2)=P 3 stb.

P(m)=P(m-1)*P(1)=P(1)*P(M-1)=P m,

amely lehetővé teszi az állapotok közötti átmenet valószínűségeinek tetszőleges számú lépésben történő meghatározását, egy lépésben ismerve az átmeneti mátrixot, nevezetesen P ij (m) - a P(m) mátrix eleme az S állapotból való elmozdulás valószínűsége i S j kijelentésére m lépésben.

Példa: Az időjárás egy bizonyos régióban hosszú ideig csapadékos és száraz között változik. Ha esik, akkor 0,7 valószínűséggel másnap esik az eső; Ha egy adott napon száraz az idő, akkor 0,6-os valószínűséggel másnap is kitart. Úgy tudni, szerdán esős volt az idő. Mennyi a valószínűsége, hogy jövő pénteken eső lesz?

Ebben a feladatban írjuk fel a Markov-lánc összes állapotát: D – esős idő, C – száraz idő.

Készítsünk állapotgráfot:

Válasz: p 11 = p (D sarok | D átl.) = 0,61.

Az m→∞ р 1 (m), р 2 (m),…, р n (m) valószínűségi határait, ha léteznek, ún. állapotok valószínűségének korlátozása.

A következő tétel bizonyítható: ha egy Markov-láncban az egyes állapotokból (adott számú lépésben) el lehet menni egymáshoz, akkor az állapotok korlátozó valószínűségei léteznek, és nem függenek a rendszer kezdeti állapotától .

Így m→∞-ként egy bizonyos korlátozó stacionárius rezsim jön létre a rendszerben, amelyben az egyes állapotok bizonyos állandó valószínűséggel lépnek fel.

A határvalószínűségekből összeállított p vektornak ki kell elégítenie a p=p*P összefüggést.

Az államban töltött átlagos idő S i a T időre egyenlő p i *T-vel, ahol p i - S i állapot határvalószínűsége. Átlagos idő az állapotba való visszatéréshez S i egyenlő .

Példa.

Számos gazdasági probléma esetén ismerni kell az évek váltakozását az éves folyóhozamok bizonyos értékeivel. Természetesen ez a váltakozás nem határozható meg teljesen pontosan. A váltakozás (átmenet) valószínűségének meghatározásához az áramlásokat négy fokozat (a rendszer állapota) bevezetésével osztjuk fel: első (legkisebb áramlás), második, harmadik, negyedik (legmagasabb áramlás). A határozottság kedvéért feltételezzük, hogy az első fokozatot soha nem követi a negyedik, a negyediket pedig az első a nedvesség felhalmozódása miatt (a talajban, tározóban stb.). A megfigyelések azt mutatták, hogy egy bizonyos régióban más átmenetek is lehetségesek, és:

a) az első fokozatból a középsők mindegyikére kétszer olyan gyakran léphet, mint ismét az elsőre, azaz.

p 11 = 0,2; p 12 = 0,4; p 13 = 0,4; p 14 = 0;

b) a negyedik fokozatból négyszer és ötször gyakrabban fordul elő átmenet a második és harmadik fokozatba, mint a második, azaz a visszatérés.

kemény, azaz.

a negyedikben, azaz.

p 41 = 0; p 42 = 0,4; p 43 = 0,5; p 44 = 0,1;

c) a másodikból a többi fokozatba csak ritkábban lehet: az elsőben - kétszer kevesebb, a harmadikban 25%-kal, a negyedikben - négyszer ritkábban, mint a másodikra való áttérés, azaz.

p 21 = 0,2; p 22 = 0,4; p 23 = 0,3; p 24 = 0,1;

d) a harmadik fokozatból a második fokozatba való áttérés olyan valószínű, mint a harmadik fokozatba való visszatérés, az első és negyedik fokozatba való átállás pedig négyszer kisebb, i.e.

p 31 = 0,1; p 32 = 0,4; p 33 = 0,4; p 34 = 0,1;

Készítsünk grafikont:

Hozzuk létre az átmenet valószínűségeinek mátrixát:

Határozzuk meg az aszályok és a nagyvízi évek közötti átlagos időt. Ehhez meg kell találni a limiteloszlást. Létezik, mert tétel feltétele teljesül (a P2 mátrix nem tartalmaz nulla elemet, azaz két lépésben a rendszer bármely állapotából bármelyik másikba lehet lépni).

ahol p4=0,08; p 3 =; p 2 =; p 1 =0,15

Az S i állapotba való visszatérés gyakorisága egyenlő.

Ebből következően a száraz évek gyakorisága átlagosan 6,85, i.e. 6-7 év, esős év 12.

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

A mi témánk tanfolyami munka Markov láncok. A Markov-láncokat a kiváló orosz matematikusról, Andrej Andrejevics Markovról nevezték el, aki sokat dolgozott véletlenszerű folyamatokés nagyban 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 olyan kísérletek sorozata, amelyek mindegyikében a teljes csoport egy és csak egy összeférhetetlen eseménye jelenik meg, és annak feltételes valószínűsége, hogy az esemény a 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 egy 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 történt, akkor annak feltételes valószínűsége, hogy az esemény bekövetkezik a hetedik kísérletben, nem függ milyen események jelentek meg az első, második, ..., ötödik tesztben.

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 egyikében van: , és csak bizonyos időpillanatokban változtatja meg állapotát, az, hogy a rendszer egyik állapotból a másikba lép (például -ból -be). 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).

A szemléltetés kedvéért vegyünk egy példát.

1. példa Képzeljük el, hogy egy egyenes vonalon elhelyezkedő részecske mozog ezen az egyenesen a pillanatokban fellépő véletlenszerű sokkok 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, kivéve, ha a részecske 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 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 ahelyett, hogy egyszerűen írna .

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.

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

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 kijelölésben az első index az előző állapot számát, a második pedig a következő állapot számát jelöli. 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 szavakkal, 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, 0,2 valószínűséggel állapotba kerül, majd 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 Adott átmeneti mátrix segítségével készítsünk állapotgráfot.

Mert 4. rendű 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 azonosba való átmenetének valószínűségét (azon követelmény alapján, hogy a mátrix sorai elemeinek összege egyenlő legyen 1), majd készítse el a rendszer átmeneti mátrixát.

§3. Markov egyenlőség

Meghatározás. Jelöljük annak a valószínűségével, hogy lépések (tesztek) eredményeként a rendszer állapotból állapotba kerül. Például a második állapotból az ötödik állapotba való átmenet valószínűsége 10 lépésben.

Hangsúlyozzuk, hogy megkapjuk az átmeneti valószínűségeket

Tűzzünk ki magunknak egy feladatot: az átmeneti valószínűségek ismeretében keressük meg a rendszer állapotból állapotba lépésenkénti átmenetének valószínűségét.

Ebből a célból figyelembe veszünk egy köztes állapotot (és között). Más szóval, feltételezzük, hogy a kezdeti állapotból lépésenként a rendszer valószínűséggel egy köztes állapotba kerül, majd a köztes állapotból a hátralévő lépésekben valószínűséggel a végső állapotba kerül.

A teljes valószínűségi képlet segítségével azt kapjuk

. (1)

Ezt a képletet Markov-egyenlőségnek nevezik.

Magyarázat. Vezessük be a következő jelölést:

– a minket érdeklő esemény (a rendszer lépésenként halad át a kezdeti állapotból a végső állapotba), ezért, ; − hipotézisek (lépésekben a rendszer a kezdeti állapotból a köztes állapotba kerül), tehát − a bekövetkezés feltételes valószínűsége, feltéve, hogy a hipotézis megtörtént (lépésekben a rendszer a köztes állapotból a végső állapotba kerül), ebből adódóan,

A teljes valószínűségi képlet szerint

()

Vagy az általunk elfogadott jelölésben

ami egybeesik Markov képletével (1).

Az összes átmeneti valószínűség ismeretében, vagyis az állapotból állapotba való átmenet mátrixának egy lépésben történő ismeretében két lépésben megtalálhatja az állapotból az állapotba való átmenet valószínűségét, tehát magát az átmeneti mátrixot; ismert mátrix segítségével három lépésben megtalálhatja az állapotról állapotra való átmenet mátrixát stb.

Valóban, a Markov-egyenlőség bevezetése

jellánc véletlenszerű valószínűség

(2)

Így a (2) képlet segítségével megtalálhatja az összes valószínűséget, és így magát a mátrixot is. Mivel a (2) képlet közvetlen használata fárasztónak bizonyul, és a mátrixszámítás gyorsabban vezet a célhoz, a (2)-ből eredő összefüggéseket mátrix formában írom le:

Az (1) besorolással hasonlóképpen kapjuk

Általában

1. tétel. Bármely s, t

(3)

Bizonyíték. Számítsuk ki a valószínűséget a teljes valószínűségi képlet () segítségével, helyezés

Az egyenlőségből

Ennélfogva egyenlőségből (4) és

a tétel kijelentését kapjuk.

Határozzuk meg a mátrixot, a mátrixban a (3) jelölés alakja

Azóta hol van az átmenet valószínűségi mátrix. Az (5)-ből az következik

(6)

A mátrixok elméletében kapott eredmények lehetővé teszik, hogy a (6) képlet segítségével kiszámítsuk és tanulmányozzuk viselkedésüket, amikor

1. példaÁtmeneti mátrix megadva Keresse meg az átmeneti mátrixot

Megoldás. Használjuk a képletet

A mátrixokat megszorozva végül a következőt kapjuk:

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

Valószínűségi eloszlás in önkényes pillanat az időt a teljes valószínűségi képlet segítségével találhatjuk meg

(7)

Kiderülhet, hogy nem az időtől függ. Hívjuk fel helyhez kötött elosztás vektor , megfelel a feltételeknek

hol vannak az átmenet valószínűségei.

Ha Markov-láncban akkor bármelyikhez

Ezt az állítást a (7) és (8) indukció követi.

Mutassuk be a valószínűségkorlátozási tétel megfogalmazását a Markov-láncok egyik fontos osztályára.

1. tétel. Ha valamilyen >0 esetén a mátrix minden eleme pozitív, akkor bármely , for

, (9)

Ahol stacionárius eloszlás valamilyen konstanssal, amely kielégíti a 0 egyenlőtlenséget< h <1.

Mivel , akkor a tétel feltételei szerint bármely állapotból pozitív valószínűséggel el lehet jutni időben bármely állapotba. A tétel feltételei kizárják azokat a láncokat, amelyek bizonyos értelemben periodikusak.

Ha az 1. Tétel feltételei teljesülnek, akkor annak a valószínűsége, hogy a rendszer a határértékben egy bizonyos állapotba kerül, nem függ a kezdeti eloszlástól. Valójában (9) és (7) az következik, hogy bármely kezdeti eloszlás esetén

Tekintsünk néhány példát olyan Markov-láncokra, amelyekre az 1. Tétel feltételei nem teljesülnek. Nem nehéz ellenőrizni, hogy az ilyen példák példák-e. A példában az átmenet valószínűségeinek vannak határai, de ezek a határértékek a kezdeti állapottól függenek. Főleg mikor

Más példákban a valószínűségi tartományok nyilvánvalóan nem léteznek.

Keressük meg a stacionárius eloszlást az 1. példában. Meg kell találnunk a vektort feltételeknek eleget tesz (8):

;

Így tehát létezik stacionárius eloszlás, de nem minden koordinátavektor pozitív.

A polinomiális sémához egy adott típus kimeneteleinek számával megegyező valószínűségi változókat vezettünk be. Vezessünk be hasonló mennyiségeket a Markov láncokhoz. Legyen ahányszor a rendszer időben belép az állapotba. Ezután a rendszer állapotba ütközésének gyakorisága. A (9) képletekkel bebizonyíthatjuk, hogy amikor megközelíti . Ehhez aszimptotikus képleteket kell beszereznie Csebisev-egyenlőtlenségére, és használnia kell. Itt van a képlet származtatása. Képviseljük a formában

(10)

hol, ha és egyébként. Mert

akkor a matematikai elvárás és a (9) képlet tulajdonságát felhasználva azt kapjuk

Az 1. Tétel értelmében ennek az egyenlőségnek a jobb oldalán lévő hármas tag egy konvergens sorozat parciális összege. Elhelyezés , kapunk

Mert a

A (11) képletből különösen az következik

nál nél

Kaphat egy képletet is, amelyet a variancia kiszámításához használnak.

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

Először bizonyítsunk be két lemmát. Tegyük fel

1. lemma. Bármelyiknek vannak korlátai

Bizonyíték. A (3) egyenlet felhasználásával megkapjuk

Így a szekvenciák egyszerre monotonok és korlátozottak. Ez magában foglalja az 1. lemma kijelentését.

2. lemma. Ha a 2. Tétel feltételei teljesülnek, akkor vannak állandók, oly módon, hogy

Bármilyen

ahol , az összesítést jelenti, amelyre pozitív, és az összegzést a többire vonatkozóan. Innen

. (12)

Mivel az 1. Tétel feltételei szerint az átmeneti valószínűségek mindegyikre, akkor bármelyikre

És az állapotok véges száma miatt

Most becsüljük meg a különbséget . A (3) egyenlet felhasználásával , , megkapjuk

Innen a (8)-(10) használatával azt találjuk

Ezt az összefüggést a (14) egyenlőtlenséggel kombinálva megkapjuk a lemma állítását.

Menj a tétel bizonyítására. Mivel a sorozatok monotonok, akkor

0<. (15)

Ebből és az 1. lemmából azt találjuk

Ezért amikor megkapja és

A pozitivitás az egyenlőtlenségből következik (15). A (3) egyenletben lévő határértékre átlépve azt kapjuk, hogy kielégíti a (12) egyenletet. A tétel bizonyítást nyert.

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

A Markov-láncok jó bevezetőként szolgálnak a véletlenszerű folyamatok elméletébe, pl. a valószínűségi változók családjának egyszerű sorozatainak elmélete, általában egy paraméter függvényében, amely a legtöbb alkalmazásban az idő szerepét tölti be. Elsősorban egy folyamat hosszú távú és helyi viselkedésének teljes leírására szolgál. Íme néhány a legtöbbet tanulmányozott kérdés ezzel kapcsolatban.

Brown-mozgás és általánosításai - diffúziós folyamatok és független növekményes folyamatok . A véletlenszerű folyamatok elmélete hozzájárult a valószínűségelmélet, az operátorelmélet és a differenciálegyenletek elmélete közötti kapcsolat elmélyítéséhez, ami többek között a fizika és más alkalmazások szempontjából is fontos volt. Az alkalmazások között megtalálhatók az aktuáriusi (biztosítási) matematika, a sorbanálláselmélet, a genetika, a forgalomirányítás, az elektromos áramkör-elmélet és a leltárelmélet számára érdekes folyamatok.

Martingales . Ezek a folyamatok elegendő tulajdonságot őriznek meg a Markov-láncoknak ahhoz, hogy a fontos ergodikus tételek érvényesek maradjanak rájuk. A martingálok abban különböznek a Markov-láncoktól, hogy a jelenlegi állapot ismeretében csak a jövő matematikai elvárása, de nem feltétlenül maga a valószínűségi eloszlás, nem függ a múlttól. A martingálelmélet amellett, hogy fontos kutatási eszköz, új határtételekkel gazdagította a statisztikában, a maghasadáselméletben, a genetikában és az információelméletben felmerülő véletlenszerű folyamatok elméletét.

Stacionárius folyamatok . A legrégebbi ismert ergodikus tétel, mint fentebb már említettük, egy stacionárius véletlenszerű folyamat korlátozó viselkedését leíró eredményként értelmezhető. Egy ilyen folyamatnak megvan az a tulajdonsága, hogy minden valószínűségi törvény, amelyet teljesít, invariáns marad az időeltolódások tekintetében. A fizikusok által először hipotézisként megfogalmazott ergodikus tétel olyan állításként ábrázolható, hogy bizonyos feltételek mellett az együttes átlag egybeesik az időátlaggal. Ez azt jelenti, hogy ugyanaz az információ nyerhető egy rendszer hosszú távú megfigyeléséből és ugyanazon rendszer számos független másolatának egyidejű (és azonnali) megfigyeléséből. A nagy számok törvénye nem más, mint Birkhoff ergodikus tételének egy speciális esete. A stacionárius Gauss-folyamatok viselkedésének tágabb értelemben vett interpolációja és előrejelzése a klasszikus legkisebb négyzetek elméletének fontos általánosításaként szolgál. A stacionárius folyamatok elmélete számos területen szükséges kutatási eszköz, például a kommunikációelméletben, amely zaj vagy véletlenszerű interferencia jelenlétében üzeneteket továbbító rendszerek tanulmányozásával és létrehozásával foglalkozik.

A Markov-folyamatok (utóhatások nélküli folyamatok) óriási szerepet játszanak a sorbanállási rendszerek (QS) modellezésében, valamint a társadalomban előforduló társadalmi-gazdasági folyamatok kezelésének modellezésében és stratégiaválasztásában.

A Markov-lánc is használható szövegek generálására. Bemenetként több szöveget adunk meg, majd egy Markov-láncot építünk fel az egyik szó következő valószínűségével, és ennek alapján készítjük el az eredményül kapott szöveget. A játék nagyon szórakoztatónak bizonyul!

Következtetés

Így a kurzusunkban a Markov-lánckörről beszéltünk. Megtanultuk, hogy milyen területeken és hogyan használják, független tesztek igazolták a Markov-lánc valószínűségkorlátozási tételét, példákat adtak egy tipikus és homogén Markov-láncra, valamint az átmeneti mátrix megtalálására.

Láttuk, hogy a Markov-láncterv a független tesztterv közvetlen általánosítása.

Felhasznált irodalom jegyzéke

1. Chistyakov V.P. Valószínűségelmélet tanfolyam. 6. kiadás, rev. − St. Petersburg: Lan Publishing House, 2003. − 272 p. − (Tankönyv egyetemek számára. Szakirodalom).

2. Gnedenko B.V. Valószínűségelmélet tanfolyam.

3. Gmurman V.E. Valószínűségelmélet és matematikai statisztika.

4. Ventzel E.S. Valószínűségszámítás és mérnöki alkalmazásai.

5. Kolmogorov A.N., Zhurbenko I.G., Prokhorov A.V. Bevezetés a valószínűségszámításba. − Moszkva-Izhevszk: Számítógépes Kutatóintézet, 2003, 188 pp.

6. Katz M. Valószínűségszámítás és kapcsolódó kérdések a fizikában.

Markov lánc- események láncolata, amelyben az egyes események valószínűsége csak az előző állapottól függ.

Ez a cikk absztrakt jellegű, a végén megadott, helyenként hivatkozott források alapján íródott.

Bevezetés a Markov-láncok elméletébe

A Markov-lánc véletlenszerű események sorozata, amelyben az egyes események valószínűsége csak attól az állapottól függ, amelyben a folyamat éppen található, és nem függ a korábbi állapotoktól. A végső diszkrét áramkört a következők határozzák meg:

∑ j=1…n p ij = 1

Példa átmeneti valószínűségek mátrixára S = (S 1, ..., S 5) állapothalmazzal, p (0) = (1, 0, 0, 0, 0 kezdeti valószínűségek vektorával):

VAL VEL A kezdeti valószínűségek vektorát és az átmeneti mátrixot felhasználva kiszámíthatjuk a p (n) sztochasztikus vektort - a p (n) (i) valószínűségekből összeállított vektort, hogy a folyamat n időpontban i állapotba kerül. A p(n) értéket a következő képlet segítségével kaphatja meg:

p(n) = p(0) × Pn

A p (n) vektorok n növekedésével bizonyos esetekben stabilizálódnak - konvergálnak egy bizonyos ρ valószínűségi vektorhoz, amelyet a lánc stacionárius eloszlásának nevezhetünk. A stacionaritás abban nyilvánul meg, hogy p (0) = ρ feltétellel bármely n esetén p (n) = ρ értéket kapunk.

A stacionárius eloszláshoz való konvergenciát garantáló legegyszerűbb kritérium a következő: ha a P átmeneti valószínűségi mátrix minden eleme pozitív, akkor mivel n a végtelen felé hajlik, a p (n) vektor a ρ vektorhoz hajlik, ami az egyetlen megoldás. az űrlap rendszeréhez

Az is kimutatható, hogy ha n valamilyen pozitív értékére a P n mátrix minden eleme pozitív, akkor a p (n) vektor továbbra is stabilizálódik.

Ezen állítások bizonyítékát részletesen bemutatjuk.

Egy Markov-láncot átmeneti gráfként ábrázolunk, melynek csúcsai a lánc állapotainak, az ívei pedig a köztük lévő átmeneteknek felelnek meg. Az si és sj csúcsokat összekötő ív (i, j) súlya egyenlő lesz az első állapotból a másodikba való átmenet pi(j) valószínűségével. A fent látható mátrixnak megfelelő grafikon:

NAK NEK Markov-láncok állapotainak osztályozása

A Markov-láncok vizsgálatakor a rendszer rövid időn belüli viselkedésére lehetünk kíváncsiak. Ebben az esetben az abszolút valószínűségek kiszámítása az előző szakasz képleteivel történik. Fontosabb azonban a rendszer viselkedésének tanulmányozása hosszú időintervallumban, amikor az átmenetek száma a végtelenbe hajlik. Ezután a Markov-láncok állapotainak definíciói kerülnek bemutatásra, amelyek szükségesek a rendszer viselkedésének hosszú távú tanulmányozásához.

A Markov-láncokat az egyik állapotból a másikba való átmenet lehetőségétől függően osztályozzák.

A Markov-lánc állapotcsoportjait (az átmeneti gráf csúcsainak részhalmazai), amelyek megfelelnek az átmeneti gráf sorrenddiagramjának zsákutcájának, a lánc ergodikus osztályainak nevezzük. Ha figyelembe vesszük a fent bemutatott gráfot, láthatjuk, hogy 1 ergodikus osztályt tartalmaz, M1 = (S5), amely az M2 = (S1, S2, S3, S4) csúcsok egy részhalmazának megfelelő erősen összefüggő komponensből érhető el. Az ergodikus osztályokba tartozó állapotokat esszenciálisnak, a többit nem esszenciálisnak nevezzük (bár az ilyen nevek nem egyeznek jól a józan ésszel). Az si elnyelő állapot az ergodikus osztály speciális esete. Aztán ha egyszer ilyen állapotba kerül, a folyamat leáll. Si esetén pii = 1 lesz igaz, azaz. az átmeneti gráfban csak egy él fog kijönni belőle - egy hurok.

Az elnyelő Markov-láncokat programok és számítási folyamatok ideiglenes modelljeként használják. A program modellezésekor az áramkör állapotait a program blokkjaival azonosítjuk, és az átmeneti valószínűségek mátrixa határozza meg a blokkok közötti átmenetek sorrendjét, a program szerkezetétől és a kezdeti adatok eloszlásának függvényében, az értékeket amelyek befolyásolják a számítási folyamat fejlődését. A program abszorbeáló áramkörrel történő ábrázolása eredményeként kiszámolható a programblokkokhoz való hozzáférések száma és a program végrehajtási ideje, átlagértékekkel, szórásokkal és szükség esetén eloszlással becsülve. Ezen statisztikák felhasználásával a jövőben optimalizálhatja a programkódot – alacsony szintű módszereket alkalmazhat a program kritikus részei felgyorsításához. Ezt a módszert kódprofilozásnak nevezik.

Például Dijkstra algoritmusában a következő áramköri állapotok vannak jelen:

vertex (v), bontsa ki az új csúcsot a prioritási sorból, menjen csak a b állapotba;

begin (b), a gyengítési eljárás kimenő íveinek keresési ciklusának kezdete;

elemzés (a), a következő ív elemzése, lehetséges átmenet a, d vagy e-re;

csökkenés (d), a gráf valamely csúcsának becslésének csökkentése, átlépés a-ba;

vége (e), a ciklus befejezése, átlépés a következő csúcsra.

Marad a csúcsok közötti átmenet valószínűségeinek beállítása, és tanulmányozhatja a csúcsok közötti átmenetek időtartamát, a különböző állapotokba kerülés valószínűségét és a folyamat egyéb átlagos jellemzőit.

Hasonlóképpen, a számítási folyamat, amely a rendszererőforrásokhoz a program által meghatározott sorrendben való hozzáféréshez vezet, egy elnyelő Markov-lánccal ábrázolható, amelynek állapotai megfelelnek a rendszer erőforrásainak - processzor, memória és perifériás eszközök - használatának; átmenet a valószínűségek a különböző erőforrásokhoz való hozzáférés sorrendjét tükrözik. Ennek köszönhetően a számítási folyamat jellemzőinek elemzésére alkalmas formában kerül bemutatásra.

Egy Markov-láncról azt mondjuk, hogy irreducibilis, ha bármely Sj állapot elérhető bármely más Si állapotból véges számú átmenetben. Ebben az esetben az áramkör összes állapotáról azt mondjuk, hogy kommunikál, és az átmeneti gráf az erős kapcsolódás összetevője. Egy ergodikus lánc által generált folyamat, amely egy bizonyos állapotban kezdődött, soha nem ér véget, hanem egymás után halad át egyik állapotból a másikba, és az átmenet valószínűségétől függően különböző állapotokba kerül, különböző gyakorisággal. Ezért az ergodikus lánc fő jellemzője az

annak a valószínűsége, hogy a folyamat Sj, j = 1,…, n állapotokban van, az idő hány része, amelyet a folyamat az egyes állapotokban tölt. A rendszer megbízhatóságának modelljeként az irreducibilis áramköröket használják. Valójában, ha egy folyamat által használt erőforrás nagyon gyakran meghibásodik, az egész rendszer funkcionalitása veszélybe kerül. Ilyen esetekben egy ilyen kritikus erőforrás megkettőzése segíthet elkerülni a hibákat. Ebben az esetben a rendszer állapotait, amelyek a működőképes és meghibásodott berendezések összetételében különböznek egymástól, áramköri állapotokként értelmezik, amelyek közötti átmenetek a meghibásodásokhoz és az eszközök helyreállításához, valamint a köztük lévő kapcsolatok megváltozásához kapcsolódnak, és amelyeket a rendszer fenntartása érdekében hajtanak végre. a rendszer működőképességét. Az irreducibilis áramkör jellemzőinek becslései képet adnak a rendszer egészének viselkedésének megbízhatóságáról. Az ilyen áramkörök modellek is lehetnek az eszközök és a feldolgozásra benyújtott feladatok közötti interakcióról.

Példák a felhasználásra

Hiba szerviz rendszer

Egy szerver több blokkból áll, például modemekből vagy hálózati kártyákból, amelyek fogadják a felhasználóktól a szolgáltatásra vonatkozó kéréseket. Ha minden blokk foglalt, a kérés elveszik. Ha az egyik blokk elfogad egy kérést, akkor a feldolgozás végéig foglalt lesz. Vegyük állapotnak a nem foglalt blokkok számát. Az idő diszkrét lesz. Jelöljük α-val a kérés fogadásának valószínűségét. Azt is hisszük, hogy a szolgálati idő is véletlenszerű, és független folytatásokból áll, pl. egy β valószínűségű kérést egy lépésben, majd (1 - β) valószínűséggel e lépés után új kérésként. Ez adja meg (1 - β) β valószínűségét kétlépcsős szolgáltatás esetén, (1 - β)2 β valószínűségét háromlépcsős szolgáltatás esetén stb. Nézzünk egy példát 4 párhuzamosan működő eszközzel. Hozzuk létre az átmenet valószínűségeinek mátrixát a kiválasztott állapotokhoz:

M Megjegyezhető, hogy egyedi ergodikus osztálya van, és ezért a valószínűségi vektorok osztályában a p × P = p rendszernek egyedi megoldása van. Írjuk fel annak a rendszernek az egyenleteit, amely lehetővé teszi, hogy megtaláljuk ezt a megoldást:

Most már ismert a πi valószínűségek halmaza, hogy stacionárius üzemmódban a rendszer i blokkot foglal el. Ekkor a p 4 = C γ 4 /4 idő töredéke a rendszer összes blokkja foglalt, a rendszer nem válaszol a kérésekre. A kapott eredmények tetszőleges számú blokkra vonatkoznak. Mostantól kihasználhatja ezeket: összehasonlíthatja a további eszközök költségeit és a rendszer teljes kihasználtsági idejének csökkenését.

Erről a példáról bővebben itt olvashat.

Döntéshozatali folyamatok véges és végtelen számú szakaszból

Tekintsünk egy folyamatot, amelyben több átmeneti valószínűségi mátrix létezik. Az idő minden pillanatában az egyik vagy másik mátrix kiválasztása attól függ, hogy milyen döntést hozunk. A fentiek megérthetők a következő példa segítségével. A talajelemzés eredményeként a kertész három szám egyikével értékeli annak állapotát: (1) - jó, (2) - kielégítő vagy (3) - rossz. Ugyanakkor a kertész észrevette, hogy a talaj adott évi termőképessége csak az előző évi állapotától függ. Ezért a talaj külső hatások nélküli átmenetének valószínűsége egyik állapotból a másikba a következő Markov-lánccal ábrázolható P1 mátrixszal:

L Természetes, hogy a talaj termőképessége idővel romlik. Például, ha tavaly kielégítő volt a talaj állapota, akkor idén már csak úgy maradhat, vagy romlik, de nem lesz jó. A kertész azonban befolyásolhatja a talaj állapotát, és megváltoztathatja a P1 mátrixban az átmenet valószínűségét a megfelelő P2 mátrixból:

T Most már minden egyes állapotból a másikba való átmenethez hozzárendelhetünk egy bizonyos jövedelemfüggvényt, amelyet egy éves időszak nyereségeként vagy veszteségeként határozunk meg. A kertész eldöntheti, hogy használ-e műtrágyát vagy sem, ez határozza meg végső bevételét vagy veszteségét. Vezessük be az R1 és R2 mátrixokat, amelyek a műtrágyaköltség és a talajminőség függvényében határozzák meg a bevételi függvényeket:

N Végül a kertész azzal a problémával szembesül, hogy melyik stratégiát válassza az átlagos várható bevétel maximalizálása érdekében. Kétféle probléma jöhet szóba: véges és végtelen számú fokozattal. Ebben az esetben a kertész tevékenysége egyszer biztosan véget ér. Ezenkívül a vizualizálók véges számú szakaszban oldják meg a döntéshozatali problémát. Hagyja, hogy a kertész N év múlva abbahagyja a foglalkozást. Most az a feladatunk, hogy meghatározzuk a kertész számára az optimális viselkedési stratégiát, vagyis azt a stratégiát, amely maximalizálja a bevételét. Problémánkban a szakaszok számának végessége abban nyilvánul meg, hogy a kertészt nem érdekli, mi lesz a termőföldjével N+1 évig (N-ig minden év fontos számára). Most láthatjuk, hogy ebben az esetben a stratégia keresési probléma dinamikus programozási problémává változik. Ha fn(i)-vel jelöljük azt a maximális átlagos várható jövedelmet, amelyet az n-től N-ig terjedő szakaszok során, az i-es állapottól kezdve elérhetünk, akkor könnyen levezethető a visszatérő

Z ahol k a használt stratégia száma. Ez az egyenlet azon a tényen alapul, hogy a rijk + fn+1(j) összjövedelem a pijk valószínűséggel az n szakasz i állapotából az n+1 szakaszban lévő j állapotba való átmenet eredményeként keletkezik.

Most az fn(i) csökkenő irányú (n = N…1) szekvenciális kiszámításával találhatjuk meg az optimális megoldást. Ugyanakkor a kezdeti valószínűségek vektorának beillesztése a problémafelvetésbe nem bonyolítja a megoldást.

Ezt a példát is tárgyaljuk.

Szavak kombinációinak modellezése a szövegben

Tekintsünk egy szöveget, amely w szavakból áll. Képzeljünk el egy folyamatot, amelyben az állapotok szavak, így amikor (Si) állapotban van, a rendszer az átmeneti valószínűségek mátrixa szerint (sj) állapotba kerül. Mindenekelőtt a rendszer „betanítása” szükséges: kellően nagy szöveget kell megadni bemenetként az átmenet valószínűségeinek értékeléséhez. És akkor megépítheti a Markov-lánc pályáit. A Markov-lánc algoritmussal szerkesztett szöveg szemantikai terhelésének növelése csak a sorrend növelésével lehetséges, ahol az állapot nem egy szó, hanem nagyobb teljesítményű halmazok - párok (u, v), hármasok (u, v, w) stb. Sőt, az első és ötödik rend láncolatában továbbra is kevés értelme lesz. A jelentés akkor kezd kialakulni, amikor a sorrendi dimenzió legalább a forrásszöveg tipikus kifejezésében szereplő szavak átlagos számára nő. De nem lehet így haladni, mert a szöveg szemantikai terhelésének növekedése a magasrendű Markov-láncokban sokkal lassabban megy végbe, mint a szöveg egyediségének csökkenése. És egy Markov-láncokra épített szöveg, például harmincadrendű, továbbra sem lesz annyira értelmes, hogy érdekelje az embert, hanem már meglehetősen hasonlít az eredeti szöveghez, és az állapotok száma egy ilyen láncban legyen csodálatos.

Ezt a technológiát ma már nagyon széles körben használják (sajnos) az interneten weboldal-tartalom létrehozására. Azok az emberek, akik szeretnék növelni webhelyük forgalmát és javítani a keresőmotorok helyezésén, hajlamosak a lehető legtöbb keresési kulcsszót feltenni oldalaikra. A keresőmotorok azonban olyan algoritmusokat használnak, amelyek meg tudják különböztetni a valódi szöveget a kulcsszavak inkoherens zagyvaságától. Ezután a keresőmotorok megtévesztésére olyan szövegeket használnak, amelyeket egy Markov-láncon alapuló generátor készített. Természetesen vannak pozitív példák a Markov-láncok szövegmunkára való alkalmazására, a szerzőség meghatározására és a szövegek hitelességének elemzésére használják.

Markov-láncok és lottó

Egyes esetekben a valószínűségi modellt használják a számok előrejelzésére különböző lottójátékokban. Úgy tűnik, nincs értelme Markov-láncokkal modellezni a különböző keringések sorrendjét. Ami a sorsolás során a labdákkal történt, az semmilyen módon nem befolyásolja a következő sorsolás eredményét, mivel a sorsolást követően a labdák összegyűjtésre kerülnek, és a következő sorsolásnál rögzített sorrendben kerülnek a lottótálcára. Ebben az esetben megszakad a kapcsolat a múltbeli keringéssel. Egy másik dolog az egy húzáson belül kieső labdák sorozata. Ebben az esetben a következő labda ejtését a lottógép állapota határozza meg az előző labda leejtésének időpontjában. Így az egy húzás során elejtett labdák sorozata egy Markov-lánc, és egy ilyen modell használható. Itt van egy nagy nehézség a numerikus lottó elemzésekor. A lottógép állapota a következő labda kiesése után meghatározza a további eseményeket, de a probléma az, hogy ez az állapot számunkra ismeretlen. Csak annyit tudunk, hogy egy bizonyos labda kiesett. De amikor ez a golyó kiesik, a fennmaradó golyókat különböző módon lehet elhelyezni, így nagyon sok állapotból álló csoport van, amely ugyanannak a megfigyelt eseménynek felel meg. Ezért csak az ilyen állapotcsoportok közötti átmenet valószínűségeinek mátrixát állíthatjuk össze. Ezek a valószínűségek a különböző egyedi állapotok közötti átmenetek valószínűségeinek átlagai, ami természetesen csökkenti a Markov-lánc modell alkalmazásának hatékonyságát a numerikus lottó esetében.

Hasonlóan ehhez az esethez, egy ilyen neurális hálózati modell használható időjárás, devizaárfolyamok előrejelzésére és más olyan rendszerekkel kapcsolatban, ahol rendelkezésre állnak a múltbeli adatok és az újonnan kapott információk a jövőben felhasználhatók. Egy jó alkalmazás ebben az esetben, amikor a rendszernek csak a megnyilvánulásai ismertek, de a belső (rejtett) állapotok nem, alkalmazható rejtett Markov-modellekre, amelyekről a Wikikönyvek részletesen tárgyalnak (rejtett Markov-modellek).

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.

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 összeférhetetlen eseményei, és annak feltételes valószínűsége, hogy az esemény a harmadik kísérletben fog bekövetkezni, feltéve, hogy az esemény a harmadik kísérletben történt, nem függ a korábbi kísérletek 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.

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 pillanatnyi állapotba kerül, 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).

A szemléltetés kedvéért 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 helyezkedhet el: ; 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, kivéve, ha a részecske 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 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.

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