Proceset shumëdimensionale Markov. Metodat e teorisë së proceseve Markov. Zinxhirë diskrete Markov. Shembull

Shumë operacione që duhet të analizohen kur zgjedh një zgjidhje optimale zhvillohen si procese të rastësishme në varësi të një numri faktorësh të rastësishëm.

Për një përshkrim matematikor të shumë operacioneve që zhvillohen në formën e një procesi të rastësishëm, mund të zbatohet me sukses aparati matematikor i zhvilluar në teorinë e probabilitetit për të ashtuquajturat procese të rastësishme Markov.

Le të shpjegojmë konceptin e një procesi të rastësishëm Markov.

Le të ketë një sistem S, gjendja e të cilit ndryshon me kalimin e kohës (sipas sistemit SÇdo gjë mund të kuptohet: ndërmarrje industriale, pajisje teknike, dyqan riparimi, etj.). Nëse gjendja e sistemit S ndryshon me kalimin e kohës në mënyrë të rastësishme, të paparashikueshme paraprakisht, ata thonë se në sistem S rrjedhjet proces i rastësishëm.

Shembuj të proceseve të rastësishme:

luhatjet e çmimeve në bursë;

shërbimi ndaj klientit në një sallon flokësh ose dyqan riparimi;

zbatimi i planit të furnizimit për një grup ndërmarrjesh etj.

Ecuria specifike e secilit prej këtyre proceseve varet nga një numër faktorësh të rastësishëm, të paparashikueshëm më parë, si p.sh.

ardhja e lajmeve të paparashikueshme për ndryshimet politike në bursë;

natyra e rastësishme e fluksit të aplikacioneve (kërkesave) që vijnë nga klientët;

ndërprerje të rastësishme në zbatimin e planit të furnizimit etj.

PËRKUFIZIM. Një proces i rastësishëm që ndodh në një sistem quhet Markoviane(ose proces pa pasoja), nëse ka vetinë e mëposhtme: për çdo moment të kohës t 0 probabiliteti i ndonjë gjendjeje të sistemit në të ardhmen (me t > t 0) varet vetëm nga gjendja e tij në të tashmen (me t = t 0) dhe nuk varet nga kur dhe si erdhi sistemi në këtë gjendje (d.m.th., si u zhvillua procesi në të kaluarën).

Me fjalë të tjera, në një proces të rastësishëm Markov, zhvillimi i tij në të ardhmen varet vetëm nga gjendja aktuale dhe nuk varet nga "parahistoria" e procesit.

Le të shohim një shembull. Lëreni sistemin S përfaqëson një bursë që ekziston prej disa kohësh. Ne jemi të interesuar se si do të funksionojë sistemi në të ardhmen. Është e qartë, të paktën në një përafrim të parë, se karakteristikat e performancës së ardhshme (probabilitetet e një rënie të çmimit të një aksioni të caktuar në një javë) varen nga gjendja e sistemit në këtë moment (një sërë faktorësh si p.sh. pasi këtu mund të ndërhyjnë vendimet e qeverisë ose rezultatet e zgjedhjeve) dhe nuk varen nga kur dhe si sistemi arriti gjendjen e tij aktuale (nuk varet nga natyra e lëvizjeve të çmimeve të këtyre aksioneve në të kaluarën).

Në praktikë, ne shpesh hasim procese të rastësishme që, në shkallë të ndryshme të përafrimit, mund të konsiderohen Markoviane.

Teoria e proceseve të rastësishme Markov ka një gamë të gjerë aplikimesh të ndryshme. Ne do të jemi të interesuar kryesisht në zbatimin e teorisë së proceseve të rastësishme Markov në ndërtim modele matematikore operacionet, rrjedha dhe rezultati i të cilave varen ndjeshëm nga faktorë të rastësishëm.

Proceset e rastësishme Markov ndahen në klasat varësisht se si dhe në cilat momente kohore sistemi S" mund të ndryshojë gjendjet e tij.

PËRKUFIZIM. Procesi i rastësishëm quhet proces me gjendje diskrete, nëse është e mundur gjendjet e sistemit s x, s 2, s v... mund të renditen (numërohen) njëri pas tjetrit, dhe vetë procesi është se herë pas here sistemi S kërcen befas (në çast) nga një gjendje në tjetrën.

Për shembull, zhvillimi i projektit S kryhet së bashku nga dy departamente, secili prej të cilave mund të bëjë një gabim. Gjendjet e mëposhtme të sistemit janë të mundshme:

5, - të dy departamentet punojnë normalisht;

s 2 - departamenti i parë gaboi, i dyti punon mirë;

s 3 - departamenti i dytë bëri një gabim, i pari funksionon mirë;

s 4 - të dy departamentet bënë një gabim.

Procesi që ndodh në sistem është se ai në mënyrë të rastësishme në disa momente të kohës lëviz ("kërcen") nga një gjendje në tjetrën. Sistemi ka gjithsej katër gjendje të mundshme. Para nesh është një proces me gjendje diskrete.

Përveç proceseve me gjendje diskrete, ekzistojnë procese të rastësishme me gjendje të vazhdueshme: këto procese karakterizohen nga një kalim gradual dhe i qetë nga një gjendje në tjetrën. Për shembull, procesi i ndryshimit të tensionit në një rrjet ndriçimi është një proces i rastësishëm me gjendje të vazhdueshme.

Ne do të shqyrtojmë vetëm procese të rastësishme me gjendje diskrete.

