Markov-ketju

On matematiikka , joka on Markovin ketju on diskreetti-aika Markov-prosessia , tai jatkuva-aikainen ja diskreetti tila-avaruus. Markov-prosessi on stokastinen prosessi, jolla on Markov-ominaisuus : tulevaisuuden ennustamiseen hyödyllinen tieto sisältyy kokonaan prosessin nykytilaan eikä ole riippuvainen aikaisemmista tiloista (järjestelmällä ei ole "muistia"). Markov-prosessit on nimetty keksijänsä Andrei Markovin mukaan .

Diskreetin ajan Markovin prosessi on sekvenssi on satunnainen muuttujien arvojen tilassa tilaan , jota huomaa seuraavassa. Arvo on prosessin tila tällä hetkellä.Sovelluksia, joissa tilatila on rajallinen tai laskettavissa, on lukemattomia: sitten puhutaan Markov-ketjusta tai erillisillä tilatiloilla varustetuista Markov-ketjuista . Markovin yleisten prosessien olennaiset ominaisuudet , esimerkiksi toistumis- ja ergodisuusominaisuudet , voidaan ilmaista tai todistaa yksinkertaisemmin erillisten tilatilan Markov-ketjujen tapauksessa . Tämä artikkeli koskee tarkalleen erillisiä tilatilan Markov-ketjuja . ${\ displaystyle X_ {0},}$ ${\ displaystyle X_ {1},}$ ${\ displaystyle X_ {2},}$ ${\ displaystyle X_ {3}, \ \ pisteet}$ $E$ $X_ {n}$ $ei.$ $E$

Andrei Markov julkaisi ensimmäiset tulokset rajallisista tilatila-Markov-ketjuista vuonna 1906 . Kolmogorov julkaisi yleistyksen laskettavaan äärettömään tilatilaan vuonna 1936 . Markov prosessit liittyvät Brownin liikettä ja ergodinen hypoteesi , kaksi aiheisiin tilastollisen fysiikan , jotka olivat erittäin tärkeitä alussa XX : nnen vuosisadan .

Heikko Markov-ominaisuus

Määritelmät

Tämä on Markov-ketjun ominaisuus: tulevaisuuden ennustamista nykyisyydestä ei tarkenneta menneisyyttä koskevilla lisätiedoilla, koska kaikki tulevaisuuden ennustamiseen hyödyllinen tieto sisältyy tämänhetkiseen tilanteeseen. prosessi. Heikossa Markov-omaisuudessa on useita vastaavia muotoja, jotka kaikki merkitsevät sitä, että havaitaan , että ehdollinen menneisyyden tuntemisen laki , eli tieto on vain funktio : $X _ {{n + 1}}$ ${\ displaystyle \ left (X_ {k} \ right) _ {0 \ leq k \ leq n},}$ $X_ {n}$ ${\ alkaa {tasattu} \ kaikki n \ geq 0, \ kaikki (i_ {0}, \ ldots, i _ {{n-1}}, i, j) & \ E ^ {{n + 2}} , \\ {\ mathbb {P}} {\ iso (} X _ {{n + 1}} = j & \ keski \, X_ {0} = i_ {0}, X_ {1} = i_ {1} , \ ldots, X _ {{n-1}} = i _ {{n-1}}, X_ {n} = i {\ Big)} = {\ mathbb {P}} \ vasemmalle (X _ {{ n + 1}} = j \ keskellä X_ {n} = i \ oikea). \ end {tasattu}}$

Markov-ketjujen yleinen muunnos on homogeeninen Markov-ketju , jolle siirtymätodennäköisyys on riippumaton : $ei$ ${\ displaystyle \ forall n \ geq 1, \ forall (i, j) \ in E ^ {2}, \ quad \ mathbb {P} (X_ {n + 1} = j \ keskellä X_ {n} = i) = \ mathbb {P} (X_ {n} = j \ keskellä X_ {n-1} = i)}$

Artikkelin loppuosassa otetaan huomioon vain homogeeniset Markov-ketjut. Kiinnostavasta epähomogeenisten Markov-ketjujen käytöstä yhdistelmällisessä optimoinnissa on artikkelissa Simuloitu hehkutus . Markovilla on vahva ominaisuus , joka liittyy ajatukseen pysähtymisajasta : tämä vahva Markov-ominaisuus on ratkaisevan tärkeä tärkeiden tulosten todistamiseksi (erilaiset toistumiskriteerit, voimakas suurten lakien määrä Markov-ketjuille). Se todetaan artikkelissa " Markovin omaisuus ".

Kriteeri

Peruskriteerinä - Antaa olla jono riippumattomia satunnaismuuttujia samaa lakia, jossa arvot tilassa , ja joko mitattavissa kartan vuonna Oletetaan, että jono on määritelty toistumisen suhteen: ${\ displaystyle Y = (Y_ {n}) _ {n \ geq 1}}$ $F$ $f$ $E \ kertaa F$ ${\ displaystyle E.}$ ${\ displaystyle X = (X_ {n}) _ {n \ geq 0}}$ $\ forall n \ geq 0, \ qquad X _ {{n + 1}} = f \ vasen (X_ {n}, Y _ {{n + 1}} \ oikea),$ ja oletetaan, että sekvenssi on riippumaton. Sitten on homogeeninen Markov-ketju. $Y$ ${\ displaystyle X_ {0}.}$ $X$

Esimerkki: pikkukuvien kerääjän ongelma :

Petit Pierre kerää jalkapallomaajoukkueen yhdentoista pelaajan muotokuvat, jotka hän löytää suklaapatukoiden pakkausten sisäpuolella olevista tarroista; joka kerta, kun hän ostaa tabletin, hänellä on 1 11 mahdollisuus löytää pelaajan muotokuva (kaikesta ). Huomaa tilan kokoelma Pierre Petit, pakkauksen avaamisen jälkeen sen e suklaapatukka. on Markov-ketju alkaen , koska se sopii edelliseen kehykseen valinnasta lähtien $k$ $k$ ${\ displaystyle X_ {n} \ in {\ mathcal {P}} ([\! [1,11] \!])}$ $ei$ ${\ displaystyle X = (X_ {n}) _ {n \ geq 0}}$ ${\ displaystyle X_ {0} = \ tyhjennä}$ ${\ displaystyle F = [\! [1,11] \!], \ E = {\ mathcal {P}} (F), \ f (x, y) = x \ cup \ {y \},}$ $X _ {{n + 1}} = X_ {n} \ kuppi \ {Y _ {{n + 1}} \},$ jossa satunnaismuuttujat ovat toisistaan riippumattomia ja yhdenmukaisia satunnaismuuttujia : ne ovat suklaapatukkaista vedettyjen vinjettien peräkkäiset numerot. Kokoelman loppuun saattamiseen tarvittava keskimääräinen aika (tässä määrä tabletteja, jotka Petit Pierren on ostettava keskimäärin kokoelmansa loppuun saattamiseksi) on yhteensä vinjettikokoelmalle, missä on kolmas harmoninen numero . Esimerkiksi suklaapatukat. ${\ displaystyle Y_ {n}}$ ${\ displaystyle [\! [1,11] \!]}$ $EI$ ${\ displaystyle N \, H_ {N},}$ ${\ displaystyle H_ {N}}$ $EI$ ${\ displaystyle 11 \, H_ {11} = 33,2 \ pistettä \ quad}$

