Statsionaarsete Markovi ahelate uurija

Üleminekumaatriksi simulaator k-sammu arenguga ja intuitsioon statsionaarse oleku kohta.

Näidisarvutus — Statsionaarsete Markovi ahelate uurija

1	0.65985
2	0.218714
3	0.121436
Kaugus statsionaarsusest	0.08893

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Statsionaarsete Markovi ahelate uurija

Jaotus on statsionaarne, kui veel üks samm ei muuda midagi: πP = π. See on üleminekumaatriksi püsipunkt — ahel liigub küll endiselt olekute vahel, kuid proportsioonid enam ei muutu.

Mida iga sümbol tähendab

P: üleminekumaatriks. Reas i ja veerus j asuv element on tõenäosus liikuda olekust i olekusse j, seega peab iga rea summa olema 1 — mida ülalolev ruudustik sinu eest kontrollib.
p(0): algjaotus: kust ahel algab. Vaikimisi väärtus (1, 0, 0) tähendab, et see algab kindlalt olekust 1.
p(k): jaotus pärast k sammu, mis saadakse igal sammul korrutades maatriksiga P.
π: statsionaarne jaotus — see, mis rahuldab tingimust πP = π.
k: mitu sammu astutakse (määratakse ülal). Trajektooritabel näitab iga jaotust alates p(0) kuni p(k).

Kust valem tuleb

Kirjuta välja, mida statsionaarsus nõuab: pärast ühte sammu on jaotus muutumatu, st πP = π.
Ümber reastatult on see π(P − I) = 0 — lineaarvõrrandisüsteem, kus on üks võrrand iga oleku kohta. Eraldi võetuna on sellel lõpmata palju lahendeid, sest lahendi iga kordne on samuti lahend.
Lisa tingimus, mis teeb sellest tõenäosusjaotuse, Σπ = 1, ja vastus on üheselt määratud. Vaikimisi maatriksi puhul on see täpselt 8/13, 3/13, 2/13 — ülal esitatud 0.615385, 0.230769, 0.153846.

Kuidas nähtut lugeda

Kolm paneeli. p(k) on koht, kus ahel pärast sinu k sammu tegelikult asub; π on see, kuhu see teel on, koos iteratsioonide arvu ja teabega selle kohta, kas see koondus; ning kaugus statsionaarsusest mõõdab nendevahelist erinevust — vaikimisi k = 8 korral 0.08893, mispõhjusel märkus ütlebki, et ahel ei ole veel täielikult segunenud. Allpool olev trajektooritabel näitab iga sammu alates (1, 0, 0).

Eeldab: Lõplik olekute hulk ja tõenäosused, mis aja jooksul ei muutu. See, et iga rea summa peab olema 1, ei ole vormindusreegel, vaid väide, et ahel peab igal sammul kuhugi edasi liikuma.
Ei kehti, kui: Ülaltoodud π on nimetatud hinnanguks põhjusel: selleni jõutakse ahelas korduvalt samme astudes — vaikimisi maatriksi puhul 83 iteratsiooni järel — ning protsess peatatakse, kui järjestikused jaotused enam ei muutu. See on arvutuslik hinnang, mitte tõestus. Täpne vastus on siin ratsionaalarvude hulk 8/13, 3/13, 2/13 ning kuvatud kümnendmurrud on need kuue kohani ümardatuna.

PageRank on täpselt seesama arvutus, tehtud kogu veebi peal 🖖

Statsionaarne jaotus ei ole ainult õpikuülesanne — Google rajati ühele sellisele. Käsitle iga veebilehte olekuna ja iga linki üleminekuna: selle tohutu ahela statsionaarne jaotus ütleb, kui sageli lõputult linke klõpsiv lugeja igale lehele satuks. See ongi PageRank. Ka kuulus summutustegur 0,85, mis saadab surfaja 15% juhtudest juhuslikule lehele, ei ole meelevaldne peenhäälestus: see tagab, et iga olek suudab jõuda igasse teise, ja just see on tingimus, mis üldse teeb statsionaarse jaotuse ühesuseks ja saavutatavaks. Ilma selleta püüaksid väljapääsuta lehed ja suletud tsüklid jalutuskäigu lõksu ja rikuksid vastuse.

