Markovo grandinės pereinamųjų būsenų matrica. Markovo grandinės

1. matrica P2 grandinės perėjimas iš būsenos i valstybėje j dviese
žingsnis;

2. tikimybių pasiskirstymas per būsenas šiuo metu t=2;

3. tikimybė, kad šiuo metu t=1 grandinės būsena bus A2;

4. stacionarus paskirstymas.

Sprendimas. Diskretinei Markovo grandinei jos homogeniškumo atveju galioja toks ryšys:

čia P1 – perėjimo viename žingsnyje tikimybių matrica;
Рn - n žingsnių perėjimo tikimybių matrica;

1. Raskite P2 perėjimo matricą dviem etapais

Įjunkite tikimybių pasiskirstymą per būsenas S laiptelis nustatomas pagal vektorių
.
Matricos pažinimas Pn pereinant n žingsnių, galime nustatyti tikimybių pasiskirstymą per būsenas on (S+n)-tas žingsnis . (5)

2. Raskime tikimybių pasiskirstymą pagal sistemos būsenas šiuo metu t=2. Įdėkime (5) S=0 ir n=2. Tada .

Sulauksime.

3. Raskime tikimybių pasiskirstymą pagal sistemos būsenas šiuo metu t=1.

Įdėkime (5) s=0 ir n=1, tada .
Kaip mes galime pamatyti, kad tikimybė, kad šiuo metu t=1 grandinės būsena bus A2, lygus р2(1)=0,69.
Tikimybių pasiskirstymas tarp būsenų vadinamas stacionariu, jei jis nesikeičia nuo žingsnio iki žingsnio, tai yra
Tada iš santykio (5) at n=1 gauname

4. Raskime stacionarų skirstinį. Kadangi =2, turime =(р1; р2). Parašykime sistemą tiesines lygtis(6) in koordinačių forma

Paskutinė sąlyga vadinama normalizavimu. Sistemoje (6) viena lygtis visada yra kitų tiesinė kombinacija. Todėl jį galima užbraukti. Išspręskime pirmąją sistemos lygtį ir normalizavimo lygtį kartu. Turime 0,6 p1=0,3p2, tai yra p2=2p1. Tada p1+2p1=1 arba , tai yra . Vadinasi,.
Atsakymas:
1) perėjimo matrica dviem žingsniais tam tikrai Markovo grandinei turi formą ;
2) tikimybių pasiskirstymas per būsenas šiuo metu t=2 lygus ;
3) tikimybė, kad šiuo metu t=1 grandinės būsena bus A2, yra lygus p2(t)=0,69;
4) stacionarus skirstinys turi formą

Matrica duota ištisinės Markovo grandinės perėjimo intensyvumas. Sukurti pažymėtą būsenos grafiką, atitinkantį matricą Λ; sukurti sistemą diferencialines lygtis Kolmogorov – būsenų tikimybių; Raskite ribinį tikimybių skirstinį. Sprendimas. Vienalytė Markovo grandinė su baigtiniu skaičiumi būsenų A1, A2,…A kuriai būdinga perėjimo intensyvumo matrica ,

Kur - Markovo grandinės perėjimo iš būsenos intensyvumas Аi valstybėje Аj; рij(Δt)- perėjimo tikimybė Ai →Aj per laiko intervalą Δ t.

Sistemos perėjimai iš būsenos į būseną patogiai nurodomi naudojant pažymėtą būsenos grafiką, kuriame yra pažymėti intensyvumą atitinkantys lankai λ ij>0. Sukurkime pažymėtos būsenos grafiką tam tikrai perėjimo intensyvumo matricai

Leisti būti tikimybių vektoriumi rj(t),
j=1, 2,…,, sistema yra būsenoje Ajšiuo metu t.

Akivaizdu, kad 0≤ rj(t)≤1 ir . Tada pagal skaliarinio argumento vektorinės funkcijos diferenciacijos taisyklę gauname . Tikimybės rj(t) tenkina Kolmogorovo diferencialinių lygčių (SDEK) sistemą, kuri in matricos forma atrodo kaip. (7)

Jei pradiniu momentu sistema buvo būsenoje Аj, tada SDUK turėtų būti išspręstas pradinėmis sąlygomis
ri(0)=1, рj(0)=0, j≠i,j = 1, 2,…,. (8)
SDUK rinkinys (7) ir pradines sąlygas(8) vienareikšmiškai apibūdina vienalytę Markovo grandinę su nuolatinis laikas ir baigtinis skaičius būsenų.
Sudaryk SDEK tam tikrai Markovo grandinei. Nuo =3, tada j=1, 2, 3.

Iš (7) santykio gauname

.
Iš čia mes turėsime

Paskutinė sąlyga vadinama normalizavimu.
Tikimybių pasiskirstymas per būsenas vadinamas stacionarus, jei laikui bėgant nesikeičia, tai yra, kur rj=konst, j=1,2,…,. Iš čia .

Tada iš SDUK (7) gauname stacionaraus skirstinio nustatymo sistemą
(9)
Šiai problemai mes turėsime iš SDUK

Iš normalizavimo sąlygos gauname 3р2+р2+р2=1 arba . Todėl ribinis skirstinys turi formą .
Atkreipkite dėmesį, kad šį rezultatą galima gauti tiesiogiai iš pažymėtos būsenos grafiko, jei naudosime taisyklę: stacionariam pasiskirstymui – produktų suma λ jipi, j≠i, rodyklėms, kilusioms iš i-oji būsena yra lygi produktų sumai λ jipi, j≠i, rodyklėms, įtrauktoms į i– valstybė. tikrai,

