Pagina 1 van 1

Markov Ketens: communicerende classes (open en gesloten)

Geplaatst: 13 sep 2017, 09:52
door Ilona
Hoi,
Ik ben bezig met mijn opgaves en ik moet de communicerende classes van een markov keten vinden en daarnaast dan aangeven of deze open of gesloten zijn. Ik kon helaas niet bij het college zijn dankzij de NS, dus ik stel hier dan maar even mijn vraag.

Ik heb een probability transitie matrix gekregen en deze heb ik even getekend.

Afbeelding

Nu dacht ik zelf dat de communicerende classes {1,6}, {3} en {2, 4, 5} zijn. Maar dan zouden deze allemaal gesloten zijn? Klopt dit wel of mis ik wat? Ik begin namelijk heel erg te twijfelen.


Groeten,
Ilona

Re: Markov Ketens: communicerende classes (open en gesloten)

Geplaatst: 13 sep 2017, 20:26
door arie
Zie bijvoorbeeld https://en.wikipedia.org/wiki/Markov_chain#Reducibility.
Toegepast op je gerichte graaf, waarin elke pijl correspondeert met een overgangskans groter dan nul:

Toestand j is accessible (= toegankelijk) vanuit toestand i als er in je graaf een gericht pad is van i naar j.

Toestand j communicates met toestand i als er een gericht pad is van i naar j EN er ook een gericht pad is van j naar i (dus als j accessible is vanuit i en i accessible is vanuit j).
NOOT: deze paden mogen lengte nul hebben, iedere toestand communiceert dus met zichzelf.

Communicate is een equivalentierelatie tussen je states (= toestanden):
- reflexief: elke toestand is in nul stappen (= pad met lengte nul) te bereiken vanuit zichzelf
- symmetrisch: vanuit de definitie: er is een pad van i naar j EN een pad van j naar i (anders communiceert i niet met j). Dus als i communiceert met j, communiceert ook j met i.
- transitief: ALS er paden zijn van i naar j en van j naar i EN er paden zijn van j naar k en van k naar j, DAN zijn er ook paden van i naar k (ga van i naar j en dan van j naar k) en van k naar i (ga van k naar j en dan van j naar i)

De equivalentieklassen van deze relatie zijn jouw communicerende classes.
Dat heb je correct weergegeven in jouw voorbeeld:
{1,6}: je kan van 1 naar 6 EN van 6 naar 1.
Je kan ook van 1 naar 5, 2 of 3, maar dan is er telkens geen pad terug naar 1, dus 2,3 en 5 behoren niet tot deze klasse.
{3}: vanuit 3 is er geen pad naar een andere toestand, deze klasse bestaat dus uit 1 element
{2, 4, 5}: je kan van 2 naar 4 EN van 4 naar 2, van 2 naar 5 EN van 5 naar 2 EN van 4 naar 5 EN van 5 naar 4

Een communicerende klasse is closed (= gesloten) als "the probability of leaving the class is zero", ofwel: als er vanuit die klasse GEEN pad is naar een andere klasse, ofwel: er zijn vanuit een gesloten klasse geen uitgaande pijlen naar states van andere klassen.
Nog anders gezegd: als je in een van de toestanden van een gesloten klasse bent, dan kan je niet meer ontsnappen naar een andere klasse.
Is er vanuit een klasse A WEL een pad naar een andere klasse B, dan is A open.

Kan je nu in jouw voorbeeld aangeven welke klassen open en welke gesloten zijn?

Re: Markov Ketens: communicerende classes (open en gesloten)

Geplaatst: 16 sep 2017, 12:17
door Ilona
Hallo Arie,
Heel erg bedankt voor de super duidelijke, uitgebreide uitleg. Het boek was helaas veel minder duidelijk.
Ik begrijp hieruit dat {1,6} open is en dat de andere twee gesloten zijn. Het heeft mijn in ieder geval sowieso heel veel verduidelijkt.
Groeten,
Ilona