Kur analizoni procese të rastësishme me gjendje diskrete, është shumë e përshtatshme të përdorni një skemë gjeometrike - të ashtuquajturin grafik të gjendjes. Grafiku i gjendjes përshkruan gjeometrikisht gjendjet e mundshme të sistemit dhe kalimet e mundshme të tij nga një gjendje në tjetrën.

Le të ketë një sistem S me gjendje diskrete:

Çdo gjendje do të përfaqësohet nga një drejtkëndësh, dhe kalimet e mundshme ("kërcimet") nga një gjendje në tjetrën do të përfaqësohen nga shigjetat që lidhin këta drejtkëndësha. Një shembull i grafikut të gjendjes është paraqitur në Fig. 4.1.

Vini re se shigjetat shënojnë vetëm kalimet e drejtpërdrejta nga një gjendje në tjetrën; nëse sistemi mund të kalojë nga gjendja s 2 në 5 3 vetëm përmes s y atëherë shigjetat shënojnë vetëm kalimet s 2-> dhe l, 1 -> 5 3, por jo s 2 -» s y Le të shohim disa shembuj:

1. Sistemi S- një kompani që mund të jetë në një nga pesë shtetet e mundshme: s ]- punon me fitim;

s 2- humbi perspektivat e zhvillimit dhe pushoi së gjeneruari fitim;

5 3 - u bë objekt për një marrje të mundshme;

s 4- është nën kontroll të jashtëm;

s 5- prona e shoqërisë së likuiduar shitet në ankand.

Grafiku i gjendjes së kompanisë është paraqitur në Fig. 4.2.

Oriz. 4.2

2. Sistemi S- një bankë me dy degë. Gjendjet e mëposhtme të sistemit janë të mundshme:
5, - të dyja degët operojnë me fitim;

s 2 - dega e parë funksionon pa fitim, e dyta funksionon me fitim;

5 3 - dega e dytë funksionon pa fitim, e para funksionon me fitim;

s 4 - të dyja degët funksionojnë pa fitim.

Supozohet se nuk ka përmirësim të gjendjes.

Grafiku i gjendjes është paraqitur në Fig. 4.3. Vini re se grafiku nuk tregon një kalim të mundshëm nga gjendja s ] direkt tek s4, të cilat do të realizohen nëse banka menjëherë do të funksionojë me humbje. Mundësia e një ngjarje të tillë mund të neglizhohet, siç e vërteton praktika.

Oriz. 4.3

3. Sistemi S- një shoqëri investimi e përbërë nga dy tregtarë (departamente): I dhe II; secila prej tyre mund të fillojë në një moment të caktuar të funksionojë me humbje. Nëse kjo ndodh, menaxhmenti i kompanisë merr menjëherë masa për të rivendosur funksionimin fitimprurës të departamentit.

Sistemi i mundshëm thotë: s- aktivitetet e të dy departamenteve janë fitimprurëse; s 2- departamenti i parë po restaurohet, i dyti funksionon me fitim;

s 3- departamenti i parë funksionon me fitim, i dyti po restaurohet;

s 4- të dy departamentet janë duke u restauruar.

Grafiku i gjendjes së sistemit është paraqitur në Fig. 4.4.

4. Në kushtet e shembullit të mëparshëm, veprimtaritë e çdo tregtari, përpara se të fillojë të rivendosë punën fitimprurëse të departamentit, i nënshtrohen studimit nga drejtuesit e shoqërisë për të marrë masa për përmirësimin e saj.

Për lehtësi, ne do t'i numërojmë gjendjet e sistemit jo me një, por me dy indekse; e para do të nënkuptojë statusin e tregtarit të parë (1 - punon me fitim, 2 - aktivitetet e tij po studiohen nga menaxhmenti, 3 - rikthen aktivitetin fitimprurës të departamentit); e dyta - të njëjtat gjendje për tregtarin e dytë. Për shembull, s 23 do të thotë: aktivitetet e tregtarit të parë po studiohen, i dyti po rivendos punën fitimprurëse.

Gjendjet e mundshme të sistemit S:

s u- aktivitetet e të dy tregtarëve sjellin fitim;

s l2- tregtari i parë punon me fitim, aktivitetet e të dytit studiohen nga menaxhmenti i kompanisë;

5 13 - tregtari i parë punon me fitim, i dyti rikthen veprimtarinë fitimprurëse të departamentit;

s 2l- veprimtaritë e tregtarit të parë studiohen nga menaxhmenti, i dyti punon me fitim;

s 22 - aktivitetet e të dy tregtarëve studiohen nga menaxhmenti;

5 23 - studiohet puna e tregtarit të parë, tregtari i dytë rikthen aktivitetet fitimprurëse të departamentit;
5 31 - tregtari i parë rikthen aktivitetet fitimprurëse të departamentit, i dyti punon me fitim;
5 32 - aktiviteti fitimprurës i departamentit rivendoset nga tregtari i parë, studiohet puna e tregtarit të dytë;
5 33 - të dy tregtarët rivendosin punën fitimprurëse të departamentit të tyre.

Janë nëntë shtete gjithsej. Grafiku i gjendjes është paraqitur në Fig. 4.5.

Nga përkufizimi i një procesi Markov të dhënë në seksionin 5.1.6, si dhe drejtpërdrejt nga formula (5.6), vijon

Dendësia e kushtëzuar

quhet dendësia e probabilitetit të kalimit të një procesi Markov nga gjendja y në kohën s në gjendjen x në kohën t.

Duke përdorur formulën (2.57), ne përcaktojmë densitetin shumëdimensional të probabilitetit (të çdo rendi të kufizuar) të procesit Markov

