Homogénne je Markovov reťazec, pre ktorý je podmienená pravdepodobnosť prechodu zo stavu v stave nezávisí od čísla testu. Namiesto toho pre homogénne reťazce
použiť notáciu
.

Príkladom homogénneho Markovho reťazca sú náhodné prechádzky. Nech je hmotná častica na priamke Ox v bode s celočíselnou súradnicou x=n. V určitých časoch
častica náhle zmení svoju polohu (napr. s pravdepodobnosťou p sa môže pohnúť doprava a s pravdepodobnosťou 1 –p– doľava). Je zrejmé, že súradnica častice po skoku závisí od toho, kde bola častica po bezprostredne predchádzajúcom skoku, a nezávisí od toho, ako sa pohybovala v predchádzajúcich časových okamihoch.

V nasledujúcom texte sa obmedzíme na uvažovanie o konečných homogénnych Markovových reťazcoch.

Pravdepodobnosti prechodu. Prechodová matica.

Pravdepodobnosť prechodu
sa nazýva podmienená pravdepodobnosť, že zo stav V dôsledku nasledujúceho testu systém prejde do stavu . Takže index súvisí s predchádzajúcim a - do následného stavu.

Prechodová matica systémy volajú maticu, ktorá obsahuje všetky pravdepodobnosti prechodu tohto systému:

, Kde predstavujú pravdepodobnosti prechodu v jednom kroku.

Všimnime si niektoré vlastnosti prechodovej matice.

Markovova rovnosť

Označme podľa
pravdepodobnosť, že v dôsledku n krokov (testov) sa systém posunie zo stavu v stave . Napríklad,
- pravdepodobnosť prechodu v 10 krokoch z tretieho stavu do šiesteho. Všimnite si, že keď n = 1, táto pravdepodobnosť sa jednoducho zníži na pravdepodobnosť prechodu
.

Vynára sa otázka, ako, poznať pravdepodobnosti prechodu
nájdite pravdepodobnosti prechodu stavu v stave krok za krokom Na tento účel sa použije medziprodukt (medzi A ) stav. Inými slovami, verí sa, že z pôvodného stavu Po m krokoch systém s pravdepodobnosťou prejde do stredného stavu
, po ktorých v zostávajúcich n–m krokoch prejde z medzistavu do konečného stavu s pravdepodobnosťou
. Pomocou vzorca celkovej pravdepodobnosti môžeme ukázať, že vzorec je platný

Tento vzorec sa nazýva Markovova rovnosť .

Poznanie všetkých pravdepodobností prechodu
, t.j. poznať prechodovú maticu zo stavu do stavu v jednom kroku môžete nájsť pravdepodobnosti
prechod zo stavu do stavu v dvoch krokoch, a teda samotná matica prechodu , potom - podľa známej matice - Nájsť atď.

Ak do Markovovej rovnosti vložíme n= 2,m= 1, dostaneme

alebo
. V maticovej forme to možno zapísať ako
.

Za predpokladu n=3,m=2 dostaneme
. Vo všeobecnom prípade je vzťah pravdivý
.

Príklad. Nechajte prechodovú maticu rovná

Musíme nájsť prechodovú maticu
.

Násobiaca matica na seba, dostaneme
.

Pre praktické aplikácie je mimoriadne dôležitá otázka výpočtu pravdepodobnosti, že systém bude v konkrétnom stave v konkrétnom čase. Riešenie tejto otázky si vyžaduje znalosť počiatočných podmienok, t.j. pravdepodobnosť, že systém bude v počiatočnom čase v určitých stavoch. Počiatočné rozdelenie pravdepodobnosti Markovovho reťazca je rozdelenie pravdepodobnosti stavov na začiatku procesu.

Tu cez
označuje pravdepodobnosť, že systém je v stave v počiatočnom okamihu. V špeciálnom prípade, ak je počiatočný stav systému presne známy (napr
), potom počiatočná pravdepodobnosť
a všetky ostatné sú rovné nule.

Ak je pre homogénny Markovov reťazec dané počiatočné rozdelenie pravdepodobnosti a matica prechodu, potom sú pravdepodobnosti systému uvedené v n-tom kroku
sa vypočítajú pomocou opakujúceho sa vzorca

.

Pre ilustráciu si uveďme jednoduchý príklad. Uvažujme o procese fungovania určitého systému (napríklad zariadenia). Nechajte zariadenie jeden deň v jednom z dvoch stavov - prevádzkyschopné ( ) a chybné ( ). Ako výsledok hromadných pozorovaní činnosti zariadenia bola zostavená nasledujúca prechodová matica
,

Kde - pravdepodobnosť, že zariadenie zostane v dobrom stave;

- pravdepodobnosť prechodu zariadenia z prevádzkyschopného do chybného stavu;

- pravdepodobnosť prechodu zariadenia z chybného do prevádzkyschopného stavu;

- pravdepodobnosť, že zariadenie zostane v „chybnom“ stave.

Nech je vektor počiatočných pravdepodobností stavov zariadení daný vzťahom

, t.j.
(v počiatočnom momente bolo zariadenie chybné). Po troch dňoch je potrebné určiť pravdepodobnosti stavu zariadenia.

Riešenie: Pomocou prechodovej matice určíme pravdepodobnosti stavov po prvom kroku (po prvom dni):

Pravdepodobnosti stavov po druhom kroku (druhý deň) sú rovnaké

Napokon, pravdepodobnosti stavov po treťom kroku (tretí deň) sú rovnaké

Pravdepodobnosť, že zariadenie bude v dobrom stave je teda 0,819, respektíve, že bude v poruchovom stave, je 0,181.

Markov proces- náhodný proces vyskytujúci sa v systéme, ktorý má vlastnosť: pre každý časový okamih t 0, pravdepodobnosť akéhokoľvek stavu systému v budúcnosti (v t>t 0) závisí len od jeho stavu v súčasnosti (v t = t 0) a nezávisí od toho, kedy a ako sa systém do tohto stavu dostal (t. j. ako sa proces vyvíjal v minulosti).

V praxi sa často stretávame s náhodnými procesmi, ktoré v rôznej miere aproximácie možno považovať za markovovské.

Akýkoľvek Markovov proces je opísaný pomocou stavových pravdepodobností a pravdepodobností prechodu.

Pravdepodobnosti stavov P k (t) Markovovho procesu sú pravdepodobnosti, že náhodný proces (systém) v čase t je v stave S k:

Prechodové pravdepodobnosti Markovovho procesu sú pravdepodobnosti prechodu procesu (systému) z jedného stavu do druhého:

Markovov proces je tzv homogénne, ak pravdepodobnosti prechodu za jednotku času nezávisia od toho, kde na časovej osi k prechodu dôjde.

Najjednoduchší proces je Markov reťaz– Markov náhodný proces s diskrétnym časom a diskrétnou konečnou množinou stavov.

Pri analýze sú Markovove reťazce stavový graf, na ktorom sú v jednom kroku vyznačené všetky stavy reťazca (systému) a nenulové pravdepodobnosti.

Markovov reťazec si možno predstaviť tak, že bod predstavujúci systém sa náhodne pohybuje cez stavový graf, ťahá zo stavu do stavu v jednom kroku alebo zostáva v rovnakom stave niekoľko krokov.

