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?
Puzzels
