Zinxhirë homogjenë Markov. Zinxhirët e rregullt Markov Njohja e zinxhirëve ciklikë Markov pdf

Homogjene është një zinxhir Markov për të cilin probabiliteti i kushtëzuar i kalimit nga një gjendje në një gjendje nuk varet nga numri i testit. Për zinxhirë homogjenë në vend
përdorni shënimin
.

Një shembull i një zinxhiri homogjen Markov janë ecjet e rastësishme. Le të jetë një grimcë materiale në drejtëzën Ox në një pikë me koordinatë numër të plotë x=n. Në kohë të caktuara
grimca ndryshon pozicionin e saj befas (për shembull, me probabilitet p mund të lëvizë djathtas dhe me probabilitet 1 –p– majtas). Natyrisht, koordinata e grimcës pas kërcimit varet nga vendi ku ishte grimca pas kërcimit menjëherë paraardhës, dhe nuk varet nga mënyra se si ajo lëvizi në momentet e mëparshme kohore.

Në atë që vijon, ne do të kufizojmë veten në marrjen në konsideratë të zinxhirëve homogjenë të fundëm Markov.

Probabilitetet e tranzicionit. Matrica e tranzicionit.

Probabiliteti i tranzicionit
quhet probabiliteti i kushtëzuar që nga gjendja Si rezultat i testit të radhës, sistemi do të kalojë në gjendje . Pra indeksi lidhet me atë të mëparshmen, dhe - në gjendjen pasuese.

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

, Ku përfaqësojnë probabilitetet e tranzicionit në një hap.

Le të vëmë re disa veçori të matricës së tranzicionit.

Barazia Markov

Le të shënojmë me
probabiliteti që si rezultat i n hapave (testeve) sistemi të largohet nga gjendja në një gjendje . Për shembull,
- probabiliteti i kalimit në 10 hapa nga gjendja e tretë në të gjashtin. Vini re se kur n= 1 kjo probabilitet thjesht reduktohet në probabilitetin e tranzicionit
.

Shtrohet pyetja, si, duke ditur probabilitetet e tranzicionit
, gjeni probabilitetet e tranzicionit të gjendjes në një gjendje hap pas hapi Për këtë qëllim, një ndërmjetës (ndërmjet Dhe ) gjendje. Me fjalë të tjera, besohet se nga gjendja origjinale Pas m hapave, sistemi do të kalojë në një gjendje të ndërmjetme me probabilitet
, pas së cilës në hapat e mbetur n–m do të kalojë nga gjendja e ndërmjetme në gjendjen përfundimtare me probabilitet
. Duke përdorur formulën e probabilitetit total, mund të tregojmë se formula është e vlefshme

Kjo formulë quhet Barazia Markov .

Njohja e të gjitha probabiliteteve të tranzicionit
, d.m.th. njohja e matricës së tranzicionit nga shteti në shtet në një hap, ju mund të gjeni probabilitetet
kalimi nga gjendja në gjendje në dy hapa, dhe për rrjedhojë edhe vetë matrica e tranzicionit , atëherë - sipas matricës së njohur - Gjej etj.

Në të vërtetë, duke vendosur n= 2,m= 1 në barazinë Markov, marrim

ose
. Në formë matrice kjo mund të shkruhet si
.

Duke supozuar n=3,m=2, marrim
. Në rastin e përgjithshëm, marrëdhënia është e vërtetë
.

Shembull. Lëreni matricën e tranzicionit e barabartë me

Ne duhet të gjejmë matricën e tranzicionit
.

Matrica e shumëzimit në vetvete, marrim
.

Për aplikime praktike, çështja e llogaritjes së probabilitetit që një sistem të jetë në një gjendje të caktuar në një moment të caktuar kohor është jashtëzakonisht i rëndësishëm. Zgjidhja e kësaj pyetje kërkon njohjen e kushteve fillestare, d.m.th. probabilitetet që sistemi të jetë në gjendje të caktuara në kohën fillestare. Shpërndarja fillestare e probabilitetit të një zinxhiri Markov është shpërndarja e probabilitetit të gjendjeve në fillim të procesit.

Këtu nëpërmjet
tregon probabilitetin që sistemi të jetë në gjendje në momentin fillestar të kohës. Në rastin e veçantë, nëse dihet saktësisht gjendja fillestare e sistemit (për shembull
), pastaj probabiliteti fillestar
, dhe të gjitha të tjerat janë të barabarta me zero.

Nëse për një zinxhir homogjen Markov jepet shpërndarja fillestare e probabilitetit dhe matrica e tranzicionit, atëherë probabilitetet e sistemit shprehen në hapin e ntë
llogariten duke përdorur formulën e përsëritur

Për ta ilustruar, le të japim një shembull të thjeshtë. Le të shqyrtojmë procesin e funksionimit të një sistemi të caktuar (për shembull, një pajisje). Lëreni pajisjen të jetë në njërën nga dy gjendjet për një ditë - në shërbim ( ) dhe i gabuar ( ). Si rezultat i vëzhgimeve masive të funksionimit të pajisjes, u përpilua matrica e mëposhtme e tranzicionit
,

Ku - gjasat që pajisja të mbetet në gjendje të mirë;

- probabiliteti i kalimit të pajisjes nga një gjendje shërbimi në një gjendje të gabuar;

- probabiliteti i kalimit të pajisjes nga një gjendje e gabuar në një gjendje shërbimi;

- probabiliteti që pajisja të mbetet në gjendje "të gabuar".

Le të jepet vektori i probabiliteteve fillestare të gjendjeve të pajisjes nga relacioni

, d.m.th.
(në momentin fillestar pajisja ishte me defekt). Kërkohet të përcaktohen probabilitetet e gjendjes së pajisjes pas tre ditësh.

Zgjidhje: Duke përdorur matricën e tranzicionit, ne përcaktojmë probabilitetet e gjendjeve pas hapit të parë (pas ditës së parë):

