Matrica e gjendjeve të tranzicionit të një zinxhiri Markov. Zinxhirët Markov

1. matricë P2 kalimi i qarkut nga gjendja i në një gjendje j në dy
hap;

2. shpërndarja e probabilitetit mbi gjendjet në këtë moment t=2;

3. probabiliteti që për momentin t=1 gjendja e qarkut do të jetë A2;

4. shpërndarje stacionare.

Zgjidhje. Për një zinxhir diskret Markov në rastin e homogjenitetit të tij, lidhja e mëposhtme është e vërtetë:

ku P1 është matrica e probabiliteteve të tranzicionit në një hap;
Рn - matrica e probabiliteteve të tranzicionit për n hapa;

1. Gjeni matricën e tranzicionit P2 në dy hapa

Lëreni shpërndarjen e probabilitetit mbi gjendjet S hapi th përcaktohet nga vektori
.
Njohja e matricës Pn tranzicioni në n hapa, ne mund të përcaktojmë shpërndarjen e probabilitetit mbi gjendjet në (S+n)-hapi i th . (5)

2. Le të gjejmë shpërndarjen e probabilitetit mbi gjendjet e sistemit për momentin t=2. Le të vendosim (5) S=0 dhe n=2. Pastaj .

Do ta marrim.

3. Le të gjejmë shpërndarjen e probabilitetit mbi gjendjet e sistemit për momentin t=1.

Le të vendosim (5) s=0 dhe n=1, atëherë .
Si mund ta shohim se probabiliteti që në këtë moment t=1 gjendja e qarkut do të jetë A2, të barabartë p2 (1)=0,69.
Shpërndarja e probabilitetit mbi gjendjet quhet stacionare nëse nuk ndryshon nga hapi në hap, d.m.th
Pastaj nga relacioni (5) në n=1 marrim

4. Le të gjejmë shpërndarjen stacionare. Meqenëse =2 kemi =(p1; p2). Le të shkruajmë sistemin ekuacionet lineare(6) në formë koordinative

Gjendja e fundit quhet normalizim. Në sistemin (6) një ekuacion është gjithmonë një kombinim linear i të tjerëve. Prandaj, mund të kalohet. Le të zgjidhim së bashku ekuacionin e parë të sistemit dhe ekuacionin e normalizimit. Kemi 0.6 p1=0,3p2, kjo eshte p2=2p1. Pastaj p1+2p1=1 ose , domethënë . Prandaj, .
Përgjigje:
1) matrica e tranzicionit në dy hapa për një zinxhir të caktuar Markov ka formën ;
2) shpërndarja e probabilitetit mbi gjendjet në këtë moment t=2 është e barabartë ;
3) probabiliteti që për momentin t=1 gjendja e qarkut do të jetë A2, është e barabartë p2(t)=0,69;
4) shpërndarja stacionare ka formën

Matrica e dhënë intensitetet e tranzicionit të një zinxhiri të vazhdueshëm Markov. Krijoni një grafik të gjendjes së emërtuar që korrespondon me matricën Λ; krijoni një sistem ekuacionet diferenciale Kolmogorov për probabilitete shtetërore; gjeni shpërndarjen e probabilitetit kufizues. Zgjidhje. Zinxhiri homogjen Markov me një numër të kufizuar gjendjesh A1, A2,…A karakterizohet nga matrica e intensiteteve të tranzicionit ,

Ku - intensiteti i kalimit të zinxhirit Markov nga shteti Аi në një gjendje Аj; рij (Δt)-probabiliteti i tranzicionit Ai→Aj për interval kohor Δ t.

Kalimet e sistemit nga gjendja në gjendje specifikohen lehtësisht duke përdorur një grafik të gjendjes së etiketuar, në të cilin shënohen harqet që korrespondojnë me intensitetet λ ij>0. Le të krijojmë një grafik të gjendjes së emërtuar për një matricë të caktuar të intensitetit të tranzicionit

Le të jetë një vektor i probabiliteteve Rj(t),
j=1, 2,…,, sistemi është në gjendje Aj në moment t.

Natyrisht 0≤ Rj(t)≤1 dhe . Pastaj, sipas rregullit për diferencimin e një funksioni vektorial të një argumenti skalar, marrim . Probabilitetet Rj(t) kënaq sistemin e ekuacioneve diferenciale Kolmogorov (SDEK), i cili në forma matrice duket si. (7)

Nëse në momentin fillestar sistemi ishte në gjendje Аj, atëherë SDUK duhet të zgjidhet në kushtet fillestare
Ri(0)=1, рj(0)=0, j≠i,j=1, 2,…,. (8)
Seti i SDUK (7) dhe kushtet fillestare(8) përshkruan në mënyrë unike një zinxhir homogjen Markov me kohë të vazhdueshme dhe një numër të kufizuar gjendjesh.
Le të hartojmë një SDEK për një zinxhir të caktuar Markov. Meqenëse =3, atëherë j=1, 2, 3.

Nga relacioni (7) marrim

.
Nga këtu do të kemi

Gjendja e fundit quhet normalizim.
Shpërndarja e probabilitetit mbi gjendjet quhet stacionare, nëse nuk ndryshon me kalimin e kohës, pra ku Rj=konst, j=1,2,…,. Nga këtu .

Pastaj nga SDUK (7) marrim një sistem për gjetjen e shpërndarjes stacionare
(9)
Për këtë problem, nga SDUK do të kemi

Nga kushti i normalizimit marrim 3р2+р2+р2=1 ose . Prandaj, shpërndarja kufitare ka formën .
Vini re se ky rezultat mund të merret direkt nga grafiku i gjendjes së etiketuar nëse përdorim rregullin: për një shpërndarje stacionare, shuma e produkteve λ jipi, j≠i, për shigjetat që vijnë nga i-gjendja është e barabartë me shumën e produkteve λ jipi, j≠i, për shigjetat e përfshira në i-shtet. Vërtet,

Është e qartë se sistemi që rezulton është i barabartë me atë të përpiluar duke përdorur SDUK. Prandaj ka të njëjtën zgjidhje.
Përgjigje: shpërndarja stacionare ka formën .

Përkufizimi. Një zinxhir Markov quhet homogjen nëse probabiliteti i kushtëzuar (kalimi nga gjendja në gjendje) nuk varet nga numri i provës. Kjo është arsyeja pse ata thjesht shkruajnë në vend të tyre.