Akivaizdu, kad gauta sistema yra lygiavertė sistemai, sudarytai naudojant SDUK. Todėl jis turi tą patį sprendimą.
Atsakymas: stacionarus skirstinys turi formą .

Apibrėžimas. Markovo grandinė vadinama vienalyte, jei sąlyginė tikimybė (perėjimas iš būsenos į būseną) nepriklauso nuo bandymo skaičiaus. Štai kodėl jie tiesiog rašo.

1 pavyzdys. Atsitiktinis pasivaikščiojimas. Tegul taške, kurio koordinatė yra sveikoji, tiesioje linijoje yra medžiagos dalelė. Tam tikrais laiko momentais dalelė patiria smūgius. Stūmimo įtakoje dalelė juda su tikimybe vienu vienetu į dešinę ir su tikimybe vienu vienetu į kairę. Akivaizdu, kad dalelės padėtis (koordinatė) po smūgio priklauso nuo to, kur dalelė buvo po iš karto prieš tai buvusio smūgio, ir nepriklauso nuo to, kaip ji judėjo veikiama kitų ankstesnių smūgių.

Taigi atsitiktinis pasivaikščiojimas? Vienalytės diskretinio laiko Markovo grandinės pavyzdys.

Perėjimo tikimybė yra sąlyginė tikimybė, kad iš būsenos (kurioje sistema atsidūrė atlikus tam tikrą testą, nesvarbu, koks skaičius) dėl kito bandymo sistema pereis į būseną.

Taigi, pavadinime pirmasis indeksas nurodo ankstesnio numerį, o antrasis? paskesnis valstybinis numeris. Pavyzdžiui, - perėjimo iš antrosios būsenos į trečią tikimybė.

Tegu būsenų skaičius baigtinis ir lygus.

Sistemos perėjimo matrica yra matrica, kurioje yra visos šios sistemos perėjimo tikimybės:

Kadangi kiekvienoje matricos eilutėje yra įvykių (perėjimo iš tos pačios būsenos į bet kokią galimą būseną) tikimybės, kurios sudaro pilna grupė, tada šių įvykių tikimybių suma lygi vienetui. Kitaip tariant, kiekvienos perėjimo matricos eilutės perėjimo tikimybių suma yra lygi vienetui:

Pateiksime sistemos, kuri gali būti trijų būsenų, pereinamosios matricos pavyzdį; perėjimas iš būsenos į būseną vyksta pagal vienalytės Markovo grandinės schemą; perėjimo tikimybės pateikiamos matrica:

Čia matome, kad jei sistema buvo būsenoje, tai pakeitus būseną vienu žingsniu ji išliks toje pačioje būsenoje su 0,5 tikimybe, išliks toje pačioje būsenoje su tikimybe 0,5, pereis į būseną. su 0,2 tikimybe, tada po perėjimo ji gali atsidurti būsenose; ji negali pereiti iš valstybės į. Paskutinė eilutė matrica rodo, kad iš būsenos pereiti į bet kurią iš galimų būsenų su ta pačia tikimybe 0,1.

Remiantis sistemos pereinamąja matrica, galima sukonstruoti taip vadinamą sistemos būsenų grafiką, kuris dar vadinamas paženklintu būsenos grafiku. Tai patogu vizualiai pavaizduoti grandinę. Pažvelkime į grafikų sudarymo tvarką naudodami pavyzdį.

2 pavyzdys. Naudodami nurodytą perėjimo matricą, sukurkite būsenos grafiką.

Nes matrica ketvirta tvarka, tada, atitinkamai, sistema turi 4 galimas būsenas.

Grafike nerodomos tikimybės, kad sistema pereis iš vienos būsenos į tą pačią. Svarstant konkrečios sistemos Patogu pirmiausia sudaryti būsenų grafiką, tada nustatyti sistemos perėjimų iš vienos būsenos į tą pačią tikimybę (remiantis reikalavimu, kad matricos eilučių elementų suma būtų lygi vienetui), o tada konstruoti perėjimą. sistemos matrica.

Šis straipsnis yra abstraktaus pobūdžio, parašytas remiantis tuo, kas pateikta šaltinių pabaiga, kurios cituojamos vietomis.

Markovo grandinių teorijos įvadas

Markovo grandinė yra tokia seka atsitiktiniai įvykiai, kuriame kiekvieno įvykio tikimybė priklauso tik nuo būsenos, kurioje vyksta procesas dabartinis momentas ir nepriklauso nuo ankstesnių būsenų.

1. Galutinė diskretinė grandinė nustatoma taip:
2. būsenų rinkinys S = (s 1, …, s n), įvykis yra perėjimas iš vienos būsenos į kitą atsitiktinio bandymo rezultatas vektorius pradines tikimybes
3. (pradinis skirstinys) p (0) = ( p (0) (1),…, p (0) (n)), nustatant tikimybę p (0) (i), kad pradiniu momentu t = 0 procesas buvo valstybėje s i perėjimo tikimybių matrica P = ( p i j), apibūdinanti proceso perėjimo su tikimybę dabartinė būklė

s i į kitą būseną s j , o perėjimų iš vienos būsenos tikimybių suma lygi 1:

∑ j = 1… n p i j = 1

Perėjimo tikimybių matricos su būsenų rinkiniu S = (S 1, ..., S 5) pavyzdys, pradinių tikimybių vektorius p (0) = (1, 0, 0, 0, 0):