Probabilitetet e gjendjeve pas hapit të dytë (dita e dytë) janë të barabarta

Së fundi, probabilitetet e gjendjeve pas hapit të tretë (dita e tretë) janë të barabarta

Kështu, probabiliteti që pajisja të jetë në gjendje të mirë është 0,819, dhe që të jetë në gjendje të gabuar është përkatësisht 0,181.

Procesi Markov- një proces i rastësishëm që ndodh në sistem, i cili ka vetinë: për çdo moment të kohës t 0, probabiliteti i çdo gjendjeje të sistemit në të ardhmen (në t>t 0) varet vetëm nga gjendja e tij në të tashmen (në 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).

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

Çdo proces Markov përshkruhet duke përdorur probabilitetet e gjendjes dhe probabilitetet e tranzicionit.

Probabilitetet e gjendjeve P k (t) të një procesi Markov janë probabilitetet që procesi (sistemi) i rastësishëm në kohën t është në gjendjen S k:

Probabilitetet e tranzicionit të një procesi Markov janë probabilitetet e kalimit të një procesi (sistemi) nga një gjendje në tjetrën:

Procesi Markov quhet homogjene, nëse probabilitetet e kalimit për njësi të kohës nuk varen nga vendi ku në boshtin kohor ndodh kalimi.

Procesi më i thjeshtë është zinxhir Markov– Procesi i rastësishëm Markov me kohë diskrete dhe grup diskrete të fundme të gjendjeve.

Kur analizohen, zinxhirët Markov janë grafiku i gjendjes, në të cilën janë shënuar në një hap të gjitha gjendjet e zinxhirit (sistemit) dhe probabilitetet jozero.

Një zinxhir Markov mund të mendohet sikur një pikë që përfaqëson një sistem lëviz rastësisht nëpër një grafik gjendjeje, duke u zvarritur nga një gjendje në tjetrën në një hap ose duke qëndruar në të njëjtën gjendje për disa hapa.

Probabilitetet e kalimit të një zinxhiri Markov në një hap shkruhen në formën e një matrice P=||P ij ||, e cila quhet matrica e probabilitetit të tranzicionit ose thjesht matrica e tranzicionit.

Shembull: grupi i gjendjeve të studentëve të specialitetit është si më poshtë:

S 1 – student i parë;

S 2 – student i dytë…;

S 5 – student i vitit të 5-të;

S 6 – specialist i diplomuar në universitet;

S 7 - një person që ka studiuar në një universitet, por nuk është diplomuar.

Nga gjendja S 1 brenda një viti, kalimet në gjendjen S 2 janë të mundshme me probabilitet r 1 ; S 1 me probabilitet q 1 dhe S 7 me probabilitet p 1, dhe:

r 1 +q 1 +p 1 =1.

Le të ndërtojmë një grafik të gjendjes për këtë zinxhir Markov dhe ta shënojmë me probabilitete kalimi (jo zero).

Le të krijojmë një matricë të probabiliteteve të tranzicionit:

Matricat e tranzicionit kanë vetitë e mëposhtme:

Të gjithë elementët e tyre janë jonegativë;

Shumat e rreshtave të tyre janë të barabarta me një.

Matricat me këtë veti quhen stokastike.

Matricat e tranzicionit ju lejojnë të llogaritni probabilitetin e çdo trajektoreje të zinxhirit Markov duke përdorur teoremën e shumëzimit të probabilitetit.

Për zinxhirët homogjenë Markov, matricat e tranzicionit nuk varen nga koha.

Kur studioni zinxhirët Markov, ato me interes më të madh janë:

Probabilitetet e kalimit në m hapa;

Shpërndarja mbi gjendjet në hapin m→∞;

Koha mesatare e kaluar në një gjendje të caktuar;

Koha mesatare për t'u kthyer në këtë gjendje.

Konsideroni një zinxhir homogjen Markov me n gjendje. Për të marrë probabilitetin e kalimit nga gjendja S i në gjendjen S j në hapa m, në përputhje me formulën e probabilitetit total, duhet të mblidhen produktet e probabilitetit të kalimit nga gjendja Si në gjendjen e ndërmjetme Sk në l hapa me probabilitetin. të kalimit nga Sk në Sj në hapat m-l të mbetur, d.m.th.

Kjo lidhje është për të gjitha i=1, …, n; j=1, …,n mund të përfaqësohet si produkt i matricave:

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

Kështu kemi:

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

P(3)=P(2)*P(1)=P(1)*P(2)=P 3, etj.

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

e cila bën të mundur gjetjen e probabiliteteve të kalimit midis gjendjeve në çdo numër hapash, duke ditur matricën e tranzicionit në një hap, përkatësisht P ij (m) - një element i matricës P(m) është probabiliteti i lëvizjes nga gjendja S. i për të deklaruar S j në m hapa.

Shembull: Moti në një rajon të caktuar alternon me shi dhe të thatë për periudha të gjata kohore. Nëse bie shi, atëherë me probabilitet 0.7 do të bjerë shi të nesërmen; Nëse moti është i thatë në një ditë të caktuar, atëherë me një probabilitet prej 0.6 do të vazhdojë të nesërmen. Mësohet se të mërkurën ka qenë mot me shi. Sa është probabiliteti që të premten e ardhshme të bjerë shi?

Le të shkruajmë të gjitha gjendjet e zinxhirit Markov në këtë problem: D – mot me shi, C – mot i thatë.

Le të ndërtojmë një grafik të gjendjes:

Përgjigje: p 11 = p (D thembra | D mesatar) = 0,61.

Kufijtë e probabilitetit р 1 (m), р 2 (m),…, р n (m) për m→∞, nëse ekzistojnë, quhen probabilitetet kufizuese të gjendjeve.