Shembulli 1. Ecje e rastësishme. Le të jetë një grimcë materiale në një vijë të drejtë në një pikë me një koordinatë numër të plotë. Në momente të caktuara kohore grimca përjeton goditje. Nën ndikimin e një shtytjeje, grimca lëviz me probabilitet një njësi në të djathtë dhe me probabilitet një njësi në të majtë. Është e qartë se pozicioni (koordinata) e një grimce pas një goditjeje varet nga vendi ku ishte grimca pas goditjes menjëherë paraardhëse, dhe nuk varet nga mënyra se si ajo lëvizi nën ndikimin e goditjeve të tjera të mëparshme.

Pra, një shëtitje e rastësishme? Një shembull i një zinxhiri homogjen Markov në kohë diskrete.

Probabiliteti i tranzicionit është probabiliteti i kushtëzuar që nga gjendja (në të cilën sistemi u gjend si rezultat i ndonjë testi, pavarësisht nga numri) si rezultat i testit të ardhshëm sistemi do të kalojë në gjendje.

Kështu, në shënim, indeksi i parë tregon numrin e të mëparshmit, dhe i dyti? numri i shtetit pasues. Për shembull, - probabiliteti i kalimit nga gjendja e dytë në të tretën.

Le të jetë numri i gjendjeve të fundme dhe të barabartë.

Matrica e tranzicionit e një sistemi është një matricë që përmban të gjitha probabilitetet e tranzicionit të këtij sistemi:

Meqenëse çdo rresht i matricës përmban probabilitetet e ngjarjeve (kalimi nga e njëjta gjendje në çdo gjendje të mundshme), të cilat formojnë grupi i plotë, atëherë shuma e probabiliteteve të këtyre ngjarjeve është e barabartë me një. Me fjalë të tjera, shuma e probabiliteteve të tranzicionit të çdo rreshti të matricës së tranzicionit është e barabartë me një:

Le të japim një shembull të matricës së tranzicionit të një sistemi që mund të jetë në tre gjendje; kalimi nga gjendja në gjendje ndodh sipas skemës së një zinxhiri homogjen Markov; probabilitetet e tranzicionit jepen nga matrica:

Këtu shohim se nëse sistemi ishte në gjendje, atëherë pas ndryshimit të gjendjes në një hap do të mbetet në të njëjtën gjendje me një probabilitet 0.5, do të mbetet në të njëjtën gjendje me një probabilitet prej 0.5, do të shkojë në një gjendje me një probabilitet prej 0.2, atëherë pas tranzicionit, ajo mund të gjendet në gjendje; nuk mund të lëvizë nga shteti në. Rreshti i fundit matrica na tregon se nga një gjendje të shkojmë në ndonjë nga gjendjet e mundshme me të njëjtin probabilitet prej 0.1.

Bazuar në matricën e tranzicionit të sistemit, ju mund të ndërtoni të ashtuquajturin grafik të gjendjes së sistemit, ai quhet gjithashtu një grafik i etiketuar gjendjeje. Kjo është e përshtatshme për një paraqitje vizuale të qarkut. Le të shohim rendin e ndërtimit të grafikëve duke përdorur një shembull.

Shembulli 2. Duke përdorur një matricë të caktuar tranzicioni, ndërtoni një grafik të gjendjes.

Sepse matricë rendit i katërt, atëherë, në përputhje me rrethanat, sistemi ka 4 gjendje të mundshme.

Grafiku nuk tregon probabilitetet e kalimit të sistemit nga një gjendje në të njëjtën. Duke rishikuar sisteme specifikeËshtë e përshtatshme që së pari të ndërtohet një grafik gjendjeje, pastaj të përcaktohet probabiliteti i kalimit të sistemit nga një gjendje në të njëjtën (bazuar në kërkesën që shuma e elementeve të rreshtave të matricës të jetë e barabartë me një), dhe më pas të ndërtohet një tranzicion matricës së sistemit.

Ky artikullështë e një natyre abstrakte, e shkruar në bazë të atyre të dhëna në fundi i burimeve, të cilat citohen në vende.

Hyrje në teorinë e zinxhirëve Markov

Një zinxhir Markov është një sekuencë e tillë ngjarje të rastësishme, në të cilën probabiliteti i secilës ngjarje varet vetëm nga gjendja në të cilën ndodhet procesi ky moment dhe është i pavarur nga shtetet e mëparshme. Qarku përfundimtar diskret përcaktohet nga:

1. grup gjendjesh S = (s 1, ..., s n), ngjarja është një kalim nga një gjendje në tjetrën si rezultat i një prove të rastësishme
2. vektoriale probabilitetet fillestare(shpërndarja fillestare) p (0) = ( p (0) (1),…, p (0) (n)), duke përcaktuar probabilitetin p (0) (i) që në kohën fillestare t = 0 procesi ishte në gjendjen s i
3. matrica e probabiliteteve të tranzicionit P = ( p i j), që karakterizon probabilitetin e tranzicionit të procesit me gjendja e tanishme s i në gjendjen tjetër s j , ndërsa shuma e probabiliteteve të kalimit nga një gjendje është e barabartë me 1:

∑ j =1… n p i j = 1

Një shembull i një matrice probabiliteti të tranzicionit me një grup gjendjesh S = (S 1, ..., S 5), një vektor i probabiliteteve fillestare p (0) = (1, 0, 0, 0, 0):

Duke përdorur vektorin e probabiliteteve fillestare dhe matricën e tranzicionit, ne mund të llogarisim vektorin stokastik p (n) - një vektor i përbërë nga probabilitetet p (n) (i) që procesi të jetë në gjendjen i në kohën n. Ju mund të merrni p(n) duke përdorur formulën:

P(n) = p(0)×Pn

Vektorët p (n) ndërsa n rritet, në disa raste, stabilizohen - ato konvergojnë në një vektor të caktuar probabiliteti ρ, i cili mund të quhet shpërndarja e palëvizshme e zinxhirit. Stacionariteti manifestohet në faktin se duke marrë p (0) = ρ, marrim p (n) = ρ për çdo n.
Kriteri më i thjeshtë, e cila garanton konvergjencën në një shpërndarje stacionare, duket kështu: nëse të gjithë elementët e matricës së probabiliteteve të tranzicionit P janë pozitive, atëherë ndërsa n priret në pafundësi, vektori p (n) tenton te vektori ρ, i cili është zgjidhja e vetme në sistemin e formës
p × P = p.
Gjithashtu mund të tregohet se nëse, për disa vlerë pozitive n të gjithë elementët e matricës P n janë pozitive, atëherë vektori p (n) do të stabilizohet ende.
Prova e këtyre deklaratave jepet në detaje.

