Lanț Markov omogen. Lanțuri Markov obișnuite. Structura datelor dictogramei

Un lanț Markov este un proces Markov în timp discret definit într-un spațiu măsurabil.

Introducere

Procesele aleatoare Markov poartă numele remarcabilului matematician rus A.A.Markov (1856-1922), care a început pentru prima dată să studieze conexiunea probabilistică a variabilelor aleatoare și a creat o teorie care poate fi numită „dinamica probabilității”.

În viitor, bazele acestei teorii au devenit baza inițială pentru teoria generală a proceselor aleatorii, precum și pentru științe aplicate atât de importante precum teoria proceselor de difuzie, teoria fiabilității, teoria cozilor de așteptare etc. În prezent, teoria proceselor Markov și aplicațiile sale sunt utilizate pe scară largă în diverse domenii.

Datorită simplității și clarității comparative a aparatului matematic, a fiabilității ridicate și a acurateții soluțiilor obținute, procesele Markov au primit o atenție deosebită din partea specialiștilor implicați în cercetarea operațională și teoria luării optime a deciziilor.

Exemplu simplu: aruncarea unei monede

Înainte de a descrie schema generală, să ne uităm la un exemplu simplu. Să presupunem că vorbim despre aruncarea succesivă a unei monede când se joacă „aruncare”; moneda este aruncată la momente condiționale t = 0, 1, ... și la fiecare pas jucătorul poate câștiga ±1 cu aceeași probabilitate 1/2, deci la momentul t câștigul total este o variabilă aleatorie ξ(t) cu valori posibile j = 0, ±1, ...

Cu condiția ca ξ(t) = k, la pasul următor câștigul va fi deja egal cu ξ(t+1) = k ± 1, luând valorile indicate j = k ± 1 cu aceeași probabilitate 1/2.

În mod convențional, putem spune că aici, cu probabilitatea corespunzătoare, are loc o tranziție de la starea ξ(t) = k la starea ξ(t + 1) = k ± 1.

Formule și definiții

Generalizând acest exemplu, ne putem imagina un „sistem” cu un număr numărabil de stări posibile de „fază”, care trece aleatoriu de la o stare la alta într-un timp discret t = 0, 1, ....

Fie ξ(t) poziția sa la momentul t ca rezultat al unui lanț de tranziții aleatorii

ξ(0) - ξ(1) - ... - ξ(t) - ... ... (1)

Să notăm formal toate stările posibile prin numere întregi i = 0, ±1, ... Să presupunem că, cu o stare cunoscută ξ(t) = k, la pasul următor sistemul trece în starea ξ(t+1) = j cu probabilitate condiționată

p kj = P(ξ(t+1) = j|ξ(t) = k) ... (2)

indiferent de comportamentul său în trecut, mai precis, indiferent de lanțul de tranziții (1) până la momentul t:

P(ξ(t+1) = j|ξ(0) = i, ..., ξ(t) = k) = P(ξ(t+1) = j|ξ(t) = k) pentru toate t, k, j ... (3) - proprietatea Markov.

O astfel de schemă probabilistică se numește lanț Markov omogen cu un număr numărabil de stări- omogenitatea sa constă în faptul că definit la (2) probabilități de tranziție p kj, ∑ j p kj = 1, k = 0, ±1, ..., nu depind de timp, adică P(ξ(t+1) = j|ξ(t) = k) = P ij - matricea probabilității de tranzițieîntr-un singur pas nu depinde de n.

Este clar că P ij este o matrice pătrată cu intrări nenegative și sume unitare peste rânduri.

O astfel de matrice (finită sau infinită) se numește matrice stocastică. Orice matrice stocastică poate servi ca o matrice a probabilităților de tranziție.

În practică: livrarea echipamentelor pe raioane

Să presupunem că o anumită companie livrează echipamente în Moscova: în districtul de nord (să notăm A), sud (B) și central (C). Firma are un grup de curieri care deservesc aceste zone. Este clar ca pentru urmatoarea livrare, curierul merge in zona care in prezent este mai aproape de el. S-au determinat statistic următoarele:

1) după livrarea către A, următoarea livrare în 30 de cazuri se efectuează în A, în 30 de cazuri - în B și în 40 de cazuri - în C;