Teorema e mëposhtme mund të vërtetohet: nëse në një zinxhir Markov mund të kaloni nga + çdo gjendje (në një numër të caktuar hapash) tek njëri-tjetri, atëherë probabilitetet kufizuese të gjendjeve ekzistojnë dhe nuk varen nga gjendja fillestare e sistemit. .

Kështu, si m→∞, në sistem vendoset një regjim i caktuar i palëvizshëm kufizues, në të cilin secila prej gjendjeve ndodh me një probabilitet të caktuar konstant.

Vektori p, i përbërë nga probabilitete margjinale, duhet të plotësojë relacionin: p=p*P.

Koha mesatare e kaluar në shtet S i për kohën T është e barabartë me p i *T, ku p i - probabiliteti margjinal i gjendjes S i. Koha mesatare për t'u kthyer në gjendje S i është i barabartë me .

Shembull.

Për shumë probleme ekonomike është e nevojshme të dihet ndërrimi i viteve me vlera të caktuara të prurjeve vjetore të lumenjve. Natyrisht, ky alternim nuk mund të përcaktohet absolutisht saktësisht. Për të përcaktuar probabilitetet e alternimit (tranzicionit), ne i ndajmë rrjedhat duke futur katër shkallëzime (gjendjet e sistemit): e para (rrjedhja më e ulët), e dyta, e treta, e katërta (rrjedhja më e lartë). Për saktësi, do të supozojmë se gradimi i parë nuk pasohet kurrë nga i katërti, dhe i katërti nga i pari për shkak të akumulimit të lagështirës (në tokë, rezervuar, etj.). Vëzhgimet kanë treguar se në një rajon të caktuar janë të mundshme tranzicione të tjera dhe:

a) nga gradimi i parë mund të kaloni në secilën prej atyre të mesit dy herë më shpesh se përsëri në të parën, d.m.th.

p 11 =0,2; p 12 =0,4; p 13 =0,4; p 14 =0;

b) nga gradimi i katërt, kalimet në gradimin e dytë dhe të tretë ndodhin katër dhe pesë herë më shpesh se kthimet si në të dytin, d.m.th.

vështirë, d.m.th.

në të katërtën, d.m.th.

p 41 =0; p 42 =0,4; p 43 =0,5; p 44 =0,1;

c) nga gradimet e dyta në të tjera mund të jenë vetëm më pak të shpeshta: në të parën - dy herë më pak, në të tretën me 25%, në të katërtin - katër herë më rrallë se kalimi në të dytin, d.m.th.

p 21 =0,2;p 22 =0,4; p 23 =0,3; p 24 =0,1;

d) nga gradimi i tretë, një kalim në gradimin e dytë është po aq i mundshëm sa një kthim në gradimin e tretë, dhe kalimet në gradimin e parë dhe të katërt janë katër herë më pak të mundshme, d.m.th.

p 31 =0,1; p 32 =0,4; p 33 =0,4; p 34 =0,1;

Le të ndërtojmë një grafik:

Le të krijojmë një matricë të probabiliteteve të tranzicionit:

Le të gjejmë kohën mesatare midis thatësirës dhe viteve me ujë të lartë. Për ta bërë këtë, ju duhet të gjeni shpërndarjen e kufirit. Ajo ekziston sepse kushti i teoremës është i plotësuar (matrica P2 nuk përmban elemente zero, d.m.th., në dy hapa mund të kaloni nga çdo gjendje e sistemit në një tjetër).

Ku p 4 =0,08; p 3 =; p 2 =; p 1 =0,15

Frekuenca e kthimit në gjendjen S i është e barabartë me .

Për rrjedhojë, frekuenca e viteve të thata është mesatarisht 6.85, d.m.th. 6-7 vjet, dhe vitet me shi 12.

Zinxhirët Markov

Prezantimi

§ 1. Zinxhiri Markov

§ 2. Zinxhiri homogjen Markov. Probabilitetet e tranzicionit. Matrica e Tranzicionit

§3. Barazia Markov

§4. Shpërndarja e palëvizshme. Teorema e probabilitetit të kufirit

§5. Vërtetimi i teoremës mbi probabilitetet kufizuese në një zinxhir Markov

§6. Aplikimet e zinxhirëve Markov

konkluzioni

Lista e literaturës së përdorur

Prezantimi

Tema e punës sonë të kursit është zinxhiri Markov. Zinxhirët Markov kanë marrë emrin e matematikanit të shquar rus, Andrei Andreevich Markov, i cili ka punuar gjerësisht në procese të rastësishme dhe ka dhënë një kontribut të madh në zhvillimin e kësaj fushe. Kohët e fundit, ju mund të dëgjoni për përdorimin e zinxhirëve Markov në një sërë fushash: teknologji moderne në internet, kur analizoni tekste letrare, apo edhe kur zhvilloni taktika për një ekip futbolli. Ata që nuk e dinë se çfarë janë zinxhirët Markov mund të kenë ndjenjën se është diçka shumë komplekse dhe pothuajse e pakuptueshme.

Jo, është e kundërta. Një zinxhir Markov është një nga rastet më të thjeshta të një sekuence ngjarjesh të rastësishme. Por, megjithë thjeshtësinë e tij, shpesh mund të jetë i dobishëm edhe kur përshkruan fenomene mjaft komplekse. Një zinxhir Markov është një sekuencë ngjarjesh të rastësishme në të cilat probabiliteti i secilës ngjarje varet vetëm nga ajo e mëparshme, por nuk varet nga ngjarjet e mëparshme.

Para se të thellohemi më thellë, duhet të shqyrtojmë disa çështje ndihmëse që njihen përgjithësisht, por janë absolutisht të nevojshme për ekspozim të mëtejshëm.

Qëllimi i punës sime të kursit është të studioj më në detaje aplikimet e zinxhirëve Markov, deklarimin e problemit dhe problemet Markov.

§1. zinxhir Markov

Le të imagjinojmë se po kryhet një sekuencë testesh.