Një zinxhir Markov përshkruhet si një grafik tranzicioni, kulmet e të cilit korrespondojnë me gjendjet e zinxhirit, dhe harqet korrespondojnë me tranzicionet midis tyre. Pesha e harkut (i, j) që lidh kulmet s i dhe s j do të jetë e barabartë me probabilitetin p i (j) kalimi nga gjendja e parë në të dytën. Grafiku që korrespondon me matricën e treguar më sipër:

Klasifikimi i gjendjeve të zinxhirëve Markov

Kur shqyrtojmë zinxhirët Markov, mund të jemi të interesuar për sjelljen e sistemit për një periudhë të shkurtër kohore. Në këtë rast, probabilitetet absolute llogariten duke përdorur formulat nga seksioni i mëparshëm. Megjithatë, është më e rëndësishme të studiohet sjellja e sistemit interval i madh koha kur numri i kalimeve priret në pafundësi. Më pas, prezantohen përkufizimet e gjendjeve të zinxhirëve Markov, të cilat janë të nevojshme për studimin e sjelljes së sistemit në afat të gjatë.
Zinxhirët Markov klasifikohen në varësi të mundësisë së kalimit nga një gjendje në tjetrën.
Grupet e gjendjeve të një zinxhiri Markov (nëngrupet e kulmeve të grafikut të tranzicionit), të cilat korrespondojnë me kulme të pafundme të diagramit të rendit të grafikut të tranzicionit, quhen klasa ergodike të zinxhirit. Nëse marrim parasysh grafikun e treguar më sipër, mund të shohim se ai përmban 1 klasë ergodike M 1 = ( S 5 ), e arritshme nga një komponent i lidhur fort që korrespondon me një nëngrup kulmesh M 2 = ( S 1 , S 2 , S 3 , S 4). Shtetet që janë në klasa ergodike quhen thelbësore, dhe pjesa tjetër quhen jo thelbësore (edhe pse emra të tillë nuk përshtaten mirë me sens të përbashkët). Gjendja absorbuese s i është një rast i veçantë i klasës ergodike. Pastaj, pasi të jetë në një gjendje të tillë, procesi do të ndalet. Për S i, p ii = 1 do të jetë e vërtetë, d.m.th. në grafikun e tranzicionit, vetëm një skaj do të dalë prej tij - një lak.

Përthithëse Zinxhirët Markov përdoren si modele të përkohshme të programeve dhe proceseve llogaritëse. Gjatë modelimit të një programi, gjendjet e qarkut identifikohen me blloqet e programit, dhe matrica e probabiliteteve të tranzicionit përcakton rendin e kalimeve midis blloqeve, në varësi të strukturës së programit dhe shpërndarjes së të dhënave fillestare, vlerave . prej të cilave ndikojnë në zhvillimin e procesit llogaritës. Si rezultat i paraqitjes së programit nga qarku thithës, është e mundur të llogaritet numri i akseseve në blloqet e programit dhe koha e ekzekutimit të programit, e vlerësuar vlerat mesatare, variancat dhe, nëse është e nevojshme, shpërndarjet. Duke përdorur këto statistika në të ardhmen, mund të optimizoni kodin e programit - përdorni metoda të nivelit të ulët për të shpejtuar pjesët kritike të programit. Kjo metodë quhet profilizimi i kodit.

Për shembull, në algoritmin e Dijkstra janë të pranishme gjendjet e mëposhtme të qarkut:

• kulmi (v), hiqni një kulm të ri nga radha prioritare, shkoni vetëm në gjendjen b;
• fillimi (b), fillimi i ciklit të kërkimit të harqeve dalëse për procedurën e dobësimit;
• analiza (a), analiza e harkut të ardhshëm, kalimi i mundshëm në a, d ose e;
• zvogëlimi (d), zvogëlimi i vlerësimit për disa kulme të grafikut, duke kaluar në një;
• fundi (e), përfundimi i lakut, duke kaluar në kulmin tjetër.

Mbetet për të vendosur probabilitetet e kalimit midis kulmeve, dhe mund të studioni kohëzgjatjen e tranzicionit midis kulmeve, probabilitetet për të hyrë në gjendje të ndryshme dhe karakteristika të tjera mesatare të procesit.

Në mënyrë të ngjashme, procesi llogaritës, i cili zbret në qasjen në burimet e sistemit në rendin e përcaktuar nga programi, mund të përfaqësohet nga një zinxhir thithës Markov, gjendjet e të cilit korrespondojnë me përdorimin e burimeve të sistemit - procesor, memorie dhe tranzicion periferik probabilitetet pasqyrojnë rendin e aksesit në burime të ndryshme. Falë kësaj, procesi llogaritës paraqitet në një formë të përshtatshme për të analizuar karakteristikat e tij.

Një zinxhir Markov quhet i pakalueshëm nëse një gjendje S j mund të arrihet nga çdo gjendje tjetër S i në një numër të kufizuar kalimesh. Në këtë rast, të gjitha gjendjet e qarkut thuhet se janë duke komunikuar, dhe grafiku i tranzicionit është një komponent i lidhjes së fortë. Një proces i gjeneruar nga një zinxhir ergodik, që ka filluar në një gjendje të caktuar, nuk përfundon kurrë, por kalon në mënyrë sekuenciale nga një gjendje në tjetrën, duke përfunduar në gjendje të ndryshme me frekuenca të ndryshme në varësi të probabiliteteve të tranzicionit. Prandaj, karakteristika kryesore e një zinxhiri ergodik është
probabiliteti që procesi të jetë në gjendjet S j , j = 1,…, n, proporcioni i kohës që kalon procesi në secilën prej gjendjeve. Qarqet e pakalueshme përdoren si modele të besueshmërisë së sistemit. Në të vërtetë, nëse një burim që një proces përdor shumë shpesh dështon, funksionaliteti i të gjithë sistemit do të jetë në rrezik. Në këtë rast, dublikimi i një burimi të tillë kritik mund të ndihmojë në shmangien e dështimeve. Në këtë rast, gjendjet e sistemit, të cilat ndryshojnë në përbërjen e pajisjeve të shërbimit dhe të dështuar, interpretohen si gjendje qarku, kalimet ndërmjet të cilave shoqërohen me dështime dhe restaurim të pajisjeve dhe ndryshime në lidhjet midis tyre, të kryera për të ruajtur funksionueshmërinë e sistemit. Vlerësimet e karakteristikave të një qarku të pareduktueshëm japin një ide mbi besueshmërinë e sjelljes së sistemit në tërësi. Gjithashtu, qarqe të tilla mund të jenë modele të ndërveprimit midis pajisjeve dhe detyrave të paraqitura për përpunim.