Huomautuksia:

Markov-ominaisuus johtuu sen itsenäisyydestä, se pysyy totta, kun niillä on erilaiset lait, ja kun "toistumissuhde" riippuu riippumattomuuden lisäksi tehdyistä oletuksista on vain tarkoitus varmistaa ketjun homogeenisuus Markovin toimesta. ${\ displaystyle Y_ {i} \;}$ $Y_ {i}$ ${\ displaystyle X_ {n + 1} = f_ {n} \ vasen (X_ {n}, Y_ {n + 1} \ oikea)}$ $ei.$
Kriteeri on perustavanlaatuinen siinä mielessä, että mikä tahansa homogeeninen Markov-ketju voidaan simuloida muodon toistumisen avulla hyvin valitulle toiminnolle . Voimme jopa valita ja valita riippumattomia ja yhdenmukaisia muuttujia aikavälillä [0,1], mikä on kätevää Markov-ketjujen tutkimiseen Monte-Carlo-menetelmillä . ${\ displaystyle X_ {n + 1} = f \ vasen (X_ {n}, Y_ {n + 1} \ oikea),}$ $f$ ${\ displaystyle F = [0,1],}$ ${\ displaystyle Y_ {j}}$

Siirtymätodennäköisyydet

Määritelmä

Määritelmä - numero kutsutaan todennäköisyys valtion to tilasiirtymän yhdessä vaiheessa , tai todennäköisyys valtion to- tilasiirtymän , jos ei ole epäselvyyttä. Huomaamme usein tämän numeron ${\ displaystyle \ mathbb {P} \ vasen (X_ {1} = j \ keskellä X_ {0} = i \ oikea)}$ $i$ $j$ $i$ ${\ displaystyle j,}$ ${\ displaystyle p_ {i, j}:}$ $p _ {{i, j}} = {\ mathbb {P}} \ vasen (X _ {{1}} = j \ keskellä X_ {0} = i \ oikea).$

Perhenumeroita kutsutaan Markov-ketjun siirtymämatriisiksi , siirtymän ytimeksi tai siirtymäoperaattoriksi . ${\ displaystyle P = \ left (p_ {i, j} \ right) _ {(i, j) \ in E ^ {2}}}$

Terminologia siirtyminen matriisi on eniten käytetty, mutta se on tarkoituksenmukaista, varsinaisesti vain silloin, kun on kokonaisluku Kun on rajallinen, esimerkiksi Cardinal yksi voi aina useita elementtejä mielivaltaisesti 1 , mikä erottaa ongelma, mutta epätäydellisesti, koska tämä numerointi on vasta-intuitiivinen monissa esimerkeissä. ${\ displaystyle n \ geq 1,}$ ${\ displaystyle E = \ {1,2, \ ldots, n \}.}$ $E$ ${\ displaystyle n,}$ $E$ ${\ displaystyle n,}$

Ehrenfestin malli: kaksi koiraa ja heidän kirppunsa:

Kaksi koiraa jakaa kirput seuraavasti: joka kerralla yksi kirppuista valitaan satunnaisesti ja hyppää sitten koiralta toiselle. Järjestelmän tilaa kuvaa elementti jossa $EI$ $EI$ ${\ displaystyle x = (x_ {1}, x_ {2}, \ pisteitä, x_ {N}) \ kohteessa \ {0,1 \} ^ {N},}$ $x _ {{i}} = 0 {\ text {tai}} 1 {\ text {riippuen siitä, onko siru n}} ^ {{\ circ}} \ i {\ text {1. vai 2. koiralla .}}$

Joten on elementtejä, mutta niiden numerointi yhdestä arvoon olisi hankalaa seurata järjestelmän kehitystä, joka koostuu yhden satunnaisen koordinaatin valitsemisesta ja sen arvon muuttamisesta. Jos haluamme ymmärtää järjestelmää vähemmän yksityiskohtaisesti (koska emme pysty tunnistamaan yhtä pelimerkkiä toisesta), voimme yksinkertaisesti tutkia pelimerkkien määrää koiralla # 1, mikä merkitsee sitä, että valitsemme jälleen, ymmärtämiseksi se olisi häpeä numeroida tilat uudestaan 1: stä Huomaa, että tässä uudessa mallinnuksessa $E$ $2 ^ {N}$ $2 ^ {N}$ $EI$ $x$ ${\ displaystyle E = \ {0,1,2, \ pistettä, N \}.}$ ${\ displaystyle N + 1.}$ $p _ {{k, k + 1}} = {\ tfrac {Nk} N} {\ text {et}} p _ {{k, k-1}} = {\ tfrac {k} N},$ koska esimerkiksi pelimerkkien määrä koiran takana n ° 1 siirtyy k: sta arvoon k-1, jos se on yksi näistä k pelimerkistä, joka valitaan hypätä, "järjestelmässä" olevien N pelimerkkien joukossa . Tätä mallia kutsutaan useammin " Ehrenfest Urns -malliksi ". Tatiana ja Paul Ehrenfest esittivät sen vuonna 1907 havainnollistamaan joitain "paradokseja", jotka syntyivät syntyvän tilastomekaniikan perustassa, ja mallinnamaan vaaleanpunainen melu . Ehrenfestin uurnan malli katsoi matemaatikko Mark Kac on olla "luultavasti yksi kaikkein opettavainen malleja kaikissa fysiikan."

Sen sijaan, että numeroidaan tilat uudestaan numerosta 1, on monissa tapauksissa ergonomisempaa hyväksyä rajalliset tai äärettömät matriisit, joiden rivit ja sarakkeet on "numeroitu" käyttämällä kahden tällaisen "matriisin" tuloja ja määritetään sitten hyvin luonnollisesti mennessä ${\ displaystyle E.}$ ${\ displaystyle A = \ vasen (a_ {i, j} \ oikea) _ {(i, j) \ kohteessa E ^ {2}}}$ ${\ displaystyle B = \ left (b_ {i, j} \ right) _ {(i, j) \ in E ^ {2}}}$ $(AB) _ {{i, j}} = \ sum _ {{\ ell \ E}} a _ {{i, \ ell}} b _ {{\ ell, j}},$ analogisesti kahden neliömäisen matriisin tulon klassisemman kaavan kanssa ${\ displaystyle n,}$ $(AB) _ {{i, j}} = \ summa _ {{k = 1}} ^ {n} a _ {{i, k}} b _ {{k, j}}.$

Ominaisuudet

Lausuma - Siirtymämatriisi on stokastinen : minkä tahansa rivin ehtojen summa antaa aina 1. ${\ displaystyle P = \ left (p_ {i, j} \ right) _ {(i, j) \ in E ^ {2}}}$ $P$ $\ kaikki i \ E: ssä, \ quad \ summa _ {{j \ E}} p _ {{i, j}} = 1.$

Lausuma - Markov-ketjun laille on tunnusomaista pari, joka muodostuu sen siirtymämatriisista ja sen alkuperäisestä laista (laista ): sillä kaiken yhteisen lain antaa ${\ displaystyle X = \ vasen (X_ {n} \ oikea) _ {n \ geq 0}}$ ${\ displaystyle P,}$ $X_ {0}$ $n \ geq 1$ ${\ displaystyle (X_ {0}, X_ {1}, \ ldots, X_ {n})}$ ${\ mathbb {P}} \ vasen (X _ {{0}} = i_ {0}, X _ {{1}} = i_ {1}, \ ldots, X _ {{n-1}} = i _ {{n -1}}, X _ {{n}} = i_ {n} \ oikea) = {\ mathbb {P}} \ vasen (X _ {{0}} = i_ {0} \ oikea) \ p _ {{i_ {{0}}, i_ {1}}} \, p _ {{i _ {{1}}, i_ {2}}} \, \ ldots \, p _ {{i _ {{n-2}}, i _ {{n-1}}}} \, p _ {{i _ {{n-1}}, i_ {n}}}.$