Përkufizimi. Një zinxhir Markov është një sekuencë sprovash në secilën prej të cilave shfaqet një dhe vetëm një nga ngjarjet e papajtueshme të grupit të plotë, dhe probabiliteti i kushtëzuar që ngjarja të ndodhë në provën e tretë është , me kusht që ngjarja të ketë ndodhur në gjykimin e th , nuk varet nga rezultatet e testeve të mëparshme.

Për shembull, nëse sekuenca e sprovave formon një zinxhir Markov dhe grupi i plotë përbëhet nga katër ngjarje të papajtueshme, dhe dihet se ngjarja ka ndodhur në provën e gjashtë, atëherë probabiliteti i kushtëzuar që ngjarja të ndodhë në provën e shtatë nuk varet. se cilat ngjarje u shfaqën në testet e para, të dyta, ..., të pesta.

Vini re se testet e pavarura janë një rast i veçantë i një zinxhiri Markov. Në të vërtetë, nëse testet janë të pavarura, atëherë shfaqja e një ngjarjeje të caktuar në asnjë test nuk varet nga rezultatet e testeve të kryera më parë. Nga kjo rrjedh se koncepti i një zinxhiri Markov është një përgjithësim i konceptit të gjykimeve të pavarura.

Shpesh, kur paraqesin teorinë e zinxhirëve Markov, ata i përmbahen një terminologjie të ndryshme dhe flasin për një sistem fizik të caktuar, i cili në çdo moment të kohës është në një nga gjendjet: , dhe e ndryshon gjendjen e tij vetëm në momente të veçanta të kohës, që është, sistemi lëviz nga një gjendje në tjetrën (për shembull, nga në ). Për zinxhirët Markov, probabiliteti për të shkuar në çdo shtet është për momentin varet vetëm nga ajo gjendje në të cilën ishte sistemi për momentin, dhe nuk ndryshon sepse gjendjet e tij në momentet e mëparshme bëhen të njohura. Gjithashtu, në veçanti, pas testimit sistemi mund të mbetet në të njëjtën gjendje ("lëviz" nga një gjendje në tjetrën).

Për ta ilustruar, merrni parasysh një shembull.

Shembulli 1. Le të imagjinojmë që një grimcë e vendosur në një vijë të drejtë lëviz përgjatë kësaj vije të drejtë nën ndikimin e goditjeve të rastësishme që ndodhin në momente. Një grimcë mund të gjendet në pika me koordinata të plota: ; Muret reflektuese janë të vendosura në pika. Çdo shtytje e lëviz grimcën në të djathtë me probabilitet dhe në të majtë me probabilitet, përveç nëse grimca është afër një muri. Nëse grimca është afër murit, atëherë çdo shtytje e lëviz atë një njësi brenda hendekut midis mureve. Këtu shohim se ky shembull i ecjes së grimcave është një zinxhir tipik Markov.

Kështu, ngjarjet quhen gjendje të sistemit, dhe testet quhen ndryshime në gjendjet e tij.

Le të përcaktojmë tani një zinxhir Markov duke përdorur terminologji të re.

Një zinxhir Markov me kohë diskrete është një qark, gjendjet e të cilit ndryshojnë në kohë të caktuara fikse.

Një zinxhir Markov me kohë të vazhdueshme është një zinxhir, gjendjet e të cilit ndryshojnë në çdo moment të mundshëm të rastësishëm në kohë.

§2. Zinxhiri homogjen Markov. Probabilitetet e tranzicionit. Matrica e Tranzicionit

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. Prandaj, në vend që të shkruani thjesht .

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.

Kështu, një ecje e rastësishme është një shembull i një zinxhiri homogjen Markov me 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ë përcaktim, indeksi i parë tregon numrin e gjendjes së mëparshme, dhe i dyti tregon numrin e gjendjes pasuese. Për shembull, është probabiliteti i kalimit nga gjendja e dytë në të tretën.

Le të jetë numri i shteteve të fundme dhe të barabartë me .

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) që formojnë një grup të plotë, 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, ai do të mbetet në të njëjtën gjendje me probabilitet 0.5, do të mbetet në të njëjtën gjendje me probabilitet 0.5, do të shkojë në gjendje me probabilitet 0.2, pastaj pas tranzicionit mund të përfundojë në shtete; nuk mund të lëvizë nga shteti në. Rreshti i fundit i matricës na tregon se nga një gjendje të shkojmë në ndonjë nga gjendjet e mundshme me probabilitet të njëjtë prej 0.1.

Bazuar në matricën e tranzicionit të sistemit, mund të ndërtoni një të ashtuquajtur grafik të gjendjes së sistemit; ai quhet gjithashtu një grafik i gjendjes së emërtuar. 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 matrica e rendit të 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. Kur merren në konsideratë sisteme specifike, është e përshtatshme që së pari të ndërtohet një grafik i gjendjes, 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 ndërtoni një matricë tranzicioni të sistemit.

§3. Barazia Markov

Përkufizimi. Le të shënojmë me probabilitetin që si rezultat i hapave (testeve) sistemi të kalojë nga një gjendje në tjetrën. Për shembull, është probabiliteti i kalimit në 10 hapa nga gjendja e dytë në të pestën.

Theksojmë se në marrim probabilitetet e tranzicionit

Le t'i vendosim vetes një detyrë: duke ditur probabilitetet e tranzicionit, të gjejmë probabilitetet e kalimit të sistemit nga gjendja në gjendje me hapa.

Për këtë qëllim, ne prezantojmë një gjendje të ndërmjetme (ndërmjet dhe ). Me fjalë të tjera, do të supozojmë se nga gjendja fillestare në hapa sistemi do të kalojë në një gjendje të ndërmjetme me probabilitet, pas së cilës në hapat e mbetur nga gjendja e ndërmjetme do të kalojë në gjendjen përfundimtare me probabilitet.