Shembuj të përdorimit

Sistemi i shërbimit të dështimit

Një server përbëhet nga disa blloqe, të tilla si modem ose kartat e rrjetit, të cilat marrin kërkesa nga përdoruesit për shërbim. Nëse të gjitha blloqet janë të zëna, kërkesa humbet. Nëse njëri prej blloqeve pranon një kërkesë, atëherë ai bëhet i zënë deri në fund të përpunimit të tij. Le të marrim numrin e blloqeve të pabanuara si shtete. Koha do të jetë diskrete. Le të shënojmë me α probabilitetin për të marrë një kërkesë. Ne gjithashtu besojmë se koha e shërbimit është gjithashtu e rastësishme dhe përbëhet nga vazhdime të pavarura, d.m.th. një kërkesë me probabilitet β shërbehet në një hap dhe me probabilitet (1 - β) shërbehet pas këtij hapi si kërkesë e re. Kjo jep një probabilitet prej (1 - β) β për një shërbim me dy hapa, (1 - β) 2 β për një shërbim me tre hapa, etj. Le të shqyrtojmë një shembull me 4 pajisje që funksionojnë paralelisht. Le të krijojmë një matricë të probabiliteteve të tranzicionit për gjendjet e zgjedhura:

Mund të vërehet se ai ka një klasë unike ergodike, dhe për këtë arsye sistemi p × P = p në klasën e vektorëve të probabilitetit ka vetëm vendim. Le të shkruajmë ekuacionet e sistemit që na lejon të gjejmë këtë zgjidhje:

P 0 (1 - α) + p 1 β = p 0 ,
p 0 α + p 1 (1 - α - β) + p 2 2 β = p 1,
p 1 α + p 2 (1 - α - 2 β) + p 3 3 β = p 2,
p 2 α + p 3 (1 - α - 3 β) + p 4 4 β = p 3,
p 3 α + p 4 (1 - 4 β) = p 4 .

Nga kjo marrim (me γ = α / β):

P 1 = γ p 0 ,
p 2 = γ 2 p 0 /2,
p 3 = γ 3 p 0 /3,
p 4 = γ 4 p 0 /4,

Nga gjendja e normalizimit rrjedh:

P 0 = C = (1 + γ + γ 2 /2 + γ 3 /3 + γ 4 /4) -1.

Tani grupi i probabiliteteve π i dihet që në modalitetin stacionar sistemi do të ketë blloqe i të zëna. Pastaj një pjesë e kohës p 4 = C γ 4 / 4 të gjitha blloqet në sistem janë të zëna, sistemi nuk i përgjigjet kërkesave. Rezultatet e marra vlejnë për çdo numër blloqesh. Tani mund të përfitoni prej tyre: mund të krahasoni kostot e pajisjeve shtesë dhe reduktimin e kohës që sistemi është plotësisht i zënë.
Ju mund të lexoni më shumë rreth këtij shembulli në.

Proceset e vendimmarrjes me një numër të kufizuar dhe të pafund fazash

Konsideroni një proces në të cilin ka disa matrica të probabilitetit të tranzicionit. Për çdo moment në kohë, zgjedhja e një ose një matrice tjetër varet nga vendimi që marrim. Sa më sipër mund të kuptohet duke përdorur shembullin e mëposhtëm. Si rezultat i analizës së tokës, kopshtari vlerëson gjendjen e tij me një nga tre numrat: (1) - i mirë, (2) - i kënaqshëm, ose (3) - i dobët. Në të njëjtën kohë, kopshtari vuri re se produktiviteti i tokës në vitin aktual varet vetëm nga gjendja e saj në vitin e kaluar. Prandaj, probabiliteti i tranzicionit të tokës pa ndikimet e jashtme nga një gjendje në tjetrën mund të përfaqësohet nga zinxhiri i mëposhtëm Markov me matricën P1:

Tani mund ta lidhim çdo kalim nga një shtet në tjetrin me një funksion të caktuar të ardhurash, i cili përcaktohet si fitim ose humbje për një periudhë njëvjeçare. Kopshtari mund të zgjedhë të përdorë ose të mos përdorë plehra, kjo do të përcaktojë të ardhurat ose humbjen e tij përfundimtare. Le të prezantojmë matricat R1 dhe R2, të cilat përcaktojnë funksionet e të ardhurave në varësi të kostos së plehrave dhe cilësisë së tokës:

Së fundi, kopshtari përballet me problemin se cilën strategji të zgjedhë për të maksimizuar kthimin mesatar të pritur. Mund të konsiderohen dy lloje problemesh: të fundme dhe numër i pafund fazat. NË në këtë rast Një ditë puna e një kopshtari do të përfundojë patjetër. Për më tepër, vizualizuesit zgjidhin problemin e vendimmarrjes për numër i kufizuar fazat. Lëreni kopshtarin ta ndalojë profesionin e tij pas N vitesh. Detyra jonë tani është të përcaktojmë strategjinë optimale të sjelljes për kopshtarin, domethënë strategjinë që do të maksimizojë të ardhurat e tij. Përfundimi i numrit të fazave në problemin tonë manifestohet në faktin se kopshtarit nuk i intereson se çfarë do të ndodhë me tokën e tij bujqësore në N + 1 vit (të gjitha vitet deri në N janë të rëndësishme për të). Tani mund të shohim se në këtë rast problemi i kërkimit të strategjisë kthehet në një problem programimi dinamik. Nëse shënojmë me f n (i) të ardhurat mesatare maksimale të pritshme që mund të merren për fazat nga n deri në N përfshirëse, duke filluar nga gjendja numër i, atëherë është e lehtë të nxirret një lidhje përsëritëse që lidh f n (i) me numrat f n + 1 (j)