Prechodové pravdepodobnosti Markovovho reťazca v jednom kroku sú zapísané vo forme matice P=||P ij ||, ktorá sa nazýva matica pravdepodobnosti prechodu alebo jednoducho matica prechodu.

Príklad: množina stavov študentov špecializácie je nasledovná:

S 1 – prvák;

S 2 – druhák…;

S 5 – študent 5. ročníka;

S 6 – špecialista s vysokoškolským vzdelaním;

S 7 – osoba, ktorá študovala na vysokej škole, ale nedokončila ju.

Zo stavu S 1 v priebehu roka sú možné prechody do stavu S 2 s pravdepodobnosťou r 1 ; S 1 s pravdepodobnosťou q 1 a S 7 s pravdepodobnosťou p 1 a:

r1+q1+p1=1.

Zostavme stavový graf pre tento Markovov reťazec a označme ho pravdepodobnosťami prechodu (nenulovými).

Vytvorme maticu pravdepodobnosti prechodu:

Prechodové matice majú nasledujúce vlastnosti:

Všetky ich prvky nie sú negatívne;

Ich riadkové súčty sa rovnajú jednej.

Matice s touto vlastnosťou sa nazývajú stochastické.

Prechodové matice vám umožňujú vypočítať pravdepodobnosť akejkoľvek trajektórie Markovovho reťazca pomocou vety o násobení pravdepodobnosti.

Pre homogénne Markovove reťazce prechodové matice nezávisia od času.

Pri štúdiu Markovových reťazcov sú najzaujímavejšie:

Pravdepodobnosti prechodu v m krokoch;

Distribúcia cez stavy v kroku m→∞;

Priemerný čas strávený v určitom stave;

Priemerný čas návratu do tohto stavu.

Uvažujme homogénny Markovov reťazec s n stavmi. Na získanie pravdepodobnosti prechodu zo stavu Si do stavu Sj v m krokoch by sa v súlade so vzorcom celkovej pravdepodobnosti mali sčítať súčin pravdepodobnosti prechodu zo stavu Si do prechodného stavu Sk v l krokoch pravdepodobnosťou. prechodu zo Sk na Sj v zostávajúcich m-l krokoch, t.j.

Tento vzťah platí pre všetky i=1, …, n; j=1, …,n možno reprezentovať ako súčin matíc:

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

Máme teda:

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

P(3)=P(2)*P(1)=P(1)*P(2)=P3 atď.

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

čo umožňuje nájsť pravdepodobnosti prechodu medzi stavmi v ľubovoľnom počte krokov, pričom poznáme maticu prechodu v jednom kroku, a to P ij (m) - prvok matice P(m) je pravdepodobnosť prechodu zo stavu S i uviesť S j v m krokoch.

Príklad: Počasie v určitom regióne sa po dlhú dobu strieda medzi daždivými a suchými. Ak prší, potom s pravdepodobnosťou 0,7 bude pršať nasledujúci deň; Ak je v určitý deň počasie suché, tak s pravdepodobnosťou 0,6 pretrvá aj nasledujúci deň. Je známe, že v stredu bolo daždivé počasie. Aká je pravdepodobnosť, že budúci piatok bude pršať?

Zapíšme si všetky stavy Markovho reťazca v tejto úlohe: D – daždivé počasie, C – suché počasie.

Zostavme stavový graf:

Odpoveď: p 11 = p (D päta | D avg) = 0,61.

Limity pravdepodobnosti р 1 (m), р 2 (m),…, р n (m) pre m→∞, ak existujú, sa nazývajú obmedzujúce pravdepodobnosti stavov.

Dá sa dokázať nasledujúca veta: ak v Markovovom reťazci môžete prejsť od + každého stavu (v danom počte krokov) k sebe, potom limitné pravdepodobnosti stavov existujú a nezávisia od počiatočného stavu systému. .

Ako m→∞ je teda v systéme nastolený istý limitný stacionárny režim, v ktorom sa každý zo stavov vyskytuje s určitou konštantnou pravdepodobnosťou.

Vektor p, zložený z hraničných pravdepodobností, musí spĺňať vzťah: p=p*P.

Priemerný čas strávený v štáte S i pre čas T sa rovná p i *T, kde p i - hraničná pravdepodobnosť stavu S i . Priemerný čas návratu do stavu S i sa rovná .

Príklad.

Pri mnohých ekonomických problémoch je potrebné poznať striedanie rokov s určitými hodnotami ročných prietokov riek. Samozrejme, toto striedanie sa nedá určiť úplne presne. Na určenie pravdepodobnosti striedania (prechodu) rozdeľujeme toky zavedením štyroch stupňov (stavov systému): prvý (najnižší prietok), druhý, tretí, štvrtý (najvyšší prietok). Pre istotu budeme predpokladať, že po prvej gradácii nikdy nenasleduje štvrtá a po štvrtej prvá z dôvodu hromadenia vlhkosti (v zemi, nádrži a pod.). Pozorovania ukázali, že v určitej oblasti sú možné iné prechody a:

a) od prvej gradácie môžete prejsť na každú zo stredných dvakrát častejšie ako znova na prvú, t.j.

p11 = 0,2; p12 = 0,4; p13 = 0,4; p14=0;

b) zo štvrtej gradácie sa prechody do druhej a tretej gradácie vyskytujú štyrikrát a päťkrát častejšie ako návraty ako v druhej, t.j.

tvrdý, t.j.

vo štvrtom, t.j.

p41=0; p42 = 0,4; p43 = 0,5; p44 = 0,1;

c) od druhého k iným gradáciám môže byť len menej časté: v prvom - dvakrát menej, v treťom o 25%, vo štvrtom - štyrikrát menej často ako prechod na druhý, t.j.

p21 = 0,2; p22 = 0,4; p23 = 0,3; p24 = 0,1;

d) od tretieho stupňa je prechod do druhého stupňa rovnako pravdepodobný ako návrat do tretieho stupňa a prechody do prvého a štvrtého stupňa sú štyrikrát menej pravdepodobné, t.j.

p31 = 0,1; p32 = 0,4; p33 = 0,4; p34 = 0,1;

Zostavme si graf:

Vytvorme maticu pravdepodobnosti prechodu:

Nájdite priemerný čas medzi obdobiami sucha a rokmi vysokej vody. Aby ste to dosiahli, musíte nájsť rozdelenie limitov. Existuje, pretože podmienka vety je splnená (matica P2 neobsahuje nulové prvky, t.j. v dvoch krokoch sa dá prejsť z ľubovoľného stavu systému do akéhokoľvek iného).

kde p4 = 0,08; p3 =; p2 =; p1 = 0,15

Frekvencia návratu do stavu S i sa rovná .

Následne je frekvencia suchých rokov v priemere 6,85, t.j. 6-7 rokov a daždivé roky 12.

Markovove reťaze

Úvod

§ 1. Markov reťaz

§ 2. Homogénna Markovova reťaz. Pravdepodobnosti prechodu. Prechodová matica

§3. Markovova rovnosť

§4. Stacionárny rozvod. Veta limitnej pravdepodobnosti

§5. Dôkaz vety o obmedzenej pravdepodobnosti v Markovovom reťazci

§6. Aplikácia Markovových reťazí

Záver

Zoznam použitej literatúry

Úvod

