Markovketten - Exam.pdf

Aufgabe 3)

Betrachten wir eine Markov-Kette mit den Zuständen 1, 2 und 3 und der folgenden Übergangsmatrix P: \[ P = \begin{pmatrix} 0.7 & 0.2 & 0.1 \ 0.3 & 0.4 & 0.3 \ 0.2 & 0.3 & 0.5 \ \end{pmatrix} \]

b)

Überprüfe, ob die gegebene Markov-Kette ergodisch ist. Erfüllt diese Markov-Kette die Bedingungen der Irreduzibilität und Aperiodizität?

Lösung:

Um zu überprüfen, ob die gegebene Markov-Kette ergodisch ist, müssen wir die Bedingungen der Irreduzibilität und Aperiodizität prüfen. Eine Markov-Kette ist ergodisch, wenn sie sowohl irreduzibel als auch aperiodisch ist.

• Irreduzibilität:

Eine Markov-Kette ist irreduzibel, wenn es möglich ist, von jedem Zustand jeden anderen Zustand zu erreichen.

Die Übergangsmatrix ist:

P = \begin{pmatrix} 0.7 & 0.2 & 0.1 \ 0.3 & 0.4 & 0.3 \ 0.2 & 0.3 & 0.5 \end{pmatrix}

Wir prüfen die Erreichbarkeit:

• Von Zustand 1 zu Zustand 2 und 3:
• 1 -> 2: Wahrscheinlichkeit 0.2
• 1 -> 3: Wahrscheinlichkeit 0.1
• 1 -> 2 -> 3: Wahrscheinlichkeit 0.2 * 0.3 = 0.06
• 1 -> 3 -> 2: Wahrscheinlichkeit 0.1 * 0.3 = 0.03
• Von Zustand 2 zu Zustand 1 und 3:
• 2 -> 1: Wahrscheinlichkeit 0.3
• 2 -> 3: Wahrscheinlichkeit 0.3
• 2 -> 1 -> 3: Wahrscheinlichkeit 0.3 * 0.1 = 0.03
• 2 -> 3 -> 1: Wahrscheinlichkeit 0.3 * 0.2 = 0.06
• Von Zustand 3 zu Zustand 1 und 2:
• 3 -> 1: Wahrscheinlichkeit 0.2
• 3 -> 2: Wahrscheinlichkeit 0.3
• 3 -> 1 -> 2: Wahrscheinlichkeit 0.2 * 0.2 = 0.04
• 3 -> 2 -> 1: Wahrscheinlichkeit 0.3 * 0.3 = 0.09

Da es von jedem Zustand möglich ist, jeden anderen Zustand zu erreichen (direkt oder über andere Zustände), ist die Kette irreduzibel.

• Aperiodizität:

Eine Markov-Kette ist aperiodisch, wenn der größte gemeinsame Teiler der Perioden aller Zustände 1 ist. Dies bedeutet, dass für jeden Zustand eine Rückkehrmöglichkeit mit verschieden langen Zyklen existiert (insbesondere muss ein 1-Zyklus existieren oder die Zyklen verschiedenen Längen haben, deren größter gemeinsamer Teiler 1 ist).

Wir überprüfen dies auf Basis der Diagonaleinträge der Übergangsmatrix:

• Zustand 1: 0.7 (Rückkehrmöglichkeit in einem Schritt)
• Zustand 2: 0.4 (Rückkehrmöglichkeit in einem Schritt)
• Zustand 3: 0.5 (Rückkehrmöglichkeit in einem Schritt)

Da jeder Zustand eine positive Wahrscheinlichkeit hat, zu sich selbst zurückzukehren (direkt in einem Schritt), sind alle Zustände aperiodisch.

Da die gegebene Markov-Kette sowohl irreduzibel als auch aperiodisch ist, gilt sie als ergodisch.

Fazit: Die gegebene Markov-Kette ist ergodisch, weil sie sowohl irreduzibel als auch aperiodisch ist.

Aufgabe 4)

Betrachte eine Markov-Kette mit den Zuständen \( S = \{0, 1, 2, 3 \} \) und der Übergangsmatrix \( P = \begin{pmatrix} 0.5 & 0.5 & 0 & 0 \ 0.25 & 0.5 & 0.25 & 0 \ 0 & 0.25 & 0.5 & 0.25 \ 0 & 0 & 0.5 & 0.5 \end{pmatrix} \). Diese Markov-Kette stellt eine einfache Modellierung von Zustandsübergängen dar, wobei vom aktuellen Zustand nur der nächste Zustand abhängt.