2) după livrare la B, următoarea livrare este în 40 de cazuri la A, în 40 de cazuri la B și în 20 de cazuri la C;

3) după livrarea la C, următoarea livrare este în 50 de cazuri la A, în 30 de cazuri la B și în 20 de cazuri la C.

Astfel, aria următoarei livrări este determinată doar de livrarea anterioară.

Matricea probabilității de tranziție va arăta astfel:

De exemplu, p 12 \u003d 0,4 este probabilitatea ca, după livrarea în zona B, următoarea livrare să se facă în zona A.

Să presupunem că fiecare livrare, urmată de o mutare în districtul următor, durează 15 minute. Apoi, conform statisticilor, după 15 minute, 30% dintre curierii care au fost în A vor fi în A, 30% vor fi în B și 40% în C.

Întrucât în ​​momentul următor fiecare dintre curieri va fi neapărat într-unul dintre districte, suma peste coloane este 1. Și, deoarece avem de-a face cu probabilități, fiecare element al matricei este 0<р ij <1.

Cea mai importantă circumstanță care ne permite să interpretăm acest model ca un lanț Markov este că locația curierului la momentul t + 1 depinde numai din locația la ora t.

Acum să punem o întrebare simplă: dacă curierul pleacă de la C, care este probabilitatea ca, după ce a făcut două livrări, să fie în B, adică. Cum poți obține B în 2 pași? Deci, există mai multe căi de la C la B în 2 pași:

1) mai întâi de la C la C și apoi de la C la B;

2) C-->B și B-->B;

3) C-->A și A-->B.

Ținând cont de regula înmulțirii evenimentelor independente, obținem că probabilitatea dorită este egală cu:

P = P(CA)*P(AB) + P(CB)*P(BB) + P(CC)*P(CB)

Înlocuirea valorilor numerice:

P = 0,5*0,3 + 0,3*0,4 + 0,2*0,3 = 0,33

Rezultatul obtinut spune ca daca curierul a inceput lucrul de la C, atunci in 33 de cazuri din 100 va fi in B dupa doua livrari.

Este clar că calculele sunt simple, dar dacă trebuie să determinați probabilitatea după 5 sau 15 livrări, acest lucru poate dura destul de mult.

Să arătăm o modalitate mai simplă de a calcula astfel de probabilități. Pentru a obține probabilitățile de tranziție din diferite stări în 2 pași, pătratăm matricea P:

Atunci elementul (2, 3) este probabilitatea de a trece de la C la B în 2 pași, care a fost obținută mai sus într-un mod diferit. Rețineți că și elementele din matricea P2 variază de la 0 la 1, iar suma dintre coloane este 1.

Acea. dacă trebuie să determinați probabilitățile de tranziție de la C la B în 3 pași:

1 cale. p(CA)*P(AB) + p(CB)*P(BB) + p(CC)*P(CB) = 0,37*0,3 + 0,33*0,4 + 0,3*0,3 = 0,333 unde p(CA) - probabilitatea trecerii de la C la A în 2 pași (adică acesta este un element (1, 3) al matricei P 2).

2 sensuri. Calculați matricea P 3:

Matricea probabilităților de tranziție la a 7-a putere va arăta astfel:

Este ușor de observat că elementele fiecărui rând tind spre anumite numere. Acest lucru sugerează că după un număr suficient de mare de livrări, nu mai contează în ce județ a început să lucreze curierul. Acea. la sfârșitul săptămânii aproximativ 38,9% vor fi în A, 33,3% vor fi în B și 27,8% vor fi în C.

O astfel de convergență este garantată dacă toate elementele matricei probabilităților de tranziție aparțin intervalului (0, 1).

procesul Markov- un proces aleatoriu care are loc în sistem, care are următoarea proprietate: pentru fiecare moment de timp t 0, probabilitatea oricărei stări a sistemului în viitor (pentru t>t 0) depinde numai de starea sa în prezent ( pentru t= t 0) și nu depinde de când și cum a ajuns sistemul în această stare (adică cum s-a dezvoltat procesul în trecut).

În practică, există adesea procese aleatorii care pot fi considerate procese Markov cu diferite grade de aproximare.

Orice proces Markov este descris folosind probabilitățile de stare și probabilitățile de tranziție.