Témou našej práce v kurze je Markov reťazec. Markovove reťazce sú pomenované po vynikajúcom ruskom matematikovi Andrejovi Andreevičovi Markovovi, ktorý vo veľkej miere pracoval na náhodných procesoch a významne prispel k rozvoju tejto oblasti. V poslednej dobe môžete počuť o využití Markovových reťazcov v rôznych oblastiach: moderné webové technológie, pri analýze literárnych textov alebo dokonca pri vývoji taktiky pre futbalový tím. Kto nevie, čo sú Markovove reťazce, môže mať pocit, že ide o niečo veľmi zložité a takmer nepochopiteľné.

Nie, je to práve naopak. Markovov reťazec je jedným z najjednoduchších prípadov postupnosti náhodných udalostí. Ale napriek svojej jednoduchosti môže byť často užitočný aj pri opise pomerne zložitých javov. Markovov reťazec je postupnosť náhodných udalostí, v ktorých pravdepodobnosť každej udalosti závisí iba od predchádzajúcej udalosti, ale nezávisí od skorších udalostí.

Predtým, ako sa ponoríme hlbšie, musíme zvážiť niekoľko pomocných otázok, ktoré sú všeobecne známe, ale sú absolútne nevyhnutné pre ďalší výklad.

Cieľom mojej kurzovej práce je podrobnejšie študovať aplikácie Markovových reťazcov, zadávania problémov a Markovových problémov.

§1. Markov reťaz

Predstavme si, že sa vykonáva postupnosť testov.

Definícia. Markovov reťazec je sekvencia pokusov, v ktorých sa objaví len jedna z nekompatibilných udalostí celej skupiny a podmienená pravdepodobnosť, že sa udalosť vyskytne v tomto pokuse, je za predpokladu, že udalosť nastala v 1. súdnom konaní , nezávisí od výsledkov predchádzajúcich testov.

Napríklad, ak postupnosť pokusov tvorí Markovov reťazec a celá skupina pozostáva zo štyroch nekompatibilných udalostí a je známe, že udalosť nastala v šiestom pokuse, potom podmienená pravdepodobnosť, že udalosť nastane v siedmom pokuse, nezávisí o tom, aké udalosti sa objavili v prvom, druhom, ..., piatom teste.

Všimnite si, že nezávislé testy sú špeciálnym prípadom Markovovho reťazca. V skutočnosti, ak sú testy nezávislé, potom výskyt určitej udalosti v akomkoľvek teste nezávisí od výsledkov predtým vykonaných testov. Z toho vyplýva, že koncept Markovovho reťazca je zovšeobecnením konceptu nezávislých pokusov.

Pri prezentácii teórie Markovových reťazcov sa často držia inej terminológie a hovoria o určitom fyzikálnom systéme, ktorý sa v každom okamihu nachádza v jednom zo stavov: , a mení svoj stav iba v rôznych časových okamihoch, že je, že systém sa presúva z jedného stavu do druhého (napríklad z do ). Pre Markovove reťazce je pravdepodobnosť prechodu do akéhokoľvek stavu momentálne závisí len od toho, v akom stave sa systém práve nachádzal, a nemení sa, pretože jeho stavy v skorších momentoch sa stanú známymi. Najmä po skúške môže systém zostať v rovnakom stave („presun“ zo stavu do stavu).

Pre ilustráciu uvažujme o príklade.

Príklad 1 Predstavme si, že častica umiestnená na priamke sa pohybuje po tejto priamke pod vplyvom náhodných otrasov vyskytujúcich sa v momentoch . Častica môže byť umiestnená v bodoch s celočíselnými súradnicami: ; Reflexné steny sú umiestnené v bodoch. Každé zatlačenie posunie časticu s pravdepodobnosťou doprava a s pravdepodobnosťou doľava, pokiaľ sa častica nenachádza pri stene. Ak je častica blízko steny, potom ju akékoľvek zatlačenie posunie o jednu jednotku vo vnútri medzery medzi stenami. Tu vidíme, že tento príklad chôdze častice je typický Markovov reťazec.

Udalosti sa teda nazývajú stavy systému a testy sa nazývajú zmeny jeho stavov.

Poďme teraz definovať Markovov reťazec pomocou novej terminológie.

Markovov reťazec s diskrétnym časom je obvod, ktorého stavy sa menia v určitých pevných časoch.

Markovov reťazec so spojitým časom je reťazec, ktorého stavy sa menia v ľubovoľných náhodných možných okamihoch v čase.

§2. Homogénny Markov reťazec. Pravdepodobnosti prechodu. Prechodová matica

Definícia. Markovov reťazec sa nazýva homogénny, ak podmienená pravdepodobnosť (prechod zo stavu do stavu) nezávisí od čísla pokusu. Preto namiesto písania jednoducho .

Príklad 1 Náhodná prechádzka. Nech je hmotná častica na priamke v bode s celočíselnou súradnicou. V určitých časových okamihoch častica zažíva otrasy. Pod vplyvom postrčenia sa častica pohne s pravdepodobnosťou o jednotku doprava a s pravdepodobnosťou o jednotku doľava. Je zrejmé, že poloha (súradnica) častice po otrase závisí od toho, kde sa častica nachádzala po bezprostredne predchádzajúcom otrase, a nezávisí od toho, ako sa pohybovala pod vplyvom iných predchádzajúcich otrasov.

Náhodná prechádzka je teda príkladom homogénneho Markovovho reťazca s diskrétnym časom.

Pravdepodobnosť prechodu je podmienená pravdepodobnosť, že zo stavu (v ktorom sa systém ocitol v dôsledku nejakého testu, bez ohľadu na to aké číslo) sa v dôsledku nasledujúceho testu systém presunie do stavu.

V označení teda prvý index označuje číslo predchádzajúceho stavu a druhý označuje číslo nasledujúceho stavu. Ide napríklad o pravdepodobnosť prechodu z druhého stavu do tretieho.

Nech je počet stavov konečný a rovný .

Matica prechodu systému je matica, ktorá obsahuje všetky pravdepodobnosti prechodu tohto systému:

Keďže každý riadok matice obsahuje pravdepodobnosti udalostí (prechod z rovnakého stavu do akéhokoľvek možného stavu), ktoré tvoria ucelenú skupinu, súčet pravdepodobností týchto udalostí sa rovná jednej. Inými slovami, súčet pravdepodobností prechodu každého riadku prechodovej matice sa rovná jednej:

Uveďme príklad prechodovej matice systému, ktorý môže byť v troch stavoch; prechod zo stavu do stavu nastáva podľa schémy homogénneho Markovovho reťazca; pravdepodobnosti prechodu sú dané maticou:

Tu vidíme, že ak bol systém v stave, tak po zmene stavu v jednom kroku zostane v rovnakom stave s pravdepodobnosťou 0,5, zostane v rovnakom stave s pravdepodobnosťou 0,5, prejde do stavu s pravdepodobnosťou 0,2, potom po prechode môže skončiť v štátoch ; nemôže prejsť zo štátu do. Posledný riadok matice nám ukazuje, že zo stavu prejsť do ktoréhokoľvek z možných stavov s rovnakou pravdepodobnosťou 0,1.

Na základe prechodovej matice systému môžete zostaviť takzvaný stavový graf systému, ktorý sa nazýva aj označený stavový graf. To je vhodné pre vizuálnu reprezentáciu obvodu. Pozrime sa na poradie vytvárania grafov na príklade.