Formula (5.60) nënkupton faktorizimin e densitetit të probabilitetit shumëdimensional të një procesi Markov - përfaqësimi i tij si produkt i densitetit njëdimensional dhe densiteteve të probabilitetit të tranzicionit. Kushti i faktorizimit (5.60) i densitetit shumëdimensional - tipar karakteristik Proceset Markov (krahasoni me një kusht të ngjashëm faktorizimi më të thjeshtë (5.4) për proceset me vlera të pavarura).

Dendësia njëdimensionale dhe dendësia e probabilitetit të tranzicionit janë të lidhura nga relacioni

Dendësia e probabilitetit të tranzicionit të një procesi Markov nuk është një funksion arbitrar i shpërndarjes së kushtëzuar që plotëson vetëm kushtet e zakonshme të jonegativitetit dhe normalizimit, d.m.th. Ai gjithashtu duhet të plotësojë disa ekuacione integrale. Në të vërtetë, nga (5.60) në kemi

Duke integruar të dyja anët e kësaj barazie mbi , ne marrim

dhe që nga ajo kohë

Ekuacioni integral (5.62) quhet ekuacioni Kolmogorov-Chapman.

5.4.2. Proceset homogjene Markov.

Nëse shpërndarja e probabilitetit të një procesi Markov është e pandryshueshme në një zhvendosje kohore, atëherë ai quhet homogjen (stacionar). Në këtë rast, densiteti i probabilitetit të tranzicionit (5.59) varet vetëm nga një parametër kohor.

Kushti i faktorizimit për densitetin shumëdimensional të një procesi homogjen Markov është shkruar në formën) [shih (5.60)]

Vini re se klasa e proceseve homogjene Markov përkon me klasën e konsideruar të proceseve homogjene të rastit me rritje të pavarura.

5.4.3. Procesi Markov i lidhur shumëfishohet.

Ne e quajmë një proces Markov - të lidhur nëse densiteti i probabilitetit të tranzicionit varet nga k vlerat e mëparshme të procesit [shih (5.58)]:

Kushti i faktorizimit për densitetin shumëdimensional të një procesi të lidhur Markov shkruhet si

dhe ekuacioni Kolmogorov-Chapman

5.4.4. Procesi i vektorit Markov.

Një grup procesesh të rastësishme formon një proces Markov vektor nëse për një përshkrim të plotë probabilistik të këtij grupi është e nevojshme dhe e mjaftueshme të dihet shpërndarjen e përbashkët

dhe shpërndarja e kushtëzuar

ose dendësia përkatëse e probabilitetit të tranzicionit

Duke zëvendësuar - (5.62) madhësitë skalare me ato vektoriale, marrim relacionet përkatëse për procesin vektor Markov.

Secili nga proceset e rastësishme që i përkasin grupit që formon procesin vektorial Markov quhet një komponent i procesit të Markovit vektor, i cili, megjithatë, nuk është një proces skalar Markov, në përgjithësi.

Le të vëmë re lidhjen midis proceseve të Markovit me vektor dhe të shumëfishuar: një sekuencë Markov e lidhur mund të interpretohet gjithashtu si një sekuencë e Markovit (madhësia k)

5.4.5. Procesi Gaussian Markov.

Një proces Markov quhet Gaussian nëse shpërndarja e tij i bindet ligjit normal të shpërndarjes së probabilitetit (shih seksionin 5.2.1). Si për çdo proces Gaussian, funksioni korrelativ i procesit Gaussian Markov ofron përshkrimin e tij të plotë probabilistik. Mund të vërtetohet se një proces i rastësishëm është një proces Gaussian Markov i përqendruar nëse dhe vetëm nëse në funksionin e tij korrelacion plotëson ekuacionin

Për një proces homogjen Gaussian Markov, kushti (5.71) shkruhet duke përdorur një funksion korrelacioni të normalizuar, i cili natyrisht varet nga një argument

Me përjashtim të zgjidhjes së parëndësishme, ekuacioni (5.72) ka një zgjidhje unike

Kështu, një proces Gaussian me qendër stacionare me dispersion është Markovian nëse dhe vetëm nëse funksioni i tij i korrelacionit (Fig. 5.4)

ose dendësia spektrale përkatëse e fuqisë së procesit (Fig. 5.5)

Nga (5.74) dhe, në përputhje me rrethanat, nga (5.75) rrjedh se një proces homogjen Gaussian Markov është i vazhdueshëm në katrorin mesatar, por problemi 5.6 gjithashtu nuk është i diferencueshëm në katrorin mesatar.

Oriz. 5.4. Funksioni i korrelacionit të normalizuar të një procesi homogjen Gaussian Markov

Oriz. 5.5. Dendësia spektrale e fuqisë së një procesi homogjen Gaussian Markov

5.4.6. Sekuenca Gaussian Markov.

Le të jetë një sekuencë e variablave të rastësishme Gausiane të përqendruara me varianca dhe koeficientë korrelacioni Në mënyrë që kjo sekuencë të jetë Markoviane, është e nevojshme dhe e mjaftueshme

Për një sekuencë të palëvizshme Gaussian Markov, nga (5.76) vijon

ku është koeficienti i korrelacionit midis dy anëtarëve ngjitur të sekuencës.

Çdo nënsekuencë e një sekuence Gaussian Markov është gjithashtu Gaussian, Markovian.

5.4.7. Ekuacioni diferencial për densitetin e probabilitetit të kalimit të një procesi të vazhdueshëm Markov.

Zgjidhja e ekuacionit integral Kolmogorov-Chapman (5.62) është një detyrë e vështirë. Përcaktimi i densitetit të probabilitetit të kalimit të një procesi Markov mund të reduktohet në zgjidhjen e një ekuacioni diferencial nëse kufizohemi në procese të vazhdueshme. Një proces Markov quhet i vazhdueshëm nëse lëvizjet e dukshme janë të mundshme vetëm me një probabilitet të ulët për periudha të shkurtra kohore. Më saktësisht, kjo do të thotë se çfarëdo