Probabilitățile stărilor P k (t) ale unui proces Markov sunt probabilitățile ca procesul (sistemul) aleatoriu la momentul t să fie în starea S k:

Probabilitățile de tranziție ale unui proces Markov sunt probabilitățile trecerii procesului (sistemului) de la o stare la alta:

Procesul Markov este numit omogen dacă probabilitățile de tranziție pe unitatea de timp nu depind de locul în care are loc tranziția pe axa timpului.

Cel mai simplu proces este lanțul Markov este un proces aleator Markov cu timp discret și un set finit discret de stări.

În analiza lanțurilor Markov sunt grafic de stare, pe care toate stările lanțului (sistemului) și probabilitățile diferite de zero sunt marcate într-un singur pas.

Un lanț Markov poate fi gândit ca și cum un punct care reprezintă un sistem se mișcă aleatoriu printr-un grafic de stări, trăgând de la o stare la alta într-un singur pas sau rămânând mai mulți pași în aceeași stare.

Probabilitățile de tranziție ale lanțului Markov într-un singur pas sunt scrise ca o matrice P=||P ij ||, care se numește matricea probabilității de tranziție sau pur și simplu matricea de tranziție.

Exemplu: setul de stări ale studenților specialității este următorul:

S 1 - boboc;

S 2 - student al doilea ...;

S 5 - student anul 5;

S 6 - un specialist care a absolvit o universitate;

S 7 - o persoană care a studiat la o universitate, dar nu a absolvit-o.

Din starea S 1 într-un an, sunt posibile treceri la starea S 2 cu probabilitatea r 1 ; S 1 cu probabilitatea q 1 și S 7 cu probabilitatea p 1, în plus:

r 1 + q 1 + p 1 =1.

Să construim un grafic al stărilor lanțului Markov dat și să-l etichetăm cu probabilități de tranziție (altele decât zero).

Să facem o matrice a probabilităților de tranziție:

Matricele de tranziție au proprietatea:

Toate elementele lor sunt nenegative;

Sumele lor de rând sunt egale cu unu.

Matricele cu această proprietate se numesc stocastice.

Matricele de tranziție vă permit să calculați probabilitatea oricărei traiectorii a lanțului Markov folosind teorema înmulțirii probabilității.

Pentru lanțurile Markov omogene, matricele de tranziție nu depind de timp.

Când studiezi lanțurile Markov, cele mai interesante sunt:

Probabilități de tranziție în m trepte;

Distribuția pe stări la pasul m→∞;

Timpul mediu petrecut într-o anumită stare;

Timpul mediu pentru a reveni la această stare.

Se consideră un lanț Markov omogen cu n stări. Pentru a obține probabilitatea de trecere de la starea S i la starea S j în m pași, în conformitate cu formula probabilității totale, se însumează produsele probabilității de tranziție de la starea Si la starea intermediară Sk în l pași cu probabilitatea de trecere de la Sk la Sj în pașii m-l rămași, adică .

Acest raport este pentru toți i=1, …, n; j=1, …,n poate fi reprezentat ca produs de matrici:

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

Astfel, avem:

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

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

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

ceea ce face posibilă găsirea probabilităților de tranziție între stări în orice număr de trepte, cunoscând matricea de tranziție într-un singur pas și anume P ij (m) - un element al matricei P (m) există probabilitatea de a trece din starea S i pentru a afirma S j în m pași.

Exemplu: Vremea într-o regiune se schimbă de la ploioasă la uscată pentru perioade lungi de timp. Dacă plouă, atunci cu o probabilitate de 0,7 va ploua a doua zi; dacă într-o zi vremea este uscată, atunci cu o probabilitate de 0,6 va continua a doua zi. Se știe că miercuri vremea a fost ploioasă. Care este probabilitatea ca vinerea viitoare să fie ploioasă?

Să notăm toate stările lanțului Markov în această problemă: D - vreme ploioasă, C - vreme uscată.

Să construim un grafic de stare:

Răspuns: p 11 \u003d p (D toc | D miercuri) \u003d 0,61.

Limitele de probabilitate р 1 (m), р 2 (m),…, р n (m) la m→∞, dacă există, se numesc limitarea probabilităţilor stărilor.

