Rechnen mit Übergangsmatrizen: Definition & Anwendung

Definition

Eine Übergangsmatrix $$U$$​ fasst die Übergangswahrscheinlichkeiten einer Markow-Kette in einer Matrix zusammen. 

$$a_{xy}:$$ Wahrscheinlichkeit von Zustand $$y$$​ in Zustand $$x$$​ zu wechseln.

Rechnen mit Übergangsmatrizen

Hat man einen Zustandsvektor einer Markow-Kette zum Zeitpunkt $$t$$​, so kann der Zustandsvektor zum folgenden Zeitpunkt ($$t+1$$​ ) mittels Vektor-Matrix Multiplikation ermittelt werden. 

Beispiel – Eine Münze wird so oft geworfen, bis sie Kopf zeigt. Die Chance, dass bei einem Wurf Kopf auftritt, ist $$0,5$$​. Dieser Zufallsprozess kann als Markow-Kette mit zwei Zuständen beschrieben werden. Der erste Zustand ist, dass die Münze auf Kopf liegt (sobald die Münze einmal auf Kopf landet, wird das Experiment abgebrochen und damit ist die Münze zu jedem späteren Zeitpunkt auf Kopf). Der zweite Zustand ist, dass die Münze auf Zahl liegt, wonach die Münze erneut geworfen wird. Dieses System kann mit der folgenden Übergangsmatrix dargestellt werden:

$$U=\begin{pmatrix}1 & 0,5\\0 & 0,5 \end{pmatrix}$$​​

Die Startverteilung (die Wahrscheinlichkeiten der Zustände nach dem ersten Wurf) kann durch den folgenden Zustandsvektor beschrieben werden:

$$v=\left(\begin{array}{c}0,5\\ 0,5\end{array}\right)$$​​

Nun kann die Vektor-Matrix Multiplikation verwendet werden, um die Zustandsvektoren zu verschiedenen Zeitpunkten zu bestimmen:

Absorbierende Zustände

Ein absorbierender Zustand einer Markow-Kette ist ein Zustand, der nicht mehr aufgehoben werden kann. Das bedeutet, dass die Wahrscheinlichkeit, von einem solchen Zustand zu einem anderen Zustand zu wechseln gleich $$0$$​ ist. Alle anderen Zustände heißen innere Zustände. 

Absorptionswahrscheinlichkeiten

Eine Absorptionswahrscheinlichkeit eines Zustandes ist die Wahrscheinlichkeit, mit der eine Markow-Kette, die sich in diesem Zustand befindet, irgendwann einen bestimmten absorbierenden Zustand erreicht. 

Beispiel – Im vorherigen Beispiel ist „Kopf“ der einzige absorbierende Zustand. Sobald die Münze nämlich auf Kopf landet, wird die Münze nicht mehr geworfen. Damit ist die Wahrscheinlichkeit, dass sich der Zustand des Systems nochmals ändert, gleich $$0$$​.
Die Absorptionswahrscheinlichkeit von „Zahl“ bezüglich „Kopf“ ist die Wahrscheinlichkeit, dass wenn die Münze auf Zahl liegt, irgendwann später im Experiment „Kopf“ eintritt. Die Wahrscheinlichkeit, dass niemals Kopf kommt, ist gleich $$0$$​ (da unendlich viele Male immer wieder Zahl kommen müsste). Daher ist die Wahrscheinlichkeit, dass irgendwann im Experiment „Kopf“ kommt, gleich $$1$$​. Damit ist die Absorptionswahrscheinlichkeit von „Zahl“ gleich $$1$$​.

1. Mittelwertsregel

Die 1. Mittelwertsregel ist eine Möglichkeit, um ein Gleichungssystem aufzustellen, mit dessen Hilfe es möglich ist, die Absorptionswahrscheinlichkeiten von einzelnen Zuständen bezüglich eines absorbierenden Zustandes zu bestimmen. Sie besagt:

Dabei ist zu beachten, dass für die Absorptionswahrscheinlichkeit des absorbierenden Zustandes von Interesse $$1$$​ einzusetzen ist und für die Absorptionswahrscheinlichkeiten aller anderen absorbierender Zustände $$0$$​.
Auf diese Weise ergibt sich ein Gleichungssystem mit n Gleichungen und $$n$$​ Variablen:

Wird dieses Gleichungssystem gelöst, erhält man die einzelnen Absorptionswahrscheinlichkeiten.

Beispiel – Im Münzwurfbeispiel ist das Gleichungssystem definiert durch die Mittelwertsregel das Folgende:

$$a_1\cdot1+a_2\cdot0= a_1$$​​

$$a_1\cdot0,5+a_2\cdot0,5= a_2$$​​

​Da der erste Zustand (Kopf) ein absorbierender Zustand ist, gilt $$a_1=1$$​.

$$1\cdot1+a_2 \cdot 0=1$$​​

$$1\cdot 0,5+a_2\cdot 0,5=a_2$$​​

Die erste Gleichung wird somit obsolet, wodurch sich das System auf die zweite Gleichung reduziert. Diese kann wie folgt umgeformt werden:

$$1\cdot 0,5+a_2 \cdot 0,5=a_2$$​​

$$0,5=0,5\cdot a_2$$​​

$$1=a_2$$​​

Damit ist die Absorptionswahrscheinlichkeit von $$a_2$$​ (also „Zahl“) bezüglich „Kopf“ in der Tat gleich $$1$$​.