Realizimet e një procesi Markov të vazhdueshëm me probabilitet një janë të vazhdueshme.

Nga ekuacioni (5.62), duke supozuar dhe ndryshuar emërtimet e variablave, marrim

Për më tepër, është e qartë se

Nga dy barazitë e fundit rrjedh

Le të supozojmë se densiteti i probabilitetit të tranzicionit mund të zgjerohet në një seri Taylor

Duke zëvendësuar (5.80) në (5.79), duke i ndarë të dyja anët dhe duke kaluar në kufirin në fitojmë

5.4.8. Proceset e difuzionit.

Nëse funksionet janë të fundme përveç zeros dhe për , atëherë procesi i vazhdueshëm Markov quhet difuzion. Nga (5.81) rrjedh se densiteti i probabilitetit të tranzicionit të procesit të difuzionit plotëson ekuacionin diferencial të pjesshëm

quhet ekuacioni i anasjelltë i Kolmogorovit.

Në mënyrë të ngjashme, mund të vërtetohet se densiteti i probabilitetit të tranzicionit të procesit të difuzionit kënaq ekuacioni i drejtpërdrejtë Kolmogorov:

koeficienti drift, dhe

Koeficienti i difuzionit.

Ekuacioni i drejtpërdrejtë i Kolmogorovit (5.84) njihet edhe si ekuacioni Fokker-Plavka. Ekuacionet (5.83) dhe (5.84) i përkasin klasës së ekuacioneve diferenciale parciale parabolike. Në (5.83) variablat janë dhe variablat y dhe T përfshihen vetëm në kusht. Në (5.84) variablat janë y dhe dhe t hyjnë vetëm përmes kushtit fillestar. Metodat për zgjidhjen e ekuacioneve të Kolmogorov janë konsideruar, për shembull,.

5.4.9. Proceset e difuzionit të palëvizshëm.

Për proceset e difuzionit të palëvizshëm, koeficientët e zhvendosjes (5.85) dhe difuzioni (5.86) nuk varen nga parametri i kohës, dhe densiteti i probabilitetit të tranzicionit varet vetëm nga diferenca. Pastaj nga (5.84) marrim

me gjendje fillestare

Nëse ekziston një kufi në densitetin e probabilitetit të tranzicionit që nuk varet nga gjendja fillestare, atëherë ai quhet funksioni kufizues i shpërndarjes së një procesi të palëvizshëm difuz.

Nga (5.88) rrjedh se . Prandaj, funksioni i shpërndarjes kufitare mund të gjendet nga ekuacioni diferencial i zakonshëm i rendit të parë

zgjidhja e të cilit ka formën

konstantet përcaktohen nga gjendja e normalizimit dhe gjendja kufitare

5.4.10. Procesi i difuzionit Gaussian.

Konsideroni një proces të rastësishëm të palëvizshëm Gaussian me mesatare zero, variancë dhe funksion korrelacioni të normalizuar. Dendësia e shpërndarjes së kushtëzuar të këtij procesi të rastësishëm [shih (2.74)]

Le të gjejmë për densitetin e probabilitetit të kushtëzuar në shqyrtim funksionet e përcaktuara sipas (5.82):

(5.92)

ku është vlera e derivatit kur i afrohet zeros nga e djathta. Nëse e vazhdueshme në zero, atëherë supozojmë se ajo pëson një ndërprerje në . Pastaj

Në këtë seksion, ne përdorim metodën e procesit Markov për të gjetur demodulatorin optimal. Prezantimi ynë është sipërfaqësor, ndaj për një shqyrtim më të detajuar, lexuesit e interesuar duhet t'i referohen burime shtesë(në veçanti, ). Dhe këtë herë do të supozojmë se mesazhi është një proces i rastësishëm Gaussian me një paraqitje të fundme në variablat e gjendjes, d.m.th.

ku është një proces i rastësishëm Gaussian i bardhë me funksion kovariance

Edhe pse ne nuk e përdorim këtë fakt gjatë prezantimit tonë, duhet theksuar se këtë paragraf procedura mund të kryhet edhe kur ekuacioni i gjendjes dhe ekuacioni i vëzhgimit janë jolineare dhe kanë formën

Vini re se nën disa kufizime të vendosura është një proces Markov vektor, i cili nuk është domosdoshmërisht Gaussian. Asnjë nga metodat e diskutuara më parë nuk lejon zgjidhjen e problemeve me mesazhet e kësaj klase. Shumica e rezultateve që do të merren në këtë seksion mund të merren edhe për procesin më të përgjithshëm të përshkruar nga ekuacionet (78) dhe (79).

Le t'i kthehemi modelit në formën e një procesi të rastësishëm të përshkruar nga relacionet Për hir të thjeshtësisë së shënimit, do të shqyrtojmë një mesazh që është një proces skalar Gaussian Markov dhe me anë të të cilit luhatja e transmetuar modulohet nga njëfarë inercie. - lloj modulimi pa pagesë. Dridhja e pranuar shkruhet në formë

Procesi i mesazhit plotëson ekuacionin diferencial të rendit të parë

Kështu, për çdo vlerë të fundme, mesazhi është një proces i palëvizshëm dhe ka një spektër Butterworth të rendit të parë. Më tej, për shkak të faktit se procesi Markov është i rendit të parë, densiteti i probabilitetit të tij në mungesë të ndonjë vëzhgimi plotëson ekuacionin Fokker-Planck [shih (3.79)]