F n (i) = max k (∑ j =1 m p ij k [ r ij k + f n +1 (j)]), n = 1, 2, …, N

Këtu k është numri i strategjisë së përdorur. Ky ekuacion bazohet në faktin se të ardhurat totale r ij k + f n +1 (j) përftohen si rezultat i kalimit nga gjendja i në fazën n në gjendjen j në fazën n +1 me probabilitet p ij k.
Tani zgjidhja optimale mund të gjendet duke llogaritur në mënyrë sekuenciale f n (i) në drejtimin zbritës (n = N ...1). Në të njëjtën kohë, futja e një vektori të probabiliteteve fillestare në deklaratën e problemit nuk do ta komplikojë zgjidhjen e tij.
Ky shembull diskutuar gjithashtu në.

Modelimi i kombinimeve të fjalëve në tekst

Konsideroni një tekst të përbërë nga fjalët w. Le të imagjinojmë një proces në të cilin gjendjet janë fjalë, kështu që kur është në gjendjen (S i) sistemi kalon në gjendjen (s j) sipas matricës së probabiliteteve të tranzicionit. Para së gjithash, është e nevojshme të "trajnohet" sistemi: të sigurohet një tekst mjaft i madh si hyrje për të vlerësuar probabilitetet e tranzicionit. Dhe pastaj mund të ndërtoni trajektoret e zinxhirit Markov. Rritja e ngarkesës semantike të një teksti të ndërtuar duke përdorur algoritmin e zinxhirit Markov është i mundur vetëm duke rritur rendin, ku gjendja nuk është një fjalë, por vendoset me fuqi më të madhe - çifte (u, v), treshe (u, v, w) , etj. Për më tepër, në zinxhirët e rendit të parë dhe të pestë, do të ketë ende pak kuptim. Kuptimi do të fillojë të shfaqet ndërsa dimensioni i renditjes rritet në të paktën numrin mesatar të fjalëve në një frazë tipike teksti burimor. Por është e pamundur të lëvizësh në këtë mënyrë, sepse rritja e ngarkesës semantike të tekstit në zinxhirët Markov të rendit të lartë ndodh shumë më ngadalë sesa rënia në veçantinë e tekstit. Dhe një tekst i ndërtuar mbi zinxhirët Markov, për shembull, i rendit të tridhjetë, nuk do të jetë akoma aq kuptimplotë sa të jetë me interes për njerëzit, por tashmë mjaft i ngjashëm me teksti origjinal, përveç kësaj, numri i shteteve në një qark të tillë do të jetë i mahnitshëm.
Kjo teknologji tani përdoret shumë gjerësisht (për fat të keq) në internet për të krijuar përmbajtje në ueb faqe. Njerëzit që duan të rrisin trafikun në faqen e tyre të internetit dhe të përmirësojnë renditjen e saj Motorë kërkimi, përpiqen të vendosin sa më shumë në faqet e tyre fjalë kyçe Për kërkim. Por motorët e kërkimit përdorin algoritme që mund të dallojnë tekstin real nga një grumbull fjalësh kyçe jokoherente. Më pas, për të mashtruar motorët e kërkimit, ata përdorin tekste të krijuara nga një gjenerator i bazuar në një zinxhir Markov. Ka, sigurisht, shembuj pozitivë përdorimi i zinxhirëve Markov për të punuar me tekstin, ato përdoren në përcaktimin e autorësisë dhe analizimin e autenticitetit të teksteve.

Zinxhirët dhe llotaritë Markov

Në disa raste model probabilistik përdoret në parashikimin e numrave në lotari të ndryshme. Me sa duket, nuk ka kuptim përdorimi i zinxhirëve Markov për të modeluar sekuencën e qarkullimeve të ndryshme. Ajo që ndodhi me topat në short nuk do të ndikojë në asnjë mënyrë në rezultatet e shortit të radhës, pasi pas shortit topat mblidhen dhe në shortin tjetër vendosen në tabaka e shortit në rend fiks. Në këtë rast humbet lidhja me qarkullimin e kaluar. Një tjetër gjë është sekuenca e topave që bien brenda një barazimi. Në këtë rast, rënia e topit të radhës përcaktohet nga gjendja e makinës së lotarisë në momentin e rënies së topit të mëparshëm. Kështu, sekuenca e topave të rënë në një barazim është një zinxhir Markov, dhe një model i tillë mund të përdoret. Këtu ka një vështirësi të madhe kur analizohen llotaritë numerike. Gjendja e makinës së lotarisë pas rënies së topit të radhës përcakton ngjarje të mëtejshme, por problemi është se kjo gjendje është e panjohur për ne. Gjithçka që dimë është se një top i caktuar ra jashtë. Por kur ky top hidhet, topat e mbetur mund të renditen në mënyra të ndryshme, në mënyrë që të ketë një grup shumë numer i madh gjendjet që korrespondojnë me të njëjtën ngjarje të vëzhguar. Prandaj, ne mund të ndërtojmë vetëm një matricë të probabiliteteve të tranzicionit midis grupeve të tilla shtetesh. Këto probabilitete janë mesatarja e probabiliteteve të kalimeve ndërmjet të ndryshmeve shtete të veçanta, e cila natyrisht redukton efikasitetin e aplikimit të modelit të zinxhirit Markov në lotaritë numerike.
Ngjashëm me këtë rast, një model i tillë rrjet nervor mund të përdoret për parashikimin e motit, kuotat e monedhës dhe në lidhje me sisteme të tjera ku të dhënat historike janë të disponueshme dhe informacioni i marrë rishtazi mund të përdoret në të ardhmen. Përdorimi i mirë në këtë rast, kur dihen vetëm manifestimet e sistemit, por jo edhe gjendjet e brendshme (të fshehura), mund të aplikohen modelet e fshehura Markov, të cilat diskutohen në detaje në Wikibooks (modelet e fshehura Markov).

Letërsia

1. Romanovsky I.V. Analiza diskrete: Një libër shkollor për studentët, botimi 3. - Shën Petersburg: Dialekti Nevski; BHV Petersburg, 2003.
2. Taha, Hamdy A. Hyrje në Kërkimin Operacional, botimi i 6-të. - M.: Shtepi botuese Williams, 2001.
3. Werner M. Bazat e kodimit. Libër mësuesi për universitetet. - M.: Tekhnosferë, 2004.
4. Belyaev A., Gavrilov M., Masalskikh A., Medvinsky M. Proceset Markov, 2004.

