Matrise av overgangstilstander til en Markov-kjede. Vanlige Markov-kjeder. La oss merke seg noen av funksjonene

i seg selv, og delvis vurderer vi det på grunn av at presentasjonen ikke krever innføring av et stort antall nye begreper.

Tenk på problemet med et esel som står nøyaktig mellom to høystakker: rughalm og hvetehalm (fig. 10.5).

Eselet står mellom to høystakker: «Rug» og «Hvete» (Fig. 10.5). Hvert minutt beveger han seg enten ti meter mot den første høystakken (med sannsynlighet), eller mot den andre høystakken (med sannsynlighet), eller forblir der han sto (med sannsynlighet); denne oppførselen kalles endimensjonal Tilfeldig tur. Vi vil anta at begge høystakkene er "absorberende" i den forstand at hvis et esel nærmer seg en av høystakkene, vil det forbli der. Når du kjenner avstanden mellom to høystakker og utgangsposisjonen til eselet, kan du stille flere spørsmål, for eksempel: hvilken høystakk er det mest sannsynlig at han havner på, og hva er den mest sannsynlige tiden det vil ta ham å komme dit?

Ris. 10.5.

For å utforske dette problemet mer detaljert, la oss anta at avstanden mellom støtene er femti meter og at eselet vårt er tjue meter fra "Wheat"-sjokket. Hvis steder du kan stoppe er angitt med ( - selve sjokkene), så kan dens utgangsposisjon spesifiseres av vektoren hvis komponent er lik sannsynligheten for at den opprinnelig er lokalisert i . Videre, etter ett minutt er sannsynlighetene for plasseringen beskrevet av vektoren, og etter to minutter - av vektoren. Det er klart at direkte beregning av sannsynligheten for at han er på et gitt sted etter at minutter har gått, blir vanskelig. Det viste seg at den mest praktiske måten å gjøre dette på er å gå inn overgangsmatrise.

La være sannsynligheten for at den vil flytte fra til om ett minutt. For eksempel, og. Disse sannsynlighetene kalles overgangssannsynligheter, og -matrisen kalles overgangsmatrise. Merk at hvert element i matrisen er ikke-negativt og at summen av elementene i en av radene er lik én. Av alt dette følger det at - den første radvektoren definert ovenfor, plasseringen av eselet etter ett minutt er beskrevet av radvektoren, og etter minutter - av vektoren. Med andre ord bestemmer den -te komponenten av vektoren sannsynligheten for at eselet etter minutter havner i .

Disse begrepene kan generaliseres. La oss ringe vektor av sannsynligheter en radvektor, hvis komponenter er ikke-negative og summerer seg til én. Deretter overgangsmatrise er definert som en kvadratisk matrise der hver rad er en vektor av sannsynligheter. Nå kan vi definere en Markov-kjede (eller bare en kjede) som et par , der det er - overgangsmatrise, og det er en radvektor. Hvis hvert element av betraktes som sannsynligheten for overgang fra posisjon til posisjon, og - som den opprinnelige vektoren av sannsynligheter, kommer vi til det klassiske konseptet diskret stasjonær Markov-kjede, som finnes i bøker om sannsynlighetsteori (se Feller V. Introduction to theory of probability and its applications. Vol. 1. M.: Mir. 1967) Stillingen kalles vanligvis kjedens tilstand. La oss beskrive ulike måter deres klassifiseringer.

Vi vil være interessert i følgende: er det mulig å komme seg fra en gitt stat til en annen, og i så fall på hvilken korteste tid. For eksempel, i eselproblemet kan du komme deg fra til på tre minutter, men du kan ikke komme deg fra til til i det hele tatt. Derfor vil vi i hovedsak ikke være interessert i selve sannsynlighetene, men i om de er positive eller ikke. Så er det håp om at alle disse dataene kan representeres i form av en digraf, hvis toppunkter tilsvarer tilstander, og buene indikerer om det er mulig å flytte fra en tilstand til en annen på ett minutt. Mer presist, hvis hver tilstand er representert av dens tilsvarende toppunkt).

Markov tilfeldig prosess med diskrete tilstander og diskret tid kalt en Markov-kjede . For en slik prosess, øyeblikk t 1, t 2 når systemet S kan endre sin tilstand, betraktes som påfølgende trinn i prosessen, og argumentet som prosessen avhenger av er ikke tid t, og trinnnummeret er 1, 2, k, Den tilfeldige prosessen i dette tilfellet er preget av en sekvens av tilstander S(0), S(1), S(2), S(k), Hvor S(0)- innledende tilstand av systemet (før det første trinnet); S(1)- tilstanden til systemet etter det første trinnet; S(k)- tilstanden til systemet etter k trinn...

Begivenhet ( S(k) = Si), bestående i det faktum at umiddelbart etter k av trinnet er systemet i staten S i (Jeg= 1, 2,), er en tilfeldig hendelse. Sekvens av stater S(0), S(1), S(k), kan betraktes som en sekvens av tilfeldige hendelser. Denne tilfeldige hendelsesforløpet kalles Markov kjede , hvis for hvert trinn sannsynligheten for overgang fra en hvilken som helst tilstand Si til en hvilken som helst Sj ikke avhenger av når og hvordan systemet kom til tilstanden Si. Opprinnelige tilstand S(0) kan være forhåndsbestemt eller tilfeldig.