Megjithatë, meqenëse është vërejtur gjatë intervalit kohor, densiteti i probabilitetit me interes për ne nuk është një densitet i pakushtëzuar, por një densitet për shkak të lëkundjes së vëzhguar

Vini re se (86) është dendësia e probabilitetit të një ndryshoreje të rastësishme (një vlerë që tregon vlerën e a në momentin kohor për shkak të lëkundjes së vëzhguar dhe është qartësisht një karakteristikë e caktuar. Mund të tregohet se kjo densitet probabiliteti e plotëson ekuacionin

ku pritshmëritë matematikore merren nga dendësia Nëse prezantojmë formalisht derivatin

atëherë (87) mund të shkruhet zyrtarisht si një ekuacion diferencial

Marrëdhënia midis densitetit të pasmë dhe vlerësimit të gabimit mesatar katror minimal është i njohur mirë. Vlerësimi për gabimin mesatar katror minimal është mesatarja e kushtëzuar e densitetit të pasmë (shih faqen 73 të vëllimit të parë), d.m.th.

Duke shumëzuar të dyja anët e (89) me A, duke integruar mbi dhe duke marrë parasysh kushtet përkatëse në skajet e intervalit, marrim (shih problemin 7.2.2)

Vini re se (91) ende përmban pritje matematikore Siç pritej, ky ekuacion nuk mund të zgjidhet për rastin e përgjithshëm të modulimit. Në rast metoda lineare modulimi është e lehtë të tregohet (për shembull, 18] ose problemi 7.2.1) që reduktohet në Për shumë probleme të modulimit jolinear, suksesi mund të arrihet duke u zgjeruar në një seri termash të ndryshëm të ekuacionit (91). Pastaj, nëse supozojmë se gabimi i vlerësimit është i vogël dhe vendosim disa kushte në momentet e rendit më të lartë, mund të neglizhojmë termat e rendit të dytë dhe më të lartë dhe të marrim ekuacionin e përafërt të mëposhtëm (një derivim i detajuar është dhënë në kapitullin 4 të librit ):