Naudodami pradinių tikimybių vektorių ir pereinamąją matricą, galime apskaičiuoti stochastinį vektorių p (n) - vektorių, sudarytą iš tikimybių p (n) (i), kad procesas bus i būsenoje momentu n. Galite gauti p(n) naudodami formulę:

P(n) = p(0) × Pn
Vektoriai p (n), kai n auga, kai kuriais atvejais stabilizuojasi – susilieja į tam tikrą tikimybių vektorių ρ, kurį galima pavadinti stacionariu grandinės skirstiniu. Stacionarumas pasireiškia tuo, kad imant p (0) = ρ, gauname p (n) = ρ bet kuriam n.
Paprasčiausias kriterijus
, kuris garantuoja konvergenciją į stacionarų skirstinį, atrodo taip: jei visi perėjimo tikimybių P matricos elementai yra teigiami, tai n linkus į begalybę, vektorius p (n) linksta į vektorių ρ, kuris yra vienintelis sprendimas. į formos sistemą p × P = p. n visi matricos P n elementai yra teigiami, tada vektorius p (n) vis tiek stabilizuosis.
Pateikiami išsamūs šių teiginių įrodymai.

Markovo grandinė pavaizduota kaip pereinamasis grafikas, kurio viršūnės atitinka grandinės būsenas, o lankai – perėjimus tarp jų. Lanko (i, j), jungiančio viršūnes s i ir s j, svoris bus lygus tikimybei p i (j) perėjimas iš pirmosios būsenos į antrąją.

Grafikas, atitinkantis aukščiau pateiktą matricą:

Markovo grandinių būsenų klasifikacija Svarstydami Markovo grandines galime susidomėti sistemos elgesiu per trumpą laiką. Šiuo atveju absoliučios tikimybės apskaičiuojamos naudojant formules iš ankstesnio skyriaus. Tačiau svarbiau yra ištirti sistemos elgseną didelis intervalas
laikas, kai perėjimų skaičius linkęs į begalybę.
Toliau pateikiami Markovo grandinių būsenų apibrėžimai, būtini norint ištirti sistemos elgseną ilgalaikėje perspektyvoje. Markovo grandinės klasifikuojamos atsižvelgiant į galimybę pereiti iš vienos būsenos į kitą. Markovo grandinės būsenų grupės (pereinamojo grafo viršūnių poaibiai), atitinkančios pereinamojo grafo eilės diagramos aklavietės viršūnes, vadinamos ergodinėmis grandinės klasėmis.

Jei atsižvelgsime į aukščiau pateiktą grafiką, pamatytume, kad jame yra 1 ergodinė klasė M 1 = ( S 5 ), pasiekiama iš stipriai sujungto komponento, atitinkančio viršūnių poaibį M 2 = ( S 1 , S 2 , S 3 , S 4). Būsenos, kurios yra ergodinėse klasėse, vadinamos esminėmis, o likusios – neesminėmis (nors tokie pavadinimai nedera su sveikas protas). Sugerianti būsena s i yra ypatingas ergodinės klasės atvejis. Tada, atsidūrus tokioje būsenoje, procesas sustos. S i atveju p ii = 1 bus teisinga, t.y. pereinamajame grafe iš jo išeis tik viena briauna – kilpa., dispersijos ir, jei reikia, skirstiniai. Naudodami šią statistiką ateityje galėsite optimizuoti programos kodą – naudokite žemo lygio metodus, kad paspartintumėte svarbias programos dalis. Šis metodas vadinamas kodo profiliavimu.

Pavyzdžiui, Dijkstra algoritme yra šios grandinės būsenos:

• viršūnė (v), pašalinkite naują viršūnę iš prioritetinės eilės, eikite tik į būseną b;
• pradžia (b), išeinančių lankų, skirtų susilpninimo procedūrai, paieškos ciklo pradžia;
• analizė (a), kito lanko analizė, galimas perėjimas prie a, d arba e;
• mažėjimas (d), mažinant įvertį kuriai nors grafo viršūnei, pereinant prie a ;
• pabaiga (e), kilpos užbaigimas, perėjimas į kitą viršūnę.

Belieka nustatyti perėjimo tarp viršūnių tikimybes, o jūs galite ištirti perėjimų tarp viršūnių trukmę, tikimybę patekti į įvairias būsenas ir kitas vidutines proceso charakteristikas.

Panašiai skaičiavimo procesas, kuris baigiasi prieiga prie sistemos išteklių programos nustatyta tvarka, gali būti pavaizduotas absorbuojančia Markovo grandine, kurios būsenos atitinka sistemos išteklių naudojimą - procesoriaus, atminties ir periferinių įrenginių perėjimą tikimybės atspindi prieigos prie įvairių išteklių tvarką. Dėl to skaičiavimo procesas pateikiamas tokia forma, kad būtų patogu analizuoti jo charakteristikas.

Markovo grandinė vadinama neredukuojama, jei bet kurią būseną S j galima pasiekti iš bet kurios kitos būsenos S i per baigtinį perėjimų skaičių. Šiuo atveju sakoma, kad visos grandinės būsenos palaiko ryšį, o perėjimo grafikas yra stipraus ryšio komponentas.
tikimybė, kad procesas bus būsenose S j , j = 1,…, n, laiko dalis, kurią procesas praleidžia kiekvienoje iš būsenų.

Neredukuojamos grandinės naudojamos kaip sistemos patikimumo modeliai. Iš tiesų, jei resursas, kurį procesas naudoja labai dažnai, sugenda, kils pavojus visos sistemos funkcionalumui.

Tokiu atveju tokio kritinio resurso dubliavimas gali padėti išvengti gedimų.