Duke përdorur formulën e probabilitetit total, marrim

. (1)

Kjo formulë quhet barazia e Markovit.

Shpjegim. Le të prezantojmë shënimin e mëposhtëm:

– ngjarja që na intereson (në hapa sistemi do të kalojë nga gjendja fillestare në gjendjen përfundimtare), pra, ; - hipoteza (me hapa sistemi do të kalojë nga gjendja fillestare në gjendjen e ndërmjetme), pra, - probabiliteti i kushtëzuar i ndodhjes, me kusht që hipoteza të ketë ndodhur (në hapa sistemi do të kalojë nga gjendja e ndërmjetme në gjendjen përfundimtare), prandaj,

Sipas formulës së probabilitetit total,

()

Ose në shënimin që kemi miratuar

që përkon me formulën e Markovit (1).

Duke ditur të gjitha probabilitetet e tranzicionit, d.m.th., duke ditur matricën e tranzicionit nga gjendja në gjendje në një hap, mund të gjeni probabilitetet e kalimit nga gjendja në gjendje në dy hapa, dhe për rrjedhojë edhe vetë matricën e tranzicionit; duke përdorur një matricë të njohur, mund të gjeni matricën e tranzicionit nga gjendja në gjendje në tre hapa, etj.

Në të vërtetë, duke vënë në barazinë Markov

probabiliteti i rastësishëm i zinxhirit të shenjave

(2)

Kështu, duke përdorur formulën (2) mund të gjeni të gjitha probabilitetet dhe, rrjedhimisht, vetë matricën. Meqenëse përdorimi i drejtpërdrejtë i formulës (2) rezulton të jetë i lodhshëm, dhe llogaritja e matricës çon më shpejt te qëllimi, unë do t'i shkruaj marrëdhëniet që dalin nga (2) në formë matrice:

Duke vendosur (1), ne marrim në mënyrë të ngjashme

Në përgjithësi

Teorema 1. Për çdo s, t

(3)

Dëshmi. Le të llogarisim probabilitetin duke përdorur formulën e probabilitetit total (), duke vendosur

Nga barazitë

Prandaj nga barazitë (4) dhe

marrim pohimin e teoremës.

Le të përkufizojmë matricën.Në matricën shënimi (3) ka formën

Që atëherë ku është matrica e probabilitetit të tranzicionit. Nga (5) vijon

(6)

Rezultatet e marra në teorinë e matricave lejojnë përdorimin e formulës (6) për të llogaritur dhe studiuar sjelljen e tyre kur

Shembulli 1. Matrica e tranzicionit e specifikuar Gjeni matricën e tranzicionit

Zgjidhje. Le të përdorim formulën

Duke shumëzuar matricat, më në fund marrim:

§4. Shpërndarja e palëvizshme. Teorema e probabilitetit të kufirit

Shpërndarja e probabilitetit në një moment arbitrar në kohë mund të gjendet duke përdorur formulën e probabilitetit total

(7)

Mund të rezultojë se nuk varet nga koha. Le të thërrasim shpërndarje stacionare vektoriale , duke plotesuar kushtet

ku janë probabilitetet e tranzicionit.

Nëse në një zinxhir Markov pastaj për ndonjë

Ky pohim pason nga induksioni nga (7) dhe (8).

Le të paraqesim formulimin e teoremës mbi probabilitetet kufizuese për një klasë të rëndësishme të zinxhirëve Markov.

Teorema 1. Nëse për disa >0 të gjithë elementët e matricës janë pozitivë, atëherë për çdo , për

, (9)

Ku shpërndarje stacionare me një konstante të caktuar që plotëson pabarazinë 0< h <1.

Meqenëse, atëherë sipas kushteve të teoremës, nga çdo gjendje mund të arrini në çdo gjendje në kohë me një probabilitet pozitiv. Kushtet e teoremës përjashtojnë zinxhirët që në një farë kuptimi janë periodikë.

Nëse plotësohen kushtet e teoremës 1, atëherë probabiliteti që sistemi të jetë në një gjendje të caktuar në kufi nuk varet nga shpërndarja fillestare. Në të vërtetë, nga (9) dhe (7) rrjedh se për çdo shpërndarje fillestare,

Le të shqyrtojmë disa shembuj të zinxhirëve Markov për të cilët nuk plotësohen kushtet e Teoremës 1. Nuk është e vështirë të verifikohet se shembuj të tillë janë shembuj. Në shembull, probabilitetet e tranzicionit kanë kufij, por këto kufij varen nga gjendja fillestare. Në veçanti, kur

Në shembuj të tjerë, diapazoni i probabilitetit për padyshim nuk ekziston.

Le të gjejmë shpërndarjen stacionare në shembullin 1. Duhet të gjejmë vektorin kushte të kënaqshme (8):

;

Prandaj, kështu, ekziston një shpërndarje stacionare, por jo të gjithë vektorët e koordinatave janë pozitivë.

Për skemën polinomiale, u prezantuan ndryshore të rastësishme të barabarta me numrin e rezultateve të një lloji të caktuar. Le të prezantojmë sasi të ngjashme për zinxhirët Markov. Le të jetë numri i herëve që sistemi hyn në gjendje në kohë. Pastaj frekuenca e sistemit që godet gjendjen. Duke përdorur formulat (9), mund të vërtetojmë se kur afrohet . Për ta bërë këtë, ju duhet të merrni formula asimptotike për dhe dhe të përdorni pabarazinë e Chebyshev. Këtu është derivimi i formulës për . Le ta paraqesim atë në formë

(10)

ku, nëse dhe ndryshe. Sepse

atëherë, duke përdorur vetinë e pritjes matematikore dhe formulën (9), marrim

Në bazë të teoremës 1, termi i trefishtë në anën e djathtë të kësaj barazie është një shumë e pjesshme e një serie konvergjente. Duke vënë , marrim

Sepse