Príklad 2 Pomocou danej prechodovej matice zostrojte stavový graf.

Pretože matice štvrtého rádu, potom má systém podľa toho 4 možné stavy.

Graf neuvádza pravdepodobnosti prechodu systému z jedného stavu do toho istého. Pri zvažovaní konkrétnych systémov je vhodné najskôr zostrojiť stavový graf, potom určiť pravdepodobnosť prechodov systému z jedného stavu do rovnakého (na základe požiadavky, aby súčet prvkov riadkov matice bol rovný jeden) a potom zostrojte prechodovú maticu systému.

§3. Markovova rovnosť

Definícia. Označme pravdepodobnosťou, že v dôsledku krokov (testov) sa systém bude pohybovať zo stavu do stavu . Napríklad je to pravdepodobnosť prechodu v 10 krokoch z druhého stavu do piateho.

Zdôrazňujeme, že pri získame pravdepodobnosti prechodu

Dajme si úlohu: poznať pravdepodobnosti prechodu, nájsť pravdepodobnosti prechodu systému zo stavu do stavu v krokoch.

Na tento účel uvádzame do úvahy prechodný stav (medzi a ). Inými slovami, budeme predpokladať, že z počiatočného stavu v krokoch systém prejde do medzistavu s pravdepodobnosťou , po ktorom v zostávajúcich krokoch z medzistavu prejde do konečného stavu s pravdepodobnosťou .

Pomocou vzorca celkovej pravdepodobnosti dostaneme

. (1)

Tento vzorec sa nazýva Markovova rovnosť.

Vysvetlenie. Predstavme si nasledujúci zápis:

– udalosť, o ktorú sa zaujímame (v krokoch systém prejde z počiatočného stavu do konečného stavu), teda ; − hypotézy (v krokoch systém prejde z počiatočného stavu do medzistavu), teda − podmienená pravdepodobnosť výskytu za predpokladu, že sa hypotéza uskutočnila (v krokoch sa systém presunie z medzistavu do konečného stavu), preto

Podľa vzorca celkovej pravdepodobnosti

()

Alebo v zápise, ktorý sme si osvojili

čo sa zhoduje s Markovovým vzorcom (1).

Poznaním všetkých pravdepodobností prechodu, teda poznaním matice prechodu zo stavu do stavu v jednom kroku, môžete nájsť pravdepodobnosti prechodu zo stavu do stavu v dvoch krokoch, a teda samotnú maticu prechodu; pomocou známej matice môžete nájsť maticu prechodu zo stavu do stavu v troch krokoch atď.

Vskutku, vloženie Markovovej rovnosti

,

reťazec značiek náhodná pravdepodobnosť

,

(2)

Pomocou vzorca (2) teda môžete nájsť všetky pravdepodobnosti a teda aj samotnú maticu. Keďže priame použitie vzorca (2) sa ukazuje ako únavné a maticový počet vedie k cieľu rýchlejšie, napíšem vzťahy vyplývajúce z (2) v maticovej forme:

Vložením (1) dostaneme podobne

Všeobecne

Veta 1. Pre akékoľvek s, t

(3)

Dôkaz. Vypočítajme pravdepodobnosť pomocou vzorca celkovej pravdepodobnosti (), uvedenie

Z rovnosti

Preto z rovnosti (4) a

dostaneme výrok vety.

Definujme maticu V maticovom zápise (3) má tvar

Odvtedy kde je matica pravdepodobnosti prechodu. Z (5) vyplýva

(6)

Výsledky získané v teórii matíc umožňujú pomocou vzorca (6) vypočítať a študovať ich správanie pri

Príklad 1 Určená prechodová matica Nájdite maticu prechodu

Riešenie. Použime vzorec

Vynásobením matíc nakoniec dostaneme:

.

§4. Stacionárny rozvod. Veta limitnej pravdepodobnosti

Rozdelenie pravdepodobnosti v ľubovoľnom časovom bode možno nájsť pomocou vzorca celkovej pravdepodobnosti

(7)

Môže sa ukázať, že to nezávisí od času. Zavolajme stacionárna distribúcia vektor , spĺňajúce podmienky

kde sú pravdepodobnosti prechodu.

Ak v markovskom reťazci potom za akékoľvek

Toto tvrdenie nasleduje indukciou z (7) a (8).

Uveďme formuláciu vety o limitných pravdepodobnostiach pre jednu dôležitú triedu Markovových reťazcov.

Veta 1. Ak pre niektoré >0 sú všetky prvky matice kladné, potom pre ľubovoľné , pre

, (9)

Kde stacionárne rozdelenie s nejakou konštantou spĺňajúcou nerovnosť 0< h <1.

Od , teda podľa podmienok vety sa z akéhokoľvek stavu môžete dostať v čase do akéhokoľvek stavu s kladnou pravdepodobnosťou. Podmienky vety vylučujú reťazce, ktoré sú v istom zmysle periodické.

Ak sú splnené podmienky vety 1, potom pravdepodobnosť, že systém je v určitom stave v limite, nezávisí od počiatočného rozdelenia. V skutočnosti z (9) a (7) vyplýva, že pre akúkoľvek počiatočnú distribúciu,

Uvažujme niekoľko príkladov Markovových reťazcov, pre ktoré nie sú splnené podmienky vety 1. Nie je ťažké overiť, že takéto príklady sú príklady. V tomto príklade majú pravdepodobnosti prechodu limity, ale tieto limity závisia od počiatočného stavu. Najmä vtedy, keď

V iných príkladoch rozsahy pravdepodobnosti zjavne neexistujú.

Nájdite stacionárne rozdelenie v príklade 1. Musíme nájsť vektor splnenie podmienok (8):

,

;

Preto existuje stacionárne rozdelenie, ale nie všetky súradnicové vektory sú pozitívne.

Pre polynomickú schému boli zavedené náhodné premenné rovnajúce sa počtu výsledkov daného typu. Uveďme podobné množstvá pre Markovove reťazce. Dovoliť je počet, koľkokrát systém vstúpi do stavu v čase. Potom frekvencia zasiahnutia systému do stavu . Pomocou vzorcov (9) môžeme dokázať, že keď sa priblíži . Aby ste to dosiahli, musíte získať asymptotické vzorce pre Čebyševovu nerovnosť a použiť ju. Tu je odvodenie vzorca pre . Predstavme si to vo forme

(10)

kde, ak a inak. Pretože

,

potom pomocou vlastnosti matematického očakávania a vzorca (9) získame

.

Na základe vety 1 je trojitý člen na pravej strane tejto rovnosti čiastočným súčtom konvergentného radu. Umiestňovanie , dostaneme

Pretože

Najmä zo vzorca (11) vyplýva, že

pri

Môžete tiež získať vzorec, ktorý sa používa na výpočet rozptylu.

§5. Dôkaz vety o obmedzenej pravdepodobnosti v Markovovom reťazci

Dokážme najprv dve lemmy. Položme

Lema 1. Pre každého existujú limity

Dôkaz. Pomocou rovnice (3) dostaneme

Sekvencie sú teda monotónne aj obmedzené. To znamená vyhlásenie Lemy 1.

Lema 2. Ak sú splnené podmienky vety 2, potom existujú konštanty, také že

Pre akékoľvek