Vizualizues

1. Proceset e vendimmarrjes Alekseev V. Markov, 2002.
2. Zinxhirët Belyaev A. Markov, 2002.

Metodat përshkrimet matematikore Markoviane procese të rastësishme në një sistem me gjendje diskrete (DS) varen nga ajo se në cilat momente kohore (të njohura më parë ose të rastësishme) mund të ndodhin kalimet e sistemit nga një gjendje në tjetrën.
Nëse kalimi i një sistemi nga shteti në gjendje është i mundur në momente të paracaktuara kohore, kemi të bëjmë me proces i rastësishëm Markov me kohë diskrete. Nëse tranzicioni është i mundur në ndonjë moment i rastësishëm kohë, atëherë kemi të bëjmë me proces i rastësishëm Markov me kohë të vazhdueshme.
Le të ketë sistemi fizik S, e cila mund të jetë në n shteteve S 1 , S 2 , …, S n. Kalimet nga një gjendje në tjetrën janë të mundshme vetëm në momente kohore t 1 , t 2 , …, tk, këto momente le t'i quajmë hapa kohorë. Ne do të shqyrtojmë sipërmarrjen e përbashkët në sistem S si funksion i argumentit të plotë 1, 2, ..., k, ku argumenti është numri i hapit.
Shembull: S 1 → S 2 → S 3 → S 2 .
Le të biem dakord të caktojmë S i (k) – një ngjarje që konsiston në faktin se pas k hapat sistemi është në gjendjen S i.
Për çdo k ngjarjet S 1 ( k), S 2 ( k),…, S n (k) formë grupi i plotë i ngjarjeve dhe janë të papajtueshme.

Një proces në një sistem mund të përfaqësohet si një zinxhir ngjarjesh.
Shembull: S 1 (0) , S 2 (1), S 3 (2) , S 5 (3) ,….
Kjo sekuencë quhet zinxhir Markov , nëse për çdo hap probabiliteti i kalimit nga çdo gjendje S i në çdo kusht Sj nuk varet se kur dhe si ka arritur sistemi në gjendje S i.
Lëreni në çdo moment pas çdo k- sistemi i hapit të thtë S mund të jetë në një nga shtetet S 1 , S 2 , …, S n, pra një ngjarje nga një grup i plotë ngjarjesh mund të ndodhë: S 1 (k), S 2 ( k) , …, S n (k) . Le të tregojmë probabilitetet e këtyre ngjarjeve:
P 1 (1) = P(S 1 (1)); P 2 (1) = P(S 2 (1)); …; Pn(1) = P(S n (k));
P 1 (2) = P(S 1 (2)); P 2 (2) = P(S 2 (2)); ...; Pn(2) = P(S n (2));
P 1 (k) = P(S 1 (k)); P 2 (k) = P(S 2 (k)); …; Pn(k) = P(S n (k)).
Është e lehtë të shihet se për çdo numër hapi kushti është i plotësuar
P 1 (k) + P 2 (k) +…+ Pn(k) = 1.
Le t'i quajmë këto probabilitete probabilitetet shtetërore Prandaj, detyra do të tingëllojë si kjo: gjeni probabilitetet e gjendjeve të sistemit për cilindo k.
Shembull. Le të ketë një lloj sistemi që mund të jetë në cilindo nga gjashtë shtetet. atëherë proceset që ndodhin në të mund të përshkruhen ose si grafik i ndryshimeve në gjendjen e sistemit (Fig. 7.9, A), ose në formën e një grafiku të gjendjes së sistemit (Fig. 7.9, b).

A)

Oriz. 7.9
Gjithashtu, proceset në sistem mund të përshkruhen si një sekuencë gjendjesh: S 1 , S 3 , S 2 , S 2 , S 3 , S 5 , S 6 , S 2 .
Probabiliteti i gjendjes në ( k Hapi + 1) varet vetëm nga gjendja në k- m hap.
Për çdo hap k ka disa probabilitete që sistemi të kalojë nga çdo gjendje në një gjendje tjetër, le t'i quajmë këto probabilitete probabilitetet e tranzicionit të një zinxhiri Markov.
Disa nga këto probabilitete do të jenë 0 nëse kalimi nga një gjendje në tjetrën nuk është i mundur në një hap.
Zinxhiri Markov quhet homogjene, nëse gjendjet e tranzicionit nuk varen nga numri i hapit, ndryshe quhet heterogjene.
Le të ketë një zinxhir homogjen Markov dhe le të sistemit S Ajo ka n gjendjet e mundshme: S 1 , …, S n. Le të dihet probabiliteti i kalimit në një gjendje tjetër në një hap për çdo shtet, d.m.th. P ij(nga S i V Sj në një hap), atëherë mund të shkruajmë probabilitetet e tranzicionit si matricë.

. (7.1)
Përgjatë diagonales së kësaj matrice janë probabilitetet që sistemi të kalojë nga gjendja S i në të njëjtin shtet S i.
Përdorimi i ngjarjeve të futura më parë , ne mund t'i shkruajmë probabilitetet e tranzicionit si probabilitete të kushtëzuara:
.
Natyrisht, shuma e termave në çdo rresht të matricës (1) është e barabartë me një, pasi ngjarjet formojnë një grup të plotë ngjarjesh të papajtueshme.

Kur merren parasysh zinxhirët Markov, si dhe kur analizohet një proces i rastësishëm Markov, përdoren grafikë të ndryshëm të gjendjes (Fig. 7.10).

Oriz. 7.10

Ky sistem mund të jetë në cilindo nga gjashtë shtetet, ndërsa P ijështë probabiliteti i kalimit të sistemit nga gjendja S i në një gjendje Sj. Për këtë sistem, ne shkruajmë ekuacionet që sistemi ishte në një gjendje dhe jashtë tij gjatë kohës t nuk doli:

NË rast i përgjithshëm zinxhiri Markov është johomogjen, pra probabiliteti P ij ndryshon nga hapi në hap. Supozoni se është dhënë një matricë e probabiliteteve të tranzicionit në çdo hap, atëherë probabiliteti që sistemi S në k-Hapi i thte do te jete ne shtet S i, mund të gjendet duke përdorur formulën