Esittely

Induktiolla, luokassa 0, ${\ mathbb {P}} \ vasen (X _ {{0}} = i_ {0} \ right) = {\ mathbb {P}} \ left (X _ {{0}} = i_ {0} \ right ).$

Rivillä poseeraamalla ${\ displaystyle n,}$ ${\ displaystyle P_ {k} = \ mathbb {P} \ vasen (X_ {0} = i_ {0}, X_ {1} = i_ {1}, \ ldots, X_ {k-1} = i_ {k- 1}, X_ {k} = i_ {k} \ oikea),}$ ${\ frac {P_ {n}} {P _ {{n-1}}}} = {\ mathbb {P}} {\ Iso (} X _ {{n}} = i_ {n} \ keski \, X_ {0} = i_ {0}, X_ {1} = i_ {1}, \ ldots, X _ {{n-1}} = i _ {{n-1}} {\ iso)} = p _ {{i _ {{n-1}}, i_ {n}}},$ heikon Markov-ominaisuuden vuoksi, joten jos sillä on odotettu ilmaisu, niin myös. ${\ displaystyle P_ {n-1}}$ $P_ {n}$

Kun tutkimme tiettyä Markov-ketjua, sen siirtymämatriisi on yleensä hyvin määritelty ja kiinteä koko tutkimuksen ajan, mutta alkuperäinen laki voi muuttua tutkimuksen aikana ja merkintöjen on heijastettava tällä hetkellä tarkasteltavaa alkuperäistä lakia: jos sillä hetkellä Tutkimuksessa tarkastellaan Markovin alkuperäisen jakauman ketjua, joka on määritelty siihen mennessä. Todennäköisyydet ja odotukset huomioidaan . Erityisesti, jos sanomme, että Markovin ketju alkaa todennäköisyyksistä, huomataan ja odotukset huomioidaan ${\ displaystyle \ forall i \ in E, \ quad \ mathbb {P} \ left (X_ {0} = i \ right) = \ mu _ {i}, \ quad}$ ${\ displaystyle \ mathbb {P} _ {\ mu} \ vasen (\ pisteitä \ oikea), \ quad}$ ${\ displaystyle \ mathbb {E} _ {\ mu} \ vasen [\ pisteet \ oikea]. \ quad}$ ${\ displaystyle \ mathbb {P} \ vasen (X_ {0} = j \ oikea) = 1, \ quad}$ ${\ displaystyle j, \ quad}$ ${\ displaystyle \ mathbb {P} _ {j} \ vasen (\ pisteitä \ oikea), \ quad}$ ${\ displaystyle \ mathbb {E} _ {j} \ vasen [\ pisteet \ oikea]. \ quad}$

Siirtymämatriisin voimat

Sillä todennäköisyys siirtymisen vaiheessa, ei riipu : ${\ displaystyle k \ geq 1,}$ $k$ ${\ displaystyle \ mathbb {P} \ vasen (X_ {n + k} = j \ keskellä X_ {n} = i \ oikea),}$ $ei$

Ehdotus - siirtyminen matriisi vaiheet , on yhtä suuri kuin voima nnen siirtymisen matriisin Me merkille $k$ ${\ displaystyle \ left (\ mathbb {P} \ left (X_ {n + k} = j \ mid X_ {n} = i \ right) \ right) _ {(i, j) \ in E ^ {2} },}$ $k$ $P.$ $p _ {{i, j}} ^ {{(k)}} = {\ mathbb {P}} \ vasen (X _ {{n + k}} = j \ keskellä X_ {n} = i \ oikea) ,$ ja $P ^ {k} = \ vasen (p _ {{i, j}} ^ {{(k)}} \ oikea) _ {{(i, j) \ kirjaimessa E ^ {2}}}.$

Esittely

Toistumisen kautta. Luokalla 1 se on seurausta jo heikossa Markov-ominaisuudessa jo mainitussa Markov-ketjussa : ${\ mathbb {P}} \ vasen (X _ {{n + 1}} = j \ keskellä X_ {n} = i \ oikea) = {\ mathbb {P}} \ vasen (X _ {{1}} = j \ keskellä X_ {0} = i \ oikea).$

Sijoitus ${\ displaystyle k,}$ ${\ aloita {tasattu} {\ mathbb {P}} \ vasen (X_ {n} = i {\ text {ja}} X _ {{n + k}} = j \ oikea) & = \ summa _ {{ \ ell \ sisään E}} {\ mathbb {P}} \ vasen (X_ {n} = i, \, X _ {{n + k-1}} = \ ell {\ text {ja}} X _ { {n + k}} = j \ oikea) \\ & = \ summa _ {{\ \ \ \ E}}} {\ mathbb {P}} \ vasen (X_ {n} = i, \, X _ {{ n + k- 1}} = \ ell \ oikea) \ {\ mathbb {P}} \ vasen (X _ {{n + k}} = j \ keskellä X_ {n} = i, \, X _ {{ n + k-1}} = \ ell \ oikea) \\ & = \ summa _ {{\ ell \ E}} {\ mathbb {P}} \ vasen (X_ {n} = i, \, X _ {{n + k-1}} = \ ell \ oikea) \ p _ {{\ ell, j}} \\ & = {\ mathbb {P}} \ vasen (X_ {n} = i \ oikea) \ \ summa _ {{\ ell \ E}}} p _ {{i, \ ell}} ^ {{(k-1)}} \ p _ {{\ ell, j}} \\ & = {\ mathbb {P}} \ vasen (X_ {n} = i \ oikea) \ p _ {{i, j}} ^ {{(k)}}, \ end {tasattu}}$ tai

1 st tasa on kolmas selviö todennäköisyydellä ,
2 toinen tasa-arvo on määritelmän ehdollisen todennäköisyyden ,
3 : nnen tasa johtuu muoto alhainen Markovin ominaisuus,
4 nnen tasa-arvo on toistuminen omaisuutta ei ${\ displaystyle k-1,}$
5 nnen tasa-arvo on kaava tuotteen kahden "ryhmät", sovelletaan tuotteen kanssa ${\ displaystyle P ^ {k-1}}$ $P.$

Lopuksi jaamme tämän yhtälösekvenssin kaksi äärimmäistä termiä ellei tämä viimeinen termi ole nolla, jolloin voimme määritellä mielivaltaisesti, siis esimerkiksi yhtä kuin ${\ displaystyle \ mathbb {P} \ vasen (X_ {n} = i \ oikea),}$ ${\ displaystyle \ mathbb {P} \ vasen (X_ {n + k} = j \ keskellä X_ {n} = i \ oikea)}$ ${\ displaystyle p_ {i, j} ^ {(k)}.}$

Yksinkertaisesti soveltamalla kokonaistodennäköisyyskaavaa päätellään Markov-ketjun marginaalilakit.