a)

Überprüfe, ob die gegebene Übergangsmatrix eine gültige stochastische Matrix ist. Begründe Deine Antwort ausführlich.

• Hinweis: Eine stochastische Matrix erfüllt die Eigenschaft, dass alle Einträge zwischen 0 und 1 liegen und die Summe jeder Zeile gleich 1 ist.

Lösung:

Um zu überprüfen, ob die gegebene Übergangsmatrix eine gültige stochastische Matrix ist, müssen wir zwei Hauptbedingungen prüfen:

• Alle Einträge müssen zwischen 0 und 1 liegen.
• Die Summe jeder Zeile muss gleich 1 sein.

Die gegebene Übergangsmatrix ist:

 P = \begin{pmatrix} 0.5 & 0.5 & 0 & 0 \ 0.25 & 0.5 & 0.25 & 0 \ 0 & 0.25 & 0.5 & 0.25 \ 0 & 0 & 0.5 & 0.5 \end{pmatrix} 

• Überprüfe die Einträge:
• Für die erste Zeile: 0.5, 0.5, 0, 0
• Für die zweite Zeile: 0.25, 0.5, 0.25, 0
• Für die dritte Zeile: 0, 0.25, 0.5, 0.25
• Für die vierte Zeile: 0, 0, 0.5, 0.5

Alle Einträge der Matrix sind Zahlen im Bereich von 0 bis 1. Diese Bedingung ist erfüllt.

• Berechne die Summe jeder Zeile:
• Für die erste Zeile: 0.5 + 0.5 + 0 + 0 = 1
• Für die zweite Zeile: 0.25 + 0.5 + 0.25 + 0 = 1
• Für die dritte Zeile: 0 + 0.25 + 0.5 + 0.25 = 1
• Für die vierte Zeile: 0 + 0 + 0.5 + 0.5 = 1

Die Summe jeder Zeile der Matrix ist 1. Auch diese Bedingung ist erfüllt.

Da sowohl alle Einträge zwischen 0 und 1 liegen als auch die Summe jeder Zeile gleich 1 ist, ist die gegebene Übergangsmatrix eine gültige stochastische Matrix.

c)

Überprüfe, ob die gegebene Markov-Kette ergodisch ist. Begründe Deine Antwort mit Hilfe der Konzepte der Irreduzibilität und Aperiodizität.

• Hinweis: Eine Markov-Kette ist ergodisch, wenn sie irreduzibel und aperiodisch ist.

Lösung:

Um zu überprüfen, ob die gegebene Markov-Kette ergodisch ist, müssen wir die Konzepte der Irreduzibilität und Aperiodizität anwenden. Eine Markov-Kette ist ergodisch, wenn sie irreduzibel und aperiodisch ist.

Irreduzibilität

Eine Markov-Kette ist irreduzibel, wenn es möglich ist, von jedem Zustand jeden anderen Zustand in endlich vielen Schritten zu erreichen. Wir betrachten die Übergangsmatrix:

 P = \begin{pmatrix} 0.5 & 0.5 & 0 & 0 \ 0.25 & 0.5 & 0.25 & 0 \ 0 & 0.25 & 0.5 & 0.25 \ 0 & 0 & 0.5 & 0.5 \end{pmatrix} 

Um zu überprüfen, ob die Markov-Kette irreduzibel ist, müssen wir feststellen, ob es von jedem Zustand aus eine positive Wahrscheinlichkeit gibt, jeden anderen Zustand zu erreichen.

• Von Zustand 0 kann man in einem Schritt nach 1 gehen (0.5) oder im Zustand 0 bleiben (0.5).
• Von Zustand 1 kann man in einem Schritt nach 0 (0.25), 1 (0.5) oder 2 (0.25) gehen.
• Von Zustand 2 kann man in einem Schritt nach 1 (0.25), 2 (0.5) oder 3 (0.25) gehen.
• Von Zustand 3 kann man in einem Schritt nach 2 (0.5) oder im Zustand 3 bleiben (0.5).

Da der Übergang von einem Zustand zum anderen nur eine begrenzte Anzahl von Schritten erfordert, ist die gegebene Markov-Kette irreduzibel.

Aperiodizität

Eine Markov-Kette ist aperiodisch, wenn es keinen periodischen Zyklus gibt, d.h., es gibt keinen Zustand, der nur nach einer festen Anzahl von Schritten erreichbar ist. Wir überprüfen, ob es für alle Zustände einen Zeitpunkt gibt, an dem die Wahrscheinlichkeit des Übergangs zu sich selbst größer als null ist:

• Zustand 0: Man kann in jedem Schritt im Zustand 0 bleiben (0.5).
• Zustand 1: Man kann in jedem Schritt im Zustand 1 bleiben (0.5).
• Zustand 2: Man kann in jedem Schritt im Zustand 2 bleiben (0.5).
• Zustand 3: Man kann in jedem Schritt im Zustand 3 bleiben (0.5).

Da es für alle Zustände eine positive Wahrscheinlichkeit gibt, nach einer unterschiedlichen Anzahl von Schritten zum Zustand zurückzukehren, ist die Kette aperiodisch.

Ergebnis

Da die gegebene Markov-Kette sowohl irreduzibel als auch aperiodisch ist, ist sie ergodisch.

d)

Angenommen, Zustand 3 ist ein absorbierender Zustand (d.h. vom Zustand 3 gibt es keine Übergänge zu anderen Zuständen). Bestimme die erwartete Zeit bis zur Absorption, wenn die Kette in Zustand 0 beginnt.

• Hinweis: Verwende die Methode der fundamentalen Matrix.

Lösung:

Um die erwartete Zeit bis zur Absorption in Zustand 3 zu bestimmen, beginnen wir in Zustand 0 und verwenden die Methode der fundamentalen Matrix. Zunächst müssen wir die Übergangsmatrix anpassen, damit der Zustand 3 als absorbierender Zustand behandelt wird. Das bedeutet, dass alle Übergangswahrscheinlichkeiten von Zustand 3 zu 3 geändert werden, d.h., die Wahrscheinlichkeit vom Zustand 3 zu einem anderen Zustand geht auf 0 und vom Zustand 3 zu Zustand 3 ist 1:

P = \begin{pmatrix} 0.5 & 0.5 & 0 & 0 \ 0.25 & 0.5 & 0.25 & 0 \ 0 & 0.25 & 0.5 & 0.25 \ 0 & 0 & 0 & 1 \end{pmatrix}

Nun müssen wir den Übergangsunterblock für die transienten Zustände extrahieren, d.h., die Zeilen und Spalten, die den absorbierenden Zustand ausschließen:

Q = \begin{pmatrix} 0.5 & 0.5 & 0 \ 0.25 & 0.5 & 0.25 \ 0 & 0.25 & 0.5 \end{pmatrix}

Um die fundamentale Matrix \(N\) zu berechnen, verwenden wir die Formel:

N = (I - Q)^{-1}

Dabei ist \(I\) die Einheitsmatrix. Lass uns die Matrix \(I - Q\) berechnen:

I - Q = \begin{pmatrix} 1 & 0 & 0 \ 0 & 1 & 0 \ 0 & 0 & 1 \end{pmatrix} - \begin{pmatrix} 0.5 & 0.5 & 0 \ 0.25 & 0.5 & 0.25 \ 0 & 0.25 & 0.5 \end{pmatrix} = \begin{pmatrix} 0.5 & -0.5 & 0 \ -0.25 & 0.5 & -0.25 \ 0 & -0.25 & 0.5 \end{pmatrix}

Nun berechnen wir die Inverse von \(I - Q\):

N = (I - Q)^{-1}

Um die Inverse zu finden, verwenden wir eine numerische Methode oder Matrixalgebra:

N = \begin{pmatrix} 0.5 & -0.5 & 0 \ -0.25 & 0.5 & -0.25 \ 0 & -0.25 & 0.5 \end{pmatrix}^{-1} = \begin{pmatrix} 2 & 2 & 1 \ 1 & 2 & 1 \ 0.5 & 1 & 2 \end{pmatrix}

Die erwartete Zeit bis zur Absorption von jedem transienten Zustand wird durch \(N \mathbf{1}\) gegeben, wobei \( \mathbf{1} \) ein Vektor aus Einsen ist:

t = N \begin{pmatrix} 1 \ 1 \ 1 \end{pmatrix} = \begin{pmatrix} 2 & 2 & 1 \ 1 & 2 & 1 \ 0.5 & 1 & 2 \end{pmatrix} \begin{pmatrix} 1 \ 1 \ 1 \end{pmatrix} = \begin{pmatrix} 5 \ 4 \ 3.5 \end{pmatrix}

Also ist die erwartete Zeit bis zur Absorption, beginnend in Zustand 0, gleich:

t_0 = 5