ku tregon një vlerësim të përafërt bazuar në gabimin mesatar katror minimal. Funksioni është një kusht i përafërt [sipas gabimit mesatar katror, i cili plotëson ekuacionin diferencial

me gjendje kufitare

Vini re se ekuacioni i vlerësimit (92) dhe ekuacioni i dispersionit (93) janë të lidhur. Vini re më tej se rrënja e kushtëzuar e gabimit mesatar katror [d.m.th. e gabimi, me kusht që përafrimet që duhen bërë për të marrë janë të vlefshme kur gabimi është i vogël.

Shohim që ekuacioni (92) mund të zbatohet në formë bllok diagrami, treguar në Fig. 7.3. Ky zbatim është shumë i ngjashëm me strukturën e vlerësuesit maksimal të probabilitetit të pasëm të sintetizuar në Kap. 2, me ndryshimin e vetëm që tani filtri në lak zbatohet automatikisht. Disavantazhi i këtij zbatimi është prania e komunikimit midis sytheve.

Në rastin e modulimit këndor, mund të tregohet se ky bashkim zakonisht mund të neglizhohet. Për shembull, me modulimin e fazës

Supozohet se është shumë më e madhe se frekuenca më e lartë në spektrin e mesazheve dhe se sistemi është në një gjendje statistikisht stacionare. Në këtë rast tregohet se

plotëson ekuacionin e dispersionit gjatë zëvendësimit

Për një proces Markov të rendit të parë, ky ekuacion ka formën

Diagrami bllok i marrësit është paraqitur në Fig. 7.4. Kjo strukturë përkon saktësisht me pjesën e zbatuar të marrësit të përafërt të probabilitetit maksimal të pasëm, i cili u sintetizua më herët (shih problemin në (68)) tani mund të interpretohet si një gabim i përafërt mesatar katror i kushtëzuar.

Oriz. 7.4. Marrësi optimal: modulimi fazor, komunikimi me spektrin e rendit të parë Butterworth.

Për shkak se shumë nga detajet e prodhimit janë lënë jashtë, është e rëndësishme të vihen re kufizimet e rezultatit. Ekuacioni diferencial(91), e cila përcakton mesataren e kushtëzuar, është e saktë. Megjithatë, përafrimet që lidhen me marrjen e (92)-(93) korrespondojnë me supozimin linearizimi. Prandaj, rezultati ynë është një vlerësim i përafërt i bazuar në gabimin mesatar katror minimal që korrespondon me termin e parë të zgjerimit të serisë së vlerësimit të saktë. Për të marrë një përafrim më të mirë, mund të mbani numër më i madh termat e zgjerimit (shih, për shembull,). Vështirësia me këtë procedurë është se përafrimi me dy terma është tashmë aq kompleks sa që ndoshta nuk paraqet ndonjë interes praktik.

Le të ndodhë një s.p. me gjendje diskrete
dhe koha diskrete, d.m.th. kalimi i një sistemi nga një gjendje në tjetrën ndodh vetëm në momente të caktuara kohore
. Këto momente quhen hapat procesi (zakonisht ndryshimi midis momenteve të vëzhgimit ngjitur
e barabartë me një numër konstant - gjatësia e hapit të marrë si njësi e kohës);
fillimi i procesit.

Kjo s.p. mund të konsiderohet si një sekuencë (zinxhir) ngjarjesh
.

gjendja fillestare e sistemit, d.m.th. para hapit të parë;
gjendja e sistemit pas hapit të parë,
gjendja e sistemit pas hapit të dytë, etj.), d.m.th. ngjarje si
Ku.

Quhet një proces i rastësishëm Markov me gjendje diskrete dhe kohë diskrete zinxhir Markov(zinxhiri Markov).

Vini re se zinxhir Markov, në të cilën probabilitetet e kushtëzuara të gjendjeve në të ardhmen varen vetëm nga gjendja në fazën e fundit (dhe nuk varen nga ato të mëparshmet) quhet zinxhir i thjeshtë Markov. (A.A. Markov 1856-1922 - Matematikan rus).

Një shembull i një sistemi të tillë mund të shërbejë si një pajisje teknike, gjendjet e mundshme të së cilës janë si më poshtë:

punë e mirë;

inspektimi dhe mirëmbajtja parandaluese;

punë rinovimi;

fshirje për shkak të papërdorshmërisë;

Grafiku i gjendjes së punës është paraqitur në figurë

Oriz. 1.11.(A.A. Belov, etj.)

Nga analiza e grafikut del qartë se nga gjendja e funksionimit normal të kulmit sistemi mund të hyjë në një gjendje të mirëmbajtjes parandaluese , dhe pastaj kthehuni në . Ose lëvizni nga ne gjendje riparimi , pas së cilës ose kthehet në , ose shkoni në gjendje fshirjeje. Shtetit është i kufizuar, pasi kalimi prej tij është i pamundur. Kalimi nga përsëri brenda do të thotë një vonesë në këtë gjendje.

Në praktikë, ne shpesh hasim sisteme, gjendjet e të cilave formojnë një zinxhir në të cilin secili shtet (përveç ekstremit Dhe ) lidhet me një vijë të drejtë dhe reagimet me dy fqinje,
dhe gjendjet ekstreme - me një fqinj (shih figurën)

Fig.1.12(Belov...)

Një shembull i një sistemi të tillë është një pajisje teknike e përbërë nga njësi të ngjashme. Çdo gjendje e sistemit karakterizohet nga numri i defekteve nyjet në momentin e verifikimit.

Objektivi kryesor i studimit është gjetja e probabiliteteve të gjendjes në çdo
m hap. Ne do të llogarisim probabilitetet e gjendjeve të një sistemi diskret

Këtu do të shqyrtojmë vetëm zinxhirët e thjeshtë Markov. Më tej, ne gjithashtu do të shqyrtojmë shkurtimisht konceptet e proceseve të vazhdueshme Markov.

Me ndryshime kohore diskrete në gjendjet e sistemit, thirret çdo kalim nga një gjendje në tjetrën hap.

Nga përkufizimi i një zinxhiri Markov rezulton se për të probabiliteti i tranzicionit të sistemit në një gjendje të
m hap varet vetëm nga shteti sistemi ishte në atë të mëparshëm
hap.

Ku
probabiliteti i pakushtëzuar që
Në hapin e parë, sistemi do të jetë në gjendje . Për të gjetur këto probabilitete, është e nevojshme të dihet shpërndarjen fillestare të probabilitetit, d.m.th. probabilitete shtetërore
në një moment në kohë
(fillimi i procesit) dhe i ashtuquajturi probabilitetet e tranzicionit
Zinxhiri Markov në
m hap.

Probabiliteti i tranzicionit
quhet probabiliteti i kalimit të kushtëzuar të sistemit në

hap m, në gjendje
m hap ajo ishte në gjendje , d.m.th.

(43),

ku indeksi i parë tregon numrin e gjendjes së mëparshme, dhe indeksi i dytë tregon numrin e gjendjes pasuese të sistemit.

Zinxhiri Markov quhet homogjene, nëse vlera
ato. probabilitete të kushtëzuara
nuk varen nga numri i testit, përndryshe quhet heterogjen.

Më tej, ne do të shqyrtojmë vetëm zinxhirët homogjenë që mund të specifikohen duke përdorur një vektor - probabiliteti i gjendjeve në një kohë
dhe matricat ( quhet matrica e tranzicionit)

(44)
.

Elementet e matricës
kanë vetitë themelore të matricave të zakonshme katrore dhe veçmas vetitë e mëposhtme:

A)
, b)
për çdo fiks
, d.m.th. shuma e elementeve të çdo rreshti matricat e tranzicionit e barabartë me një (si probabiliteti i ngjarjeve të tranzicionit nga një gjendje në çdo shtet tjetër të mundshëm - formimi i një grupi të plotë ngjarjesh).

Probabiliteti i gjendjes së sistemit në hapin tjetër përcaktohet nga formula e përsëritur:

Në kushte të caktuara (ergodiciteti, homogjeniteti, mungesa e cikleve) vendoset zinxhiri Markov mënyrë stacionare, në të cilën probabilitetet e gjendjeve të sistemit nuk varen nga numri i hapit. Probabilitete të tilla quhen ekstreme(ose përfundimtare) probabilitetet e zinxhirit Markov:

Ka një pohim.

Teorema 17.1.Për matricat kalimi i probabiliteteve përtej hapat
formula është e vlefshme

(45)
,

Dëshmi. Sipas rregullit të shumëzimit të dy matricave katrore
të rendit të th që kemi

Për më tepër, nga përkufizimi i matricës së tranzicionit dihet se
në çdo
.

Le të përmbledhim të dyja anët e barazisë
mbi të gjitha
, dhe duke zëvendësuar rendin e përmbledhjes pasi kemi zbatuar vetinë a) dy herë, marrim atë
matrica e tranzicionit në dy hapa. Në mënyrë të ngjashme, duke arsyetuar vazhdimisht hap pas hapi, ne marrim deklaratën tonë në rastin e përgjithshëm.