Nga formula (11), në veçanti, rrjedh se

në

Ju gjithashtu mund të merrni një formulë për të cilën përdoret për të llogaritur variancën.

§5. Vërtetimi i teoremës mbi probabilitetet kufizuese në një zinxhir Markov

Le të vërtetojmë fillimisht dy lema. Le të vendosim

Lema 1. Ka kufizime për çdo

Dëshmi. Duke përdorur ekuacionin (3) me marrim

Kështu, sekuencat janë njëkohësisht monotonike dhe të kufizuara. Kjo nënkupton deklaratën e Lemës 1.

Lema 2. Nëse plotësohen kushtet e teoremës 2, atëherë ka konstante, sikurse

Për çdo

ku , do të thotë përmbledhje mbi të gjitha për të cilat është pozitive, dhe përmbledhje mbi pjesën tjetër. Nga këtu

. (12)

Meqenëse në kushtet e teoremës 1 probabilitetet e tranzicionit për të gjithë, pastaj për çdo

Dhe për shkak të numrit të kufizuar të gjendjeve

Tani le të vlerësojmë ndryshimin . Duke përdorur ekuacionin (3) me , , marrim

Nga këtu, duke përdorur (8)-(10), gjejmë

Duke e kombinuar këtë lidhje me pabarazinë (14), marrim deklaratën e lemës.

Shkoni te vërtetimi i teoremës. Meqenëse sekuencat janë monotone, atëherë

0<. (15)

Nga kjo dhe Lema 1 gjejmë

Prandaj, kur të merrni dhe

Pozitiviteti rrjedh nga pabarazia (15). Duke kaluar në kufirin në dhe në ekuacionin (3), marrim që plotëson ekuacionin (12). Teorema është vërtetuar.

§6. Aplikimet e zinxhirëve Markov

Zinxhirët Markov shërbejnë si një hyrje e mirë në teorinë e proceseve të rastësishme, d.m.th. teoria e sekuencave të thjeshta të një familjeje variablash të rastësishëm, zakonisht në varësi të një parametri, i cili në shumicën e aplikacioneve luan rolin e kohës. Ai synon kryesisht të përshkruajë plotësisht sjelljen afatgjatë dhe lokale të një procesi. Këtu janë disa nga çështjet më të studiuara në këtë drejtim.

Lëvizja Brownian dhe përgjithësimet e saj - proceset dhe proceset e difuzionit me rritje të pavarura . Teoria e proceseve të rastësishme kontribuoi në thellimin e lidhjes midis teorisë së probabilitetit, teorisë së operatorëve dhe teorisë së ekuacioneve diferenciale, e cila, ndër të tjera, ishte e rëndësishme për fizikën dhe aplikimet e tjera. Aplikimet përfshijnë procese me interes për matematikën aktuariale (siguruese), teorinë e radhës, gjenetikën, kontrollin e trafikut, teorinë e qarkut elektrik dhe teorinë e inventarit.

Martingales . Këto procese ruajnë mjaft veti të zinxhirëve Markov, saqë teoremat e rëndësishme ergodike mbeten të vlefshme për ta. Martingales ndryshojnë nga zinxhirët Markov në atë që kur dihet gjendja aktuale, vetëm pritshmëria matematikore e së ardhmes, por jo domosdoshmërisht vetë shpërndarja e probabilitetit, nuk varet nga e kaluara. Përveç të qenit një mjet i rëndësishëm kërkimi, teoria martingale ka pasuruar teorinë e proceseve të rastësishme që lindin në statistikë, teorinë e ndarjes bërthamore, gjenetikën dhe teorinë e informacionit me teorema të reja kufitare.

Proceset stacionare . Teorema më e vjetër e njohur ergodike, siç u përmend më lart, mund të interpretohet si rezultat që përshkruan sjelljen kufizuese të një procesi të rastësishëm të palëvizshëm. Një proces i tillë ka vetinë që të gjitha ligjet probabilistike që ai plotëson mbeten të pandryshueshme në lidhje me ndërrimet kohore. Teorema ergodike, e formuluar fillimisht nga fizikanët si hipotezë, mund të përfaqësohet si një deklaratë që, në kushte të caktuara, mesatarja e ansamblit përkon me mesataren kohore. Kjo do të thotë se i njëjti informacion mund të merret nga vëzhgimi afatgjatë i një sistemi dhe nga vëzhgimi i njëkohshëm (dhe i menjëhershëm) i shumë kopjeve të pavarura të të njëjtit sistem. Ligji i numrave të mëdhenj nuk është gjë tjetër veçse një rast i veçantë i teoremës ergodike të Birkhoff-it. Interpolimi dhe parashikimi i sjelljes së proceseve të palëvizshme Gaussian, të kuptuara në një kuptim të gjerë, shërbejnë si një përgjithësim i rëndësishëm i teorisë klasike të katrorëve më të vegjël. Teoria e proceseve stacionare është një mjet i nevojshëm kërkimor në shumë fusha, për shembull, në teorinë e komunikimit, e cila merret me studimin dhe krijimin e sistemeve që transmetojnë mesazhe në prani të zhurmës ose ndërhyrjeve të rastësishme.

Proceset Markov (proceset pa pasoja) luajnë një rol të madh në modelimin e sistemeve të radhës (QS), si dhe në modelimin dhe zgjedhjen e një strategjie për menaxhimin e proceseve socio-ekonomike që ndodhin në shoqëri.

Zinxhiri Markov mund të përdoret gjithashtu për të gjeneruar tekste. Disa tekste jepen si hyrje, pastaj ndërtohet një zinxhir Markov me probabilitetet e një fjale pas tjetrës dhe teksti që rezulton krijohet bazuar në këtë zinxhir. Lodra rezulton të jetë shumë argëtuese!

konkluzioni