Duke ditur matricën e probabiliteteve të tranzicionit dhe gjendjen fillestare të sistemit, mund të gjenden probabilitetet e gjendjeve pas ndonjë k-hapi i th. Lëreni në momentin fillestar të kohës sistemi të jetë në gjendje S m. Pastaj për t = 0
.
Le të gjejmë probabilitetet pas hapit të parë. Nga shteti S m sistemi do të shkojë në shtete S 1 , S 2 etj me probabilitete P m 1 , P m 2 , …, Pmm, …, P mn. Pastaj pas hapit të parë probabilitetet do të jenë të barabarta

. (7.2)
Të gjejmë probabilitetet e gjendjes pas hapit të dytë: . Ne do t'i llogarisim këto probabilitete duke përdorur formulën probabilitet të plotë me hipoteza:
.
Hipotezat do të jenë pohimet e mëposhtme:

• pas hapit të parë sistemi ishte në gjendjen S 1 -H 1;
• pas hapit të dytë sistemi ishte në gjendjen S 2 -H 2;
• pas n të hapit të th, sistemi ishte në gjendjen S n -H n.

Probabiliteti i ndonjë gjendjeje pas hapit të dytë:

(7.3)
Formula (7.3) përmbledh të gjitha probabilitetet e tranzicionit P ij, por merren parasysh vetëm ato jo zero. Probabiliteti i ndonjë gjendje pas k-hapi i thte:

(7.4)
Kështu, probabiliteti i një gjendje pas k hapi i th percaktohet nga formula e perseritur (7.4) nepermjet probabiliteteve ( k - 1) hapi.

Detyra 6.Është dhënë një matricë e probabiliteteve të tranzicionit për një zinxhir Markov në një hap. Gjeni matricën e kalimit të një qarku të caktuar në tre hapa .
Zgjidhje. Matrica e tranzicionit e një sistemi është një matricë që përmban të gjitha probabilitetet e tranzicionit të këtij sistemi:

Çdo rresht i matricës përmban probabilitetet e ngjarjeve (kalimi nga gjendja i në një gjendje j), të cilat formojnë një grup të plotë, kështu që shuma e probabiliteteve të këtyre ngjarjeve është e barabartë me një:

Le të shënojmë me p ij (n) probabilitetin që si rezultat i n hapave (testeve) sistemi të kalojë nga gjendja i në gjendjen j. Për shembull, p 25 (10) është probabiliteti i kalimit nga gjendja e dytë në të pestin në dhjetë hapa. Vini re se për n=1 marrim probabilitete kalimi p ij (1)=p ij .
Na jepet detyra: duke ditur probabilitetet e kalimit p ij, të gjejmë probabilitetet p ij (n) të kalimit të sistemit nga gjendja. i në një gjendje j mbrapa n hapat. Për ta bërë këtë, ne prezantojmë një ndërmjetës (ndërmjet i Dhe j) shteti r. Me fjalë të tjera, ne do të supozojmë se nga gjendja fillestare i mbrapa m hapat sistemi do të kalojë në një gjendje të ndërmjetme r me probabilitet p ij (n-m), pas së cilës, për pjesën e mbetur n-m hapa nga gjendja e ndërmjetme r do të kalojë në gjendjen përfundimtare j me probabilitet p ij (n-m) . Duke përdorur formulën e probabilitetit total marrim:
.
Kjo formulë quhet barazia e Markovit. Duke përdorur këtë formulë, mund të gjeni të gjitha probabilitetet p ij (n), dhe, rrjedhimisht, vetë matricën P n. Meqenëse llogaritja e matricës çon më shpejt te qëllimi, ne shkruajmë relacionin e matricës që rezulton nga formula që rezulton në formë të përgjithshme.
Le të llogarisim matricën e tranzicionit të zinxhirit Markov në tre hapa duke përdorur formulën që rezulton:

Përgjigje:.

Detyra nr. 1. Matrica e probabilitetit të tranzicionit të zinxhirit Markov ka formën:
.
Shpërndarja mbi gjendjet në kohën t=0 përcaktohet nga vektori:
π 0 =(0,5; 0,2; 0,3)
Gjej: a) shpërndarja sipas gjendjes në momentet t=1,2,3,4.
c) shpërndarje stacionare.

Zinxhiri Markov është një proces Markov në kohë diskrete i përcaktuar në hapësirë ​​të matshme.

Prezantimi

Proceset e rastësishme Markov janë emëruar pas matematikanit të shquar rus A.A. Markov (1856-1922), i cili fillimisht filloi studimin e lidhjes probabilistike të ndryshoreve të rastësishme dhe krijoi një teori që mund të quhet "dinamika e probabilitetit".

NË bazat e mëtejshme kjo teori ishte baza fillestare teori e përgjithshme procese të rastësishme, si dhe të tilla të rëndësishme Shkencat e aplikuara, si teoria e proceseve të difuzionit, teoria e besueshmërisë, teoria në radhë etj. Aktualisht, teoria e proceseve Markov dhe aplikimet e saj përdoren gjerësisht në fusha të ndryshme.

Për shkak të thjeshtësisë dhe qartësisë krahasuese të aparatit matematikor, besueshmërisë dhe saktësisë së lartë të zgjidhjeve të marra, Vëmendje e veçantë proceset Markov marrë nga specialistë të përfshirë në kërkimin e operacioneve dhe teorinë e vendimmarrjes optimale.

Shembull i thjeshtë: hedhja e një monedhe

Para se të jepni një përshkrim skema e përgjithshme, le t'i drejtohemi shembull i thjeshtë. Le të pretendojmë se po flasim për për hedhjen e njëpasnjëshme të një monedhe në një lojë hedhjeje; një monedhë hidhet në momente të kushtëzuara të kohës t = 0, 1, ... dhe në çdo hap lojtari mund të fitojë ±1 me të njëjtin probabilitet prej 1/2, kështu që në kohën t fitorja totale e tij është vlerë e rastësishmeξ(t) me vlerat e mundshme j = 0, ±1, ...

Me kusht që ξ(t) = k, në hapin tjetër fitimi do të jetë tashmë i barabartë me ξ(t+1) = k ± 1, duke marrë vlerat e specifikuara j = k ± 1 me probabilitet të barabartë 1/2.

Në mënyrë konvencionale, mund të themi se këtu, me probabilitetin përkatës, ndodh një kalim nga gjendja ξ(t) = k në gjendjen ξ(t+1) = k ± 1.