Kuhu pikas plaanis paika loksub 🖖

Üleminekumaatriksi iga rida on lihtsalt tõenäosuste kogum: kui oled ühes olekus, kui tõenäoliselt hüppad järgmisel sammul igasse teise. Korruta oma praegust tõenäosusvektorit iga sammu kohta ühe korra maatriksiga P, ja arvud triivivad püsiva segu poole — statsionaarse jaotuse π poole. See segu näitab, kui suure osa ajast süsteem pikas plaanis igas olekus veedab — proovi ilma näidet ja jälgi, kuidas p(k) paika loksub.

Ainus siht, milleni ta kunagi ei jõua 🖖

Sea kahe olekuga maatriks väärtusele [[0,1],[1,0]] — münt, mis alati pöördub. Sellel on täiesti kehtiv ainus statsionaarne jaotus π = (0.5, 0.5), kuid kui alustad olekust (1, 0), põrkab p(k) igavesti 1,0 → 0,1 → 1,0 ega koondu kunagi. Just sellised perioodilised ahelad on põhjus, miks uurija võib näidata converged: no; garanteeritud koondumine nõuab aperioodilist ahelat, mitte ainult ainsat π-d.

Harjutus

Kontrolli ennast

Ennusta vastust esmalt ise ja kasuta siis ülal olevaid juhtelemente. Ava lahendus alles siis, kui oled otsustanud — just see teebki sellest harjutuse.

Vaikimisi alustab ahel kindlalt olekus 1, p(0) = (1, 0, 0). Muuda see (0, 0, 1)-ks, nii et ta alustaks hoopis olekus 3. Ennusta, millised näidud muutuvad ja millised mitte.

Näita vastust

p(k) ja kaugus muutuvad; π ja iteratsioonide arv mitte. Olekust 1 jõuab kaheksa sammu väärtusteni 0.659852, 0.218714, 0.121436, kaugus 0.08893. Olekust 3 jõuavad nad väärtusteni 0.522304, 0.255274, 0.222421, kaugus 0.18616 — kaugemale, sest olek 3 on kõige haruldasem sihtkoht. Mõlemal korral näitab π sama 83 iteratsiooni järel 0.615385, 0.230769, 0.153846. Alguspunkt otsustab, kui kaugel ahel on, mitte kunagi seda, kuhu ta läheb: πP = π mainib ainult maatriksit.
Tagasi (1, 0, 0) juurde ja tõsta nüüd sammude arvu. Mitme sammu järel näitab kaugus statsionaarsusest 0 — ja kas ahel on siis kohal?

Näita vastust

k = 80 juures on seal 0, ja ei, ei ole. Juba k = 40 juures on kaugus 0.000024; paneeli kuus kümnendkohta lihtsalt saavad enne otsa kui vahe. See ahel läheneb π-le geomeetriliselt ega jõua sinna lõpliku arvu sammudega kunagi, nii et 0 on ekraani ümardus — samal põhjusel on ka π ise märgitud hinnanguks. Võrdle k = 8-ga, kus kaugus on 0.08893 ja märkus ütleb ikka, et ahel pole läbi seganud.

Ülesanne täielikult lahendatud

Kolme olekuga ahela kaheksa sammu, alustatuna olekus 1 5 sammu
Kolme olekuga ahel, mis algas täielikult olekus 1 ja mida käitati kaheksa sammu. Leidke, kuhu see liigub ja kui palju tal on veel minna.
1. Üks samm on vektori ja maatriksi korrutis: tõenäosus olla järgmisena olekus j on summa üle i tõenäosusest olla praegu olekus i ja liikuda i → j.
  
  $p_{k + 1} = p_{k} P, p_{0} = (1, 0, 0)$
2. Kaheksa sellist sammu annavad jaotuse, mille paneel kuvab. Olekus 1 on endiselt kaks kolmandikku tõenäosusest, mida on palju, arvestades, et ahel algas sealt täieliku kindlusega.
  
  $p_{8} = (0.65985, 0.218714, 0.121436)$