kde , znamená súčet všetkých, pre ktoré je kladný, a súčet všetkých ostatných . Odtiaľ

. (12)

Keďže za podmienok vety 1 sú pravdepodobnosti prechodu pre všetky , potom pre ľubovoľné

A to kvôli konečnému počtu štátov

Poďme teraz odhadnúť rozdiel . Pomocou rovnice (3) s , dostaneme

Odtiaľ pomocou (8)-(10) nájdeme

=.

Kombináciou tohto vzťahu s nerovnosťou (14) dostaneme výrok lemy.

Prejdite na dôkaz vety. Keďže sekvencie sú monotónne, potom

0<. (15)

Z tohto a Lemy 1 nájdeme

Preto, keď dostanete a

Pozitivita vyplýva z nerovnosti (15). Prejdením na limitu a v rovnici (3) dostaneme, že spĺňa rovnicu (12). Veta bola dokázaná.

§6. Aplikácia Markovových reťazí

Markovove reťazce slúžia ako dobrý úvod do teórie náhodných procesov, t.j. teória jednoduchých postupností rodiny náhodných premenných, zvyčajne závislých od parametra, ktorý vo väčšine aplikácií zohráva úlohu času. Je určený predovšetkým na úplný opis dlhodobého aj lokálneho správania procesu. Tu sú niektoré z najviac študovaných problémov v tomto smere.

Brownov pohyb a jeho zovšeobecnenia - difúzne procesy a procesy s nezávislými prírastkami . Teória náhodných procesov prispela k prehĺbeniu prepojenia medzi teóriou pravdepodobnosti, teóriou operátorov a teóriou diferenciálnych rovníc, ktorá bola okrem iného dôležitá pre fyziku a iné aplikácie. Aplikácie zahŕňajú procesy, ktoré sú zaujímavé pre poistnú matematiku (poistenie), teóriu radenia, genetiku, riadenie dopravy, teóriu elektrických obvodov a teóriu zásob.

Martingales . Tieto procesy zachovávajú dostatok vlastností Markovových reťazcov, aby pre ne zostali platné dôležité ergodické vety. Martingales sa líši od Markovových reťazcov tým, že keď je známy súčasný stav, od minulosti nezávisí iba matematické očakávanie budúcnosti, ale nie nevyhnutne samotné rozdelenie pravdepodobnosti. Okrem toho, že teória martingalov je dôležitým nástrojom výskumu, obohatila teóriu náhodných procesov vznikajúcich v štatistike, teóriu jadrového štiepenia, genetiku a teóriu informácie o nové limitné vety.

Stacionárne procesy . Najstaršiu známu ergodickú vetu, ako bolo uvedené vyššie, možno interpretovať ako výsledok opisujúci obmedzujúce správanie stacionárneho náhodného procesu. Takýto proces má tú vlastnosť, že všetky pravdepodobnostné zákony, ktoré spĺňa, zostávajú vzhľadom na časové posuny nemenné. Ergodickú vetu, ktorú fyzici prvýkrát sformulovali ako hypotézu, možno znázorniť ako tvrdenie, že za určitých podmienok sa súborový priemer zhoduje s časovým priemerom. To znamená, že rovnaké informácie možno získať z dlhodobého pozorovania systému a zo súčasného (a okamžitého) pozorovania mnohých nezávislých kópií toho istého systému. Zákon veľkých čísel nie je nič iné ako špeciálny prípad Birkhoffovej ergodickej vety. Interpolácia a predikcia správania sa stacionárnych Gaussových procesov, chápaná v širšom zmysle, slúži ako dôležité zovšeobecnenie klasickej teórie najmenších štvorcov. Teória stacionárnych procesov je nevyhnutným výskumným nástrojom v mnohých oblastiach, napríklad v teórii komunikácie, ktorá sa zaoberá štúdiom a tvorbou systémov, ktoré prenášajú správy v prítomnosti šumu alebo náhodného rušenia.

Markovove procesy (procesy bez následkov) zohrávajú obrovskú úlohu pri modelovaní čakacích systémov (QS), ako aj pri modelovaní a výbere stratégie riadenia sociálno-ekonomických procesov vyskytujúcich sa v spoločnosti.

Markov reťazec sa dá použiť aj na generovanie textov. Ako vstup je dodaných niekoľko textov, potom sa zostaví Markovov reťazec s pravdepodobnosťou jedného slova za druhým a na základe tohto reťazca sa vytvorí výsledný text. Ukazuje sa, že hračka je veľmi zábavná!

Záver

V našej práci na kurze sme teda hovorili o Markovovom reťazovom okruhu. Dozvedeli sme sa, v akých oblastiach a ako sa používa, nezávislé testy dokázali vetu o limitujúcich pravdepodobnostiach v Markovovom reťazci, uviedli príklady na typický a homogénny Markovov reťazec, ako aj na nájdenie matice prechodu.

Videli sme, že dizajn Markovovej reťaze je priamym zovšeobecnením dizajnu nezávislého testu.

Zoznam použitej literatúry

1. Chistyakov V.P. Kurz teórie pravdepodobnosti. 6. vydanie, rev. − Petrohrad: Vydavateľstvo Lan, 2003. − 272 s. − (Učebnica pre vysoké školy. Odborná literatúra).

2. Gnedenko B.V. Kurz teórie pravdepodobnosti.

3. Gmurman V.E. Teória pravdepodobnosti a matematická štatistika.

4. Ventzel E.S. Teória pravdepodobnosti a jej inžinierske aplikácie.

5. Kolmogorov A.N., Zhurbenko I.G., Prochorov A.V. Úvod do teórie pravdepodobnosti. − Moskva-Iževsk: Inštitút počítačového výskumu, 2003, 188 s.

6. Katz M. Pravdepodobnosť a súvisiace problémy vo fyzike.

Markov reťaz- reťazec udalostí, v ktorom pravdepodobnosť každej udalosti závisí len od predchádzajúceho stavu.

Tento článok má abstraktný charakter, je napísaný na základe zdrojov uvedených na konci, ktoré sú miestami citované.

Úvod do teórie Markovových reťazcov

Markovov reťazec je postupnosť náhodných udalostí, v ktorých pravdepodobnosť každej udalosti závisí iba od stavu, v ktorom sa proces práve nachádza, a nezávisí od skorších stavov. Konečný diskrétny obvod je určený:

∑ j = 1… n p ij = 1

Príklad matice pravdepodobností prechodu s množinou stavov S = (S 1, ..., S 5), vektor počiatočných pravdepodobností p (0) = (1, 0, 0, 0, 0):

S Pomocou vektora počiatočných pravdepodobností a prechodovej matice môžeme vypočítať stochastický vektor p (n) - vektor zložený z pravdepodobností p (n) (i), že proces bude v čase n v stave i. P (n) môžete získať pomocou vzorca:

p(n) = p(0)xPn

Vektory p (n) s rastom n sa v niektorých prípadoch stabilizujú - konvergujú k určitému pravdepodobnostnému vektoru ρ, ktorý možno nazvať stacionárnym rozložením reťazca. Stacionarita sa prejavuje v tom, že ak vezmeme p (0) = ρ, dostaneme p (n) = ρ pre ľubovoľné n.