Seuraus - Lain antaa ${\ displaystyle X_ {n + k}}$ ${\ mathbb {P}} \ vasen (X _ {{n + k}} = j \ oikea) = \ summa _ {{i \ in E}} {\ mathbb {P}} \ vasen (X _ {{ n}} = i \ oikea) p _ {{i, j}} ^ {{(k)}}.$

Erityisesti, ${\ mathbb {P}} \ vasen (X _ {{n}} = j \ oikea) = \ summa _ {{i \ in E}} {\ mathbb {P}} \ vasen (X _ {{0} } = i \ oikea) p _ {{i, j}} ^ {{(n)}}.$

Matriisikirjoituksessa, jos lain lakia pidetään viivavektorina , se muotoillaan uudelleen: ${\ displaystyle X_ {n}}$ ${\ displaystyle \ mu _ {n} = (\ mu _ {n, i}) _ {i \ E},}$ ${\ displaystyle \ mu _ {n, i} = \ mathbb {P} \ vasen (X_ {n} = i \ oikea),}$ $\ mu _ {{n + k}} = \ mu _ {{n}} P ^ {k} \ quad {\ text {et}} \ quad \ mu _ {{n}} = \ mu _ {{0 }} P ^ {n}.$

Tilojen luokitus

Sillä , sanomme, että on saavutettavissa päässä jos ja vain jos se on olemassa , että Merkitään: ${\ displaystyle (i, j) \ muodossa E ^ {2}}$ $j$ $i$ $n \ geq 0$ ${\ displaystyle \ mathbb {P} (X_ {n} = j \ keskellä X_ {0} = i)> 0.}$ $\ {j \ leftarrow i \} \ quad \ Leftightarrow \ quad \ left \ {\ olemassa n \ geq 0 {\ teksti {kuten}} p _ {{i, j}} ^ {{(n)}}> 0 \ oikea \}.$

Sanomme sen ja kommunikoimme vain ja vain, jos niitä on olemassa , ja me merkitsemme: $i$ $j$ ${\ displaystyle (n, m) \ sisään \ mathbb {N} ^ {2}}$ ${\ displaystyle \ mathbb {P} (X_ {n} = j \ keskellä X_ {0} = i)> 0}$ ${\ displaystyle \ mathbb {P} (X_ {m} = i \ keskellä X_ {0} = j)> 0.}$ $\ {j \ vasenkätinen i \} \ quad \ vasen palkki \ quad \ vasen \ {j \ vasen nuoli i {\ text {ja}} i \ vasen nuoli j \ oikea \}.$

Suhde kommunikoida , huomattava on ekvivalenssirelaatio . Kun puhumme luokasta puhuessamme Markov-ketjun tiloista, viitataan yleensä suhteen vastaavuusluokkiin . Jos kaikki valtiot kommunikoivat, Markov-ketjun sanotaan olevan lukukelvoton . ${\ displaystyle \ vasenkätinen nuoli,}$ $\ vasen suora$

Käytettävissä olevan , ilmaistun suhde ulottuu ekvivalenssiluokkiin: kahdelle luokalle ja meillä on ${\ displaystyle \ vasen nuoli,}$ $VS$ ${\ displaystyle C ^ {\ prime}}$ $\ {C \ vasen nuoli C ^ {{\ prime}} \} \ quad \ Lefrightarrow \ quad \ left \ {\ on olemassa (i, j) \ C-aikoina C ^ {{\ prime}}, \ qquad i \ leftarrow j \ right \} \ quad \ Leftightarrow \ quad \ left \ {\ forall (i, j) \ in C \ kertaa C ^ {{\ prime}}, \ qquad i \ leftarrow j \ right \}.$

Suhde on vastaavuusluokkien välinen järjestyssuhde . $\ vasen nuoli$

Luokan sanotaan olevan lopullinen, jos se ei johda mihinkään muuhun, eli jos luokka on suhteelle minimaalinen, muuten sen sanotaan olevan ohimenevä . Kuuluminen lopulliseen tai ohimenevään luokkaan vaikuttaa Markov-ketjun tilan todennäköisyysominaisuuksiin, erityisesti sen tilaan toistuvana tai ohimenevänä tilana . Viimeisten luokkien määrä ja luonne sanelevat paikallaan olevien todennäköisyyksien joukon rakenteen , joka tiivistää tarkasti Markov-ketjun asymptoottisen käyttäytymisen, kuten voidaan nähdä seuraavasta osasta ja kahdesta tämän sivun lopussa yksityiskohtaisesti esitetystä esimerkistä . ${\ displaystyle \ vasen nuoli.}$

On $M _ {{ij}} = \ vasen \ {n \ geq 1 \ | \ p _ {{i, j}} ^ {{(n)}}> 0 \ oikea \}.$

Tilan jakso on joukon GCD.Jos kaksi tilaa kommunikoi, niillä on sama jakso: voimme siis puhua tilaluokan jaksosta. Jos jakso on yhtä suuri kuin 1, luokan sanotaan olevan aperiodinen . Markov-ketjun tilojen aperiodisuus määrää lain lähentymisen kohti kiinteää todennäköisyyttä, katso sivu Markov-ketjun pysyvä todennäköisyys . $i$ ${\ displaystyle M_ {ii}.}$ $X_ {n}$

Tilojen luokittelu ja niiden jakso voidaan helposti lukea Markov-ketjukaaviosta . Jos kaikki siirtymämatriisin elementit ovat kuitenkin ehdottomasti positiivisia, Markov-ketju on pelkistämätön ja aperiodinen: Markov-ketjun graafin piirtäminen on silloin tarpeetonta.

Paikallinen laki

Määritelmä

Ei voi olla yksi tai useampia mittauksia tilasta tilaan kuten: ${\ displaystyle \ pi = (\ pi _ {i}) _ {i \ E},}$ ${\ displaystyle E,}$ $\ pi = \ pi \, P,$ tai jopa $\ for j j in E, \ qquad \ pi _ {j} = \ sum _ {{i \ in E}} \ pi _ {i} \, p _ {{i, j}}.$

Tällaista mittausta kutsutaan kiinteäksi mittaukseksi . Paikallinen mitta on siirtymämatriisin transposion ominaisfunktio , joka liittyy ominaisarvoon 1. Sitä kutsutaan kiinteäksi todennäköisyydeksi tai paikallaan olevaksi laiksi, jos se täyttää lisäedellytykset: $\ pi$

$\ kaikki i \ E, \ qquad \ pi _ {i} \ \ geq \ 0,$
$\ sum _ {{i \ in E}} \ pi _ {i} \ = \ 1.$

Termi " paikallaan " on perusteltu seuraavalla ehdotuksella:

Ehdotus - Jos ensimmäinen laki Markovin ketju (eli laki ) on kiinteä todennäköisyys sitten kaikki lain on edelleen $X_ {0}$ ${\ displaystyle \ pi,}$ ${\ displaystyle n \ geq 0,}$ $X_ {n}$ ${\ displaystyle \ pi.}$

Esittely

Tämä johtuu ominaisuuksia valtuuksia siirtymämatriisi edellä on esitetty: lain μ n ja X: n on ilmaistu funktiona lain μ 0 ja X 0 seuraavasti: tai käyttöönotto merkitsee ${\ displaystyle \ mu _ {n} = \ mu _ {0} P ^ {n} = \ pi P ^ {n},}$ ${\ displaystyle \ pi P = \ pi}$ ${\ displaystyle \ pi P ^ {n} = \ pi. \}$