Shembulli 3. Matrica e tranzicionit e specifikuar

Gjeni matricat e probabilitetit të tranzicionit
.

Bazuar në rregullin për shumëzimin e dy matricave, marrim

Ushtrimi. Kontrolloni nëse barazia është e vërtetë

Duhet theksuar se zinxhiri i fundëm diskret Markov përfaqëson një përgjithësim të mëtejshëm të skemës së Bernulit, për më tepër, për rastin e testeve të varura; testet e pavarura janë një rast i veçantë i një zinxhiri Markov. Këtu nën "ngjarja"

i referohet gjendjes së sistemit, dhe "testi" i referohet një ndryshimi në gjendjen e sistemit.

nese " testet“(eksperimentet) janë të pavarura, atëherë ndodhja e një ngjarjeje të caktuar në asnjë eksperiment nuk varet nga rezultatet e testeve të kryera më parë.

Detyrat. a) Janë dhënë matricat e tranzicionit

1.
;

2.
;

3.
.

Gjeni matricën në secilin rast
.

Përgjigjet: a) 1.
;

2.
;

c) Janë dhënë matricat e tranzicionit

;
.

Gjeni
.

Përgjigjet: c) 1.
;2.
;

3.
.

Koment. Në përgjithësi, diskrete zinxhir Markov
është një proces i rastësishëm Markov, hapësira e gjendjes së të cilit është e fundme ose e numërueshme, dhe bashkësia e indekseve
- bashkësia e të gjithë numrave të plotë jonegativë ose e ndonjë nëngrupi të saj (të fundme ose të numërueshme). Mund të flasim për si për rezultatin
th testet.

Shpesh është i përshtatshëm për të identifikuar hapësirën e gjendjes së një procesi me grupin e numrave të plotë jo negativë
dhe në këto raste thonë se është në gjendje , Nëse
.

Probabiliteti për të goditur një ndryshore të rastësishme
në një gjendje (i quajtur probabiliteti i tranzicionit me një hap), siç u përmend më lart, shënohet
, d.m.th.

Ky shënim thekson se në rastin e përgjithshëm, probabilitetet e tranzicionit varen jo vetëm nga gjendja fillestare dhe përfundimtare, por edhe nga momenti i kalimit.

Në rastet kur probabilitetet e tranzicionit me një hap nuk varen nga ndryshorja e kohës (d.m.th., nga vlera , pastaj thonë se procesi Markov ka probabilitetet e tranzicionit të palëvizshëm. Pra, për qëllime të mëtejshme, vërejmë se ekziston një barazi që nuk varet nga , Dhe tregon probabilitetin e kalimit në një gjykim nga shteti në një gjendje .

Zakonisht probabilitete e kombinuar në një matricë katrore (të fundme ose të numërueshme) në varësi të procesit në shqyrtim:

dhe quhet matricë Markov, ose matrica e probabilitetit të tranzicionit Zinxhiri Markov.

Në matricë
rreshti i paraqet shpërndarjen e probabilitetit të r.v.
me kusht që
. Nëse numri i gjendjeve është i kufizuar, atëherë - përfundimtar matricë katrore, rendi i të cilit (numri i rreshtave) është i barabartë me numrin e gjendjeve.

Natyrisht, probabilitetet plotësoni dy kushtet e mëposhtme:

A)
,

b)
për çdo fiks

Kushti b) pasqyron faktin që çdo provë shkakton njëfarë kalimi nga një gjendje në një gjendje tjetër. Për lehtësi, ne zakonisht flasim gjithashtu tranzicionit dhe në rastin kur gjendja mbetet e pandryshuar. Ka një pohim.

Teorema 17.2.Procesi është plotësisht i përcaktuar nëse jepen probabilitetet(46), d.m.th.

dhe shpërndarja e probabilitetit të një ndryshoreje të rastësishme .

Dëshmi. Le ta tregojmë atë për çdo të fundme si llogariten probabilitetet

meqenëse, sipas formulës së probabilitetit total, çdo probabilitet tjetër që lidhet me variabla të rastit mund të merret duke mbledhur termat (anëtarët) të formularit (47).

Nga përkufizimi i probabilitetit të kushtëzuar kemi

Por me përkufizimin e një procesi Markov ne marrim

Duke vendosur barazinë (49) në (48) marrim

Duke vazhduar këtë proces në mënyrë sekuenciale, marrim:

Procesi është plotësisht i përcaktuar. Çfarë duhej vërtetuar.

Proceset e rastësishme Markov janë emëruar pas matematikanit të shquar rus A.A. Markov (1856-1922), i cili fillimisht filloi studimin e marrëdhënies probabilistike të ndryshoreve të rastit dhe krijoi një teori që mund të quhet "dinamika e probabilitetit". Më pas, bazat e kësaj teorie u bënë pikënisja teori e përgjithshme proceset e rastësishme, si dhe shkenca të tilla të rëndësishme të aplikuara si teoria e proceseve të difuzionit, teoria e besueshmërisë, teoria në radhë etj. Aktualisht, teoria e proceseve Markov dhe aplikimet e saj janë përdorur gjerësisht në fusha të ndryshme të shkencave si mekanika, fizika, kimia, etj.

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

Pavarësisht nga thjeshtësia dhe qartësia e mësipërme, aplikim praktik Teoria e zinxhirëve Markov kërkon njohuri për disa terma dhe parime bazë që duhet të diskutohen përpara se të paraqiten shembuj.

Siç tregohet, proceset e rastësishme Markov i referohen rasteve të veçanta të proceseve të rastësishme (PS). Nga ana tjetër, proceset e rastësishme bazohen në koncept funksion i rastësishëm(SF).