Najjednoduchšie kritérium, ktoré zaručuje konvergenciu k stacionárnemu rozdeleniu, je nasledovné: ak sú všetky prvky matice pravdepodobnosti prechodu P kladné, potom keďže n smeruje k nekonečnu, vektor p (n) smeruje k vektoru ρ, čo je jediné riešenie. do systému formulára

Dá sa tiež ukázať, že ak pre nejakú kladnú hodnotu n sú všetky prvky matice P n kladné, potom sa vektor p (n) stále ustáli.

Dôkaz týchto tvrdení je uvedený podrobne.

Markovov reťazec je znázornený ako prechodový graf, ktorého vrcholy zodpovedajú stavom reťazca a oblúky zodpovedajú prechodom medzi nimi. Váha oblúka (i, j) spájajúceho vrcholy si a sj sa bude rovnať pravdepodobnosti pi(j) prechodu z prvého stavu do druhého. Graf zodpovedajúci vyššie uvedenej matici:

TO klasifikácia stavov Markovových reťazcov

Pri zvažovaní Markovových reťazcov nás môže zaujímať správanie sa systému v krátkom časovom období. V tomto prípade sa absolútne pravdepodobnosti vypočítajú pomocou vzorcov z predchádzajúcej časti. Dôležitejšie je však študovať správanie systému v dlhom časovom intervale, kedy počet prechodov má tendenciu k nekonečnu. Ďalej sú uvedené definície stavov Markovových reťazcov, ktoré sú potrebné pre štúdium správania systému v dlhodobom horizonte.

Markovove reťazce sú klasifikované v závislosti od možnosti prechodu z jedného stavu do druhého.

Skupiny stavov Markovovho reťazca (podmnožiny vrcholov prechodového grafu), ktoré zodpovedajú slepým vrcholom rádového diagramu prechodového grafu, sa nazývajú ergodické triedy reťazca. Ak vezmeme do úvahy graf zobrazený vyššie, vidíme, že obsahuje 1 ergodickú triedu M1 = (S5), dosiahnuteľnú zo silne prepojenej zložky zodpovedajúcej podmnožine vrcholov M2 = (S1, S2, S3, S4). Stavy, ktoré sú v ergodických triedach, sa nazývajú esenciálne a ostatné sa nazývajú nepodstatné (hoci takéto názvy sa nezhodujú so zdravým rozumom). Absorpčný stav si je špeciálnym prípadom ergodickej triedy. Potom, keď je v takomto stave, proces sa zastaví. Pre Si bude platiť pii = 1, t.j. v prechodovom grafe z neho bude vychádzať len jedna hrana - slučka.

Absorpčné Markovove reťazce sa používajú ako dočasné modely programov a výpočtových procesov. Pri modelovaní programu sú stavy obvodu identifikované s blokmi programu a matica pravdepodobností prechodu určuje poradie prechodov medzi blokmi v závislosti od štruktúry programu a distribúcie počiatočných údajov, hodnôt ​ktoré ovplyvňujú vývoj výpočtového procesu. V dôsledku reprezentácie programu absorbujúcim obvodom je možné vypočítať počet prístupov k programovým blokom a čas vykonávania programu, odhadnutý priemernými hodnotami, rozptylmi a v prípade potreby rozdeleniami. Pomocou týchto štatistík v budúcnosti môžete optimalizovať programový kód – použite nízkoúrovňové metódy na zrýchlenie kritických častí programu. Táto metóda sa nazýva profilovanie kódu.

Napríklad v Dijkstrovom algoritme sú prítomné nasledujúce stavy obvodu:

vertex (v), extrahovať nový vrchol z prioritného frontu, prejsť len do stavu b;

begin (b), začiatok cyklu vyhľadávania odchádzajúcich oblúkov pre postup zoslabovania;

analýza (a), analýza ďalšieho oblúka, možný prechod na a, d alebo e;

zníženie (d), zníženie odhadu pre nejaký vrchol grafu, prechod na a;

koniec (e), dokončenie cyklu, prechod na ďalší vrchol.

Zostáva nastaviť pravdepodobnosti prechodu medzi vrcholmi a môžete študovať trvanie prechodov medzi vrcholmi, pravdepodobnosti prechodu do rôznych stavov a ďalšie priemerné charakteristiky procesu.

Podobne výpočtový proces, ktorý spočíva v prístupe k systémovým zdrojom v poradí určenom programom, môže byť reprezentovaný absorbujúcim Markovovým reťazcom, ktorého stavy zodpovedajú využitiu systémových prostriedkov - procesor, pamäť a periférne zariadenia; pravdepodobnosti odrážajú poradie prístupu k rôznym zdrojom. Vďaka tomu je výpočtový proces prezentovaný vo forme vhodnej na analýzu jeho charakteristík.

Markovov reťazec sa považuje za neredukovateľný, ak je možné dosiahnuť akýkoľvek stav Sj z akéhokoľvek iného stavu Si v konečnom počte prechodov. V tomto prípade sa hovorí, že všetky stavy obvodu komunikujú a prechodový graf je súčasťou silnej konektivity. Proces generovaný ergodickým reťazcom, ktorý začal v určitom stave, nikdy nekončí, ale postupne prechádza z jedného stavu do druhého a končí v rôznych stavoch s rôznymi frekvenciami v závislosti od pravdepodobnosti prechodu. Preto je hlavnou charakteristikou ergodického reťazca

pravdepodobnosť, že proces je v stavoch Sj, j = 1,…, n, zlomok času, ktorý proces strávi v každom zo stavov. Ako modely spoľahlivosti systému sa používajú neredukovateľné obvody. Ak totiž zdroj, ktorý proces veľmi často používa, zlyhá, bude ohrozená funkčnosť celého systému. V takom prípade môže duplikovanie takéhoto kritického zdroja pomôcť vyhnúť sa zlyhaniam. V tomto prípade sa stavy systému, ktoré sa líšia zložením prevádzkyschopných a poruchových zariadení, interpretujú ako stavy obvodu, medzi ktorými sú prechody spojené s poruchami a obnovou zariadení a zmenami vo väzbách medzi nimi, vykonávané s cieľom zachovať prevádzkyschopnosti systému. Odhady charakteristík neredukovateľného obvodu poskytujú predstavu o spoľahlivosti správania systému ako celku. Takéto obvody môžu byť tiež modelmi interakcie medzi zariadeniami a úlohami predloženými na spracovanie.

Príklady použitia

Poruchový servisný systém

Server sa skladá z niekoľkých blokov, ako sú modemy alebo sieťové karty, ktoré prijímajú požiadavky používateľov na službu. Ak sú všetky bloky obsadené, požiadavka sa stratí. Ak jeden z blokov prijme požiadavku, je zaneprázdnený až do konca spracovania. Zoberme si počet neobsadených blokov ako stavy. Čas bude diskrétny. Označme α pravdepodobnosť prijatia požiadavky. Tiež sa domnievame, že čas služby je tiež náhodný a pozostáva z nezávislých pokračovaní, t.j. požiadavka s pravdepodobnosťou β je obsluhovaná v jednom kroku as pravdepodobnosťou (1 - β) je po tomto kroku obsluhovaná ako nová požiadavka. To dáva pravdepodobnosť (1 - β) β pre dvojkrokovú službu, (1 - β)2 β pre trojkrokovú službu atď. Zoberme si príklad so 4 paralelne pracujúcimi zariadeniami. Vytvorme maticu pravdepodobností prechodu pre vybrané stavy:

M Možno poznamenať, že má jedinečnú ergodickú triedu, a preto má systém p × P = p v triede pravdepodobnostných vektorov jedinečné riešenie. Zapíšme si rovnice systému, ktorý nám umožňuje nájsť toto riešenie:

Teraz je známa množina pravdepodobností πi, že v stacionárnom režime bude mať systém obsadených blokov i. Potom sú za zlomok času p 4 = C γ 4 /4 všetky bloky v systéme obsadené, systém nereaguje na požiadavky. Získané výsledky platia pre ľubovoľný počet blokov. Teraz ich môžete využiť: môžete porovnať náklady na prídavné zariadenia a skrátenie doby, počas ktorej je systém plne obsadený.

Viac o tomto príklade si môžete prečítať v .

Rozhodovacie procesy s konečným a nekonečným počtom etáp

Uvažujme proces, v ktorom existuje niekoľko matíc pravdepodobnosti prechodu. Pre každý moment v čase závisí výber jednej alebo druhej matice od rozhodnutia, ktoré urobíme. Vyššie uvedené možno pochopiť pomocou nasledujúceho príkladu. Na základe analýzy pôdy záhradník hodnotí jej stav jedným z troch čísel: (1) - dobrý, (2) - uspokojivý alebo (3) - zlý. Záhradník si zároveň všimol, že produktivita pôdy v bežnom roku závisí len od jej stavu v predchádzajúcom roku. Preto pravdepodobnosti prechodu pôdy bez vonkajších vplyvov z jedného stavu do druhého môžu byť reprezentované nasledujúcim Markovovým reťazcom s maticou P1:

L Je prirodzené, že produktivita pôdy sa časom zhoršuje. Napríklad, ak bol minulý rok stav pôdy uspokojivý, potom tento rok môže zostať iba rovnaký alebo sa môže stať zlým, ale nestane sa dobrým. Záhradkár však môže ovplyvniť stav pôdy a zmeniť pravdepodobnosti prechodu v matici P1 na zodpovedajúce matice P2:

T Teraz môžeme každý prechod z jedného stavu do druhého spájať s určitou príjmovou funkciou, ktorá je definovaná ako zisk alebo strata za jednoročné obdobie. Záhradkár sa môže rozhodnúť, či použije alebo nepoužije hnojivá, to určí jeho konečný príjem alebo stratu. Predstavme si matice R1 a R2, ktoré určujú príjmové funkcie v závislosti od nákladov na hnojivá a kvality pôdy:

N Napokon je záhradkár postavený pred problém, akú stratégiu zvoliť, aby maximalizoval priemerný očakávaný príjem. Možno uvažovať o dvoch typoch problémov: s konečným a nekonečným počtom štádií. V tomto prípade sa záhradníkova činnosť jedného dňa určite skončí. Vizualizátory navyše riešia problém rozhodovania pre konečný počet etáp. Nech má záhradník v úmysle skoncovať so svojím zamestnaním po N rokoch. Našou úlohou je teraz určiť optimálnu stratégiu správania záhradníka, teda stratégiu, ktorá maximalizuje jeho príjem. Konečnosť počtu etáp v našom probléme sa prejavuje v tom, že záhradkárovi je jedno, čo bude s jeho poľnohospodárskou pôdou N+1 rok (dôležité sú pre neho všetky roky až N vrátane). Teraz vidíme, že v tomto prípade sa problém hľadania stratégie zmení na problém dynamického programovania. Ak označíme fn(i) maximálny priemerný očakávaný príjem, ktorý je možné získať počas štádií od n do N vrátane, počnúc stavom číslo i, potom je ľahké odvodiť opakujúce sa

Z kde k je číslo použitej stratégie. Táto rovnica je založená na skutočnosti, že celkový príjem rijk + fn+1(j) sa získa ako výsledok prechodu zo stavu i v štádiu n do stavu j v štádiu n+1 s pravdepodobnosťou pijk.

Teraz je možné nájsť optimálne riešenie postupným výpočtom fn(i) v zostupnom smere (n = N…1). Zároveň zavedenie vektora počiatočných pravdepodobností do zadania problému neskomplikuje jeho riešenie.

Tento príklad je tiež diskutovaný v.

Modelovanie kombinácií slov v texte

Uvažujme text pozostávajúci zo slov w. Predstavme si proces, v ktorom sú stavy slová, takže keď je v stave (Si), systém prejde do stavu (sj) podľa matice pravdepodobností prechodu. V prvom rade je potrebné „trénovať“ systém: poskytnúť dostatočne veľký text ako vstup na vyhodnotenie pravdepodobnosti prechodu. A potom môžete zostaviť trajektórie Markovovho reťazca. Zvýšenie sémantickej záťaže textu konštruovaného pomocou algoritmu Markovovho reťazca je možné len zvýšením poradia, kde stavom nie je jedno slovo, ale množiny s väčšou mocnosťou - dvojice (u, v), trojice (u, v, w) , atď. Navyše v reťazcoch prvého a piateho rádu bude stále malý zmysel. Význam sa začne objavovať, keď sa rozmer poradia zvýši aspoň na priemerný počet slov v typickej fráze v zdrojovom texte. Ale takto sa pohnúť nedá, pretože rast sémantického zaťaženia textu v markovských reťazcoch vyššieho rádu nastáva oveľa pomalšie ako pokles jedinečnosti textu. A text postavený na Markovových reťazcoch, napríklad tridsiateho rádu, stále nebude taký zmysluplný, aby človeka zaujal, ale už dosť podobný pôvodnému textu a počet stavov v takom reťazci bude byť úžasný.

Táto technológia je v súčasnosti veľmi rozšírená (bohužiaľ) na internete na vytváranie obsahu webových stránok. Ľudia, ktorí chcú zvýšiť návštevnosť svojej webovej stránky a zlepšiť jej hodnotenie vo vyhľadávačoch, majú tendenciu vkladať na svoje stránky čo najviac kľúčových slov pre vyhľadávanie. Vyhľadávače však používajú algoritmy, ktoré dokážu rozlíšiť skutočný text od nesúrodej spleti kľúčových slov. Potom na oklamanie vyhľadávačov využívajú texty vytvorené generátorom na báze Markovovho reťazca. Existujú, samozrejme, pozitívne príklady využitia Markovových reťazcov na prácu s textom, používajú sa pri určovaní autorstva a analýze autenticity textov.

Markovské reťazce a lotérie

V niektorých prípadoch sa pravdepodobnostný model používa pri predpovedaní čísel v rôznych lotériách. Zjavne nemá zmysel používať Markovove reťazce na modelovanie postupnosti rôznych cirkulácií. To, čo sa stalo s loptičkami pri žrebovaní, žiadnym spôsobom neovplyvní výsledky nasledujúceho žrebovania, pretože po žrebovaní sa loptičky zbierajú a v nasledujúcom žrebovaní sa vkladajú do žrebovacej priehradky v pevnom poradí. V tomto prípade sa stratí spojenie s minulým obehom. Ďalšia vec je postupnosť vypadávania loptičiek v rámci jedného ťahu. V tomto prípade je pokles ďalšej loptičky určený stavom lotériového automatu v čase pádu predchádzajúcej loptičky. Postupnosť loptičiek vypadnutých v jednom ťahu je teda Markovova reťaz a takýto model možno použiť. Pri analýze číselných lotérií je tu veľký problém. Stav lotériového automatu po vypadnutí ďalšej loptičky určuje ďalšie dianie, problém je však v tom, že tento stav je nám neznámy. Vieme len, že vypadla istá lopta. Ale keď táto guľa vypadne, zostávajúce loptičky môžu byť usporiadané rôznymi spôsobmi, takže existuje skupina veľmi veľkého počtu stavov zodpovedajúcich rovnakej pozorovanej udalosti. Preto môžeme zostrojiť iba maticu pravdepodobností prechodu medzi takýmito skupinami stavov. Tieto pravdepodobnosti sú priemerom pravdepodobností prechodov medzi rôznymi jednotlivými stavmi, čo samozrejme znižuje efektivitu aplikácie modelu Markovho reťazca na numerické lotérie.