Kështu, në punën tonë të kursit po flisnim për qarkun e zinxhirit Markov. Mësuam në cilat fusha dhe si përdoret, testet e pavarura vërtetuan teoremën mbi probabilitetet kufizuese në një zinxhir Markov, dhanë shembuj për një zinxhir tipik dhe homogjen Markov, si dhe për gjetjen e matricës së tranzicionit.

Ne kemi parë se dizajni i zinxhirit Markov është një përgjithësim i drejtpërdrejtë i dizajnit të pavarur të testit.

Lista e literaturës së përdorur

1. Chistyakov V.P. Kursi i teorisë së probabilitetit. Botimi i 6-të, rev. − Shën Petersburg: Shtëpia Botuese Lan, 2003. − 272 f. − (Libër mësuesi për universitetet. Literaturë speciale).

2. Gnedenko B.V. Kursi i teorisë së probabilitetit.

3. Gmurman V.E. Teoria e Probabilitetit dhe Statistikat Matematikore.

4. Ventzel E.S. Teoria e probabilitetit dhe aplikimet e saj inxhinierike.

5. Kolmogorov A.N., Zhurbenko I.G., Prokhorov A.V. Hyrje në teorinë e probabilitetit. − Moskë-Izhevsk: Instituti i Kërkimeve Kompjuterike, 2003, 188 f.

6. Katz M. Probabiliteti dhe çështjet e lidhura me të në fizikë.

zinxhir Markov- një zinxhir ngjarjesh në të cilat probabiliteti i secilës ngjarje varet vetëm nga gjendja e mëparshme.

Ky artikull është i natyrës abstrakte, i shkruar mbi bazën e burimeve të dhëna në fund, të cilat citohen vende-vende.

Hyrje në teorinë e zinxhirëve Markov

Një zinxhir Markov është një sekuencë ngjarjesh të rastësishme në të cilat probabiliteti i secilës ngjarje varet vetëm nga gjendja në të cilën ndodhet aktualisht procesi dhe nuk varet nga gjendjet e mëparshme. Qarku përfundimtar diskret përcaktohet nga:

∑ j=1…n p ij = 1

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

ME 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ë që garanton konvergjencën në një shpërndarje stacionare është si vijon: nëse të gjithë elementët e matricës së probabilitetit të kalimit P janë pozitive, atëherë ndërsa n tenton në pafundësi, vektori p (n) tenton te vektori ρ, i cili është zgjidhja e vetme në sistemin e formës

Mund të tregohet gjithashtu se nëse, për një vlerë pozitive të n-së, të gjithë elementët e matricës P n janë pozitivë, atëherë vektori p (n) do të vazhdojë të stabilizohet.

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 si dhe sj do të jetë e barabartë me probabilitetin pi(j) të kalimit nga gjendja e parë në të dytën. Grafiku që korrespondon me matricën e treguar më sipër:

TE 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. Sidoqoftë, është më e rëndësishme të studiohet sjellja e sistemit për një interval të gjatë kohor, kur numri i tranzicioneve 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 M1 = (S5), e arritshme nga një komponent i lidhur fort që korrespondon me një nëngrup kulmesh M2 = (S1, S2, S3, S4). Shtetet që janë në klasa ergodike quhen thelbësore, dhe pjesa tjetër quhen jo thelbësore (edhe pse emra të tillë nuk përputhen mirë me sensin e shëndoshë). Gjendja absorbuese si ë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 Si, pii = 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.