Este posibil să se demonstreze următoarea teoremă: dacă într-un lanț Markov este posibil să se treacă de la fiecare stare (pentru unul sau altul număr de pași) una la alta, atunci probabilitățile limită ale stărilor există și nu depind de starea inițială. starea sistemului.

Astfel, când m→∞, în sistem se stabilește un anumit regim staționar limitativ, în care fiecare dintre stări se realizează cu o anumită probabilitate constantă.

Vectorul p, compus din probabilităţi marginale, trebuie să satisfacă relaţia: p=p*P.

Timp mediu în stat S i în timpul T este egal cu p i *T, unde p i - probabilitatea limitatoare a starii S i . Timp mediu de revenire la stat S i este egal cu .

Exemplu.

Pentru multe probleme economice, este necesar să se cunoască alternanța anilor cu anumite valori ale debitelor anuale ale râului. Desigur, această alternanță nu poate fi determinată în mod absolut precis. Pentru a determina probabilitățile de alternanță (tranziție), împărțim fluxurile introducând patru gradații (stări ale sistemului): prima (debitul cel mai scăzut), a doua, a treia, a patra (debitul cel mai mare). Pentru certitudine, vom presupune că prima gradație nu este niciodată urmată de a patra, iar a patra - de prima datorită acumulării de umiditate (în pământ, rezervor etc.). Observațiile au arătat că în unele regiuni sunt posibile alte tranziții și:

a) se poate trece de la prima gradație la fiecare dintre cele din mijloc de două ori mai des decât din nou la prima, i.e.

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

b) de la a patra gradație, trecerile la a doua și a treia gradație sunt de patru și cinci ori mai frecvente decât revenirea ca e la a doua, i.e.

greu, adica

la a patra, adică.

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

c) de la a doua la alte gradații nu pot fi decât mai puțin frecvente: în prima - de două ori, în a treia cu 25%, în a patra - de patru ori mai puțin decât trecerea la a doua, i.e.

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

d) de la a treia gradație, trecerea la a doua gradație este la fel de probabilă ca și revenirea la a treia gradație, iar trecerile la prima și a patra gradație sunt de patru ori mai puțin frecvente, i.e.

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

Să construim un grafic:

Să facem o matrice a probabilităților de tranziție:

Găsiți timpul mediu dintre secete și anii cu apă mare. Pentru a face acest lucru, trebuie să găsiți distribuția limită. Există pentru că condiția teoremei este îndeplinită (matricea P 2 nu conține elemente zero, adică, în doi pași, puteți trece de la orice stare a sistemului la oricare alta).

Unde p 4 \u003d 0,08; p3=; p2=; p1=0,15

Frecvența revenirii la starea S i este egală cu .

În consecință, frecvența anilor secetoși este în medie de 6,85; 6-7 ani, iar ploios 12 ani.

Lanțuri Markov obișnuite. Când descriem comportamentul sistemelor prin procesele Markov, este interesant de știut dacă poate fi atinsă vreo stare în timpul funcționării sistemului. Dacă luăm în considerare matricea probabilităților de tranziție, atunci ea arată probabilitățile de tranziție de la o stare la alta. Prin urmare, dacă un anumit grad al matricei probabilităților de tranziție are zero elemente, atunci trecerea la aceste stări la pasul corespunzător devine imposibilă.

Lanțul Markov se numește regulat dacă toate stările lanţului pot fi atinse din oricare alta . Dacă lanțul este regulat, atunci în orice moment putem fi în orice stare, indiferent de starea inițială. Se numește un lanț Markov omogen regulat, dacă orice putere a matricei sale de probabilitate de tranziție P nu conține elemente zero. După cum se știe, se numește o matrice care îndeplinește această condiție pozitiv .

În procesul de funcționare, sistemul de servicii ia pasul i una sau alta stare cu o probabilitate necondiționată

În unele cazuri, aceste probabilități nu se schimbă pentru fiecare stare de la pas la pas, adică.

Un lanț Markov omogen pentru care probabilitățile de stare sunt aceleași, i.e. nu depinde de P, numit staționar.În caz contrar, circuitul este numit nestaționară. Probabilitatea stărilor se numește probabilitatea staționară a stărilor.