3. Sihtkohaks on statsionaarne jaotus — jaotus, mille üks samm jätab muutmata. Võrrandi πP = π lahendamine tingimusel, et tõenäosuste summa on 1, annab täpsed murrud, kaheksandikud ja kolmeteistkümnendikud, mitte kümnendmurrud.
  
  $π P = π, \sum π_{i} = 1 ⟹ π = (\frac{8}{13}, \frac{3}{13}, \frac{2}{13}) = (0.615385, 0.230769, 0.153846)$
4. Nende kahe võrdlemine annab paneeli kuvatava kauguse ja see ei ole väike: pärast kaheksat sammu on ahel kokku endiselt umbes 0,089 kaugusel.
  
  $∥ p_{8} - π ∥_{1} = 0.04447 + 0.01206 + 0.03241 = 0.08893$
5. See vahe kahaneb geomeetriliselt, mida määrab maatriksi P suuruselt teine omaväärtus. Geomeetriline kahanemine tähendab, et see väheneb poole võrra kindla arvu sammude järel ega jõua lõpliku arvu sammudega kunagi nullini.
  
  $the gap shrinks like ∣ λ_{2} ∣^{k} — geometric, never zero$
Vastus

Tööriist kuvab kaheksa sammu järel 0,65985, 0,218714, 0,121436, mis on endiselt 0,08893 kaugusel statsionaarsusest. Statsionaarne jaotus on täpselt (8/13, 3/13, 2/13) ning meelespidamist vääriv tõsiasi on see, et see ei sõltu sellest, kust alustati: need samad kolm murdu on piirväärtuseks iga algjaotuse korral, mis teeb neist üleminekumaatriksi omaduse, mitte selle konkreetse käituse oma. See sõltumatus teebki statsionaarsed jaotused kasulikuks: PageRank, MCMC-sämplimine ja järjekorra täituvus tuginevad kõik sellele, et pikaajaline tulemus on üksnes üleminekureeglite omadus. Vaid sinna jõudmiseks kuluv aeg sõltub algusest.

$π = (\frac{8}{13}, \frac{3}{13}, \frac{2}{13}) is where it goes, and p_{0} does not matter$

Allikad (1)

The stationary distribution put to work on the whole web, damping factor and all: S. Brin & L. Page, “The anatomy of a large-scale hypertextual Web search engine.” Computer Networks and ISDN Systems 30, 107–117, 1998.

42Mathi meeskond · Uuendatud 2026-07-26

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Matemaatika õppetunnid →

Näiteülesanded

ergoodiline 3-olekuline ahel - Kaheksa sammu on tehtud ja näit annab L1-kauguseks endiselt 0,08893. Statsionaarne jaotus, milleni see koondub (0,615385, 0,230769, 0,153846), on täpselt 8/13, 3/13 ja 2/13. Kümnendikes kirjutatud maatriksi püsipunkt on seega kolmeteistkümnendikes, sest π saadakse võrrandi πP = π lahendamisest, mitte otse teie sisestatud elementidest.
ilm, 2 olekut - 0,666667 ja 0,333333, ning kahe olekuga ahela puhul ei pea nende leidmiseks kunagi itereerima. π saadakse kahe diagonaalivälise tõenäosuse vahetamisel ja normeerimisel: 0,4 / (0,2 + 0,4) = 2/3. Jaotusest 50/50 alustades ollakse kümne sammuga sellest 0,000035 kaugusel.
aeglaselt seguneva 3-olekuline ahel - Kolmkümmend sammu jätavad siin L1-kauguseks 0,081995. Statsionaarsusest ollakse üle kahe tuhande korra kaugemal, kui ilmaahel kümne sammuga saavutas. Põhjuseks on diagonaal: väärtuste 0,97, 0,94 ja 0,96 tõttu ei lahku ahel oma olekust peaaegu kunagi. Ahel vajas 493 astmeiteratsiooni ilmaahela 25 vastu ning π on 4/11, 4/11, 3/11.