Podobne ako v tomto prípade je možné takýto model neurónovej siete použiť na predpovedanie počasia, kurzov mien a v spojení s inými systémami, kde sú dostupné historické dáta a novoprijaté informácie je možné využiť v budúcnosti. Dobrá aplikácia v tomto prípade, keď sú známe len prejavy systému, ale nie vnútorné (skryté) stavy, sa dá aplikovať na skryté Markovove modely, o ktorých sa podrobne hovorí vo Wikiknihách (skryté Markovove modely).

Markovove reťaze

Úvod

§ 1. Markov reťaz

§ 2. Homogénna Markovova reťaz. Pravdepodobnosti prechodu. Prechodová matica

§3. Markovova rovnosť

§4. Stacionárny rozvod. Veta limitnej pravdepodobnosti

§5. Dôkaz vety o obmedzenej pravdepodobnosti v Markovovom reťazci

§6. Aplikácia Markovových reťazí

Záver

Zoznam použitej literatúry

Úvod

Témou našej práce v kurze je Markov reťazec. Markovove reťazce sú pomenované po vynikajúcom ruskom matematikovi Andrejovi Andreevičovi Markovovi, ktorý vo veľkej miere pracoval na náhodných procesoch a významne prispel k rozvoju tejto oblasti. V poslednej dobe môžete počuť o využití Markovových reťazcov v rôznych oblastiach: moderné webové technológie, pri analýze literárnych textov alebo dokonca pri vývoji taktiky pre futbalový tím. Kto nevie, čo sú Markovove reťazce, môže mať pocit, že ide o niečo veľmi zložité a takmer nepochopiteľné.

Nie, je to práve naopak. Markovov reťazec je jedným z najjednoduchších prípadov postupnosti náhodných udalostí. Ale napriek svojej jednoduchosti môže byť často užitočný aj pri opise pomerne zložitých javov. Markovov reťazec je postupnosť náhodných udalostí, v ktorých pravdepodobnosť každej udalosti závisí iba od predchádzajúcej udalosti, ale nezávisí od skorších udalostí.

Predtým, ako sa ponoríme hlbšie, musíme zvážiť niekoľko pomocných otázok, ktoré sú všeobecne známe, ale sú absolútne nevyhnutné pre ďalší výklad.

Cieľom mojej kurzovej práce je podrobnejšie študovať aplikácie Markovových reťazcov, zadávania problémov a Markovových problémov.

§1. Markov reťaz

Predstavme si, že sa vykonáva postupnosť testov.

Definícia. Markovov reťazec je sled pokusov, v každom z nich sa objavuje len jeden z nasledujúcich.

nekompatibilné udalosti celej skupiny a podmienená pravdepodobnosť, že udalosť nastane v tej skúške, za predpokladu, že sa udalosť vyskytla v tej skúške, nezávisí od výsledkov predchádzajúcich skúšok.

Napríklad, ak sled pokusov tvorí Markovov reťazec a celá skupina pozostáva zo štyroch nezlučiteľných udalostí

a je známe, že udalosť sa objavila v šiestom pokuse, potom podmienená pravdepodobnosť, že udalosť nastane v siedmom pokuse, nezávisí od toho, aké udalosti sa objavili v prvom, druhom, ..., piatom pokuse.

Všimnite si, že nezávislé testy sú špeciálnym prípadom Markovovho reťazca. V skutočnosti, ak sú testy nezávislé, potom výskyt určitej udalosti v akomkoľvek teste nezávisí od výsledkov predtým vykonaných testov. Z toho vyplýva, že koncept Markovovho reťazca je zovšeobecnením konceptu nezávislých pokusov.

Často sa pri prezentovaní teórie Markovových reťazcov pridržiavajú inej terminológie a hovoria o určitom fyzikálnom systéme

, ktorý sa v každom časovom okamihu nachádza v jednom zo stavov: , a mení svoj stav iba v samostatných bodoch v čase, to znamená, že systém sa pohybuje z jedného stavu do druhého (napríklad z do ). Pre Markovove reťazce pravdepodobnosť prechodu do akéhokoľvek stavu v súčasnosti závisí iba od toho, v akom stave sa systém práve nachádzal, a nemení sa, pretože jeho stavy v skorších momentoch sú známe. Najmä po skúške môže systém zostať v rovnakom stave („presun“ zo stavu do stavu).

Pre ilustráciu uvažujme o príklade.

Príklad 1 Predstavme si, že častica umiestnená na priamke sa pohybuje pozdĺž tejto priamky pod vplyvom náhodných otrasov vyskytujúcich sa v momentoch

. Častica môže byť umiestnená v bodoch s celočíselnými súradnicami: ; Reflexné steny sú umiestnené v bodoch. Každé zatlačenie posunie časticu s pravdepodobnosťou doprava a s pravdepodobnosťou doľava, pokiaľ sa častica nenachádza pri stene. Ak je častica blízko steny, potom ju akékoľvek zatlačenie posunie o jednu jednotku vo vnútri medzery medzi stenami. Tu vidíme, že tento príklad chôdze častice je typický Markovov reťazec.

Udalosti sa teda nazývajú stavy systému a testy sa nazývajú zmeny jeho stavov.

Poďme teraz definovať Markovov reťazec pomocou novej terminológie.

Markovov reťazec s diskrétnym časom je obvod, ktorého stavy sa menia v určitých pevných časoch.

Markovov reťazec so spojitým časom je reťazec, ktorého stavy sa menia v ľubovoľných náhodných možných okamihoch v čase.

§2. Homogénny Markov reťazec. Pravdepodobnosti prechodu. Prechodová matica

Definícia. Markovov reťazec sa považuje za homogénny, ak je podmienená pravdepodobnosť

(prechod zo stavu do stavu) nezávisí od čísla testu. Preto namiesto písania jednoducho .

Príklad 1 Náhodná prechádzka. Nech je to na priamke

v bode s celočíselnou súradnicou je hmotná častica. V určitých časových okamihoch častica zažíva otrasy. Pod vplyvom postrčenia sa častica pohne s pravdepodobnosťou o jednotku doprava a s pravdepodobnosťou o jednotku doľava. Je zrejmé, že poloha (súradnica) častice po otrase závisí od toho, kde sa častica nachádzala po bezprostredne predchádzajúcom otrase, a nezávisí od toho, ako sa pohybovala pod vplyvom iných predchádzajúcich otrasov.

Náhodná prechádzka je teda príkladom homogénneho Markovovho reťazca s diskrétnym časom.

Podobné články