Rețineți că lanțul invers...,5 ,S„,S n l ,... lanț staționar Markov...,5 j ,S n ,S x,... este, de asemenea, un lanț staționar Markov. Lanț staționar Markov reversibil dacă și numai dacă există o mulțime de numere pozitive pijamale), a căror sumă este egală cu 1, îndeplinind condițiile de echilibru

pentru toate statele.

Pentru un circuit staționar omogen, formula este valabilă

ceea ce arată că la fiecare pas probabilitățile stărilor lanțului staționar Markov nu se modifică și multiplicarea cu matricea probabilităților de tranziție nu are efect. După cum puteți vedea, vectorul din (12.32) este proprii (nemişcat) vector matricea P 5 aparţinând numărului caracteristic A,=1. Matricea P 5 va fi pozitivă.

Adesea, la primii pași, sistemul se comportă ca non-staționar, iar după un anumit număr de pași capătă proprietățile staționarității. Se numește modul staționar al sistemului regim stabilit,și non-staționare modul de tranziție.

Pentru un lanț Markov cu un număr finit de stări, cu condiția n rk (n) > 0, g, k = 1, LA, pornind de la unii P există probabilităţi limitative (finale sau staţionare) ale stărilor

Prin urmare,

Condiție : , înseamnă că P este o matrice

probabilitățile de tranziție ale unui lanț regulat. În acest caz, matricele P" converg către o matrice P,:

unde cantitatile , sunt numite marginal, sau final

ny, probabilitățile de tranziție. De aici

În același timp

Combinând ultimele două ecuații, obținem (12.32).

Dacă alegem vectorul propriu P/ al matricei stocastice ca vector al probabilităților inițiale Pm(O) pentru un lanț Markov omogen, atunci lanțul Markov este staționar începând din momentul t0.

Rândurile П y formează același vector de probabilitate Р/, ale cărui componente sunt pozitive. Matricea P y este, de asemenea, stocastică:

Deoarece rândurile lui P y sunt aceleași, atunci când sunt înmulțite în stânga cu orice vector de probabilitate, conform (12.7), se obține un rând al matricei. Prin urmare, probabilitățile finale nu depind de starea inițială.

Se numesc matricea stocastică P și lanțul Markov omogen corespunzător corect, dacă matricea nu are numere caracteristice diferite de unu și egale în valoare absolută cu unu și regulat, dacă în plus una este o rădăcină simplă a ecuației caracteristice a matricei П.

Probabilitățile limită de tranziție există numai pentru lanțurile Markov omogene obișnuite.

Numărul caracteristic al unei matrice stocastice se află întotdeauna în cercul | A|

Dacă matricea P 5 există, atunci este de dorit să o calculăm fără a găsi gradul matricei P „și limita sa limită P” = P ° °.

P-*? oo

Pentru o matrice obișnuită, există o matrice P, care poate fi calculată prin formula:

unde C(A) \u003d (A1 - l) -1 cp (A) este matricea asociată redusă; cp(A) este polinomul minim al unei matrice regulate; cp „(X) este derivata polinomului.

Pentru o matrice regulată φ(A) = D(A) și C(X) = B( A). Prin urmare,

Unde - matrice atașată; OH) este polinomul caracteristic al matricei regulate.

Se consideră un lanț Markov obișnuit cu două stări cu matrice de probabilitate de tranziție (12.28). Numerele caracteristice calculate ale matricei (12.29) sunt diferite. Există un singur număr caracteristic, egal cu 1, și este o rădăcină simplă (nu multiplă) a ecuației caracteristice (12.29). Pentru a calcula probabilitățile finale, folosim matricea asociată găsită anterior (12.30). Pentru rădăcina caracteristică Xj = 1

Derivată cu privire la X ecuații (12.29) Unde

Conform (12.34),

Rândurile matricei rezultate sunt aceleași și trebuie să fie egale cu probabilitățile de stare finală. Când înmulțim această matrice din stânga cu orice vector de probabilitate (suma elementelor vectorului de probabilitate este egală cu 1), obținem un rând al matricei.

Pentru exemplul numeric considerat anterior de găsire a probabilității unei comenzi de către un client în fiecare lună

Matricea probabilităţilor finale se calculează conform (12.35) ca