Šiuo atveju sistemos būsenos, kurios skiriasi eksploatuojamų ir sugedusių įrenginių sudėtimi, yra interpretuojamos kaip grandinės būsenos, perėjimai tarp kurių yra susiję su gedimais ir įrenginių atkūrimu bei jungčių tarp jų pasikeitimais, atliekamais siekiant palaikyti sistemos veikimas. Neredukuojamos grandinės charakteristikų įvertinimai leidžia suprasti visos sistemos veikimo patikimumą. Be to, tokios grandinės gali būti įrenginių ir apdoroti pateiktų užduočių sąveikos modeliai. Naudojimo pavyzdžiai

2 β 1 - α - 2 β 3 β

1 - α - 3 β
4β
1 - 4 β
Galima pastebėti, kad ji turi unikalią ergodinę klasę, todėl sistema p × P = p tikimybės vektorių klasėje turi
vienintelis sprendimas

. Užrašykime sistemos lygtis, leidžiančias rasti šį sprendimą:

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 .

Iš to gauname (kai γ = α / β):

Dabar žinoma tikimybių rinkinys π i, kad stacionariame režime sistemoje bus užimti i blokai. Tada dalis laiko p 4 = C γ 4 /4 visi sistemos blokai yra užimti, sistema nereaguoja į užklausas. Gauti rezultatai taikomi bet kokiam blokų skaičiui. Dabar galite jomis pasinaudoti: galite palyginti papildomų įrenginių sąnaudas ir sutrumpėjusį sistemos pilno užimtumo laiką.
Daugiau apie šį pavyzdį galite perskaityti .

Sprendimų priėmimo procesai su baigtiniu ir begaliniu etapų skaičiumi

Apsvarstykite procesą, kuriame yra kelios perėjimo tikimybės matricos. Kiekvienam laiko momentui vienos ar kitos matricos pasirinkimas priklauso nuo mūsų priimto sprendimo. Tai, kas išdėstyta aukščiau, galima suprasti naudojant šį pavyzdį. Atlikdamas dirvožemio analizę, sodininkas jo būklę įvertina vienu iš trijų skaičių: (1) – gera, (2) – patenkinama arba (3) – bloga. Kartu sodininkas pastebėjo, kad einamųjų metų dirvožemio produktyvumas priklauso tik nuo jos būklės praėjusiais metais. Todėl dirvožemio perėjimo tikimybė be

išorinių poveikių

Pateikiame matricas R1 ir R2, kurios nustato pajamų funkcijas priklausomai nuo trąšų kainos ir dirvožemio kokybės: R1 R2 Galiausiai sodininkas susiduria su problema, kokią strategiją pasirinkti, kad maksimaliai padidintų vidutinę tikėtiną grąžą. Gali būti nagrinėjamos dviejų tipų problemos: baigtinės ir begalinis skaičius etapai.

Tegul sodininkas po N metų ketina nutraukti savo užsiėmimą.

Mūsų užduotis dabar yra nustatyti optimalią sodininko elgesio strategiją, ty strategiją, kuri padidins jo pajamas. Mūsų problemos etapų skaičiaus baigtumas pasireiškia tuo, kad sodininkui nerūpi, kas bus su jo žemės ūkio paskirties žeme po N + 1 metų (jam svarbūs visi metai iki N imtinai). Dabar matome, kad šiuo atveju strategijos paieškos problema virsta dinamine programavimo problema. Jei pažymime f n (i) didžiausias vidutines tikėtinas pajamas, kurias galima gauti etapais nuo n iki N imtinai, pradedant nuo būsenos numerio i, tada nesunku išvesti pasikartojimo ryšį, jungiantį f n (i) su skaičiais f n + 1 (j)
F n (i) = maks. k (∑ j = 1 m p ij k [ r ij k + f n +1 (j)]), n = 1, 2, …, N
Čia k yra naudojamos strategijos numeris. Ši lygtis pagrįsta tuo, kad bendrosios pajamos r ij k + f n +1 (j) gaunamos perėjus iš būsenos i n stadijoje į būseną j n +1 etape su tikimybe p ij k. Dabar optimalų sprendimą galima rasti apskaičiuojant f n (i) nuosekliai mažėjimo kryptimi (n = N ...1).

Tuo pačiu metu pradinių tikimybių vektoriaus įvedimas į problemos teiginį neapsunkins jos sprendimo.

Šis pavyzdys taip pat aptarta .. Bet taip judėti neįmanoma, nes teksto semantinio krūvio augimas aukštos eilės Markovo grandinėse vyksta daug lėčiau nei teksto unikalumo mažėjimas. O tekstas, pastatytas ant Markovo grandinių, pavyzdžiui, trisdešimto eilės, vis tiek nebus toks prasmingas, kad būtų įdomus žmonėms, bet jau gana panašus į originalus tekstas, be to, būsenų skaičius tokioje grandinėje bus nuostabus.
Ši technologija dabar labai plačiai naudojama (deja) internete kuriant tinklalapio turinį. Žmonės, norintys padidinti srautą į savo svetainę ir pagerinti jos reitingą paieškos sistemos, stengiasi į savo puslapius įtraukti kuo daugiau raktinius žodžius ieškoti. Tačiau paieškos sistemos naudoja algoritmus, kurie gali atskirti tikrą tekstą nuo nenuoseklaus raktinių žodžių kratinio. Tada, norėdami apgauti paieškos sistemas, jie naudoja tekstus, sukurtus generatoriaus, paremto Markovo grandine. Yra, žinoma, teigiamų pavyzdžių Markovo grandinių naudojimas darbui su tekstu, jos naudojamos nustatant autorystę ir analizuojant tekstų autentiškumą.