Formulat dhe përkufizimet

Duke e përgjithësuar këtë shembull, ne mund të imagjinojmë një "sistem" me një numër të numërueshëm të gjendjeve "fazore" të mundshme, i cili gjatë një kohe diskrete t = 0, 1, ... kalon rastësisht nga një gjendje në tjetrën.

Le të jetë ξ(t) pozicioni i tij në kohën t si rezultat i një zinxhiri kalimesh të rastësishme

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

Le të tregojmë zyrtarisht gjithçka shtetet e mundshme numra të plotë i = 0, ±1, ... Le të supozojmë se për një gjendje të njohur ξ(t) = k, në hapin tjetër sistemi shkon në gjendjen ξ(t+1) = j me probabilitet të kushtëzuar

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

pavarësisht nga sjellja e tij në të kaluarën, më saktë, pavarësisht nga zinxhiri i tranzicionit (1) deri në momentin t:

P(ξ(t+1) = j|ξ(0) = i, ..., ξ(t) = k) = P(ξ(t+1) = j|ξ(t) = k) për të gjitha t, k, j... (3) - Prona e Markovit.

Kjo skemë probabiliste quhet zinxhir homogjen Markov me një numër të numërueshëm shtetesh- homogjeniteti i tij qëndron në faktin se ato të përcaktuara në (2) probabilitetet e kalimit p kj, ∑ j p kj = 1, k = 0, ±1, ..., nuk varen nga koha, d.m.th. P(ξ(t+1) = j|ξ(t) = k) = P ij - matrica e probabilitetit të tranzicionit në një hap nuk varet nga n.

Është e qartë se P ij - matricë katrore me elemente jonegative dhe shuma njësi nëpër rreshta.

Një matricë e tillë (fundme ose e pafundme) quhet matricë stokastike. Çdo matricë stokastike mund të shërbejë si matricë e probabiliteteve të tranzicionit.

Në praktikë: dërgesa e pajisjeve në rrethe

Le të supozojmë se një kompani e caktuar jep pajisje në Moskë: rrethi verior(shënohet me A), jugore (B) dhe qendrore (C). Kompania ka një ekip korrierësh që i shërbejnë këto zona. Është e qartë se për të bërë dërgesën e radhës, korrieri shkon në zonën që është aktualisht më afër tij. Statistikisht u përcaktua sa vijon:

1) pas dorëzimit në A, dorëzimi tjetër kryhet në 30 raste në A, në 30 raste - në B dhe në 40 raste - në C;

2) pas dorëzimit te B, dorëzimi tjetër kryhet në 40 raste në A, në 40 raste - në B dhe në 20 raste - në C;

3) pas dorëzimit në C, dorëzimi tjetër kryhet në 50 raste në A, në 30 raste - në B dhe në 20 raste - në C.

Kështu, zona e ardhshme e dorëzimit përcaktohet vetëm nga dorëzimi i mëparshëm.

Matrica e probabilitetit të tranzicionit do të duket kështu:

Për shembull, p 12 = 0,4 është probabiliteti që pas dorëzimit në zonën B, dorëzimi tjetër do të bëhet në zonën A.

Le të supozojmë se çdo dërgesë e ndjekur nga lëvizja në zonën tjetër zgjat 15 minuta. Më pas, sipas statistikave, pas 15 minutash 30% e korrierëve që ishin në A do të jenë në A, 30% do të jenë në B dhe 40% do të jenë në C.

Meqenëse në momentin tjetër, secili nga korrierët do të jetë patjetër në një nga rrethet, shuma e kolonave është e barabartë me 1. Dhe duke qenë se kemi të bëjmë me probabilitete, çdo element i matricës është 0<р ij <1.

Rrethana më e rëndësishme që na lejon ta interpretojmë këtë model si zinxhir Markov është se vendndodhja e korrierit në kohën t+1 varet. vetëm nga vendndodhja në kohën t.

Tani le të bëjmë një pyetje të thjeshtë: nëse korrieri fillon nga C, sa është probabiliteti që pasi të bëjë dy dërgesa, të jetë në B, d.m.th. si mund ta arrini B në 2 hapa? Pra, ka disa shtigje nga C në B në 2 hapa:

1) së pari nga C në C dhe më pas nga C në B;

2) C-->B dhe B-->B;

3) C-->A dhe A-->B.

Jepet rregulli i shumëzimit ngjarje të pavarura, ne gjejmë se probabiliteti i dëshiruar është i barabartë me:

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

Zëvendësimi i vlerave numerike:

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

Rezultati i marrë sugjeron se nëse korrieri e ka nisur punën nga C, atëherë në 33 raste nga 100 ai do të jetë në B pas dy dërgesave.

Është e qartë se llogaritjet janë të thjeshta, por nëse duhet të përcaktoni probabilitetin pas 5 ose 15 dërgesave, mund të marrë mjaft kohë.

Le të tregojmë një mënyrë më të thjeshtë për të llogaritur probabilitete të tilla. Për të marrë probabilitetet e tranzicionit nga kushte të ndryshme në 2 hapa, ne katrore matricën P:

Atëherë elementi (2, 3) është probabiliteti i kalimit nga C në B në 2 hapa, i cili u mor më lart në një mënyrë tjetër. Vini re se elementet në matricën P2 gjithashtu variojnë nga 0 në 1, dhe shuma e kolonave është 1.

Se. nëse keni nevojë të përcaktoni probabilitetet e kalimit nga C në B në 3 hapa:

1 mënyrë. 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, ku p(CA) - probabiliteti i kalimit nga C në A në 2 hapa (d.m.th., ky është elementi (1, 3) i matricës P2).

Metoda 2. Llogaritni matricën P3:

Matrica e probabiliteteve të kalimit në fuqinë e 7-të do të duket kështu:

Është e lehtë të vërehet se elementët e çdo rreshti priren në disa numra. Kjo sugjeron që pas mjaft sasi e madhe dorëzimi, nuk ka rëndësi se në cilin rreth filloi të punojë korrieri. Se. në fund të javës afërsisht 38.9% do të jetë në A, 33.3% do të jetë në B dhe 27.8% do të jetë në C.

Një konvergjencë e tillë garantohet të ndodhë nëse të gjithë elementët e matricës së probabilitetit të tranzicionit i përkasin intervalit (0, 1).