Zinxhirët thithës 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 me një qark thithës, është e mundur të llogaritet numri i akseseve në blloqet e programit dhe koha e ekzekutimit të programit, e vlerësuar nga 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), nxirrni 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ë a;

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ë aksesin e burimeve të 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 pajisje periferike; tranzicioni 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 thuhet se është i pakalueshëm nëse një gjendje Sj mund të arrihet nga çdo gjendje tjetër Si 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 Sj, j = 1,…, n, fraksioni 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ë një rast të tillë, 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 për 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 modemet 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 probabilitetin e (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:

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

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, probabilitetet e kalimit të tokës pa ndikime të jashtme nga një gjendje në tjetrën mund të përfaqësohen nga zinxhiri i mëposhtëm Markov me matricën P1:

L Është e natyrshme që produktiviteti i tokës të përkeqësohet me kalimin e kohës. Për shembull, nëse vitin e kaluar gjendja e tokës ishte e kënaqshme, atëherë këtë vit ajo mund të mbetet e njëjtë ose të bëhet e keqe, por nuk do të bëhet e mirë. Sidoqoftë, kopshtari mund të ndikojë në gjendjen e tokës dhe të ndryshojë probabilitetet e kalimit në matricën P1 në ato përkatëse nga matrica P2:

T 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:

N Së fundi, kopshtari përballet me problemin se cilën strategji të zgjedhë për të maksimizuar të ardhurat mesatare të pritshme. Mund të konsiderohen dy lloje problemesh: me një numër të kufizuar dhe një numër të pafund fazash. Në këtë rast, një ditë aktiviteti i kopshtarit do të përfundojë patjetër. Për më tepër, vizualizuesit zgjidhin problemin e vendimmarrjes për një numër të kufizuar fazash. 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 për 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 fn(i) të ardhurat mesatare maksimale të pritshme që mund të merren gjatë fazave nga n deri në N përfshirëse, duke filluar nga gjendja numër i, atëherë është e lehtë të nxirret vlera e përsëritur.

Z ku k është numri i strategjisë së përdorur. Ky ekuacion bazohet në faktin se të ardhurat totale rijk + fn+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 pijk.

Tani zgjidhja optimale mund të gjendet duke llogaritur fn(i) në mënyrë sekuenciale 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 diskutohet gjithashtu në.

Modelimi i kombinimeve të fjalëve në tekst

Merrni parasysh 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 (Si) sistemi shkon në gjendjen (sj) 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 kur dimensioni i renditjes rritet në të paktën numrin mesatar të fjalëve në një frazë tipike në tekstin 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 një person, por tashmë mjaft i ngjashëm me tekstin origjinal, dhe numri i shteteve në një zinxhir të tillë do të behu i mrekullueshem.

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 motorëve të kërkimit priren të vendosin sa më shumë fjalë kyçe të kërkimit në faqet e tyre. 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ë të përdorimit të 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, modeli 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 e radhës vendosen në tabaka e shortit në një rend të caktuar. 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 ngjarjet e 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 prej një numri shumë të madh gjendjesh 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 ndërmjet grupeve të tilla të shteteve. Këto probabilitete janë një mesatare e probabiliteteve të kalimeve midis shteteve të ndryshme individuale, gjë që natyrisht zvogëlon efektivitetin e aplikimit të modelit të zinxhirit Markov në llotaritë numerike.

Ngjashëm me këtë rast, një model i tillë i rrjetit nervor mund të përdoret për të parashikuar motin, 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. Një aplikim i mirë në këtë rast, kur dihen vetëm manifestimet e sistemit, por jo gjendjet e brendshme (të fshehura), mund të aplikohet për modelet e fshehura të Markovit, të cilat diskutohen në detaje në Wikibooks (modelet e fshehura të Markovit).

Zinxhirët Markov

Prezantimi

§ 1. Zinxhiri Markov

§ 2. Zinxhiri homogjen Markov. Probabilitetet e tranzicionit. Matrica e Tranzicionit

§3. Barazia Markov

§4. Shpërndarja e palëvizshme. Teorema e probabilitetit të kufirit

§5. Vërtetimi i teoremës mbi probabilitetet kufizuese në një zinxhir Markov

§6. Aplikimet e zinxhirëve Markov

konkluzioni

Lista e literaturës së përdorur

Prezantimi

Para se të thellohemi më thellë, duhet të shqyrtojmë disa çështje ndihmëse që njihen përgjithësisht, por janë absolutisht të nevojshme për ekspozim të mëtejshëm.

Qëllimi i punës sime të kursit është të studioj më në detaje aplikimet e zinxhirëve Markov, deklarimin e problemit dhe problemet Markov.

§1. zinxhir Markov

Le të imagjinojmë se po kryhet një sekuencë testesh.

Përkufizimi. Një zinxhir Markov është një sekuencë provash, në secilën prej të cilave shfaqet një dhe vetëm një nga sa vijon.

ngjarjet e papajtueshme të grupit të plotë dhe probabiliteti i kushtëzuar që ngjarja të ndodhë në provën e tretë, me kusht që ngjarja të ketë ndodhur në provën e tretë, nuk varet nga rezultatet e provave të mëparshme.

Për shembull, nëse sekuenca e provave formon një zinxhir Markov dhe grupi i plotë përbëhet nga katër ngjarje të papajtueshme

, dhe dihet se ngjarja është shfaqur në gjykimin e gjashtë, atëherë probabiliteti i kushtëzuar që ngjarja të ndodhë në gjykimin e shtatë nuk varet se çfarë ngjarjesh janë paraqitur në gjykimin e parë, të dytë, ..., të pestë.

Shpesh, kur paraqesin teorinë e zinxhirëve Markov, ata i përmbahen një terminologjie të ndryshme dhe flasin për një sistem të caktuar fizik.

, i cili në çdo moment të kohës është në një nga gjendjet: , dhe e ndryshon gjendjen e tij vetëm në pika të veçanta të kohës, domethënë, sistemi lëviz nga një gjendje në tjetrën (për shembull, nga në ). Për zinxhirët Markov, probabiliteti për të shkuar në ndonjë gjendje për momentin varet vetëm nga ajo gjendje në të cilën ishte sistemi në këtë moment dhe nuk ndryshon sepse gjendjet e tij në momentet e mëparshme bëhen të njohura. Gjithashtu, në veçanti, pas testimit sistemi mund të mbetet në të njëjtën gjendje ("lëviz" nga një gjendje në tjetrën).

Për ta ilustruar, merrni parasysh një shembull.

Shembulli 1. Le të imagjinojmë që një grimcë e vendosur në një vijë të drejtë lëviz përgjatë kësaj vije të drejtë nën ndikimin e goditjeve të rastësishme që ndodhin në momente

. Një grimcë mund të vendoset në pika me koordinata me numra të plotë: ; Muret reflektuese janë të vendosura në pika. Çdo shtytje e lëviz grimcën në të djathtë me probabilitet dhe në të majtë me probabilitet, përveç nëse grimca është afër një muri. Nëse grimca është afër murit, atëherë çdo shtytje e lëviz atë një njësi brenda hendekut midis mureve. Këtu shohim se ky shembull i ecjes së grimcave është një zinxhir tipik Markov.

Kështu, ngjarjet quhen gjendje të sistemit, dhe testet quhen ndryshime në gjendjet e tij.

Le të përcaktojmë tani një zinxhir Markov duke përdorur terminologji të re.

Një zinxhir Markov me kohë diskrete është një qark, gjendjet e të cilit ndryshojnë në kohë të caktuara fikse.

Një zinxhir Markov me kohë të vazhdueshme është një zinxhir, gjendjet e të cilit ndryshojnë në çdo moment të mundshëm të rastësishëm në kohë.

§2. Zinxhiri homogjen Markov. Probabilitetet e tranzicionit. Matrica e Tranzicionit

Përkufizimi. Një zinxhir Markov thuhet se është homogjen nëse probabiliteti i kushtëzuar

(kalimi nga shteti në gjendje) nuk varet nga numri i testit. Prandaj, në vend që të shkruani thjesht .

Shembulli 1. Ecje e rastësishme. Le të jetë në një vijë të drejtë

në një pikë me një koordinatë numër të plotë ka një grimcë materiale. 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.

Kështu, një ecje e rastësishme është një shembull i një zinxhiri homogjen Markov me kohë diskrete.