Markov-ketju on paikallaan yleensä ja vain, jos sen alkuperäinen laki on paikallaan oleva todennäköisyys .

Oleminen ja ainutlaatuisuus

Diskreettien tilatila-Markov-ketjujen tapauksessa prosessin tietyt ominaisuudet määräävät, onko olemassa pysyvä todennäköisyys ja onko se ainutlaatuinen vai ei:

Markov-ketju on pelkistämätön, jos mihin tahansa tilaan pääsee mistä tahansa muusta valtiosta;
tila on toistuva positiivinen, jos odotus ensimmäisestä paluusta tähän tilaan, alkaen tästä tilasta, on rajallinen.

Jos Markov-ketjussa on ainakin yksi positiivinen toistuva tila, on olemassa kiinteä todennäköisyys. Jos on olemassa sellainen kiinteä todennäköisyys , että tila on toistuva positiivinen, ja päinvastoin. $\ pi$ ${\ displaystyle \ pi _ {i}> 0}$ $i$

Lause - Jos Markov-ketjulla on vain yksi lopullinen luokka, on enintään yksi kiinteä todennäköisyys. Sitten meillä on vastaavuus kolmen ehdotuksen välillä: ${\ displaystyle C,}$

on olemassa ainutlaatuinen kiinteä todennäköisyys, havaittu ${\ displaystyle \ pi,}$
on positiivinen toistuva tila,
kaikki lopullisen luokan tilat ovat toistuvia positiivisia.

Meillä on myös vastaavuus $\ {\ pi _ {i}> 0 \} \ Leftightarrow \ {i \ in C \} \ Lefrightarrow \ {i {\ text {on toistuva positiivinen}} \}.$

Tämä lause pätee erityisesti pelkistämättömiin Markov-ketjuihin, koska jälkimmäisillä on vain yksi luokka (joka on siten välttämättä lopullinen luokka); pelkistämättömät Markov-ketjut todistavat erityisesti ${\ displaystyle C = E.}$

Vahva laki suurista määristä ja ergoditeetista

Pelkistämättömän ja toistuvan positiivisen Markov- ketjun tapauksessa voimakas suurten lukujen laki on voimassa: funktion keskiarvo Markov-ketjun esiintymien kohdalla on yhtä suuri kuin sen keskiarvo sen pysyvän todennäköisyyden mukaan. Tarkemmin sanottuna oletuksen alla $f$ $\ sum _ {{i \ in E}} | f (i) | \, \ pi _ {i} \ <+ \ infty,$ meillä on melkein varmasti : $\ lim _ {{n}} \; {\ frac {1} {n}} \; \ sum _ {{k = 0}} ^ {{n-1}} f (X_ {k}) \ = \ \ summa _ {{i \ E}} f (i) \, \ pi _ {i} \ = \ \ pi f.$

Tapausten arvon keskiarvo on siis pitkällä aikavälillä yhtä suuri kuin kiinteän todennäköisyyden mukainen odotus. Erityisesti tämä vastaavuus on välineet sovelletaan, jos on indikaattori funktio osajoukon tila-avaruuden: $f$ $AT$ $\ lim _ {{n}} \; {\ frac {1} {n}} \; \ summa _ {{k = 0}} ^ {{n-1}} \ chi _ {A} (X_ {k }) \ = \ \ summa _ {{i \ in A}} \ \ pi _ {i} \ = \ \ pi (A).$

Tämä tekee mahdolliseksi lähestyä paikallaan olevaa todennäköisyyttä empiirisen jakauman avulla (joka on histogrammi, joka on rakennettu tietystä sekvenssistä), kuten satunnaisessa kävelyssä esteellä .