Markovo grandinės ir loterijos

Kai kuriais atvejais tikimybinis modelis naudojamas numatant skaičius įvairiose loterijose. Matyt, nėra prasmės naudoti Markovo grandines skirtingų tiražų sekai modeliuoti. Tai, kas atsitiko su kamuoliukais burtų traukimo metu, jokiu būdu neturės įtakos kito lošimo rezultatams, nes po traukimo kamuoliukai surenkami, o kitame traukime jie dedami į loterijos dėklą. fiksuota tvarka. Tokiu atveju prarandamas ryšys su praeities apyvarta. Kitas dalykas yra kamuoliukų, iškritusių per vieną traukimą, seka. būsenos, atitinkančios tą patį stebimą įvykį. Todėl galime sudaryti tik perėjimo tikimybių tarp tokių būsenų grupių matricą. Šios tikimybės yra perėjimų tarp skirtingų tikimybių vidurkis atskiros valstybės, o tai, žinoma, sumažina Markovo grandinės modelio taikymo skaitinėse loterijose efektyvumą.
Panašus į šį atvejį, toks modelis neuroninis tinklas gali būti naudojamas orų prognozavimui, valiutų kotiravimui ir kartu su kitomis sistemomis, kuriose yra istoriniai duomenys ir naujai gauta informacija gali būti naudojama ateityje. Geras naudojimasšiuo atveju, kai žinomos tik sistemos apraiškos, bet ne vidinės (paslėptos) būsenos, gali būti taikomi paslėpti Markovo modeliai, kurie išsamiai aptariami Vikiknygose (paslėpti Markovo modeliai).

Literatūra

1. Romanovskis I.V.
2. Diskreti analizė: vadovėlis studentams, 3 leidimas. - Sankt Peterburgas: Nevskio tarmė; BHV Peterburgas, 2003 m. Taha, Hamdy A. Operacijų tyrimų įvadas, 6-asis leidimas.
3. - M.:
4. Leidykla

Williamsas, 2001 m.

1. Werneris M. Kodavimo pagrindai. Vadovėlis universitetams.
2. - M.: Technosfera, 2004 m.

Belyaev A., Gavrilov M., Masalskikh A., Medvinsky M. Markovo procesai, 2004 m. Vizualizatoriai Aleksejevas V. Markovas sprendimų priėmimo procesai, 2002 m. Beliajevo A. Markovo grandinės, 2002 m. Metodai
matematinius aprašymus Markovas atsitiktiniai procesai sistemoje su diskrečiomis būsenomis (DS) priklauso nuo to, kokiais laiko momentais (anksčiau žinomais ar atsitiktiniais) gali įvykti sistemos perėjimai iš būsenos į būseną. Jei sistemos perėjimas iš būsenos į būseną yra įmanomas iš anksto nustatytais laiko momentais, mes susiduriame su atsitiktinis Markovo procesas su diskrečiu laiku.
Jei perėjimas įmanomas atsitiktinis momentas S laiko, tada mes susiduriame su n atsitiktinis Markovo procesas su nuolatiniu laiku. S 1 , S 2 , …, Tebūnie fizinę sistemą t 1 , t 2 , …, , kuris gali būti teigia S S n . Perėjimai iš būsenos į būseną galimi tik tam tikrais laiko momentais tk
, vadinkime šias akimirkas laiko žingsniais. Mes apsvarstysime bendrą įmonę sistemoje S 1 → S 2 → S 3 → S 2 .
kaip sveikojo skaičiaus argumento 1, 2, ... funkcija, k (, kur argumentas yra žingsnio numeris. Pavyzdys: . Perėjimai iš būsenos į būseną galimi tik tam tikrais laiko momentais Sutarkime paskirti S i.
k . Perėjimai iš būsenos į būseną galimi tik tam tikrais laiko momentais) – įvykis, susidedantis iš to, kad po , kur argumentas yra žingsnio numeris.žingsnių sistema yra S būsenoje , kur argumentas yra žingsnio numeris. i Dėl bet kokių (, kur argumentas yra žingsnio numeris.įvykiai S 1 ( ), S 2 (),…, S n

) forma
pilna renginių grupė S 1 (0) , S ir yra
Ši seka vadinama Markovo grandinė , jei kiekvienam žingsniui perėjimo iš bet kurios būsenos tikimybė k bet kokiomis sąlygomis S j nepriklauso nuo to, kada ir kaip sistema pasiekė būseną k.
Leiskite bet kuriuo momentu po bet kurio . Perėjimai iš būsenos į būseną galimi tik tam tikrais laiko momentais– pakopos sistema S gali būti vienoje iš valstybių S 1 , S 2 , …, Tebūnie, t. y. gali įvykti vienas įvykis iš visos įvykių grupės: S 1 (, kur argumentas yra žingsnio numeris.žingsnių sistema yra S būsenoje , kur argumentas yra žingsnio numeris.) , …, Tebūnie (, kur argumentas yra žingsnio numeris.). Pažymime šių įvykių tikimybes:
P 1 (1) = P(S 1 (1)); P 2 (1) = P(S 2 (1)); …; Pn(1) = P(Tebūnie (, kur argumentas yra žingsnio numeris.));
P 1 (2) = P(S 1 (2)); P 2 (2) = P(S2 (2)); ...; Pn(2) = P(Tebūnie (2));
P 1 (. Perėjimai iš būsenos į būseną galimi tik tam tikrais laiko momentais) = P(S 1 (. Perėjimai iš būsenos į būseną galimi tik tam tikrais laiko momentais)); P 2 (. Perėjimai iš būsenos į būseną galimi tik tam tikrais laiko momentais) = P(S 2 (. Perėjimai iš būsenos į būseną galimi tik tam tikrais laiko momentais)); …; Pn(. Perėjimai iš būsenos į būseną galimi tik tam tikrais laiko momentais) = P(Tebūnie (. Perėjimai iš būsenos į būseną galimi tik tam tikrais laiko momentais)).
Nesunku pastebėti, kad kiekvieno žingsnio numerio sąlyga yra įvykdyta
P 1 (. Perėjimai iš būsenos į būseną galimi tik tam tikrais laiko momentais) + P 2 (. Perėjimai iš būsenos į būseną galimi tik tam tikrais laiko momentais) +…+ Pn(. Perėjimai iš būsenos į būseną galimi tik tam tikrais laiko momentais) = 1.
Pavadinkime šias tikimybes būsenos tikimybės Todėl užduotis skambės taip: suraskite bet kurios sistemos būsenų tikimybes . Perėjimai iš būsenos į būseną galimi tik tam tikrais laiko momentais.
Pavyzdys. Tegul yra kokia nors sistema, kuri gali būti bet kurioje iš šešių būsenų. tada joje vykstantys procesai gali būti pavaizduoti arba kaip sistemos būklės pokyčių grafikas (7.9 pav. A), arba sistemos būsenos grafiko pavidalu (7.9 pav., b).