Sannsynlighetene for Markov-kjedetilstander kalles sannsynligheter P i (k) det som kommer etter k trinn (og opp til ( k+ 1) system S vil kunne S i (Jeg = 1, 2, n). Tydeligvis for enhver k.

Innledende sannsynlighetsfordeling av Markov-kjeden kalles sannsynlighetsfordelingen av tilstander i begynnelsen av prosessen:

Pi (0), P2 (0), Pi (0), Pn (0).

I det spesielle tilfellet, hvis den opprinnelige tilstanden til systemet S nøyaktig kjent S(0) = Si, deretter den opprinnelige sannsynligheten Р i (0)= 1, og alle andre er lik null.

Sannsynligheten for overgang (overgangssannsynlighet) til k-trinn fra staten S i i en tilstand S j kalles den betingede sannsynligheten for at systemet S etter k det th trinnet vil kunne S j forutsatt at umiddelbart før (etter k- 1 trinn) hun var i en tilstand S i.

Siden systemet kan være i en av n stater, deretter for hvert øyeblikk t må stilles inn n 2 overgangssannsynligheter P ij, som er praktisk representert i form av følgende matrise:

Hvor Р ij- sannsynlighet for overgang i ett trinn fra staten S i i en tilstand S j;

P ii- sannsynlighet for systemforsinkelse i tilstanden S i.

En slik matrise kalles en overgangsmatrise eller overgangssannsynlighetsmatrise.

Hvis overgangssannsynlighetene ikke avhenger av trinnnummeret (på tid), men bare avhenger av hvilken tilstand overgangen gjøres til hvilken, vil den tilsvarende en Markov-kjede kalles homogen .

Overgangssannsynligheter for en homogen Markov-kjede Р ij danner en kvadratisk matrise av størrelse n m.

La oss merke seg noen av funksjonene:

1. Hver linje karakteriserer den valgte tilstanden til systemet, og dens elementer representerer sannsynlighetene for alle mulige overganger i ett trinn fra den valgte (fra Jeg th) tilstand, inkludert overgangen til seg selv.

2. Elementene i kolonnene viser sannsynlighetene for alle mulige overganger av systemet i ett trinn til et gitt ( j-f) tilstand (med andre ord, raden karakteriserer sannsynligheten for at systemet går over fra en tilstand, kolonnen - til en tilstand).

3. Summen av sannsynlighetene for hver rad er lik én, siden overgangene danner en komplett gruppe av inkompatible hendelser:

4. Langs hoveddiagonalen til overgangssannsynlighetsmatrisen er sannsynlighetene P ii at systemet ikke vil forlate staten S i, men vil forbli i den.

Hvis den innledende sannsynlighetsfordelingen og matrisen for overgangssannsynligheter er gitt for en homogen Markov-kjede, så angir sannsynlighetene for systemet P i (k) (jeg, j= 1, 2, n) bestemmes av den tilbakevendende formelen:

Eksempel 1. La oss vurdere prosessen med funksjon av systemet - en bil. La bilen (systemet) i løpet av ett skift (dag) være i en av to tilstander: servicebar ( S 1) og defekt ( S 2). Systemtilstandsgrafen er vist i fig. 3.2.

Ris. 3.2.Kjøretøyets tilstandsgraf

Som et resultat av masseobservasjoner av kjøretøydrift, ble følgende matrise med overgangssannsynligheter satt sammen:

Hvor P 11= 0,8 - sannsynlighet for at bilen forblir i god stand;

P 12= 0,2 - sannsynlighet for at bilen går over fra "god" tilstand til "defekt" tilstand;

P 21= 0,9 - sannsynlighet for at bilen går over fra "defekt" tilstand til "god" tilstand;

P 22= 0,1 - sannsynlighet for at bilen forblir i "defekt" tilstand.

Vektoren for initialsannsynligheter for biltilstander er gitt, dvs. P 1 (0)= 0 og R 2 (0)=1.

Det er nødvendig å bestemme sannsynlighetene for bilens tilstander etter tre dager.

Ved å bruke matrisen for overgangssannsynligheter og formel (3.1), bestemmer vi sannsynlighetene for tilstander P i (k) etter det første trinnet (etter den første dagen):

P 1 (1) = P 1 (0) × P 11 + P 2 (0) × P 21 = 0?0,8 + 1?0,9 = 0,9;

P 2 (1) = P 1 (0) × P 12 + P 2 (0) × P 22 = 0?0,2 + 1?0,1 = 0,2.

Sannsynlighetene for stater etter det andre trinnet (etter den andre dagen) er som følger:

P 1 (2) = P 1 (1) × P 11 + P 2 (1) × P 21= 0,9x0,8 + 0,1x0,9 = 0,81;

= 0,9×0,2 + 0,1×0,1 = 0,19.

Sannsynlighetene for tilstander etter det tredje trinnet (etter den tredje dagen) er like:

P 1 (3) = P 1 (2) × P 11 + P 2 (2) × P 21= 0,81×0,8 + 0,19×0,9 = 0,819;

= 0,81×0,2 + 0,19×0,1 = 0,181.

Dermed vil bilen etter den tredje dagen være i god stand med en sannsynlighet på 0,819 og i en "defekt" tilstand med en sannsynlighet på 0,181.

Eksempel 2. Under drift kan en datamaskin betraktes som et fysisk system S, som som et resultat av kontroll kan ende opp i en av følgende tilstander: S 1- Datamaskinen er fullt operativ; S 2- Datamaskinen har feil i RAM, som den kan løse problemer i; S 3- Datamaskinen har betydelige feil og kan løse en begrenset klasse problemer; S 4– Datamaskinen er helt ute av drift.

I det første øyeblikket er datamaskinen fullt operativ (stat S 1). Datamaskinen sjekkes til faste tider t 1, t 2, t 3. Prosessen som foregår i systemet S, kan betraktes som homogen Markov kjede med tre trinn (første, andre, tredje datamaskinkontroll). Overgangssannsynlighetsmatrisen har formen

Bestem sannsynlighetene for datamaskintilstander etter tre kontroller.

Løsning. Tilstandsgrafen har formen vist i fig. 3.3. Ved siden av hver pil er den tilsvarende overgangssannsynligheten. Innledende tilstandssannsynligheter P 1 (0) = 1, P2(0) = P 3 (0) = P 4 (0) = 0.

Ris. 3.3. Datamaskintilstandsgraf

Ved å bruke formel (3.1), og tar i betraktning i summen av sannsynligheter bare de tilstandene hvorfra en direkte overgang til en gitt tilstand er mulig, finner vi:

P 1 (1) = P 1 (0) × P 11= 1 x 0,3 = 0,3;

P 2 (1) = P 1 (0) × P 12= 1 x 0,4 = 0,4;

P 3 (1) = P 1 (0) × P 13= 1 x 0,1 = 0,1;

P 4 (1) = P 1 (0) × P 14= 1 x 0,2 = 0,2;

P 1 (2) = P 1 (1) × P 11= 0,3 x 0,3 = 0,09;

P 2 (2) = P 1 (1) × P 12 + P 2 (1) × P 22= 0,3x0,4 + 0,4x0,2 = 0,20;

P 3 (2) = P 1 (1) × P 13 + P 2 (1) × P 23 + P 3 (1) × P 33 = 0,27;

P 4 (2) = P 1 (1) × P 14 + P 2 (1) × P 24 + P 3 (1) × P 34 + P 4 (1) × P 44 = 0,44;

P 1 (3) = P 1 (2) × P 11= 0,09 x 0,3 = 0,027;

P 2 (3) = P 1 (2) × P 12 + P 2 (2) × P 22= 0,09×0,4 + 0,20×0,2 = 0,076;

P 3 (3) = P 1 (2) × P 13 + P 2 (2) × P 23 + P 3 (2) × P 33 = 0,217;

P 4 (3) = P 1 (2) × P 14 + P 2 (2) × P 24 + P 3 (2) × P 34 + P 4 (2) × P 44 = 0,680.

Så sannsynlighetene for datamaskintilstander etter tre kontroller er som følger: P 1 (3) = 0,027; P 2 (3) = 0,076; P 3 (3) = 0,217; P 4 (3) = 0,680.

Oppgave 1. Et bestemt mål skytes med fire skudd om gangen t 1, t 2, t 3, t 4.

Mulig system sier: S 1- målet er uskadd; S 2- målet er litt skadet; S 3- målet fikk betydelig skade; S 4- målet er helt truffet. I det første øyeblikket er målet i en tilstand S 1. Bestem sannsynlighetene for måltilstander etter fire skudd hvis matrisen med overgangssannsynligheter har formen.

Markov-kjeder

Introduksjon

§ 1. Markov-kjeden

§ 2. Homogen Markov-kjede. Overgangssannsynligheter. Overgangsmatrise

§3. Markov likestilling

§4. Stasjonær distribusjon. Grense sannsynlighetsteorem

§5. Bevis for teoremet om begrensende sannsynligheter i en Markov-kjede

§6. Anvendelser av Markov-kjeder

Konklusjon

Liste over brukt litteratur

Introduksjon

Vårt tema kursarbeid Markov kjeder. Markov-kjeder er oppkalt etter den fremragende russiske matematikeren, Andrei Andreevich Markov, som jobbet mye med tilfeldige prosesser og ga et stort bidrag til utviklingen av dette feltet. Nylig kan du høre om bruken av Markov-kjeder på en rekke områder: moderne nettteknologi, når du analyserer litterære tekster, eller til og med når du utvikler taktikk for et fotballag. De som ikke vet hva Markov-kjeder er, kan ha følelsen av at det er noe veldig komplekst og nesten uforståelig.

Nei, det er bare motsatt. En Markov-kjede er et av de enkleste tilfellene av en sekvens av tilfeldige hendelser. Men til tross for sin enkelhet, kan den ofte være nyttig selv når man skal beskrive ganske komplekse fenomener. En Markov-kjede er en sekvens av tilfeldige hendelser der sannsynligheten for hver hendelse bare avhenger av den forrige, men ikke avhenger av tidligere hendelser.

Før vi går dypere i dybden, må vi vurdere noen få hjelpespørsmål som er generelt kjent, men som er absolutt nødvendige for videre utstilling.

Målet med kursarbeidet mitt er å studere mer detaljert bruken av Markov-kjeder, problemformulering og Markov-problemer.

§1. Markov kjede

La oss forestille oss at en sekvens av tester blir utført.

Definisjon. En Markov-kjede er en sekvens av forsøk i hver av hvilke én og bare én av de inkompatible hendelsene i hele gruppen vises, og den betingede sannsynligheten for at hendelsen inntreffer i den th prøven er , forutsatt at hendelsen skjedde i den th rettssaken , avhenger ikke av resultatene fra tidligere tester.

For eksempel, hvis sekvensen av forsøk danner en Markov-kjede og hele gruppen består av fire inkompatible hendelser, og det er kjent at hendelsen skjedde i den sjette prøven, så avhenger ikke den betingede sannsynligheten for at hendelsen skjer i den syvende prøven. på hvilke hendelser som dukket opp i den første, andre, ..., femte testen.

Merk at uavhengige tester er et spesialtilfelle av en Markov-kjede. Faktisk, hvis testene er uavhengige, avhenger ikke forekomsten av en bestemt hendelse i noen test av resultatene fra tidligere utførte tester. Det følger at begrepet en Markov-kjede er en generalisering av begrepet uavhengige forsøk.

Ofte, når de presenterer teorien om Markov-kjeder, holder de seg til en annen terminologi og snakker om et visst fysisk system, som i hvert øyeblikk er i en av tilstandene: , og endrer tilstanden bare på separate tidspunkter, som er at systemet beveger seg fra en tilstand til en annen (for eksempel fra til ). For Markov-kjeder er sannsynligheten for å gå til en hvilken som helst stat for øyeblikket avhenger bare av hvilken tilstand systemet var i for øyeblikket, og endres ikke fordi dets tilstander i tidligere øyeblikk blir kjent. Spesielt etter testen kan systemet også forbli i samme tilstand ("flytte" fra stat til stat).

For å illustrere, tenk på et eksempel.

Eksempel 1. La oss forestille oss at en partikkel plassert på en rett linje beveger seg langs denne rette linjen under påvirkning av tilfeldige sjokk som oppstår i øyeblikk . En partikkel kan være lokalisert på punkter med heltallskoordinater: ; De reflekterende veggene er plassert på punktene. Hvert trykk flytter partikkelen til høyre med sannsynlighet og til venstre med sannsynlighet, med mindre partikkelen er nær en vegg. Hvis partikkelen er nær veggen, flytter ethvert trykk den en enhet innenfor gapet mellom veggene. Her ser vi at dette eksemplet på en partikkel som går er en typisk Markov-kjede.

Dermed kalles hendelser systemets tilstander, og tester kalles endringer i dets tilstander.

La oss nå definere en Markov-kjede ved å bruke ny terminologi.

En tidsdiskret Markov-kjede er en krets hvis tilstander endres til bestemte faste tider.

En kontinuerlig-tids Markov-kjede er en kjede hvis tilstander endres på ethvert tilfeldig mulig tidspunkt.

§2. Homogen Markov-kjede. Overgangssannsynligheter. Overgangsmatrise

Definisjon. En Markov-kjede kalles homogen hvis den betingede sannsynligheten (overgang fra tilstand til tilstand) ikke er avhengig av prøvenummeret. Derfor, i stedet for å skrive enkelt .

Eksempel 1. Tilfeldig tur. La det være en materialpartikkel på en rett linje i et punkt med en heltallskoordinat. På bestemte tidspunkter opplever partikkelen sjokk. Under påvirkning av et trykk beveger partikkelen seg med sannsynlighet en enhet til høyre og med sannsynlighet en enhet til venstre. Det er klart at posisjonen (koordinaten) til en partikkel etter et sjokk avhenger av hvor partikkelen var etter det umiddelbart foregående sjokk, og ikke er avhengig av hvordan den beveget seg under påvirkning av andre tidligere sjokk.

Dermed er en tilfeldig vandring et eksempel på en homogen Markov-kjede med diskret tid.

Overgangssannsynligheten er den betingede sannsynligheten for at fra tilstanden (der systemet befant seg som et resultat av en test, uansett hvilket tall) som et resultat av neste test, vil systemet flytte til tilstanden.

Således, i betegnelsen, indikerer den første indeksen nummeret til den forrige tilstanden, og den andre indikerer nummeret til den etterfølgende tilstanden. For eksempel er sannsynligheten for overgang fra den andre tilstanden til den tredje.

La antall stater være endelig og lik .

Overgangsmatrisen til et system er en matrise som inneholder alle overgangssannsynlighetene til dette systemet:

Siden hver rad i matrisen inneholder sannsynlighetene for hendelser (overgang fra samme tilstand til enhver mulig tilstand) som danner en komplett gruppe, er summen av sannsynlighetene for disse hendelsene lik én. Med andre ord, summen av overgangssannsynlighetene for hver rad i overgangsmatrisen er lik én:

La oss gi et eksempel på overgangsmatrisen til et system som kan være i tre tilstander; overgangen fra stat til stat skjer i henhold til ordningen med en homogen Markov-kjede; overgangssannsynligheter er gitt av matrisen:

Her ser vi at hvis systemet var i tilstand, så etter å ha endret tilstanden i ett trinn, vil det forbli i samme tilstand med sannsynlighet 0,5, vil forbli i samme tilstand med sannsynlighet 0,5, vil gå inn i tilstand med sannsynlighet 0,2, deretter etter overgangen kan det ende opp i stater; den kan ikke flytte fra stat til. Den siste raden i matrisen viser oss at fra en tilstand til å gå til en av de mulige tilstandene med samme sannsynlighet på 0,1.

Basert på overgangsmatrisen til systemet kan du bygge en såkalt tilstandsgraf av systemet, den kalles også en merket tilstandsgraf. Dette er praktisk for en visuell representasjon av kretsen. La oss se på rekkefølgen for å konstruere grafer ved å bruke et eksempel.

Eksempel 2. Konstruer en tilstandsgraf ved å bruke en gitt overgangsmatrise.

Fordi matrise av fjerde orden, og følgelig har systemet 4 mulige tilstander.

Grafen indikerer ikke sannsynligheten for at systemet går over fra en tilstand til den samme. Når du vurderer spesifikke systemer, er det praktisk å først konstruere en tilstandsgraf, deretter bestemme sannsynligheten for overganger av systemet fra en tilstand til den samme (basert på kravet om at summen av elementene i radene i matrisen er lik en), og konstruer deretter en overgangsmatrise av systemet.

§3. Markov likestilling

Definisjon. La oss betegne med sannsynligheten for at systemet som et resultat av trinn (tester) vil bevege seg fra tilstand til tilstand. For eksempel er sannsynligheten for overgang i 10 trinn fra den andre tilstanden til den femte.

Vi understreker at vi får overgangssannsynlighetene

La oss sette oss en oppgave: å vite overgangssannsynlighetene, finne sannsynlighetene for at systemet går over fra tilstand til tilstand i trinn.

For dette formålet introduserer vi en mellomtilstand (mellom og ). Med andre ord vil vi anta at fra starttilstanden i trinn vil systemet bevege seg til en mellomtilstand med sannsynlighet , hvoretter det i de resterende trinnene fra mellomtilstanden vil bevege seg til slutttilstanden med sannsynlighet .

Ved å bruke totalsannsynlighetsformelen får vi

. (1)

Denne formelen kalles Markovs likhet.

Forklaring. La oss introdusere følgende notasjon:

– hendelsen vi er interessert i (i trinn vil systemet gå fra starttilstand til slutttilstand), derfor, ; − hypoteser (i trinn vil systemet bevege seg fra starttilstand til mellomtilstand), derfor − betinget sannsynlighet for forekomst, forutsatt at hypotesen fant sted (i trinn vil systemet bevege seg fra mellomtilstand til slutttilstand), derfor,

I henhold til total sannsynlighetsformelen,

()

Eller i notasjonen vi har tatt i bruk

som sammenfaller med Markovs formel (1).

Når du kjenner alle overgangssannsynligheter, det vil si å kjenne overgangsmatrisen fra tilstand til tilstand i ett trinn, kan du finne sannsynlighetene for overgang fra tilstand til tilstand i to trinn, og derfor selve overgangsmatrisen; ved hjelp av en kjent matrise kan du finne overgangsmatrisen fra tilstand til tilstand i tre trinn osv.

Faktisk, å sette inn Markov-likheten

kjede av merker tilfeldig sannsynlighet

(2)

Ved å bruke formel (2) kan du derfor finne alle sannsynlighetene og derfor selve matrisen. Siden direkte bruk av formel (2) viser seg å være kjedelig, og matriseregning fører til målet raskere, vil jeg skrive relasjonene som oppstår fra (2) i matriseform:

Setter vi inn (1), får vi på samme måte

Generelt

Teorem 1. For alle s, t

(3)

Bevis. La oss beregne sannsynligheten bruke total sannsynlighetsformel (), putting

Fra likestilling

Derav fra likestilling (4) og

vi får setningen til teoremet.

La oss definere matrisen I matrise har notasjon (3) formen

Siden da hvor er overgangssannsynlighetsmatrisen. Av (5) følger det

(6)

Resultatene oppnådd i teorien om matriser gjør det mulig å bruke formel (6) for å beregne og studere deres oppførsel når

Eksempel 1. Overgangsmatrise spesifisert Finn overgangsmatrisen

Løsning. La oss bruke formelen

Ved å multiplisere matrisene får vi til slutt:

§4. Stasjonær distribusjon. Grense sannsynlighetsteorem

Sannsynlighetsfordelingen på et vilkårlig tidspunkt kan finnes ved å bruke totalsannsynlighetsformelen

(7)

Det kan vise seg at det ikke er tidsavhengig. La oss ringe stasjonær distribusjon vektor , som tilfredsstiller betingelsene

hvor er overgangssannsynlighetene.

Hvis i en Markov-kjede deretter for noen

Dette utsagnet følger av induksjon fra (7) og (8).

La oss presentere formuleringen av teoremet om begrensende sannsynligheter for en viktig klasse av Markov-kjeder.

Teorem 1. Hvis for noen >0 alle elementene i matrisen er positive, så for noen , for

, (9)

Hvor stasjonær fordeling med en viss konstant som tilfredsstiller ulikheten 0< h <1.

Siden , da i henhold til betingelsene for teoremet, fra enhver tilstand kan du komme til enhver tilstand i tide med en positiv sannsynlighet. Betingelsene for teoremet ekskluderer kjeder som på en eller annen måte er periodiske.

Hvis betingelsene i teorem 1 er oppfylt, avhenger ikke sannsynligheten for at systemet er i en viss tilstand i grensen av startfordelingen. Faktisk, fra (9) og (7) følger det at for enhver innledende distribusjon,

La oss vurdere flere eksempler på Markov-kjeder der betingelsene i teorem 1 ikke er oppfylt. Det er ikke vanskelig å verifisere at slike eksempler er eksempler. I eksemplet har overgangssannsynlighetene grenser, men disse grensene avhenger av starttilstanden. Spesielt når

I andre eksempler eksisterer åpenbart ikke sannsynlighetsområdene for.

La oss finne den stasjonære fordelingen i eksempel 1. Vi må finne vektoren tilfredsstiller betingelser (8):

;

Derfor eksisterer det en stasjonær fordeling, men ikke alle koordinatvektorer er positive.

For polynomskjemaet ble tilfeldige variabler introdusert lik antall utfall av en gitt type. La oss introdusere lignende mengder for Markov-kjeder. La være antall ganger systemet går inn i tilstanden i tide. Deretter frekvensen av systemet treffer staten. Ved å bruke formler (9) kan vi bevise at når nærmer seg . For å gjøre dette må du skaffe asymptotiske formler for og og bruke Chebyshevs ulikhet. Her er utledningen av formelen for . La oss representere det i formen

(10)

hvor, hvis og ellers. Fordi

så, ved å bruke egenskapen til matematisk forventning og formel (9), får vi

I kraft av teorem 1 er trippelleddet på høyre side av denne likheten en delsum av en konvergent rekke. Sette , vi får

Fordi det

Spesielt av formel (11), følger det at

på

Du kan også få en formel som brukes til å beregne variansen.

§5. Bevis for teoremet om begrensende sannsynligheter i en Markov-kjede

La oss først bevise to lemmas. La oss sette

Lemma 1. Det er grenser for evt

Bevis. Ved å bruke ligning (3) med får vi

Dermed er sekvensene både monotone og begrensede. Dette innebærer uttalelsen til Lemma 1.

Lemma 2. Hvis betingelsene i teorem 2 er oppfylt, er det konstanter, slik at

For enhver

hvor , betyr summering over alt som er positivt, og summering over resten . Herfra

. (12)

Siden under betingelsene i teorem 1 overgangssannsynlighetene for alle , deretter for alle

Og på grunn av det endelige antallet tilstander

La oss nå anslå forskjellen . Ved å bruke ligning (3) med , , får vi

Herfra finner vi ved å bruke (8)-(10).

Ved å kombinere dette forholdet med ulikhet (14), får vi utsagnet om lemmaet.

Gå til beviset for teoremet. Siden sekvensene er monotone, altså

0<. (15)

Fra denne og Lemma 1 finner vi

Derfor, når du får og

Positivitet følger av ulikhet (15). Går vi til grensen ved og i ligning (3), får vi som tilfredsstiller ligning (12). Teoremet er bevist.

§6. Anvendelser av Markov-kjeder

Markov-kjeder fungerer som en god introduksjon til teorien om tilfeldige prosesser, dvs. teorien om enkle sekvenser av en familie av tilfeldige variabler, vanligvis avhengig av en parameter, som i de fleste applikasjoner spiller rollen som tid. Den er først og fremst ment å beskrive både langsiktig og lokal atferd i en prosess fullstendig. Her er noen av de mest studerte problemene i denne forbindelse.

Brownsk bevegelse og dens generaliseringer - diffusjonsprosesser og prosesser med uavhengige inkrementer . Teorien om tilfeldige prosesser bidro til en utdyping av sammenhengen mellom sannsynlighetsteorien, teorien om operatorer og teorien om differensialligninger, som blant annet var viktig for fysikk og andre anvendelser. Søknader inkluderer prosesser av interesse for aktuarmessig (forsikrings-) matematikk, køteori, genetikk, trafikkkontroll, elektrisk kretsteori og inventarteori.

Martingales . Disse prosessene bevarer nok egenskaper til Markov-kjeder til at viktige ergodiske teoremer forblir gyldige for dem. Martingales skiller seg fra Markov-kjeder ved at når den nåværende tilstanden er kjent, er det bare den matematiske forventningen til fremtiden, men ikke nødvendigvis selve sannsynlighetsfordelingen som avhenger av fortiden. I tillegg til at teorien om martingaler er et viktig verktøy for forskning, har den beriket teorien om tilfeldige prosesser som oppstår i statistikk, teorien om kjernefysisk fisjon, genetikk og informasjonsteori med nye grensesetninger.

Stasjonære prosesser . Det eldste kjente ergodiske teoremet, som nevnt ovenfor, kan tolkes som et resultat som beskriver den begrensende oppførselen til en stasjonær tilfeldig prosess. En slik prosess har egenskapen at alle sannsynlighetslovene den tilfredsstiller forblir invariante med hensyn til tidsforskyvninger. Ergodesetningen, først formulert av fysikere som en hypotese, kan representeres som et utsagn om at ensemblegjennomsnittet under visse forhold faller sammen med tidsgjennomsnittet. Dette betyr at den samme informasjonen kan fås fra langtidsobservasjon av et system og fra samtidig (og øyeblikkelig) observasjon av mange uavhengige kopier av samme system. Loven om store tall er ikke noe annet enn et spesialtilfelle av Birkhoffs ergodiske teorem. Interpolering og prediksjon av oppførselen til stasjonære gaussiske prosesser, forstått i vid forstand, tjener som en viktig generalisering av klassisk minste kvadraters teori. Teorien om stasjonære prosesser er et nødvendig forskningsverktøy på mange felt, for eksempel innen kommunikasjonsteori, som omhandler studiet og opprettelsen av systemer som overfører meldinger i nærvær av støy eller tilfeldig interferens.

Markov-prosesser (prosesser uten ettervirkninger) spiller en stor rolle i modellering av køsystemer (QS), samt i modellering og valg av en strategi for å håndtere sosioøkonomiske prosesser som skjer i samfunnet.

Markov-kjeden kan også brukes til å generere tekster. Flere tekster leveres som input, deretter bygges en Markov-kjede med sannsynligheten for at ett ord følger etter det andre, og den resulterende teksten lages basert på denne kjeden. Leken viser seg å være veldig underholdende!

Konklusjon

I kursarbeidet vårt snakket vi derfor om Markov-kjedekretsen. Vi lærte på hvilke områder og hvordan det brukes, uavhengige tester beviste teoremet om begrensende sannsynligheter i en Markov-kjede, ga eksempler på en typisk og homogen Markov-kjede, samt for å finne overgangsmatrisen.

Vi har sett at Markov-kjededesignet er en direkte generalisering av det uavhengige testdesignet.

Liste over brukt litteratur

1. Chistyakov V.P. Sannsynlighetsteorikurs. 6. utgave, rev. − St. Petersburg: Lan Publishing House, 2003. − 272 s. − (Lærebok for universiteter. Spesiallitteratur).

2. Gnedenko B.V. Sannsynlighetsteorikurs.

3. Gmurman V.E. Sannsynlighetsteori og matematisk statistikk.

4. Ventzel E.S. Sannsynlighetsteori og dens tekniske anvendelser.

5. Kolmogorov A.N., Zhurbenko I.G., Prokhorov A.V. Introduksjon til sannsynlighetsteori. − Moskva-Izhevsk: Institutt for dataforskning, 2003, 188 s.

6. Katz M. Sannsynlighet og relaterte problemstillinger i fysikk.

(Andrei Andreevich Markov (1856-1922) - russisk matematiker, akademiker)

Definisjon. En prosess som skjer i et fysisk system kalles Markovsky, hvis sannsynligheten for en hvilken som helst tilstand av systemet i fremtiden bare avhenger av tilstanden til systemet i det nåværende øyeblikket og ikke avhenger av hvordan systemet kom til denne tilstanden.

Definisjon. Markov kjede kalt en sekvens av forsøk, i hver av dem bare en av de K uforenlige hendelser Ai fra hele gruppen. I dette tilfellet den betingede sannsynligheten Pij(S) hva er i S-te testen vil arrangementet komme Aj forutsatt at i ( S – 1 ) – hendelsen skjedde under testen Ai, avhenger ikke av resultatene fra tidligere tester.

Uavhengige forsøk er et spesielt tilfelle av en Markov-kjede. Arrangementene kalles Systemtilstander, og tester - Endringer i systemtilstander.

Basert på arten av endringer i stater, kan Markov-kjeder deles inn i to grupper.

Definisjon. Diskret-tids Markov-kjede Det kalles en krets hvis tilstander endres på bestemte faste tidspunkter. Kontinuerlig Markov-kjede Det kalles en krets hvis tilstander kan endres på et hvilket som helst tilfeldig tidspunkt.

Definisjon. Homogen Det kalles en Markov-kjede hvis den betingede sannsynligheten Pij overgang av systemet fra staten Jeg I staten J er ikke avhengig av testnummeret. Sannsynlighet Pij kalt Overgangssannsynlighet.

Anta at antall tilstander er endelig og lik K.

Da vil matrisen som består av betingede overgangssannsynligheter se slik ut:

Denne matrisen kalles Systemovergangsmatrise.

Siden hver rad inneholder sannsynlighetene for hendelser som danner en komplett gruppe, er det åpenbart at summen av elementene i hver rad i matrisen er lik én.

Basert på overgangsmatrisen til systemet kan man konstruere den såkalte Systemtilstandsgraf, kalles det også Merket tilstandsgraf. Dette er praktisk for en visuell representasjon av kretsen. La oss se på rekkefølgen for å konstruere grafer ved å bruke et eksempel.

Eksempel. Konstruer en tilstandsgraf ved å bruke en gitt overgangsmatrise.

Siden matrisen er av fjerde orden, har systemet derfor 4 mulige tilstander.

La Pij(N) – sannsynligheten for at som et resultat N tester systemet vil gå fra staten Jeg i en tilstand J, R – en eller annen mellomtilstand mellom stater Jeg OG J. Sannsynligheter for overgang fra en tilstand til en annen Pij(1) = Pij.

Så sannsynligheten Pij(N) kan bli funnet ved hjelp av en formel kalt Markov likestilling:

Her T– antall trinn (forsøk) der systemet gikk over fra staten Jeg I staten R.

I prinsippet er Markovs likhet ikke annet enn en lett modifisert formel for total sannsynlighet.

Å kjenne overgangssannsynlighetene (dvs. kjenne overgangsmatrisen P1), kan vi finne sannsynlighetene for overgang fra stat til stat i to trinn Pij(2) , dvs. matrise P2, å vite det - finn matrisen P3, etc.

Direkte anvendelse av formelen oppnådd ovenfor er ikke veldig praktisk, derfor kan du bruke teknikkene for matriseregning (tross alt er denne formelen i hovedsak ikke mer enn en formel for å multiplisere to matriser).

Så i generell form kan vi skrive:

Generelt er dette faktum vanligvis formulert i form av et teorem, men beviset er ganske enkelt, så jeg vil ikke gi det.

Eksempel. Overgangsmatrise spesifisert P1. Finn matrise P3.

Definisjon. Matriser hvis summen av elementer i alle rader er lik én kalles Stokastisk. Hvis for noen P alle matriseelementer Rp ikke er lik null, kalles en slik overgangsmatrise Regelmessig.

Med andre ord definerer vanlige overgangsmatriser en Markov-kjede der hver tilstand kan nås gjennom P skritt fra enhver stat. Slike Markov-kjeder kalles også Regelmessig.

Teorem. (grensesannsynlighetsteorem) La en regulær Markov-kjede med n tilstander gis og P være dens overgangssannsynlighetsmatrise. Så er det en grense og en matrise P(¥ ) har formen:

Markov-prosessen- en tilfeldig prosess som skjer i systemet, som har egenskapen: for hvert øyeblikk av tiden t 0 avhenger sannsynligheten for en hvilken som helst tilstand av systemet i fremtiden (ved t>t 0) bare av tilstanden i nåtiden (kl. t = t 0) og er ikke avhengig av når og hvordan systemet kom til denne tilstanden (dvs. hvordan prosessen utviklet seg tidligere).

I praksis møter vi ofte tilfeldige prosesser som i varierende grad av tilnærming kan betraktes som markovske.

Enhver Markov-prosess er beskrevet ved bruk av tilstandssannsynligheter og overgangssannsynligheter.

Sannsynligheter for tilstander P k (t) for en Markov-prosess er sannsynlighetene for at den tilfeldige prosessen (systemet) på tidspunktet t er i tilstanden S k:

Overgangssannsynligheter for en Markov-prosess er sannsynlighetene for overgang av en prosess (system) fra en tilstand til en annen:

Markov-prosessen kalles homogen, hvis overgangssannsynlighetene per tidsenhet ikke avhenger av hvor på tidsaksen overgangen skjer.

Den enkleste prosessen er Markov kjede– Markov tilfeldig prosess med diskret tid og diskret endelig sett av tilstander.

Når de analyseres, er Markov-kjedene det tilstandsgraf, hvor alle tilstander i kjeden (systemet) og ikke-null sannsynligheter er merket i ett trinn.

En Markov-kjede kan tenkes som om et punkt som representerer et system beveger seg tilfeldig gjennom en tilstandsgraf, drar fra tilstand til tilstand i ett trinn eller forblir i samme tilstand i flere trinn.

Overgangssannsynlighetene til en Markov-kjede i ett trinn skrives i form av en matrise P=||P ij ||, som kalles overgangssannsynlighetsmatrisen eller ganske enkelt overgangsmatrisen.

Eksempel: settet med tilstander til studenter i spesialiteten er som følger:

S 1 – førsteårsstudent;

S 2 – andre år…;

S 5 – 5. års student;

S 6 - spesialist som ble uteksaminert fra et universitet;

S 7 – en person som studerte ved et universitet, men ikke ble uteksaminert.

Fra tilstand S 1 innen et år er overganger til tilstand S 2 mulig med sannsynlighet r 1 ; S 1 med sannsynlighet q 1 og S 7 med sannsynlighet p 1, og:

r 1 + q 1 + p 1 = 1.

La oss bygge en tilstandsgraf for denne Markov-kjeden og markere den med overgangssannsynligheter (ikke-null).

La oss lage en matrise med overgangssannsynligheter:

Overgangsmatriser har følgende egenskaper:

Alle elementene deres er ikke-negative;

Deres radsum er lik én.

Matriser med denne egenskapen kalles stokastiske.

Overgangsmatriser lar deg beregne sannsynligheten for en hvilken som helst Markov-kjedebane ved å brukeremet.

For homogene Markov-kjeder er ikke overgangsmatriser avhengig av tid.

Når du studerer Markov-kjeder, er de av størst interesse:

Sannsynligheter for overgang i m trinn;

Fordeling over tilstander ved trinn m→∞;

Gjennomsnittlig tid brukt i en bestemt tilstand;

Gjennomsnittlig tid for å gå tilbake til denne tilstanden.

Tenk på en homogen Markov-kjede med n tilstander. For å få sannsynligheten for overgang fra tilstand Si til tilstand S j i m trinn, i samsvar med totalsannsynlighetsformelen, bør man summere produktene av sannsynligheten for overgang fra tilstand Si til mellomtilstanden Sk i l trinn med sannsynligheten av overgang fra Sk til Sj i de resterende m-l trinnene, dvs.

Denne relasjonen er for alle i=1, …, n; j=1, …,n kan representeres som et produkt av matriser:

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

Dermed har vi:

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

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

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

som gjør det mulig å finne sannsynlighetene for overgang mellom tilstander i et hvilket som helst antall trinn, ved å kjenne overgangsmatrisen i ett trinn, nemlig P ij (m) - et element i matrisen P(m) er sannsynligheten for å bevege seg fra tilstand S i å angi S j i m trinn.

Eksempel: Været i en bestemt region veksler mellom regnfullt og tørt over lange perioder. Hvis det regner, vil det med sannsynlighet 0,7 regne neste dag; Hvis været er tørt på en bestemt dag, vil det med en sannsynlighet på 0,6 vedvare neste dag. Det er kjent at været var regnfull onsdag. Hva er sannsynligheten for at det blir regn neste fredag?

La oss skrive ned alle tilstandene til Markov-kjeden i denne oppgaven: D – regnvær, C – tørt vær.

La oss bygge en tilstandsgraf:

Svar: p 11 = p (D hæl | D avg) = 0,61.

Sannsynlighetsgrensene р 1 (m), р 2 (m),..., р n (m) for m→∞, hvis de finnes, kalles begrensende sannsynligheter for stater.

Følgende teorem kan bevises: hvis man i en Markov-kjede kan gå fra + hver tilstand (i et gitt antall trinn) til hverandre, så eksisterer de begrensende sannsynlighetene for tilstandene og avhenger ikke av systemets begynnelsestilstand .

Således, som m→∞, etableres et visst begrensende stasjonært regime i systemet, der hver av tilstandene oppstår med en viss konstant sannsynlighet.

Vektoren p, sammensatt av marginale sannsynligheter, må tilfredsstille relasjonen: p=p*P.

Gjennomsnittlig tid brukt i staten Si for tiden T er lik p i *T, hvor p i - marginal sannsynlighet for tilstand S i. Gjennomsnittlig tid for å gå tilbake til staten S i er lik .

Eksempel.

For mange økonomiske problemer er det nødvendig å kjenne vekslingen av år med visse verdier av årlige elvestrømmer. Selvfølgelig kan denne vekslingen ikke bestemmes helt nøyaktig. For å bestemme sannsynlighetene for veksling (overgang), deler vi strømmene ved å introdusere fire graderinger (systemets tilstander): først (laveste strømning), andre, tredje, fjerde (høyeste strømning). For nøyaktighetens skyld vil vi anta at den første graderingen aldri følges av den fjerde, og den fjerde av den første på grunn av opphopning av fuktighet (i bakken, reservoar, etc.). Observasjoner har vist at i en viss region er andre overganger mulige, og:

a) fra første gradering kan du flytte til hver av de midterste dobbelt så ofte som igjen til den første, dvs.

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

