Sie haben ein altes schottisches Schloss zu einem extrem günstigen Preis erstanden. Der Grundriss des Schlosses ist unten abgebildet. Angeblich soll es dort spuken, aber wer glaubt denn sowas?! Bei Ihrem ersten nächtlichen Aufenthalt in Ihrem neuen Schloss stellen sie allerdings fest: Es spukt tatsächlich! Der Geist des englischen Langbogenschützen Sir James Edward Roughly läuft jede Nacht in seinen Pantoffeln und mit einer Tasse Tee in der Hand durch das Schloss und kommentiert dabei das schottische Wetter („So kalt, da holt man sich ja den Tod!“).
Abbildung 1:
Sir James Edward Roughly (links) und der Grundriss des Schlosses (rechts)
Da Roughly zwar sehr freundlich ist, Sie aber jede Nacht mit seinen Kommentaren wach hält,möchten Sie Ihr Bett in einen Raum stellen, in welchem Ihr Mitbewohner möglichst selten auftaucht.Sie wissen, dass er einen soeben betretenen Raum erst im Morgengrauen wieder verlässt, und zwar mit jeweils gleicher Wahrscheinlichkeit durch je eine der Türen des Raums.
a) Modellieren Sie die Situation durch eine Markov-Kette(G,P). Es genügt, wenn SieG in grafischer Darstellung angeben und die Kanten mit den Übergangswahrscheinlichkeiten beschriften. Die Übergangsmatrix P müssen Sie nicht angeben.
b) Bestimmen Sie für jeden Raum die Wahrscheinlichkeit, dass Roughly dort auftaucht.
Hinweis: Nutzen Sie das Resultat über Irrfahrten auf ungerichteten Graphen.
c) Eines Nachts gelingt es Ihnen, Roughly in Raum 5 einzusperren und alle Türen dieses Raums zu schließen. Jetzt haben Sie zwar einen Raum weniger, aber dafür sind Sie nachts vor Roughly sicher. Ein paar Nächte später spukt es jedoch erneut. Roughlys Frau (ebenfalls ein Geist) sucht ihren Mann und wandert nun genauso wie Roughly durch das Schloss, jedoch nur durch die Räume 1 bis 4.
Sei (G′,Q) die so entstandene Markov-Kette mit den Zuständen 1, 2, 3 und 4.
i) Hat (G′,Q) eine Grenzverteilung?
ii) Wie viele stationäre Verteilungen hat (G′,Q)?
iii) Und wie viele stationäre Verteilungen hat die Markov-Kette mit der Übergangsmatrix Q²?
______________________________________________________________________________
Ansatz: a) Markov-Kette mit Pfeilen in Richtung der einzelnen Zimmer. Also von jedem Zimmer aus drei Pfeile mit W'heit 1/3, außer bei Zimmer 1 dann W'heit 1/2
b) Wenn die irrfahrt einen Knoten erreicht wird sie mit einem vi (1 <= i <= dv) fortgesetzt, wobei 1/div = 1/2 gewählt wird.
Soll man jetzt die Matrix zu der Markov-Kette aufstellen?
c) i) Uns wurde gesagt, es existiere vielleicht gar keine Grenzverteilung
ii) Auch hier erneute Unverständnis. Wurde die stationäre Verteilung nicht bereits in der Matrix berechnen ?
iii) Konvergenz: in Zweierschritten arbeiten.
Angenommen man starte in 2, dann kommt man entweder
-von 2 zu sich selbst
-von 2 nach 1 zu 3
von 2 nach 4 zu 3
von 2 nach 4 zurück zu 2
Q² ist die stationälre Verteilung.
E gilt x * Q² = x