A)

Ryžiai. 7.9
Taip pat sistemos procesai gali būti pavaizduoti kaip būsenų seka: S 1 , S 3 , S 2 , S 2 , S 3 , S 5 , S 6 , S 2 .
Būsenos tikimybė ( . Perėjimai iš būsenos į būseną galimi tik tam tikrais laiko momentais+ 1) žingsnis priklauso tik nuo būsenos k- m žingsnis.
Bet kokiam žingsniui . Perėjimai iš būsenos į būseną galimi tik tam tikrais laiko momentais yra tam tikrų tikimybių, kad sistema pereis iš bet kurios būsenos į bet kurią kitą būseną, pavadinkime šias tikimybes Markovo grandinės perėjimo tikimybės.
Kai kurios iš šių tikimybių bus 0, jei perėjimas iš vienos būsenos į kitą neįmanomas vienu žingsniu.
Markovo grandinė vadinama vienalytis, jei pereinamosios būsenos nepriklauso nuo žingsnio skaičiaus, kitu atveju jis vadinamas nevienalytis.
Tegul būna vienalytė Markovo grandinė ir tegul sistema S turi n galimos būsenos: S 1 , …, Tebūnie. Tegu kiekvienai būsenai žinoma perėjimo į kitą būseną vienu žingsniu tikimybė, t.y. P ij(nuo k V S j vienu žingsniu), tada perėjimo tikimybes galime užrašyti kaip matricą.

. (7.1)
Išilgai šios matricos įstrižainės yra tikimybės, kad sistema pereis iš būsenos k toje pačioje būsenoje k.
Naudojant anksčiau įvestus įvykius , perėjimo tikimybes galime parašyti kaip sąlygines tikimybes:
.
Akivaizdu, kad terminų suma kiekvienoje matricos eilutėje (1) yra lygus vienetui, kadangi įvykiai sudaryti visą nesuderinamų įvykių grupę.

Svarstant Markovo grandines, taip pat analizuojant Markovo atsitiktinį procesą, naudojami įvairūs būsenų grafikai (7.10 pav.).

Ryžiai. 7.10

Ši sistema gali būti bet kurioje iš šešių būsenų P ij yra sistemos perėjimo iš būsenos tikimybė k valstybėje S j. Šiai sistemai užrašome lygtis, kad sistema tuo metu buvo tam tikroje būsenoje ir išėjo iš jos t neišėjo:

IN bendras atvejis Markovo grandinė yra nehomogeniška, t.y. tikimybė P ij keičiasi nuo žingsnio iki žingsnio. Tarkime, kad kiekviename žingsnyje pateikiama perėjimo tikimybių matrica, tada tikimybė, kad sistema Sįjungta . Perėjimai iš būsenos į būseną galimi tik tam tikrais laiko momentais-tas žingsnis bus valstybėje k, galima rasti naudojant formulę

Žinant perėjimų tikimybių matricą ir pradinę sistemos būseną, galima rasti būsenų tikimybes po bet kurio . Perėjimai iš būsenos į būseną galimi tik tam tikrais laiko momentais-tas žingsnis. Tegul pradiniu laiko momentu sistema būna būsenoje S m. Tada t = 0
.
Raskime tikimybes po pirmo žingsnio. Iš valstybės S m sistema pereis į būsenas S 1 , S 2 ir tt su tikimybėmis pm 1 , pm 2 , …, Pmm, …, P mn. Tada po pirmo žingsnio tikimybės bus lygios

. (7.2)
Raskime būsenos tikimybes po antrojo žingsnio: . Šias tikimybes apskaičiuosime pagal formulę visa tikimybe su hipotezėmis:
.
Hipotezės bus šie teiginiai:

• po pirmo žingsnio sistema buvo S 1 -H 1 būsenoje;
• po antrojo žingsnio sistema buvo S 2 -H 2 būsenoje;
• po to n tajame etape sistema buvo S n -H n būsenoje.

Bet kurios būsenos tikimybė po antrojo žingsnio:

(7.3)
Formulė (7.3) apibendrina visas perėjimo tikimybes P ij, tačiau atsižvelgiama tik į nulinius vienetus. Bet kokios būklės tikimybė po . Perėjimai iš būsenos į būseną galimi tik tam tikrais laiko momentais- žingsnis:

(7.4)
Taigi, būsenos tikimybė po . Perėjimai iš būsenos į būseną galimi tik tam tikrais laiko momentaisžingsnis nustatomas pagal pasikartojimo formulę (7.4) per tikimybes ( k – 1) žingsnis.

6 užduotis. Pateikta Markovo grandinės perėjimo viename žingsnyje tikimybių matrica. Raskite tam tikros grandinės perėjimo matricą trimis žingsniais .
Sprendimas. Sistemos perėjimo matrica yra matrica, kurioje yra visos šios sistemos perėjimo tikimybės:

Kiekvienoje matricos eilutėje yra įvykių (perėjimo iš būsenos) tikimybės i valstybėje j), kurios sudaro visą grupę, todėl šių įvykių tikimybių suma lygi vienetui:

Pažymėkime p ij (n) tikimybę, kad dėl n žingsnių (testų) sistema pereis iš būsenos i į būseną j. Pavyzdžiui, p 25 (10) yra perėjimo iš antrosios būsenos į penktąją dešimties žingsnių tikimybė. Atkreipkite dėmesį, kad n=1 gauname perėjimo tikimybes p ij (1)=p ij .
Mums duota užduotis: žinant perėjimo tikimybes p ij, rasti sistemos perėjimo iš būsenos tikimybes p ij (n). i valstybėje j už nžingsniai. Norėdami tai padaryti, pristatome tarpinį (tarp i Ir j) būsena r. Kitaip tariant, manysime, kad nuo pradinės būsenos i už mžingsniais sistema pereis į tarpinę būseną r su tikimybe p ij (n-m), po kurios, likusiam n-m žingsnių iš tarpinės būsenos r pateks į galutinę būseną j su tikimybe p ij (n-m) . Naudodami bendrosios tikimybės formulę gauname:
.
Ši formulė vadinama Markovo lygybe. Naudodami šią formulę galite rasti visas p ij (n) tikimybes ir, atitinkamai, pačią matricą P n. Kadangi matricos skaičiavimas greičiau pasiekia tikslą, matricos ryšį, gautą iš gautos formulės, rašome bendra forma.
Apskaičiuokime Markovo grandinės perėjimo matricą trimis etapais, naudodami gautą formulę:

Atsakymas:.

Užduotis Nr.1. Markovo grandinės perėjimo tikimybės matrica yra tokia:
.
Pasiskirstymas tarp būsenų momentu t=0 nustatomas pagal vektorių:
π 0 =(0,5; 0,2; 0,3)
Rasti: a) pasiskirstymas pagal būseną momentais t=1,2,3,4.
c) stacionarus paskirstymas.

Markovo grandinė yra diskretiško laiko Markovo procesas, apibrėžtas išmatuojamoje erdvėje.

Įvadas

Markovo atsitiktiniai procesai pavadinti iškilaus rusų matematiko A. A. Markovo (1856–1922) vardu, kuris pirmasis pradėjo tirti atsitiktinių dydžių tikimybinį ryšį ir sukūrė teoriją, kurią galima pavadinti „tikimybių dinamika“.

IN tolesni pagrindaiši teorija buvo pradinis pagrindas bendroji teorija atsitiktiniai procesai, taip pat tokie svarbūs taikomieji mokslai, kaip difuzijos procesų teorija, patikimumo teorija, teorija eilėje ir tt Šiuo metu Markovo procesų teorija ir jos pritaikymai yra plačiai naudojami įvairiose srityse.

Dėl palyginamo matematinio aparato paprastumo ir aiškumo, didelio gautų sprendimų patikimumo ir tikslumo, ypatingas dėmesys Markovo procesai perkamos iš specialistų, dalyvaujančių operacijų tyrimuose ir optimalaus sprendimų priėmimo teorijoje.

Paprastas pavyzdys: monetos metimas

Prieš pateikdamas aprašymą bendra schema, pereikime prie paprastas pavyzdys. Tarkime, kad mes kalbame apie apie nuoseklų monetos metimą metimo žaidime; moneta metama sąlyginiais laiko momentais t = 0, 1, ... ir kiekviename žingsnyje žaidėjas gali laimėti ±1 su ta pačia tikimybe 1/2, taigi momentu t jo bendras laimėjimas yra atsitiktinis kintamasisξ(t) su galimas vertes j = 0, ±1, ...

Jei ξ(t) = k, kitame žingsnyje stiprinimas jau bus lygus ξ(t+1) = k ± 1, atsižvelgiant nurodytas vertes j = k ± 1 su lygia tikimybe 1/2.

Tradiciškai galime sakyti, kad čia su atitinkama tikimybe įvyksta perėjimas iš būsenos ξ(t) = k į būseną ξ(t+1) = k ± 1.

Formulės ir apibrėžimai

Apibendrindami šį pavyzdį, galime įsivaizduoti „sistemą“ su skaičiuojamu galimų „fazių“ būsenų skaičiumi, kuri per diskrečiąjį laiką t = 0, 1, ... atsitiktinai pereina iš būsenos į būseną.

Tegul ξ(t) yra jo padėtis momentu t dėl ​​atsitiktinių perėjimų grandinės

ξ(0) – ξ(1) – ... – ξ(t) – ... ... (1)