b) fra fjerde gradering skjer overganger til andre og tredje gradering fire og fem ganger oftere enn returer som i andre, dvs.

hardt, dvs.

i den fjerde, dvs.

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

c) fra den andre til andre graderinger kan bare være mindre hyppige: i den første - to ganger mindre, i den tredje med 25%, i den fjerde - fire ganger sjeldnere enn overgangen til den andre, dvs.

p21=0,2;p22=0,4; p 23 = 0,3; p 24 = 0,1;

d) fra tredje gradering er en overgang til andre gradering like sannsynlig som en retur til tredje gradering, og overganger til første og fjerde gradering er fire ganger mindre sannsynlig, dvs.

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

La oss lage en graf:

La oss lage en matrise med overgangssannsynligheter:

La oss finne gjennomsnittstiden mellom tørke og høyvannsår. For å gjøre dette må du finne grensefordelingen. Den eksisterer fordi betingelsen for teoremet er oppfylt (matrisen P2 inneholder ikke null elementer, dvs. i to trinn kan du gå fra hvilken som helst tilstand i systemet til en hvilken som helst annen).

Hvor p4 = 0,08; p 3 =; p 2 =; p 1 = 0,15

Frekvensen av retur til tilstand S i er lik .

Følgelig er frekvensen av tørre år i gjennomsnitt 6,85, d.v.s. 6-7 år, og regntunge år 12.