Irrfahrten bei ungerichteten Graphen

Question

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. Dabei murmelt sie stets vor sich hin: „Seit über 1000 Jahren sage ich ihm schon, dass er nicht in nassen Leinengewändern spuken soll, aber er hört ja nicht auf mich! Jetzt hat er sich bestimmt erkältet und ich darf es ausbaden!“

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

Answer 1

Bei b) habe ich eine stabile stochastische Verteilung gesucht.

Die ist \(\vec{v_{\text{fix}}} = \begin{pmatrix} \frac{1}{7}\\[1ex] \frac{3}{14}\\[1ex] \frac{3}{14}\\[1ex] \frac{3}{14}\\[1ex] \frac{3}{14} \end{pmatrix}\)

Weil der Übergangsgraph stark zusammenhängend ist, ist \(\lim_{n\to\infty}\left(P^n\cdot\vec{v}\right)=\vec{v_{\text{fix}}}\) für jeden stochastischen Vektor \(\vec{v}\).

Nutzen Sie das Resultat über Irrfahrten auf ungerichteten Graphen.

Ich weiß nicht, welches Resultat gemeint ist.

c) i) Uns wurde gesagt, es existiere vielleicht gar keine Grenzverteilung

Ich weiß nicht genau was mit Grenzverteilung gemeint ist. Der Übergangsgraph der entstandenen Markov-Kette hat aber folgende Eigenschaft:

• Es gibt eine natürliche Zahl n>1, so dass jeder Weg von einem Raum zurück in diesen Raum als Länge ein Vielfaches von n hat (in deinem Fall ist n=2).
  

Eine solche Markov-Kette nennt man periodisch.

Für periodische Markov-Ketten mit Übergangsmatrix Q gilt:

• lim_n→∞Qⁿ exitiert nicht.

Berechne auch Q², Q³ und Q^4.

Wurde die stationäre Verteilung nicht bereits in der Matrix berechnen ?

Aufgrund meines Unwissens darüber, was eine Grenzverteilung ist, kann ich darüber keine Aussage treffen.

Eine stationäre Verteilung ist auf jeden Fall eine Verteilung v, für die gilt

• Q·v = v.

iii) Und wie viele stationäre Verteilungen hat die Markov-Kette mit der Übergangsmatrix Q²?

Laut deinen Überlegungen dazu ist Q² nicht mehr periodisch (man kann zu jedem Zeitpunkt in Raum 2 sein). Löse die GLeichung

• Q²·v = v.