Înlocuind valorile numerice a \u003d 0,3, a (3 \u003d 0,4, obținem Prin urmare, probabilitatea de ordin final Probabilitatea finală de neordine

Astfel, în condițiile notate mai sus, vectorul probabilităților de stare necondiționată în limită tinde spre vectorul probabilităților de stare staționară, indiferent de stările inițiale, iar matricea probabilităților de stare de tranziție, indiferent de vectorul de stare, tinde spre staționar. matricea probabilităţilor de tranziţie a stărilor. Mai mult, rândurile matricei probabilităților de tranziție ale stărilor sunt aceleași și egale cu vectorul stărilor staționare.

Lanțuri ergodice Markov. Se numesc lanțuri Markov pentru care există probabilități finale ergodic. Dacă un lanț Markov este ergodic, atunci din fiecare dintre stările sale este posibil să ajungeți la oricare alta. Un lanț obișnuit este întotdeauna ergodic, adică. nu conţine stări ireversibile şi are un set ergodic unic de stări. Un sistem descris de un lanț ergodic Markov se numește stabil statistic.

Dacă lanțul Markov este ergodic și există probabilități de stare staționară, atunci este necesar să le calculăm. Înainte de aceasta, au fost date metode pentru determinarea probabilităților staționare prin calcularea Eagle P" = P°° și P°°.

n->OS

Cu toate acestea, este posibil să se calculeze aceste probabilități fără a găsi matricea staționară a probabilităților de tranziție.

Probabilități finale r k, k = 1,LA, sunt o soluție a sistemului de ecuații

În notația matriceală (12.36) are forma

Deoarece ecuațiile (12.36) și (12.37) sunt probabiliste, ele trebuie să îndeplinească condiția de normalizare

sau în notație matriceală

Sistemul (12.38) este o matrice dependentă liniar П de mărime px p este singular și are rang (P - 1). Prin urmare, pentru a găsi LA probabilități finale necunoscute, este necesară înlocuirea uneia dintre ecuațiile sistemului (12.36) cu ecuația (12.38) .

Ecuația (12.37) poate fi reprezentată ca

Prin urmare, pentru a găsi o soluție, este necesar să se rezolve un sistem de ecuații liniare de tipul

La rezolvare, este necesar să se folosească condiția de normalizare (12.39), astfel încât una dintre coloanele matricei B trebuie înlocuită cu vectorul unitar 1, rezultând matricea C. Dacă ultima coloană a matricei este înlocuită, sistemul (12.40) este transformat în sistem

Unde

Luați în considerare un sistem cu două stări. Conform (12.36), Să înlocuim ultima ecuație a sistemului cu condiția de normalizare:

În notația matriceală (12.41), elementele ecuației vor fi egale:

Dacă există o matrice inversă C -1 , atunci soluția poate fi găsită sub forma

Pentru exemplul luat în considerare, există matricea inversă: De aceea

Deoarece p p\u003d 1-7t 12, p 21= 1-m 22 , soluția găsită se poate scrie și ca

care este în concordanță cu soluțiile anterioare.

Să arătăm că dacă alegem vectorul stărilor staționare ca vector al stărilor inițiale, atunci procesul va trece imediat la starea staționară la primul pas.

lanțuri Markov

Introducere

§ 1. Lant Markov

§ 2. Lanţ Markov omogen. Probabilități de tranziție. Matricea de tranziție

§3. Markov egalitate

§4. Distribuție staționară. Teorema probabilităților marginale

§5. Demonstrarea teoremei privind limitarea probabilităților într-un lanț Markov

§6. Aplicații ale lanțurilor Markov

Concluzie

Lista literaturii folosite

Introducere

Tema lucrării noastre de curs este lanțul Markov. Lanțurile Markov poartă numele remarcabilului matematician rus, Andrey Andreevich Markov, care a studiat mult procesele aleatoare și a adus o mare contribuție la dezvoltarea acestui domeniu. Recent, puteți auzi despre utilizarea lanțurilor Markov într-o varietate de domenii: tehnologii web moderne, în analiza textelor literare sau chiar în dezvoltarea tacticilor de joc de echipe de fotbal. Pentru cei care nu știu ce sunt lanțurile Markov, poate exista sentimentul că acesta este ceva foarte complex și aproape inaccesibil înțelegerii.

Nu, este exact invers. Un lanț Markov este unul dintre cele mai simple cazuri ale unei secvențe de evenimente aleatoare. Dar, în ciuda simplității sale, poate fi adesea util chiar și atunci când descrie fenomene destul de complexe. Un lanț Markov este o succesiune de evenimente aleatoare în care probabilitatea fiecărui eveniment depinde doar de cel anterior, dar nu depinde de evenimentele anterioare.

Înainte de a aprofunda, este necesar să luăm în considerare câteva aspecte auxiliare care sunt bine cunoscute, dar sunt absolut necesare pentru prezentarea ulterioară.

Scopul cursului meu este de a studia mai detaliat aplicațiile lanțurilor Markov, enunțul problemei și problemele Markov.

§1. lanțul Markov

Imaginează-ți că se efectuează o secvență de teste.

Definiție. Un lanț Markov este o succesiune de încercări, în fiecare dintre ele una și numai una

evenimentele incompatibile ale întregului grup și probabilitatea condiționată ca evenimentul să se producă în cel de-al treilea proces, cu condiția ca evenimentul să fi avut loc în cel de-al treilea studiu, nu depinde de rezultatele încercărilor anterioare.

De exemplu, dacă succesiunea de încercări formează un lanț Markov și grupul complet este format din patru evenimente disjunctive

, și se știe că evenimentul a apărut în al șaselea proces, atunci probabilitatea condiționată ca evenimentul să se producă în al șaptelea proces nu depinde de ce evenimente au apărut în primul, al doilea, ..., al cincilea proces.

Rețineți că încercările independente sunt un caz special al unui lanț Markov. Într-adevăr, dacă studiile sunt independente, atunci apariția unui eveniment specific în orice proces nu depinde de rezultatele încercărilor efectuate anterior. Rezultă că conceptul de lanț Markov este o generalizare a conceptului de încercări independente.

Adesea, atunci când prezintă teoria lanțurilor Markov, ei aderă la o terminologie diferită și vorbesc despre un sistem fizic.

, care în fiecare moment de timp se află într-una din stările: , și își schimbă starea numai în anumite momente de timp, adică sistemul trece de la o stare la alta (de exemplu, de la la ). Pentru lanțurile Markov, probabilitatea de a ajunge în orice stare în acest moment depinde doar de starea în care se afla sistemul în acest moment și nu se schimbă de la faptul că stările sale devin cunoscute în momente anterioare. De asemenea, în special, după test, sistemul poate rămâne în aceeași stare („tranziție” de la stare la stare).

Pentru a ilustra, luați în considerare un exemplu.

Exemplul 1 Imaginați-vă că o particulă situată pe o linie dreaptă se mișcă de-a lungul acestei linii drepte sub influența șocurilor aleatorii care apar în anumite momente

. Particula poate fi localizată în puncte cu coordonate întregi: ; în puncte și există pereți reflectorizatori. Fiecare împingere mută particula spre dreapta cu probabilitate și spre stânga cu probabilitate, cu excepția cazului în care particula se află lângă un perete. Dacă particula este situată lângă perete, atunci orice apăsare o mută cu o unitate în interiorul golului dintre pereți. Aici vedem că acest exemplu de mers de particule este un lanț Markov tipic.

Astfel, evenimentele sunt numite stări ale sistemului, iar testele sunt numite modificări ale stărilor acestuia.

Să definim acum un lanț Markov folosind noua terminologie.

Un lanț Markov în timp discret este un lanț ale cărui stări se schimbă în anumite momente fixe în timp.

Un lanț Markov în timp continuu este un lanț ale cărui stări se schimbă în orice moment posibil.

§2. Lanț Markov omogen. Probabilități de tranziție. Matricea de tranziție

Definiție. Se spune că un lanț Markov este omogen dacă probabilitatea condiționată

(tranziția de la stat la stat) nu depinde de numărul testului. Prin urmare, în loc să scrieți simplu.

Exemplul 1 Rătăcire întâmplătoare. Lasă pe o linie dreaptă

o particulă materială este situată într-un punct cu o coordonată întreagă. În anumite momente de timp, particula suferă șocuri. Sub acțiunea împingerii, particula este deplasată cu unul spre dreapta cu probabilitate și cu unul spre stânga. Este clar că poziția (coordonată) particulei după șoc depinde de locul în care a fost particula după șocul imediat precedent și nu depinde de modul în care s-a deplasat sub acțiunea celorlalte șocuri anterioare.

Astfel, o mers aleatorie este un exemplu de lanț Markov omogen cu timp discret.

pe cont propriu și parțial o considerăm datorită faptului că prezentarea sa nu necesită introducerea unui număr mare de termeni noi.

Luați în considerare problema unui măgar care stă exact între două grămezi de paie de secară și paie de grâu (Figura 10.5).

Măgarul stă între două șocuri: „Secara” și „Grâul” (Fig. 10.5). În fiecare minut fie se deplasează cu zece metri spre primul șoc (cu probabilitate), fie către al doilea șoc (cu probabilitate), fie rămâne acolo unde a fost (cu probabilitate); un astfel de comportament se numește unidimensional mers la întâmplare. Vom presupune că ambele șocuri sunt „absorbante” în sensul că dacă măgarul vine la unul dintre șocuri, atunci va rămâne acolo. Cunoscând distanța dintre cele două șocuri și poziția inițială a măgarului, ne putem pune mai multe întrebări, de exemplu: care șoc este cel mai probabil să se regăsească și care este timpul cel mai probabil de care va avea nevoie pentru a ajunge acolo?

Orez. 10.5.

Pentru a explora această problemă mai detaliat, să presupunem că distanța dintre șocuri este de cincizeci de metri și că măgarul nostru este la douăzeci de metri de șocul de „grâu”. Dacă locurile în care vă puteți opri, desemnați prin ( - șocurile în sine), atunci poziția sa inițială poate fi specificată de vectorul --a componentă a căruia este egală cu probabilitatea ca inițial să fie situată în . În plus, după un minut, probabilitățile de localizare a acestuia sunt descrise de vector, iar după două minute - de vector. Este clar că calculul direct al probabilității de a fi într-un loc dat după un interval de minute devine dificil. S-a dovedit că este cel mai convenabil să introduci pentru asta matricea de tranziție.

Fie probabilitatea ca el să treacă de la la într-un minut. De exemplu, și . Aceste probabilități sunt numite probabilități de tranziție, iar matricea este numită matricea de tranziție. Rețineți că fiecare element al matricei este nenegativ și că suma elementelor oricăruia dintre rânduri este egală cu unu. Din toate acestea rezultă că - vectorul rând inițial definit mai sus, locația măgarului după un minut este descrisă de vectorul rând , iar după minute - de vectorul . Cu alte cuvinte, componenta --a a vectorului determină probabilitatea ca măgarul să ajungă în .

Aceste concepte pot fi generalizate. Hai sa sunăm vector de probabilitate un vector rând ale cărui componente sunt nenegative și se adună până la unul. Apoi matricea de tranziție este definită ca o matrice pătrată în care fiecare rând este un vector de probabilitate. Acum puteți defini un lanț Markov (sau doar un lanț) ca o pereche unde există - matricea de tranziție, și există un vector rând. Dacă fiecare element din este considerat probabilitatea de a trece de la o poziție la alta și - ca vectorul inițial al probabilităților, atunci ajungem la conceptul clasic lanț Markov staționar discret, care poate fi găsită în cărțile despre teoria probabilității (vezi Feller V. Introducere în teoria probabilității și aplicațiile sale. T.1. M .: Mir. 1967) Poziția se numește de obicei starea lanțului. Să descriem diferite moduri de a le clasifica.

Ne vor interesa următoarele: este posibil să trecem de la o stare dată la alta și, dacă da, în ce timp minim. De exemplu, în problema măgarului, se poate ajunge de la până la în trei minute și, în general, nu se poate ajunge de la până la . Prin urmare, ne va interesa în principal nu probabilitățile în sine, ci dacă acestea sunt pozitive sau nu. Apoi există speranța că toate aceste date pot fi reprezentate sub forma unui digraf, ale cărui vârfuri corespund stărilor, iar arcele indică dacă este posibil să se mute de la o stare la alta într-un minut. Mai precis, dacă fiecare stare este reprezentată de vârful ei corespunzător).