Një funksion i rastësishëm është një funksion vlera e të cilit për çdo vlerë të argumentit është ndryshore e rastësishme(SV). Me fjalë të tjera, SF mund të quhet një funksion që, në çdo test, merr një formë të panjohur më parë.

Shembuj të tillë të SF janë: luhatjet e tensionit në qark elektrik, shpejtësia e një makine në një pjesë të rrugës me kufizim shpejtësie, vrazhdësia e sipërfaqes së një pjese në një zonë të caktuar etj.

Si rregull, besohet se nëse argumenti i SF është koha, atëherë një proces i tillë quhet i rastësishëm. Ekziston një përkufizim tjetër i proceseve të rastësishme, më afër teorisë së vendimit. Në këtë rast, një proces i rastësishëm kuptohet si një proces i ndryshimeve të rastësishme në gjendjet e çdo fizike ose sistemi teknik nga koha ose ndonjë argument tjetër.

Është e lehtë të shihet se nëse përcaktoni një gjendje dhe përshkruani një varësi, atëherë një varësi e tillë do të jetë një funksion i rastësishëm.

Proceset e rastësishme klasifikohen sipas llojeve të gjendjeve dhe argumentit t. Në këtë rast, proceset e rastësishme mund të jenë me gjendje ose kohë diskrete ose të vazhdueshme.

Përveç shembujve të mësipërm të klasifikimit të proceseve të rastësishme, ekziston një veçori tjetër e rëndësishme. Kjo veti përshkruan lidhjen probabilistike ndërmjet gjendjeve të proceseve të rastësishme. Kështu, për shembull, nëse në një proces të rastësishëm probabiliteti i kalimit të sistemit në çdo gjendje pasuese varet vetëm nga gjendja e mëparshme, atëherë një proces i tillë quhet një proces pa efekt.

Le të vërejmë, së pari, se një proces i rastësishëm me gjendje dhe kohë diskrete quhet sekuencë e rastësishme.

Nëse një sekuencë e rastësishme ka vetinë Markov, atëherë ajo quhet zinxhir Markov.

Nga ana tjetër, nëse në një proces të rastësishëm gjendjet janë diskrete, koha është e vazhdueshme dhe ruhet vetia pas efektit, atëherë një proces i tillë i rastësishëm quhet proces Markov me kohë të vazhdueshme.

Një proces i rastësishëm Markov thuhet se është homogjen nëse probabilitetet e tranzicionit mbeten konstante gjatë procesit.

Një zinxhir Markov konsiderohet i dhënë nëse jepen dy kushte.

1. Ekziston një grup probabilitetesh tranzicioni në formën e një matrice:

2. Ekziston një vektor i probabiliteteve fillestare

duke përshkruar gjendjen fillestare të sistemit.

Përveç formës së matricës, modeli i zinxhirit Markov mund të paraqitet si një grafik i ponderuar i drejtuar (Fig. 1).

Oriz. 1

Grupi i gjendjeve të një sistemi zinxhir Markov klasifikohet në një mënyrë të caktuar, duke marrë parasysh sjelljen e mëtejshme të sistemit.

1. Komplet i pakthyeshëm (Fig. 2).

Fig.2.

Në rastin e një grupi që nuk kthehet, çdo kalim brenda këtij grupi është i mundur. Sistemi mund të largohet nga ky grup, por nuk mund të kthehet në të.

2. Kompleti i kthimit (Fig. 3).

Oriz. 3.

Në këtë rast, çdo tranzicion brenda grupit është gjithashtu i mundur. Sistemi mund të hyjë në këtë grup, por nuk mund ta lërë atë.

3. Komplet ergodik (Fig. 4).

Oriz. 4.

Në rastin e një grupi ergodik, çdo kalim brenda grupit është i mundur, por kalimet nga dhe në grup janë të përjashtuara.

4. Kompleti thithës (Fig. 5)

Oriz. 5.

Kur sistemi hyn në këtë grup, procesi përfundon.

Në disa raste, pavarësisht rastësisë së procesit, është e mundur të kontrollohen në një masë të caktuar ligjet e shpërndarjes ose parametrat e probabiliteteve të tranzicionit. Zinxhirë të tillë Markov quhen të kontrolluar. Natyrisht, me ndihmën e zinxhirëve të kontrolluar Markov (MCC), procesi i vendimmarrjes bëhet veçanërisht efektiv, siç do të diskutohet më vonë.

Karakteristika kryesore e një zinxhiri diskrete Markov (DMC) është determinizmi i intervaleve kohore midis hapave (fazave) individuale të procesit. Megjithatë, shpesh në proceset reale kjo veti nuk respektohet dhe intervalet rezultojnë të jenë të rastësishme me ndonjë ligj të shpërndarjes, megjithëse ruhet vetia Markov e procesit. Sekuenca të tilla të rastësishme quhen gjysmë-Markov.

Përveç kësaj, duke marrë parasysh praninë dhe mungesën e grupeve të caktuara të gjendjeve të përmendura më sipër, zinxhirët Markov mund të jenë absorbues nëse ka të paktën një gjendje thithëse, ose ergodik nëse probabilitetet e tranzicionit formojnë një grup ergodik. Nga ana tjetër, zinxhirët ergodik mund të jenë të rregullt ose ciklik. Zinxhirët ciklikë ndryshojnë nga ata të rregullt në atë që gjatë kalimit nëpër një numër të caktuar hapash (ciklesh) ndodh një kthim në një gjendje. Zinxhirë të rregullt nuk e kanë këtë pronë.