Formaliai pažymėkime viską galimos būsenos sveikieji skaičiai i = 0, ±1, ... Tarkime, kad žinomai būsenai ξ(t) = k, kitame žingsnyje sistema su sąlygine tikimybe pereina į būseną ξ(t+1) = j

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

nepriklausomai nuo jo elgesio praeityje, tiksliau, nepriklausomai nuo perėjimų grandinės (1) iki momento t:

P(ξ(t+1) = j|ξ(0) = i, ..., ξ(t) = k) = P(ξ(t+1) = j|ξ(t) = k) visiems t, k, j... (3) - Markovo nuosavybė.

Ši tikimybinė schema vadinama vienalytė Markovo grandinė su skaičiuojamu skaičiumi būsenų- jo homogeniškumas slypi tame, kad apibrėžti (2) perėjimo tikimybės p kj, ∑ j p kj = 1, k = 0, ±1, ..., nepriklauso nuo laiko, t.y. P(ξ(t+1) = j|ξ(t) = k) = P ij - perėjimo tikimybių matrica viename žingsnyje nepriklauso nuo n.

Aišku, kad P ij - kvadratinė matrica su neneigiamais elementais ir vienetų sumomis eilutėse.

Tokia matrica (baigtinė arba begalinė) vadinama stochastine matrica. Bet kuri stochastinė matrica gali būti perėjimo tikimybių matrica.

Praktiškai: įrangos pristatymas į rajonus

Tarkime, kad tam tikra įmonė tiekia įrangą Maskvoje: šiaurinis rajonas(žymimas A), pietinis (B) ir centrinis (C). Įmonėje dirba šias sritis aptarnaujanti kurjerių komanda. Akivaizdu, kad pristatyti kitą kurjeris vyksta į vietą, kuri šiuo metu yra arčiau jo. Statistiškai nustatyta:

1) po pristatymo į A, kitas pristatymas atliekamas 30 atvejų A, 30 atvejų - B ir 40 atvejų - C;

2) po pristatymo į B, kitas gimdymas atliekamas 40 atvejų A, 40 atvejų - B ir 20 atvejų - C;

3) po pristatymo į C, kitas gimdymas atliekamas 50 atvejų A, 30 atvejų - B ir 20 atvejų - C.

Taigi, kitą pristatymo sritį lemia tik ankstesnis pristatymas.

Perėjimo tikimybės matrica atrodys taip:

Pavyzdžiui, p 12 = 0,4 yra tikimybė, kad po pristatymo į B sritį kitas pristatymas bus atliktas A zonoje.

Tarkime, kad kiekvienas pristatymas ir perkėlimas į kitą sritį trunka 15 minučių. Tada, pagal statistiką, po 15 minučių 30% kurjerių, kurie buvo A, bus A, 30% bus B ir 40% bus C.

Kadangi kitą akimirką kiekvienas iš kurjerių tikrai bus viename iš rajonų, stulpelių suma lygi 1. O kadangi mes kalbame apie tikimybes, kiekvienas matricos elementas yra 0<р ij <1.

Svarbiausia aplinkybė, leidžianti interpretuoti šį modelį kaip Markovo grandinę, yra ta, kad priklauso kurjerio buvimo vieta laiko momentu t+1 tik iš vietos laiku t.

Dabar užduokime paprastą klausimą: jei kurjeris pradeda nuo C, kokia tikimybė, kad atlikęs du pristatymus jis atsidurs B, t.y. kaip pasiekti B 2 žingsniais? Taigi, yra keli keliai nuo C iki B dviem etapais:

1) pirmiausia iš C į C, o po to iš C į B;

2) C-->B ir B-->B;

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

Atsižvelgiant į daugybos taisyklę nepriklausomi renginiai, nustatome, kad norima tikimybė yra lygi:

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

Pakeičiančios skaitines reikšmes:

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

Gautas rezultatas rodo, kad jei kurjeris pradėjo dirbti nuo C, tai 33 atvejais iš 100 jis bus B po dviejų pristatymų.

Aišku, skaičiavimai yra paprasti, bet jei reikia nustatyti tikimybę po 5 ar 15 pristatymų, tai gali užtrukti gana daug laiko.

Parodykime paprastesnį būdą tokioms tikimybėms apskaičiuoti. Norint gauti perėjimo tikimybes iš įvairios sąlygos 2 žingsniais paverčiame matricą P kvadratu:

Tada elementas (2, 3) yra perėjimo iš C į B 2 žingsniais tikimybė, kuri buvo gauta aukščiau kitu būdu. Atkreipkite dėmesį, kad P2 matricos elementai taip pat svyruoja nuo 0 iki 1, o stulpelių suma yra 1.

Tai. jei jums reikia nustatyti perėjimo iš C į B tikimybę 3 žingsniais:

1 būdas. 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, kur p(CA) – tikimybė pereiti iš C į A 2 žingsniais (t. y. tai matricos P 2 elementas (1, 3).

2 būdas. Apskaičiuokite matricą P3:

Perėjimo į 7 laipsnį tikimybių matrica atrodys taip:

Nesunku pastebėti, kad kiekvienos eilutės elementai linkę į tam tikrus skaičius. Tai rodo, kad po pakankamai didelis kiekis pristatymas, nesvarbu, kuriame rajone kurjeris pradėjo dirbti. Tai. savaitės pabaigoje apie 38,9% bus A, 33,3% bus B ir 27,8% bus C.

Tokia konvergencija garantuotai įvyks, jei visi perėjimo tikimybių matricos elementai priklauso intervalui (0, 1).