Erityisesti, jos prosessi rakennetaan ottamalla paikallaan oleva todennäköisyys alkuperäiseksi laiksi, muutos määritetään $\ theta$ $x = (x_ {0}, x_ {1}, x_ {2}, \ pistettä) \ E ^ {{{{\ mathbb {N}}}} \ quad \ rightarrow \ quad \ theta \, x = (x_ {1}, x_ {2}, x_ {3}, \ pistettä)$ säilyttää mitan, mikä tekee Markov-ketjusta mitatun dynaamisen järjestelmän . Suurten lukujen voimakas laki johtaa siihen, että Markov-ketju on ergodinen dynaaminen järjestelmä . Ergoditeetti on samalla vahvempi kuin suurten lukujen voimakas laki, koska voimme päätellä esimerkiksi, että sillä on melkein tietty raja, mutta se on myös heikompi, koska se edellyttää periaatteessa Markov-ketjun paikallaan pysymistä, mikä ei ole asia suurten lukujen voimakkaan lain mukaan. ${\ displaystyle {\ frac {1} {n}} \; \ summa _ {k = 0} ^ {n-1} f (X_ {k}, X_ {k + 1}),}$ ${\ displaystyle \ summa _ {i, j \ E} f (i, j) \, \ pi _ {i} p_ {i, j},}$

Lähentyminen kohti paikallaan olevaa lakia

Jos Markovin ketju on redusoitumaton , positiivinen toistuvia ja jaksoton, sitten konvergoi matriisi, jossa kukin rivi on ainutlaatuinen paikallaan jakelu erityisesti lain ja suppenee on itsenäisesti alkuperäisen lain tapauksessa on tila-avaruuden valmis, tämä on todistettu Perron-Frobeniuksen lauseella . Huomaa, että on luonnollista, että relaation induktion määrittelemällä sekvenssillä on mahdollisesti rajoituksena tämän muunnoksen kiinteä piste , ts. Ratkaisu yhtälöön ${\ displaystyle P ^ {k}}$ ${\ displaystyle \ pi.}$ $\ mu _ {n}$ $X_ {n}$ $\ pi$ ${\ displaystyle \ mu _ {0}.}$ ${\ displaystyle \ mu _ {n},}$ ${\ displaystyle \ mu _ {n + 1} = \ mu _ {n} P,}$ ${\ displaystyle \ pi = \ pi P.}$

Äärellinen tilatila Markov-ketjut

Jos Markov-ketju on pelkistämätön ja jos sen tilatila on rajallinen, kaikki sen tilat ovat positiivisia toistuvia. Suurten lukujen voimakas laki on silloin voimassa.

Yleisemmin sanottuna kaikki äärellisen loppuluokan elementit ovat positiivisia toistuvia, riippumatta siitä, onko tilatila äärellinen vai ääretön.

Imeytyneen Markov-ketjun lähes paikallaan olevat jakaumat

Antaa olla Markov-ketju luonnollisten numeroiden joukossa . Oletetaan, että tila 0 absorboi ja ketju absorboituu 0: ssa melkein varmasti. Antaa olla absorboitumisajan osoitteessa 0. Sanotaan, että todennäköisyys siitä on kvasistationaaristen jakauma, mikäli kaikille ja kaikille , $(X_ {n})$ ${\ displaystyle \ {0,1,2, ... \}}$ ${\ displaystyle T_ {0} = \ inf \ {n \ geq 0, X_ {n} = 0 \}}$ $\alasti$ ${\ displaystyle \ {1,2,3, ... \}}$ ${\ displaystyle j \ geq 1}$ $n \ geq 1$

{\ displaystyle \ summa _ {i \ geq 1} \ nu _ {i} \ mathbb {P} (X_ {n} = j | X_ {0} = i, T_ {0}> n) = \ nu _ { j}.}

Sanotaan, että todennäköisyys siitä on Yaglom raja jos kaikesta ja kaikkea , $\ mu$ ${\ displaystyle \ {1,2,3, ... \}}$ $i \ geq 1$ ${\ displaystyle j \ geq 1}$

{\ displaystyle \ lim _ {n \ to \ infty} \ mathbb {P} (X_ {n} = j | X_ {0} = i, T_ {0}> n) = \ mu _ {j}.}

Yaglom-raja on melkein stationaarinen jakauma . Jos se on olemassa, Yaglom-raja on ainutlaatuinen. Toisaalta jakaumia voi olla useita.

Jos on lähes paikallaan jakelu, niin on olemassa todellinen määrä sellainen, että . $\alasti$ ${\ displaystyle \ rho (\ nu) \ in] 0,1 [}$ ${\ displaystyle \ summa _ {i} \ nu _ {i} \ mathbb {P} (T_ {0}> n | X_ {0} = i) = \ rho (\ nu) ^ {n}}$

Luokitus

Yllä olevissa kaavoissa elementti ( ) on todennäköisyys siirtymisestä kohtaan . Rivin elementtien summa on aina yhtä suuri kuin 1 ja paikallaan olevan jakauman antaa siirtymämatriisin vasen ominaisvektori. $i, j$ $i$ $j$

Joskus kohtaamme siirtymämatriiseja, joissa termi ( ) on todennäköisyys siirtymisestä kohtaan , jolloin siirtymämatriisi on yksinkertaisesti tässä kuvatun transponoima . Pylvään elementtien summa on tällöin arvoltaan 1. Lisäksi järjestelmän paikallaan olevan jakauman antaa sitten siirtymämatriisin oikea oikean ominaisvektorin vasemman ominaisvektorin sijaan. $i, j$ $j$ $i$

Esimerkki: Doudou hamsteri

Hamsterin Doudou tietää vain kolme paikkaa häkissä: lastut, joissa hän nukkuu, syöttölaite, jossa hän syö, ja pyörä, jossa hän harjoittaa. Hänen päivät ovat melko samanlaisia toistensa kanssa, ja hänen toimintaansa edustaa helposti Markov-ketju. Joka minuutti hän voi joko muuttaa toimintaansa tai jatkaa tekemäänsä toimintaa. Nimissä prosessi ilman muistia ei ole lainkaan liioiteltua puhua Doudou.

Kun hän nukkuu, hänellä on 9: stä kymmenestä mahdollisuus olla heräämättä seuraavana minuuttina.
Kun hän herää, on 1: 2 mahdollisuus, että hän menee syömään, ja 1: 2 mahdollisuus, että hän menee liikuntaan.
Ateria kestää vain minuutin, minkä jälkeen hän tekee jotain muuta.
Syömisen jälkeen on 3: sta 10: ssä mahdollisuus, että hän menee juoksemaan pyörässään, mutta varsinkin 7: stä 10: stä mahdollisuudesta palata nukkumaan.
Juoksu on väsyttävää Doudoun kannalta; on 8: sta 10: ssä mahdollisuus, että hän menee takaisin nukkumaan minuutin kuluttua. Muuten hän unohtaa edelleen, että on jo hieman väsynyt.

Kaaviot

Kaaviot voivat näyttää kaikki nuolet, joista kukin edustaa siirtymän todennäköisyyttä. Se on kuitenkin luettavampi, jos:

emme piirrä nollatodennäköisyyden nuolia (siirtyminen mahdotonta);
emme piirrä silmukoita (valtion nuoli itseään kohti) . Kuitenkin niitä on olemassa; niiden todennäköisyys on epäsuora, koska tiedämme, että kustakin tilasta lähtevien nuolien todennäköisyyksien summan on oltava yhtä suuri kuin 1.

Esimerkki implisiittisillä silmukoilla
Esimerkki piirretyillä silmukoilla

Siirtymämatriisi

Siirtyminen matriisi Tämän järjestelmän on seuraava (rivit ja sarakkeet vastaavat, jotta valtioiden edustettuina siru , syöttölaite , pyörä kaavio ): $P = {\ aloita {bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\\ end {bmatrix}}$

Ennusteet

Oletetaan, että Doudou nukkuu tutkimuksen ensimmäisen minuutin aikana. ${\ mathbf {x}} ^ {{(0)}} = {\ begin {bmatrix} 1 & 0 & 0 \ end {bmatrix}}$

Minuutin kuluttua voimme ennustaa: ${\ mathbf {x}} ^ {{(1)}} = {\ mathbf {x}} ^ {{(0)}} P = {\ aloita {bmatrix} 1 & 0 ja 0 \ loppu {bmatrix}} {\ begin {bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\\ end {bmatrix}} = {\ begin {bmatrix} 0,9 & 0,05 & 0,05 \ end {bmatrix} }$

Yhden minuutin kuluttua on siis 90% mahdollisuus, että Doudou nukkuu edelleen, 5% syövästä ja 5% juoksevasta.

${\ mathbf {x}} ^ {{(2)}} = {\ mathbf {x}} ^ {{(1)}} P = {\ mathbf {x}} ^ {{(0)}} P ^ {2} = {\ begin {bmatrix} 1 & 0 & 0 \ end {bmatrix}} {\ begin {bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 & lp {bmatrix}} ^ {2} = {\ alku {bmatrix} 0,885 & 0,045 & 0,07 \ loppu {bmatrix}}$

Kahden minuutin kuluttua on 4,5% mahdollisuus, että hamsteri syö.

Yleisesti ottaen minuutteja: $ei$ ${\ mathbf {x}} ^ {{(n)}} = {\ mathbf {x}} ^ {{(n-1)}} P$ ja ${\ mathbf {x}} ^ {{(n)}} = {\ mathbf {x}} ^ {{(0)}} P ^ {n}$

Teoria osoittaa, että tietyn ajan kuluttua todennäköisyyslaki on riippumaton alkuperäisestä laista. Huomaa se : $q$ ${\ mathbf {q}} = \ lim _ {{n \ to \ infty}} {\ mathbf {x}} ^ {{(n)}}$

Saamme lähentymisen vain ja vain, jos ketju on aperiodinen ja pelkistämätön . Näin on esimerkissämme, joten voimme kirjoittaa: ${\ begin {tasattu} P & = {\ begin {bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\\ end {bmatrix}} \\ {\ mathbf {q} } P & = {\ mathbf {q}} \ qquad {\ mbox {(}} {\ mathbf {q}} {\ mbox {on muuttumaton laki suhteessa}} P {\ mbox {.)}} \ \ & = {\ mathbf {q}} I \\ {\ mathbf {q}} (IP) & = {\ mathbf {0}} \\ & = {\ mathbf {q}} \ vasemmalle ({\ begin { bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\\ end {bmatrix}} - {\ begin {bmatrix} 0,9 & 0,05 & 0,05 \\ 0,7 & 0 & 0,3 \\ 0,8 & 0 & 0,2 \\\ end {bmatrix}} \ oikea) \\ & = {\ mathbf {q}} {\ begin {bmatrix} 0,1 & -0,05 & -0,05 \\ - 0,7 & 1 & -0,3 \ \ - 0.8 & 0 & 0, 8 \\\ end {bmatrix}} \\ & = {\ begin {bmatrix} q_ {1} & q_ {2} & q_ {3} \ end {bmatrix}} {\ begin {bmatrix} 0,1 & -0, 05 & -0,05 \\ - 0,7 & 1 & -0,3 \\ - 0,8 & 0 & 0,8 \\\ end {bmatrix}} \\ & = {\ begin {bmatrix} 0 & 0 ja 0 \ loppu {bmatrix}} \ loppu {tasattu}}$

Tietäen sen saamme: $q_ {1} + q_ {2} + q_ {3} = 1$ ${\ begin {bmatrix} q_ {1} & q_ {2} & q_ {3} \ end {bmatrix}} = {\ begin {bmatrix} 0.884 & 0.0442 & 0.0718 \ end {bmatrix}}$

Doudou viettää siis 88,4% ajastaan nukkumassa, 4,42% syö ja 7,18% juoksemisessa.

Kuva mallin vaikutuksesta

Seuraava esimerkki pyrkii osoittamaan järjestelmän mallintamisen tärkeyden. Hyvä mallinnus antaa mahdollisuuden vastata monimutkaisiin kysymyksiin yksinkertaisilla laskelmilla.

Tutkimme (fiktiivistä) sivilisaatiota, joka koostuu useista sosiaaliluokista ja jossa yksilöt voivat siirtyä luokasta toiseen. Jokainen vaihe edustaa yhtä vuotta. Harkitsemme linjaa pikemminkin kuin yksilöä, jotta vältetään kaksisata-vuotisten kansalaisten saaminen. On olemassa neljä erilaista sosiaalista tilaa:

orja;
vapaa;
kansalainen;
korkea virkamies.

Tässä yrityksessä:

orjat voivat pysyä orjina tai tulla vapaiksi ihmisiksi (ostamalla vapauden tai isäntänsä vapaana vapauttamalla);
vapaat miehet voivat pysyä vapaina tai myydä vapautensa (maksaa velkansa jne.) tai jopa tulla kansalaisiksi (jälleen ansioiden tai kansalaisuuden arvon perusteella);
kansalaiset ovat eliniän kansalaisia ja välittävät kansalaisuutensa sukuluetteloonsa (voidaan uskoa, että kansalaisten lukumäärällä on taipumus kasvaa ja että tietyn ajan kuluttua kaikki ovat kansalaisia, mutta historiallisesti tämän mallin mukaisissa sivilisaatioissa kansalaiset tuhoutuvat sodat ja uudet orjat saapuvat säännöllisesti ulkomailta). He voivat myös olla ehdokkaina vuosittaisissa vaaleissa vanhemmiksi virkamiehiksi. Toimikautensa päätyttyä heidät voidaan valita uudelleen tai tulla jälleen tavallisiksi kansalaisiksi.

Esimerkin hieman monimutkaiseksi ja siten Markov-ketjujen sovellusten laajuuden osoittamiseksi katsotaan, että virkamiehet valitaan useaksi vuodeksi. Siksi yksittäisen virkamiehen tulevaisuus riippuu siitä, kuinka kauan hän on ollut virkamies. Siksi kyseessä on ei-homogeeninen Markov-ketju. Onneksi voimme helposti palata homogeeniseen ketjuun. Itse asiassa riittää, että lisätään keinotekoinen tila kutakin toimikauden vuotta kohden. Sen sijaan, että meillä olisi valtio 4: Virallinen , meillä on valtio:

4: virkamies toimikautensa alkaessa;
5: virkamies toisella toimikaudella;
jne.

Todennäköisyydet, jotka yhdistävät kaksi peräkkäistä keinotilaa (esimerkiksi kolmannen ja neljännen vuoden), ovat arvoltaan 1, koska voidaan katsoa, että mikä tahansa aloitettu toimeksianto päättyy (voisi mallintaa päinvastaista muuttamalla näiden todennäköisyyksien arvoa). Vahvistetaan toimikausi kahdeksi vuodeksi siten, että virkamiesten ehdollisuus voidaan uusia puolella vuodessa. Sitten meillä on seuraava kaavio:

Muiden kuin vuosittaisten vaalien mallintamiseksi olisi myös tarpeen lisätä fiktiivisiä valtioita (vaalivuosi, vuosi viimeisistä vaaleista jne.).

Matriisi kirjoitetaan sitten: $P$ ${\ mathbf {P}} = {\ begin {bmatrix} {\ frac {97} {98}} & {\ frac {1} {98}} & 0 & 0 & 0 \\ {\ frac {2} { 73}} ja {\ frac {65} {73}} ja {\ frac {6} {73}} & 0 ja 0 \\ 0 ja 0 & {\ frac {12} {13}} ja {\ frac { 1} {13}} & 0 \\ 0 & 0 & 0 & 0 & 1 \ \ 0 & 0 & {\ frac {7} {8}} ja {\ frac {1} {8}} ja 0 \ end {bmatrix}}$

Kuten edellä on selitetty, anna siirtymätodennäköisyys vaiheittain. Samoin on todennäköisyys olla valtiossa vuosien jälkeen suvulle, joka on osa sosiaalista luokkaa . Tietää, mitä orjasta tulee vuosien jälkeen , riittää, kun kirjoitat: $P ^ {{n}}$ $ei$ $p _ {{ij}} ^ {{n}}$ $j$ $ei$ $i$ $ei$ ${\ displaystyle {\ begin {bmatrix} 1 & 0 & 0 & 0 & 0 \ end {bmatrix}} \ kertaa \ mathbf {P} ^ {(n)} = {\ begin {bmatrix} p_ {1} ^ { (n)} & p_ {2} ^ {(n)} ja p_ {3} ^ {(n)} ja p_ {4} ^ {(n)} & p_ {5} ^ {(n)} \ end {bmatrix}}}$

Missä on todennäköisyys olla sosiaaliluokassa vuosien kuluttua tietäen, että tutkittu linja on jättänyt orjatilan? $p_ {i} ^ {{n}}$ $i$ $ei$

Jos tiedämme kunkin sosiaaliluokan numerot vuonna 0, riittää laskea: ${\ frac 1 {\ mathrm {lign {\ akuutti e} es}}} \ kertaa {\ begin {bmatrix} {\ rm {orjat}} & {\ rm {vapaa}} ja {\ rm {kansalaiset}} & {\ rm {{\ akuutti e} lus_ {1}}} ja {\ rm {{\ akuutti e} lus_ {2}}} \ loppu {bmatrix}} \ kertaa {\ mathbf P} ^ {{n}} = Y$

Saamme näin väestön jakauman eri sosiaaliluokissa ( vuosien jälkeen ). Kertomalla tämä vektori populaation kokonaismäärällä saadaan kunkin luokan luvut vuosien lopulla . $ei$ $Y$ $ei$

Esitämme nyt itsellemme seuraavan kysymyksen: " Kuinka monella rivillä vuosien lopulla korkea virkailija on jo saanut tehtävänsä päätökseen?" " $ei$

Vastaus eroaa vuosien aikana suoritettujen toimeksiantojen lukumäärästä, koska on mahdollista valita uudelleen. Tähän kysymykseen vastaaminen tuntuu vaikealta (sen pitäisi silti olla mahdollista). Itse asiassa riittää muuttamaan ongelman mallintamista. Joten siirrymme uuteen malliin vastaamaan tähän kysymykseen. (Toisaalta se ei vastaa edellisiin kysymyksiin, joten näiden kahden mallin esittely.) $ei$

Kuvaajan muokkaaminen riittää seuraavasti:

Lisätään absorboiva yläosa, koska kun viiva on suorittanut toimeksiannon, sitä ei enää oteta huomioon.

Jos jotkut lukijat ovat kriittisiä, he voivat sanoa, että malli on väärä, koska linjat valitun virkamiehen kanssa eivät enää osallistu vaaleihin. Se ei ole niin. Valittujen virkamiesten määrä on todellakin verrannollinen kansalaisten lukumäärään. Entisten vanhempien virkamiesten palauttamatta jättäminen ehdokkaiden joukkoon ei näin ollen muuta todennäköisyyttä, että kansalainen valitaan, koska tarjottujen työpaikkojen määrä on myös, koska kansalaisten väestö on pienempi. Tämän mallin avulla voit vastata tarkasti esitettyyn kysymykseen.

Siksi meillä on uusi siirtymämatriisi: ${\ mathbf {Q}} = {\ aloita {bmatrix} {\ frac {97} {98}} ja {\ frac {1} {98}} & 0 & 0 & 0 & 0 \\ {\ frac {2 } {73}} ja {\ frac {65} {73}} ja {\ frac {6} {73}} & 0 & 0 & 0 \\ 0 & 0 & {\ frac {12} {13}} & {\ frac {1} {13}} & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \ \ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 0 ja 1 \ loppu {bmatrix}}$

Suorittamalla samat laskelmat kuin edellisissä kysymyksissä, saadaan ratkaisuvektorin viimeiseltä riviltä niiden rivien prosenttiosuus, jotka ovat suorittaneet vähintään yhden toimeksiannon tai luvun (jos kerrotaan populaation kokonaismäärällä). Toisin sanoen ongelman mallintaminen uudelleen antaa mahdollisuuden vastata kysymykseen, joka näytti niin monimutkaiselta yksinkertaisen matriisin voimien laskemisen avulla.

Sovellukset

Bernoulli prosessi on yksinkertainen esimerkki Markovin ketjun.
Markovian järjestelmät ovat hyvin läsnä fysiikassa, erityisesti tilastollisessa fysiikassa . Markovian hypoteesiin vedotaan yleisesti, kun todennäköisyyksiä käytetään järjestelmän tilan mallintamiseen, olettaen kuitenkin, että järjestelmän tuleva tila voidaan päätellä menneisyydestä, jolla on melko alhainen historia.
Kuuluisa artikkeli 1948 ja Claude Shannon , matemaattinen teoria tiedonannossa , jonka lähtökohdaksi otetaan informaatioteoriaan , esitellään aluksi käsitettä entropian peräisin Markovin mallinnus Englanti kieli . Se osoittaa siis englannin kielen ennustettavuuden tason, joka on varustettu yksinkertaisella järjestysmallilla. Vaikka tällaiset mallit ovatkin yksinkertaisia, niiden avulla voidaan edustaa järjestelmien tilastollisia ominaisuuksia hyvin ja tehdä tehokkaita ennusteita kuvaamatta koko järjestelmän järjestelmää.
In puristus , Markovin mallinnus mahdollistaa toteutumista erittäin tehokas entropiakoodauksen tekniikoita, kuten aritmeettinen koodaus . Monet kuvion tunnistamisen tai tekoälyn algoritmit , kuten Viterbi-algoritmi , jota käytetään valtaosassa matkapuhelinjärjestelmistä virheenkorjaukseen, oletetaan taustalla olevaksi Markovian prosessiksi.
Googlen käyttämän verkkosivun ( PageRank ) suosioindeksin määrittää Markov-ketju. Se määritetään todennäköisyydellä olla tällä sivulla missä tahansa Markov-ketjun tilassa, joka edustaa verkkoa. Jos on tunnettujen verkkosivujen määrä ja sivulla on linkkejä, niin sen todennäköisyys siirtyä linkitetylle sivulle (johon se osoittaa) on ja kaikille muille (etuyhteydettömät sivut). Huomaa, että meillä on . Parametri on noin 0,15. $EI$ $i$ $k_ {i}$ $p_ {i} ^ {l} = {\ tfrac {1-q} {k_ {i}}} + {\ tfrac qN}$ $p_ {i} ^ {{nl}} = {\ tfrac qN}$ $k_ {i} p_ {i} ^ {l} + (N-k_ {i}) p_ {i} ^ {{nl}} = 1$ $q$
Markov-ketjut ovat keskeinen työkalu mallinnettaessa prosesseja jonoteoriassa ja tilastoissa .
Markov-ketjuja käytetään yleisesti luotettavuus laskemista varten luotettavuus ja saatavuus sekä teknisten järjestelmien , erityisesti mallinnus vian tyyppi tapahtumasekvensseihin, korjaus, kokoonpano muuttuu.
Markov-ketjut ovat perusta autovakuutusyhtiöiden vakuutusmatemaatikkojen kehittämille Bonus / Malus-järjestelmille (todennäköisyys, että vuonna n tapahtuu n onnettomuutta, riippuu t-1-onnettomuuksien määrästä)
Markov-ketjuja käytetään myös bioinformatiikassa mallinnamaan saman sekvenssin ( esimerkiksi nukleotidien ) peräkkäisten symbolien väliset suhteet , ylittäen polynomimallin. Piilotetuilla Markov-malleilla on myös erilaisia käyttötarkoituksia, kuten segmentointi (alueellisten rajojen määrittäminen erilaisilla kemiallisilla ominaisuuksilla varustetuissa geeni- tai proteiinisekvensseissä ), moninkertainen kohdistaminen , toiminnan ennustaminen tai geenien löytäminen (piilotetut Markov-mallit ovat "joustavampia" kuin tarkat tyypin aloituskodonin + useita kodoneja + lopetuskodoneja määritelmät, ja ne soveltuvat siksi paremmin eukaryooteille (intronien läsnäolon vuoksi näiden genomissa) tai pseudogeenien löytämiseen).

Huomautuksia ja viitteitä

Katso myös

Aiheeseen liittyvät artikkelit

Markov-ketjujen Monte-Carlo-menetelmä
Adjacency-matriisi
Markovin päätösongelma (MDP)
Osittain havaittavissa oleva Markovin päätösongelma (POMDP)
Satunnainen kävely
Brownin liike
Ehrenfest Urns -malli
Piilotettu Markov-malli
Jatkuva aikainen Markov-prosessi
Markov-prosessi
Markov-kiinteistö
Markov-viltti
Martingaali

Bibliografia

Bruno Sericola: Markov-ketjut - teoria, algoritmit ja sovellukset . Hermes / Lavoisier, 2013.
Sylvie Méléard: Satunnaiset mallit ekologiassa ja evoluutiossa . Springer, 2016.
Paolo Baldi, Laurent Mazliak, Pierre Priouret, Martingales ja Markov -ketjut. Perusteoria ja korjatut harjoitukset , ( ISBN 2-7056-6425-4 ) , Hermann (painokset) , 2001

Ulkoiset linkit

Philippe Gay, " Markov ja nukkuva kauneus " , Images des Mathsissa ,5. syyskuuta 2014
(en) [PDF] Charles M. Grinstead ja J. Laurie Snell, luku. ” Markov-ketjut ”, Johdatus todennäköisyyksiin , AMS
(en) Markov-ketju ihmeellinen
Korjattu harjoitukset ( WiMS n yliopiston Nizzan Sophia Antipolis )