Matrica prelaznih stanja Markovljevog lanca. Obični Markovljevi lanci. Napomenimo neke od njegovih karakteristika
Razmotrimo problem magarca koji stoji tačno između dva plast sena: ražene i pšenične slame (slika 10.5).
Magarac stoji između dva plast sena: „Raži“ i „Pšenice“ (Sl. 10.5). Svake minute ili se kreće deset metara prema prvom plastu sijena (sa vjerovatnoćom), ili prema drugom plastu sijena (sa vjerovatnoćom), ili ostaje gdje je stajao (s vjerovatnoćom); ovo ponašanje se naziva jednodimenzionalnim nasumično hodanje. Pretpostavićemo da oba plast sijena „upijaju“ u smislu da ako se magarac približi jednom od plastova sijena, on će tu i ostati. Znajući rastojanje između dva plast sijena i početnu poziciju magarca, možete postaviti nekoliko pitanja, na primjer: na kojem plastu sijena će najvjerovatnije završiti i koje mu je najvjerovatnije vrijeme potrebno da stigne tamo?
Rice. 10.5.
Da bismo detaljnije istražili ovaj problem, pretpostavimo da je razmak između potresa pedeset metara, a da je naš magarac dvadeset metara od šoka "Pšenica". Ako su mjesta na kojima možete stati označena sa 
( - sami šokovi), tada se njegov početni položaj može specificirati vektorom čija je komponenta jednaka vjerovatnoći da se inicijalno nalazi u . Nadalje, nakon jedne minute vjerovatnoće njegove lokacije su opisane vektorom, a nakon dvije minute - vektorom. Jasno je da direktno izračunavanje vjerovatnoće njegovog boravka na datoj lokaciji nakon prolaska minuta postaje teško. Ispostavilo se da je najpogodniji način da to učinite ulazak tranziciona matrica.
Neka je vjerovatnoća da će se pomaknuti od do za jednu minutu. Na primjer, i. Ove vjerovatnoće se nazivaju vjerovatnoće tranzicije, a -matrica se zove tranziciona matrica. Imajte na umu da je svaki element matrice nenegativan i da je zbroj elemenata bilo kojeg od reda jednak jedan. Iz svega proizilazi da - početni vektor reda definiran gore, lokacija magarca nakon jedne minute je opisana vektorom reda, a nakon minuta - vektorom. Drugim riječima, -ta komponenta vektora određuje vjerovatnoću da nakon nekoliko minuta magarac završi u .
Ovi koncepti se mogu generalizovati. Hajde da pozovemo vektor verovatnoće vektor reda, čije su sve komponente nenegativne i sabiraju do jedne. Onda tranziciona matrica definira se kao kvadratna matrica u kojoj je svaki red vektor vjerovatnoća. Sada možemo definirati Markovljev lanac (ili samo lanac) kao par, gdje postoji - tranziciona matrica, i postoji vektor reda. Ako se svaki element od posmatra kao verovatnoća prelaska iz pozicije u poziciju, i - kao početni vektor verovatnoće, onda dolazimo do klasičnog koncepta diskretni stacionarni Markovljev lanac, koji se može naći u knjigama o teoriji vjerovatnoće (vidi Feller V. Uvod u teoriju vjerovatnoće i njene primjene. Vol. 1. M.: Mir. 1967) Položaj se obično naziva stanjem lanca. Hajde da opišemo razne načine njihove klasifikacije.
Zanimaće nas sledeće: da li je moguće doći iz jednog stanja u drugo, i ako jeste, u kom najkraćem roku. Na primjer, u problemu magarca možete doći od do za tri minute, ali nikako ne možete doći od do do. Stoga će nas uglavnom zanimati ne same vjerovatnoće, već da li su one pozitivne ili ne. Tada postoji nada da se svi ovi podaci mogu predstaviti u obliku digrafa, čiji vrhovi odgovaraju stanjima, a lukovi pokazuju da li je moguće prijeći iz jednog stanja u drugo u jednoj minuti. Preciznije, ako je svako stanje predstavljeno svojim odgovarajućim vrhom).
Markovljev slučajni proces sa diskretnim stanjima i diskretnim vremenom nazvan Markovljev lanac . Za takav proces, trenuci t 1, t 2 kada sistem S može promijeniti svoje stanje, smatraju se uzastopnim koracima procesa, a argument od kojeg zavisi proces nije vrijeme t, a broj koraka je 1, 2, k, Slučajni proces u ovom slučaju karakterizira niz stanja S(0), S(1), S(2), S(k), Gdje S(0)- početno stanje sistema (prije prvog koraka); S(1)- stanje sistema nakon prvog koraka; S(k)- stanje sistema nakon k korak...
Događaj ( S(k) = S i), koji se sastoji u tome da odmah nakon k od koraka sistem je u stanju S i (i= 1, 2,), je slučajan događaj. Redoslijed stanja S(0), S(1), S(k), može se smatrati nizom slučajnih događaja. Ovaj nasumični slijed događaja se zove Markov lanac , ako za svaki korak vjerovatnoća prelaska iz bilo kojeg stanja S i u bilo koje S j ne zavisi od toga kada i kako je sistem došao u stanje S i . Početno stanje S(0) može biti unaprijed određena ili nasumična.
Vjerovatnoće stanja Markovljevog lanca nazivaju se verovatnoćama P i (k)šta dolazi posle k korak (i do ( k+ 1)th) sistem Sće biti u mogućnosti da S i (i = 1, 2, n). Očigledno, za bilo koje k.
Početna raspodjela vjerovatnoće Markovljevog lanca naziva se distribucija vjerovatnoća stanja na početku procesa:
P 1 (0), P 2 (0), P i (0), P n (0).
U posebnom slučaju, ako je početno stanje sistema S tačno poznato S(0) = S i, zatim početnu vjerovatnoću R i (0)= 1, a svi ostali su jednaki nuli.
Vjerovatnoća prijelaza (vjerovatnoća prijelaza) na k-ti korak od države S i u državi Sj naziva se uslovna verovatnoća da sistem S poslije k korak će moći Sj pod uslovom da neposredno prije (poslije k- 1 korak) bila je u stanju S i.
Pošto sistem može biti u jednom od n stanja, zatim za svaki trenutak vremena t mora biti postavljeno n 2 vjerovatnoće tranzicije P ij, koji su prikladno predstavljeni u obliku sljedeće matrice:
Gdje R ij- vjerovatnoća tranzicije u jednom koraku iz stanja S i u državi Sj;
P ii- vjerovatnoća kašnjenja sistema u stanju S i.
Takva matrica se naziva matrica prijelaza ili matrica vjerojatnosti prijelaza.
Ako vjerovatnoće prijelaza ne zavise od broja koraka (od vremena), već samo od toga u koje stanje se prijelaz vrši, tada će odgovarajući naziva se Markovljev lanac homogena .
Prijelazne vjerovatnoće homogenog Markovljevog lanca R ij formiraju kvadratnu matricu veličine n m.
Napomenimo neke od njegovih karakteristika:
1. Svaka linija karakteriše izabrano stanje sistema, a njeni elementi predstavljaju verovatnoće svih mogućih prelaza u jednom koraku od izabranog (od i th) stanje, uključujući prelazak u sebe.
2. Elementi kolona pokazuju vjerovatnoće svih mogućih tranzicija sistema u jednom koraku na dati ( j-f) stanje (drugim rečima, red karakteriše verovatnoću prelaska sistema iz stanja, kolona - u stanje).
3. Zbir vjerovatnoća svakog reda jednak je jedan, budući da prijelazi čine kompletnu grupu nekompatibilnih događaja:
4. Duž glavne dijagonale matrice vjerovatnoće prijelaza nalaze se vjerovatnoće P ii da sistem neće izaći iz stanja S i, ali će ostati u njemu.
Ako su za homogeni Markovljev lanac date početna distribucija vjerovatnoće i matrica prijelaznih vjerovatnoća, tada su vjerovatnoće stanja sistema P i (k) (i, j= 1, 2, n) određuju se ponavljajućom formulom:
Primjer 1. Razmotrimo proces funkcionisanja sistema - automobila. Neka automobil (sistem) tokom jedne smjene (dana) bude u jednom od dva stanja: ispravan ( S 1) i neispravan ( S 2). Grafikon stanja sistema prikazan je na Sl. 3.2.
Rice. 3.2.Grafikon stanja vozila
Kao rezultat masovnih posmatranja rada vozila, sastavljena je sljedeća matrica vjerovatnoća tranzicije:
Gdje P 11= 0,8 - vjerovatnoća da će automobil ostati u dobrom stanju;
P 12= 0,2 - vjerovatnoća da automobil pređe iz "dobrog" stanja u "neispravno" stanje;
P 21= 0,9 - vjerovatnoća da automobil pređe iz "neispravnog" u "dobro" stanje;
P 22= 0,1 - vjerovatnoća da će automobil ostati u "neispravnom" stanju.
Dat je vektor početnih vjerovatnoća stanja automobila, tj. P 1 (0)= 0 i R 2 (0)=1.
Potrebno je utvrditi vjerovatnoće stanja automobila nakon tri dana.
Koristeći matricu vjerovatnoća tranzicije i formulu (3.1), određujemo vjerovatnoće stanja P i (k) nakon prvog koraka (nakon prvog dana):
P 1 (1) = P 1 (0)×P 11 + P 2 (0)×P 21 = 0?0,8 + 1?0,9 = 0,9;
P 2 (1) = P 1 (0)×P 12 + P 2 (0)×P 22 = 0?0,2 + 1?0,1 = 0,2.
Vjerojatnosti stanja nakon drugog koraka (nakon drugog dana) su sljedeće:
P 1 (2) = P 1 (1)×P 11 + P 2 (1)×P 21= 0,9×0,8 + 0,1×0,9 = 0,81;
= 0,9×0,2 + 0,1×0,1 = 0,19.
Vjerovatnoće stanja nakon trećeg koraka (nakon trećeg dana) su jednake:
P 1 (3) = P 1 (2)×P 11 + P 2 (2)×P 21= 0,81×0,8 + 0,19×0,9 = 0,819;
= 0,81×0,2 + 0,19×0,1 = 0,181.
Tako će nakon trećeg dana automobil biti u dobrom stanju sa vjerovatnoćom od 0,819 i u „neispravnom“ stanju sa vjerovatnoćom od 0,181.
Primjer 2. Tokom rada, računar se može smatrati fizičkim sistemom S, koji kao rezultat provjere može završiti u jednom od sljedećih stanja: S 1- Računar je potpuno operativan; S 2- Računar ima kvarove u RAM-u u kojima može riješiti probleme; S 3- Računar ima značajne greške i može riješiti ograničenu klasu problema; S 4- Računar je potpuno pokvaren.
U početnom trenutku, računar je potpuno operativan (stanje S 1). Računar se provjerava u određeno vrijeme t 1, t 2, t 3. Proces koji se odvija u sistemu S, može se smatrati homogenim Markov lanac sa tri koraka (prva, druga, treća kompjuterska provjera). Matrica vjerovatnoće prijelaza ima oblik
Odredite vjerovatnoće stanja računara nakon tri provjere.
Rješenje. Grafikon stanja ima oblik prikazan na sl. 3.3. Pored svake strelice je odgovarajuća vjerovatnoća prijelaza. Vjerovatnoće početnog stanja P 1 (0) = 1, P2(0) = P 3 (0) = P 4 (0) = 0.
Rice. 3.3. Grafikon stanja računara
Koristeći formulu (3.1), uzimajući u obzir u zbiru vjerovatnoća samo ona stanja iz kojih je moguć direktan prijelaz u dato stanje, nalazimo:
P 1 (1) = P 1 (0)×P 11= 1×0,3 = 0,3;
P 2 (1) = P 1 (0)×P 12= 1×0,4 = 0,4;
P 3 (1) = P 1 (0)×P 13= 1×0,1 = 0,1;
P 4 (1) = P 1 (0)×P 14= 1×0,2 = 0,2;
P 1 (2) = P 1 (1)×P 11= 0,3×0,3 = 0,09;
P 2 (2) = P 1 (1)×P 12 + P 2 (1)×P 22= 0,3×0,4 + 0,4×0,2 = 0,20;
P 3 (2) = P 1 (1)×P 13 + P 2 (1)×P 23 + P 3 (1)×P 33 = 0,27;
P 4 (2) = P 1 (1)×P 14 + P 2 (1)×P 24 + P 3 (1)×P 34 + P 4 (1)×P 44 = 0,44;
P 1 (3) = P 1 (2) × P 11= 0,09×0,3 = 0,027;
P 2 (3) = P 1 (2)×P 12 + P 2 (2)×P 22= 0,09×0,4 + 0,20×0,2 = 0,076;
P 3 (3) = P 1 (2)×P 13 + P 2 (2)×P 23 + P 3 (2)×P 33 = 0,217;
P 4 (3) = P 1 (2)×P 14 + P 2 (2)×P 24 + P 3 (2)×P 34 + P 4 (2)×P 44 = 0,680.
Dakle, vjerovatnoće stanja računara nakon tri provjere su sljedeće: P 1 (3) = 0,027; P 2 (3) = 0,076; P 3 (3) = 0,217; P 4 (3) = 0,680.
Zadatak 1. Određena meta se ispaljuje sa četiri hica istovremeno t 1, t 2, t 3, t 4.
Moguća stanja sistema: S 1- meta je neozlijeđena; S 2- meta je blago oštećena; S 3- cilj je pretrpio značajnu štetu; S 4- meta je potpuno pogođena. U početnom trenutku vremena meta je u stanju S 1. Odredite vjerovatnoće ciljanih stanja nakon četiri udarca ako matrica vjerovatnoća prijelaza ima oblik.
Markovski lanci
Uvod
§ 1. Markovljev lanac
§ 2. Homogeni Markovljev lanac. Vjerovatnoće tranzicije. Tranziciona matrica
§3. Markova jednakost
§4. Stacionarna distribucija. Teorema granične vjerovatnoće
§5. Dokaz teoreme o graničnim vjerovatnoćama u Markovljevom lancu
§6. Primjena Markovljevih lanaca
Zaključak
Spisak korišćene literature
Uvod
Naša tema rad na kursu Markovski lanci. Markovi lanci su dobili ime po istaknutom ruskom matematičaru Andreju Andrejeviču Markovu, koji je intenzivno radio na slučajnim procesima i dao veliki doprinos razvoju ove oblasti. U posljednje vrijeme možete čuti o upotrebi Markovljevih lanaca u raznim oblastima: modernim web tehnologijama, pri analizi književnih tekstova, pa čak i kada se razvijaju taktike za fudbalski tim. Oni koji ne znaju šta su Markovljevi lanci mogu imati osjećaj da je to nešto vrlo složeno i gotovo neshvatljivo.
Ne, upravo je suprotno. Markovljev lanac je jedan od najjednostavnijih slučajeva niza slučajnih događaja. Ali, uprkos svojoj jednostavnosti, često može biti od koristi čak i kada se opisuju prilično složeni fenomeni. Markovljev lanac je niz slučajnih događaja u kojem vjerovatnoća svakog događaja zavisi samo od prethodnog, ali ne zavisi od ranijih događaja.
Prije nego što uđemo dublje, moramo razmotriti nekoliko pomoćnih pitanja koja su općenito poznata, ali su apsolutno neophodna za dalje izlaganje.
Cilj mog kursa je da detaljnije proučim primjenu Markovljevih lanaca, iskaz problema i Markovljeve probleme.
§1. Markov lanac
Zamislimo da se izvodi niz testova.
Definicija. Markovljev lanac je niz pokušaja u svakom od kojih se pojavljuje jedan i samo jedan od nespojivih događaja iz kompletne grupe, a uslovna vjerovatnoća da se događaj dogodi u tom ogledu je 
, pod uslovom da se događaj dogodio u prvom suđenju 
, ne zavisi od rezultata prethodnih testova.
Na primjer, ako slijed pokušaja formira Markovljev lanac i kompletna grupa se sastoji od četiri nekompatibilna događaja, a poznato je da se događaj dogodio u šestom pokušaju, tada uslovna vjerovatnoća da se događaj dogodi u sedmom pokušaju ne zavisi o tome koji su se događaji pojavili u prvom, drugom, ..., petom testu.
Imajte na umu da su nezavisni testovi poseban slučaj Markovljevog lanca. Doista, ako su testovi nezavisni, onda pojava određenog događaja u bilo kojem testu ne ovisi o rezultatima prethodno obavljenih testova. Iz toga slijedi da je koncept Markovljevog lanca generalizacija koncepta nezavisnih ispitivanja.
Često se pri izlaganju teorije Markovljevih lanaca pridržavaju drugačije terminologije i govore o određenom fizičkom sistemu, koji se u svakom trenutku nalazi u jednom od stanja: , i mijenja svoje stanje samo u odvojenim trenucima vremena, tj. je, sistem se kreće iz jednog stanja u drugo (na primjer, iz do ). Za Markovljeve lance, vjerovatnoća odlaska u bilo koje stanje je trenutno zavisi samo od toga u kakvom je stanju sistem bio u ovom trenutku, i ne menja se jer njegova stanja u ranijim trenucima postaju poznata. Takođe, posebno, nakon testa sistem može ostati u istom stanju („prelaziti“ iz stanja u stanje).
Za ilustraciju, razmotrite primjer.
Primjer 1. Zamislimo da se čestica koja se nalazi na pravoj liniji kreće duž te prave linije pod utjecajem slučajnih šokova koji se javljaju u trenucima. Čestica se može locirati u tačkama sa celobrojnim koordinatama: 
; Reflektirajući zidovi se nalaze na tačkama. Svaki pritisak pomera česticu udesno sa verovatnoćom i ulevo sa verovatnoćom, osim ako je čestica blizu zida. Ako je čestica blizu zida, onda je svaki pritisak pomera za jednu jedinicu unutar procepa između zidova. Ovdje vidimo da je ovaj primjer hodanja čestice tipičan Markovljev lanac.
Dakle, događaji se nazivaju stanjima sistema, a testovi se nazivaju promjenama njegovih stanja.
Definirajmo sada Markovljev lanac koristeći novu terminologiju.
Markovljev lanac s diskretnim vremenom je kolo čija se stanja mijenjaju u određenim fiksnim vremenima.
Markovljev lanac sa kontinuiranim vremenom je lanac čija se stanja mijenjaju u bilo kojem mogućem slučajnom trenutku u vremenu.
§2. Homogeni Markovljev lanac. Vjerovatnoće tranzicije. Tranziciona matrica
Definicija. Markovljev lanac se naziva homogenim ako uslovna vjerovatnoća (prijelaz iz stanja u stanje) ne zavisi od broja pokušaja. Stoga, umjesto jednostavnog pisanja.
Primjer 1. Random walk. Neka postoji materijalna čestica na pravoj liniji u tački sa cjelobrojnom koordinatom. U određenim trenucima vremena čestica doživljava udare. Pod uticajem guranja, čestica se kreće sa verovatnoćom za jednu jedinicu udesno i sa verovatnoćom za jednu jedinicu ulevo. Jasno je da položaj (koordinate) čestice nakon udara ovisi o tome gdje se čestica nalazila nakon neposredno prethodnog udara, a ne ovisi o tome kako se kretala pod utjecajem drugih prethodnih šokova.
Dakle, slučajni hod je primjer homogenog Markovljevog lanca s diskretnim vremenom.
Vjerovatnoća prijelaza je uslovna vjerovatnoća da će iz stanja (u kojem se sistem našao kao rezultat nekog testa, bez obzira na broj) kao rezultat sljedećeg testa sistem prijeći u stanje.
Dakle, u oznaci prvi indeks označava broj prethodnog stanja, a drugi broj sljedećeg stanja. Na primjer, je vjerovatnoća prijelaza iz drugog stanja u treće.
Neka je broj stanja konačan i jednak .
Prijelazna matrica sistema je matrica koja sadrži sve vjerovatnoće prijelaza ovog sistema:
Pošto svaki red matrice sadrži vjerovatnoće događaja (prijelaza iz istog stanja u bilo koje moguće stanje) koji čine potpunu grupu, zbir vjerovatnoća ovih događaja jednak je jedan. Drugim riječima, zbroj vjerojatnosti prijelaza svakog reda prijelazne matrice jednak je jedan:
Navedimo primjer prijelazne matrice sistema koji može biti u tri stanja; prijelaz iz stanja u stanje odvija se prema shemi homogenog Markovljevog lanca; vjerovatnoće prijelaza su date matricom:
Ovde vidimo da ako je sistem bio u stanju, onda će nakon promene stanja u jednom koraku ostati u istom stanju sa verovatnoćom 0,5, ostaće u istom stanju sa verovatnoćom 0,5, preći će u stanje sa verovatnoćom 0,2, zatim nakon tranzicije može završiti u državama; ne može prelaziti iz stanja u stanje. Poslednji red matrice nam pokazuje da iz stanja idemo u bilo koje od mogućih stanja sa istom verovatnoćom od 0,1.
Na osnovu prelazne matrice sistema, možete izgraditi takozvani graf stanja sistema; naziva se i označeni graf stanja. Ovo je zgodno za vizualni prikaz kola. Pogledajmo redoslijed konstruiranja grafova koristeći primjer.
Primjer 2. Koristeći datu prijelaznu matricu, konstruirajte graf stanja.
Jer matrica četvrtog reda, onda, shodno tome, sistem ima 4 moguća stanja.
Grafikon ne pokazuje vjerovatnoće prelaska sistema iz jednog stanja u isto. Kada se razmatraju specifični sistemi, zgodno je prvo konstruisati graf stanja, a zatim odrediti verovatnoću prelaska sistema iz jednog stanja u isto (na osnovu zahteva da zbir elemenata redova matrice bude jednak jedan), a zatim konstruisati prelaznu matricu sistema.
§3. Markova jednakost
Definicija. Označimo vjerovatnoćom da će kao rezultat koraka (testova) sistem prijeći iz stanja u stanje. Na primjer, je vjerovatnoća prijelaza u 10 koraka iz drugog stanja u peto.
Naglašavamo da pri dobijamo vjerovatnoće tranzicije
Postavimo sebi zadatak: znajući vjerovatnoće prijelaza, pronaći vjerovatnoće sistema koji prelazi iz stanja u stanje u koracima.
U tu svrhu uvodimo u razmatranje srednje stanje (između i ). Drugim rečima, pretpostavićemo da će iz početnog stanja u koracima sistem preći u srednje stanje sa verovatnoćom , nakon čega će u preostalim koracima iz međustanja preći u konačno stanje sa verovatnoćom .
Koristeći formulu ukupne vjerovatnoće, dobijamo
. (1)
Ova formula se zove Markovljeva jednakost.
Objašnjenje. Hajde da uvedemo sljedeću notaciju:
– događaj koji nas zanima (u koracima će sistem prelaziti iz početnog stanja u konačno stanje), dakle, ; 
− hipoteze (u koracima sistem će se kretati iz početnog stanja u međustanje), dakle, − uslovna verovatnoća pojave, pod uslovom da se hipoteza dogodila (u koracima će sistem kretati iz međustanja u konačno stanje), dakle, 
Prema formuli ukupne vjerovatnoće,
()
Ili u notaciji koju smo usvojili
što se poklapa sa Markovom formulom (1).
Poznavajući sve vjerovatnoće prijelaza, odnosno poznavajući prijelaznu matricu iz stanja u stanje u jednom koraku, možete pronaći vjerovatnoće prijelaza iz stanja u stanje u dva koraka, a samim tim i samu matricu prijelaza; koristeći poznatu matricu, možete pronaći matricu prijelaza iz stanja u stanje u tri koraka, itd.
Zaista, stavljanjem u Markovljevu jednakost
,
lanac bodova slučajna vjerovatnoća
,
(2)
Dakle, koristeći formulu (2) možete pronaći sve vjerovatnoće, a samim tim i samu matricu. Budući da se direktna upotreba formule (2) pokaže zamornom, a matrični račun brže vodi do cilja, relacije koje proizlaze iz (2) zapisati ću u matričnom obliku:
Stavljajući u (1), dobijamo slično
Uglavnom
Teorema 1. Za bilo koji s, t
(3)
Dokaz. Izračunajmo vjerovatnoću 
koristeći formulu ukupne vjerovatnoće (), stavljajući
Od jednakosti
Dakle, iz jednakosti (4) i
dobijamo iskaz teoreme.
Definirajmo matricu.U matrici notacija (3) ima oblik
Od tada gdje je matrica vjerovatnoće tranzicije. Iz (5) slijedi
(6)
Rezultati dobiveni u teoriji matrica omogućavaju korištenje formule (6) za izračunavanje i proučavanje njihovog ponašanja kada
Primjer 1. Navedena matrica prijelaza 
Pronađite prijelaznu matricu 
Rješenje. Koristimo formulu
Množenjem matrica konačno dobijamo:
.
§4. Stacionarna distribucija. Teorema granične vjerovatnoće
Distribucija vjerovatnoće u proizvoljnom trenutku može se naći korištenjem formule ukupne vjerovatnoće
(7)
Može se ispostaviti da to ne zavisi od vremena. Hajde da pozovemo stacionarna distribucija vektor 
, zadovoljavajući uslove
gdje su vjerovatnoće tranzicije.
Ako je u lancu Markova 
onda za bilo koje
Ovaj iskaz slijedi indukcijom iz (7) i (8).
Predstavimo formulaciju teoreme o graničnim vjerovatnoćama za jednu važnu klasu Markovljevih lanaca.
Teorema 1. Ako su za neki >0 svi elementi matrice pozitivni, onda za bilo koji , za
, (9)
Gdje 
stacionarna distribucija sa nekom konstantom koja zadovoljava nejednakost 0<
h
<1.
Budući da , onda prema uvjetima teoreme, iz bilo kojeg stanja možete doći u bilo koje stanje u vremenu s pozitivnom vjerovatnoćom. Uslovi teoreme isključuju lance koji su u nekom smislu periodični.
Ako su ispunjeni uslovi teoreme 1, onda verovatnoća da je sistem u određenom stanju u graničnom stanju ne zavisi od početne raspodele. Zaista, iz (9) i (7) slijedi da za bilo koju početnu distribuciju,
Razmotrimo nekoliko primjera Markovljevih lanaca za koje nisu ispunjeni uslovi teoreme 1. Nije teško provjeriti da su takvi primjeri primjeri. U primjeru, vjerovatnoće prijelaza imaju granice, ali ove granice zavise od početnog stanja. Konkretno, kada
U drugim primjerima, rasponi vjerovatnoće za očigledno ne postoje.
Nađimo stacionarnu raspodjelu u primjeru 1. Trebamo pronaći vektor 
zadovoljavajuće uslove (8):
,
;
Dakle, postoji stacionarna raspodjela, ali nisu svi koordinatni vektori pozitivni.
Za polinomsku šemu uvedene su slučajne varijable jednake broju ishoda datog tipa. Uvedimo slične količine za Markovljeve lance. Neka je broj puta kada sistem ulazi u stanje u vremenu. Zatim frekvencija sistema koji pogađa stanje . Koristeći formule (9), možemo dokazati da kada pristupi . Da biste to učinili, trebate dobiti asimptotske formule za i i koristiti Čebiševljevu nejednakost. Ovdje je izvođenje formule za . Hajde da ga predstavimo u obliku
(10)
gdje, ako i inače. Jer
,
zatim, koristeći svojstvo matematičkog očekivanja i formulu (9), dobijamo
.
Na osnovu teoreme 1, trostruki član na desnoj strani ove jednakosti je parcijalni zbir konvergentnog niza. Stavljanje 
, dobijamo
Zbog
Iz formule (11), posebno, proizilazi da
at
Također možete dobiti formulu za koju se izračunava varijansa.
§5. Dokaz teoreme o graničnim vjerovatnoćama u Markovljevom lancu
Hajde da prvo dokažemo dve leme. Hajde da stavimo
Lema 1. Postoje ograničenja za bilo koje
Dokaz. Koristeći jednačinu (3) sa dobijamo
Dakle, sekvence su i monotone i ograničene. Ovo implicira tvrdnju leme 1.
Lema 2.
Ako su ispunjeni uslovi teoreme 2, tada postoje konstante, 
takav da
Za bilo koje
gdje , znači zbrajanje preko svih za koje je pozitivno, i zbrajanje preko ostatka . Odavde
. (12)
Pošto su pod uslovima teoreme 1 prelazne verovatnoće za sve , onda za bilo koje
I zbog konačnog broja država
Procijenimo sada razliku 
. Koristeći jednačinu (3) sa , , dobijamo
Odavde, koristeći (8)-(10), nalazimo
=
.
Kombinujući ovu relaciju sa nejednakošću (14), dobijamo tvrdnju leme.
Prijeđite na dokaz teoreme. Pošto su sekvence monotone, onda
0<
. (15)
Iz ovoga i leme 1 nalazimo
Stoga, kada dobijete i
Pozitivnost proizlazi iz nejednakosti (15). Prelaskom na granicu u i u jednačini (3), dobijamo da zadovoljava jednačinu (12). Teorema je dokazana.
§6. Primjena Markovljevih lanaca
Markovi lanci služe kao dobar uvod u teoriju slučajnih procesa, tj. teorija jednostavnih nizova porodice slučajnih varijabli, obično zavisnih od parametra, koji u većini aplikacija igra ulogu vremena. Prvenstveno je namijenjen da u potpunosti opiše kako dugoročno tako i lokalno ponašanje procesa. Evo nekih od pitanja koja se najviše proučavaju u tom pogledu.
Brownovo kretanje i njegove generalizacije - difuzijski procesi i procesi sa nezavisnim priraštajima . Teorija slučajnih procesa doprinijela je produbljivanju veze između teorije vjerovatnoće, teorije operatora i teorije diferencijalnih jednačina, što je, između ostalog, bilo važno za fiziku i druge primjene. Primjene uključuju procese od interesa za aktuarsku matematiku (osiguranje), teoriju čekanja, genetiku, kontrolu prometa, teoriju električnih kola i teoriju inventara.
Martingales . Ovi procesi čuvaju dovoljno svojstava Markovljevih lanaca da važne ergodičke teoreme ostaju važeće za njih. Martingali se razlikuju od Markovljevih lanaca po tome što kada je trenutno stanje poznato, samo matematičko očekivanje budućnosti, ali ne nužno i sama distribucija vjerovatnoće, ne zavisi od prošlosti. Osim što je važan istraživački alat, teorija martingala je obogatila teoriju slučajnih procesa koji nastaju u statistici, teoriju nuklearne fisije, genetiku i teoriju informacija novim graničnim teoremama.
Stacionarni procesi . Najstarija poznata ergodička teorema, kao što je gore navedeno, može se tumačiti kao rezultat koji opisuje ograničavajuće ponašanje stacionarnog slučajnog procesa. Takav proces ima svojstvo da svi probabilistički zakoni koje on zadovoljava ostaju invarijantni u odnosu na vremenske pomake. Ergodička teorema, koju su fizičari prvi formulisali kao hipotezu, može se predstaviti kao tvrdnja da se, pod određenim uslovima, prosek ansambla poklapa sa vremenskim prosekom. To znači da se iste informacije mogu dobiti iz dugotrajnog posmatranja sistema i iz istovremenog (i trenutnog) posmatranja više nezavisnih kopija istog sistema. Zakon velikih brojeva nije ništa drugo do poseban slučaj Birkhoffove ergodičke teoreme. Interpolacija i predviđanje ponašanja stacionarnih Gausovih procesa, shvaćenih u širem smislu, služe kao važna generalizacija klasične teorije najmanjih kvadrata. Teorija stacionarnih procesa je neophodan istraživački alat u mnogim oblastima, na primer, u teoriji komunikacija, koja se bavi proučavanjem i kreiranjem sistema koji prenose poruke u prisustvu šuma ili slučajnih smetnji.
Markovljevi procesi (procesi bez naknadnih efekata) igraju ogromnu ulogu u modeliranju sistema čekanja (QS), kao iu modeliranju i izboru strategije upravljanja socio-ekonomskim procesima koji se dešavaju u društvu.
Markov lanac se također može koristiti za generiranje tekstova. Nekoliko tekstova se dostavlja kao ulaz, zatim se gradi Markovljev lanac sa vjerovatnoćama da jedna riječ slijedi drugu, a rezultirajući tekst se kreira na osnovu ovog lanca. Ispada da je igračka veoma zabavna!
Zaključak
Dakle, u našem kursu smo govorili o kolu Markova lanca. Naučili smo u kojim oblastima i kako se koristi, nezavisnim testovima dokazana je teorema o graničnim vjerovatnoćama u Markovljevom lancu, dati primjeri za tipičan i homogeni Markovljev lanac, kao i za pronalaženje prelazne matrice.
Videli smo da je Markovljev dizajn lanca direktna generalizacija dizajna nezavisnog testa.
Spisak korišćene literature
1. Čistjakov V.P. Kurs teorije vjerovatnoće. 6. izdanje, rev. − Sankt Peterburg: Izdavačka kuća Lan, 2003. − 272 str. − (Udžbenik za univerzitete. Specijalna literatura).
2. Gnedenko B.V. Kurs teorije vjerovatnoće.
3. Gmurman V.E. Teorija vjerojatnosti i matematička statistika.
4. Ventzel E.S. Teorija vjerojatnosti i njene inženjerske primjene.
5. Kolmogorov A.N., Zhurbenko I.G., Prokhorov A.V. Uvod u teoriju vjerovatnoće. − Moskva-Iževsk: Institut za kompjuterska istraživanja, 2003, 188 str.
6. Katz M. Vjerovatnoća i srodna pitanja u fizici.
(Andrej Andrejevič Markov (1856-1922) - ruski matematičar, akademik)
Definicija. Proces koji se odvija u fizičkom sistemu naziva se Markovsky, ako u bilo kom trenutku u vremenu vjerovatnoća bilo kojeg stanja sistema u budućnosti zavisi samo od stanja sistema u trenutnom trenutku i ne zavisi od toga kako je sistem došao u ovo stanje.
Definicija. Markov lanac naziva nizom ispitivanja, u svakom od kojih samo jedan od K nekompatibilni događaji Ai iz cijele grupe. U ovom slučaju, uslovna vjerovatnoća Pij(S) šta je unutra S-th test događaj će doći Aj pod uslovom da u ( S – 1 ) – događaj se dogodio tokom testa Ai, ne zavisi od rezultata prethodnih testova.
Nezavisna suđenja su poseban slučaj Markovljevog lanca. Događaji se zovu Sistemska stanja, i testovi - Promjene stanja sistema.
Na osnovu prirode promjena stanja, Markovi lanci se mogu podijeliti u dvije grupe.
Definicija. Markovljev lanac s diskretnim vremenom To se zove strujni krug čija se stanja mijenjaju u određenim fiksnim trenucima vremena. Kontinuirani Markov lanac Zove se kolo čija se stanja mogu promijeniti u bilo kojem slučajnom trenutku u vremenu.
Definicija. Homogene Zove se Markovljev lanac ako je uslovna vjerovatnoća Pij tranzicija sistema iz države I U stanju J ne zavisi od broja testa. Vjerovatnoća Pij pozvao Vjerovatnoća tranzicije.
Pretpostavimo da je broj stanja konačan i jednak K.
Tada će matrica sastavljena od uvjetnih prijelaznih vjerovatnoća izgledati ovako:
Ova matrica se zove Sistemska tranzicijska matrica.
Budući da svaki red sadrži vjerovatnoće događaja koji čine kompletnu grupu, očigledno je da je zbroj elemenata svakog reda matrice jednak jedan.
Na osnovu prelazne matrice sistema može se konstruisati tzv Grafikon stanja sistema, takođe se zove Označeni grafikon stanja. Ovo je zgodno za vizualni prikaz kola. Pogledajmo redoslijed konstruiranja grafova koristeći primjer.
Primjer. Koristeći datu prijelaznu matricu, konstruirajte graf stanja.
Pošto je matrica četvrtog reda, onda, shodno tome, sistem ima 4 moguća stanja.
Grafikon ne pokazuje vjerovatnoće prelaska sistema iz jednog stanja u isto. Kada se razmatraju specifični sistemi, zgodno je prvo konstruisati graf stanja, a zatim odrediti verovatnoću prelaska sistema iz jednog stanja u isto (na osnovu zahteva da zbir elemenata redova matrice bude jednak jedan), a zatim konstruisati prelaznu matricu sistema.
Neka Pij(N) – vjerovatnoća da će kao rezultat N testove sistem će ići iz države I u državi J, R – neko međustanje između država I I J. Vjerojatnosti prijelaza iz jednog stanja u drugo Pij(1) = Pij.
Zatim vjerovatnoća Pij(N) može se pronaći pomoću formule tzv Markova jednakost:
Evo T– broj koraka (pokušaja) tokom kojih je sistem prešao iz stanja I U stanju R.
U principu, Markovljeva jednakost nije ništa drugo nego malo modificirana formula za ukupnu vjerovatnoću.
Poznavanje vjerojatnosti prijelaza (tj. poznavanje matrice prijelaza P1), možemo pronaći vjerovatnoće prijelaza iz stanja u stanje u dva koraka Pij(2) , odnosno matrica P2, znajući to - pronađite matricu P3, itd.
Direktna primjena gore dobivene formule nije baš zgodna, stoga možete koristiti tehnike matričnog računa (na kraju krajeva, ova formula u suštini nije ništa drugo do formula za množenje dvije matrice).
Tada u opštem obliku možemo napisati:
Općenito, ova se činjenica obično formulira u obliku teoreme, međutim, njen dokaz je prilično jednostavan, pa ga neću iznositi.
Primjer. Navedena matrica prijelaza P1. Pronađite matricu P3.
Definicija. Pozivaju se matrice čiji su zbroji elemenata svih redova jednaki jedan Stohastic. Ako za neke P svi elementi matrice Rp nisu jednake nuli, tada se takva prijelazna matrica naziva Regular.
Drugim riječima, regularne prijelazne matrice definiraju Markovljev lanac u kojem se može doći do svakog stanja P koraka iz bilo koje države. Takvi Markovljevi lanci se također nazivaju Regular.
Teorema. (teorema granične vjerovatnoće) Neka je dat regularni Markovljev lanac sa n stanja i P je njegova matrica vjerovatnoće prijelaza. Tada postoji granica i matrica P(¥ ) ima oblik:
Markov proces- slučajni proces koji se odvija u sistemu, koji ima svojstvo: za svaki trenutak vremena t 0, vjerovatnoća bilo kojeg stanja sistema u budućnosti (pri t>t 0) zavisi samo od njegovog stanja u sadašnjosti (u t = t 0) i ne zavisi od toga kada i kako je sistem došao u ovo stanje (tj. kako se proces razvijao u prošlosti).
U praksi se često susrećemo sa slučajnim procesima koji se, do različitog stepena aproksimacije, mogu smatrati markovskim.
Bilo koji Markovljev proces je opisan korištenjem vjerovatnoća stanja i vjerovatnoća tranzicije.
Vjerovatnoće stanja P k (t) Markovljevog procesa su vjerovatnoće da je slučajni proces (sistem) u trenutku t u stanju S k:
Prijelazne vjerovatnoće Markovljevog procesa su vjerovatnoće prelaska procesa (sistema) iz jednog stanja u drugo:
Markovljev proces se zove homogena, ako vjerovatnoće prijelaza po jedinici vremena ne zavise od toga gdje se na vremenskoj osi dogodi prijelaz.
Najjednostavniji proces je Markov lanac– Markovljev slučajni proces sa diskretnim vremenom i diskretnim konačnim skupom stanja.
Kada se analiziraju, Markovi lanci su graf stanja, na kojem su u jednom koraku označena sva stanja lanca (sistema) i nenulte vjerovatnoće.
Markovljev lanac se može zamisliti kao da se tačka koja predstavlja sistem kreće nasumično kroz graf stanja, povlačeći se iz stanja u stanje u jednom koraku ili ostajući u istom stanju nekoliko koraka.
Vjerovatnoće prijelaza Markovljevog lanca u jednom koraku zapisuju se u obliku matrice P=||P ij ||, koja se naziva matrica vjerovatnoće prijelaza ili jednostavno matrica prijelaza.
Primjer: skup stanja studenata specijalnosti je sljedeći:
S 1 – brucoš;
S 2 – druga godina…;
S 5 – student 5. godine;
S 6 – specijalista koji je završio fakultet;
S 7 – osoba koja je studirala na fakultetu, ali nije diplomirala.
Iz stanja S 1 u roku od godinu dana mogući su prijelazi u stanje S 2 sa vjerovatnoćom r 1 ; S 1 sa vjerovatnoćom q 1 i S 7 sa vjerovatnoćom p 1, i:
r 1 +q 1 +p 1 =1.
Napravimo graf stanja za ovaj Markovljev lanac i označimo ga vjerovatnoćama tranzicije (ne-nula).
Kreirajmo matricu vjerovatnoća tranzicije:
Prijelazne matrice imaju sljedeća svojstva:
Svi njihovi elementi su nenegativni;
Zbir njihovih redova jednak je jedan.
Matrice sa ovim svojstvom nazivaju se stohastičkim.
Prijelazne matrice vam omogućavaju da izračunate vjerovatnoću bilo koje trajektorije Markovljevog lanca koristeći teoremu množenja vjerovatnoće.
Za homogene Markovljeve lance, prelazne matrice ne zavise od vremena.
Prilikom proučavanja Markovljevih lanaca, oni od najvećeg interesa su:
Vjerojatnosti prijelaza u m koraka;
Distribucija po stanjima u koraku m→∞;
Prosječno vrijeme provedeno u određenom stanju;
Prosječno vrijeme za povratak u ovo stanje.
Razmotrimo homogeni Markovljev lanac sa n stanja. Da bi se dobila verovatnoća prelaska iz stanja S i u stanje S j u m koraka, u skladu sa formulom ukupne verovatnoće, treba zbrojiti proizvode verovatnoće prelaska iz stanja Si u srednje stanje Sk u l koraka sa verovatnoćom tranzicije iz Sk u Sj u preostalih m-l koraka, tj.
Ova relacija je za sve i=1, …, n; j=1, …,n se može predstaviti kao proizvod matrica:
P(m)=P(l)*P(m-l).
Tako imamo:
P(2)=P(1)*P(1)=P 2
P(3)=P(2)*P(1)=P(1)*P(2)=P 3, itd.
P(m)=P(m-1)*P(1)=P(1)*P(M-1)=P m ,
što omogućava da se pronađu vjerovatnoće prijelaza između stanja u bilo kojem broju koraka, znajući prijelaznu matricu u jednom koraku, naime P ij (m) - element matrice P(m) je vjerovatnoća prelaska iz stanja S i navesti S j u m koraka.
Primjer: Vrijeme u određenoj regiji naizmjenično je kišno i suvo tokom dugih vremenskih perioda. Ako pada kiša, onda će sa vjerovatnoćom 0,7 padati kiša sljedećeg dana; Ako je određenog dana vrijeme suho, onda će se s vjerovatnoćom od 0,6 zadržati i sljedećeg dana. Poznato je da je u srijedu bilo kišovito vrijeme. Kolika je vjerovatnoća da će sljedećeg petka padati kiša?
Zapišimo sva stanja Markovljevog lanca u ovom zadatku: D – kišno vrijeme, C – suho vrijeme.
Napravimo graf stanja:
Odgovor: p 11 = p (D peta | D avg) = 0,61.
Granice vjerovatnoće r 1 (m), r 2 (m),..., r n (m) za m→∞, ako postoje, nazivaju se granične vjerovatnoće stanja.
Može se dokazati sljedeća teorema: ako u Markovom lancu možete ići iz + svakog stanja (u datom broju koraka) jedno do drugog, tada granične vjerovatnoće stanja postoje i ne zavise od početnog stanja sistema .
Dakle, kao m→∞, u sistemu se uspostavlja određeni granični stacionarni režim u kojem se svako od stanja javlja sa određenom konstantnom vjerovatnoćom.
Vektor p, sastavljen od marginalnih vjerovatnoća, mora zadovoljiti relaciju: p=p*P.
Prosječno vrijeme provedeno u državi S i za vrijeme T je jednako p i *T, gdje je p i - granična vjerovatnoća stanja S i . Prosječno vrijeme za povratak u stanje S i je jednako .
Primjer.
Za mnoge ekonomske probleme potrebno je poznavati smjenu godina sa određenim vrijednostima godišnjih riječnih tokova. Naravno, ova alternacija se ne može apsolutno precizno odrediti. Da bismo odredili vjerovatnoće alternacije (tranzicije), dijelimo tokove uvođenjem četiri gradacije (stanja sistema): prvo (najniži protok), drugo, treće, četvrto (najveći protok). Definitivno ćemo pretpostaviti da nakon prve gradacije nikada ne slijedi četvrta, a četvrta prva zbog nakupljanja vlage (u zemlji, rezervoaru i sl.). Zapažanja su pokazala da su u određenom regionu moguće i druge tranzicije, a:
a) od prve gradacije možete prelaziti na svaku od srednjih dva puta češće nego ponovo na prvu, tj.
p 11 =0,2; p 12 =0,4; p 13 =0,4; p 14 =0;
b) iz četvrte gradacije prelazi na drugu i treću gradaciju se dešavaju četiri i pet puta češće od povratka kao u drugoj, tj.
teško, tj.
u četvrtom, tj.
p 41 =0; p 42 =0,4; p 43 =0,5; p 44 =0,1;
c) sa druge na druge gradacije mogu biti samo rjeđe: u prvoj - dva puta manje, u trećoj za 25%, u četvrtoj - četiri puta rjeđe od prelaska u drugu, tj.
p 21 =0,2;p 22 =0,4; p 23 =0,3; p 24 =0,1;
d) iz treće gradacije prelazak na drugu gradaciju je isto tako verovatan kao povratak u treću, a prelasci na prvu i četvrtu gradaciju četiri puta manje, tj.
p 31 =0,1; p 32 =0,4; p 33 =0,4; p 34 =0,1;
Napravimo graf:
Kreirajmo matricu vjerovatnoća tranzicije:
Nađimo prosječno vrijeme između sušnih i punovodnih godina. Da biste to učinili, morate pronaći distribuciju ograničenja. Postoji jer uslov teoreme je zadovoljen (matrica P2 ne sadrži nula elemenata, tj. u dva koraka možete ići iz bilo kojeg stanja sistema u bilo koje drugo).
Gdje je p 4 =0,08; p 3 =; p 2 =; p 1 =0,15
Učestalost povratka u stanje S i je jednaka .
Shodno tome, učestalost sušnih godina je u prosjeku 6,85, tj. 6-7 godina, a kišnih godina 12.
Učitavanje...