Markov-Kette - Übergangswahrscheinlichkeit zwischen Teilmengen

15.08.2025, 11:14

Kognitivist

Markov-Kette - Übergangswahrscheinlichkeit zwischen Teilmengen

Meine Frage:
Aus Kemeny & Snell (Finite Markov Chains) p. 60:

Zugrundegelegt wird folgende Übergangswahrscheinlichkeiten-Matrix einer Markov-Kette:
$\begin{eqnarray*} \begin{vmatrix} 0 & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 & 0 \\ 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \\ 0 & 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & 0 \end{vmatrix} \end{eqnarray*}$

Die drei untersten Zeilen und die drei Spalten ganz rechts bilden die Teilmenge Q der Matrix (bzw. Markov-Kette), bezeichnet mit s3, s4 und s5, die beiden oberen Zeilen sind s1 und s2.

Die Matrix $\begin{eqnarray*} N = \left(I-Q\right) ^{-1} \end{eqnarray*}$ lautet:
$\begin{eqnarray*} \begin{vmatrix} \frac{21}{9} & \frac{12}{9} & \frac{4}{9} \\ \frac{15}{9} & \frac{24}{9} & \frac{8}{9} \\ \frac{9}{9} & \frac{9}{9} & \frac{12}{9} \end{vmatrix} \end{eqnarray*}$

Gesucht ist jetzt die Übergangswahrscheinlichkeit dieser Teilmenge s3,s4,s5 in die andere Teilmenge s1, s2, und zwar nur in den Zustand s1.

Dieser Spaltenvektor Np1 lautet angeblich: $\begin{eqnarray*} \begin{pmatrix} \frac{1}{9} \\ \frac{2}{9} \\ \frac{3}{9} \end{pmatrix} \end{eqnarray*}$ .

Ich komme nicht drauf, wie und warum. Mir ist klar, dass man vom Zustand s3 minimal drei Schritte braucht, um zu s1 zu gelangen, und zwar über s4 und s5, aber das gibt nicht 1/9. Mir ist auch klar, dass sich im Vektor die Schrittezahl zu s1 ausdrückt, nämlich von s5 am schnellsten - nur 1 Schritt mit p = 1/4, aber warum dann 3/9?

Wer kann helfen? Warum ist das der Spaltenvektor mit den Übergangswahrscheinlichkeiten von der Teilmenge s3,s4, s5 (= Q) bzw. ihren einzelnen Zuständen (die Zeilen im Spaltenvektor) zu s1, und zwar zu s1 BEVOR s2 erreicht wird. Wie wird das gerechnet?

Meine Ideen:
Keine Idee, warum das alles durch 9 geht.
Auch mit Entscheidungsbäumen etc. komme ich nicht dahin.

19.08.2025, 08:57

Scotty1701D

Auf diesen Beitrag antworten »

RE: Markov-Kette - Übergangswahrscheinlichkeit zwischen Teilmengen
Du berechnest hier die Wahrscheinlichkeiten, dass man von den Zuständen $\begin{eqnarray*} s_3 \end{eqnarray*}$ , $\begin{eqnarray*} s_4 \end{eqnarray*}$ oder $\begin{eqnarray*} s_5 \end{eqnarray*}$ schließlich in $\begin{eqnarray*} s_1 \end{eqnarray*}$ bzw. $\begin{eqnarray*} s_2 \end{eqnarray*}$ landet. Das kann sofort im ersten Schritt, oder im zweiten, dritten, vierten, … passieren. Da das beliebig lange dauern kann, kommst du mit einem Entscheidungsbaum nicht weiter.
Die Wahrscheinlichkeiten, dass du sofort im ersten Schritt dort landest, bekommst du aus der Teilmatrix unten links
$\begin{eqnarray*} \{s_3,s_4,s_5\}\rightarrow\{s_1,s_2\} \end{eqnarray*}$ :
$\begin{eqnarray*} P=\begin{pmatrix} 0 & \frac{1}{3} \\ 0 & 0 \\ \frac{1}{4} & \frac{1}{4} \end{pmatrix} \end{eqnarray*}$

Entsprechend sind die Wahrscheinlichkeiten, im zweiten, dritten, vierten, … Schritt dort zu landen
$\begin{eqnarray*} QP,\,Q^2P,\,Q^3P,\,\dots \end{eqnarray*}$

Gesucht ist die Summe aller Wahrscheinlichkeiten:
$\begin{eqnarray*} P+QP&+&Q^2P+Q^3P+\dots<br /> &=&\left(I+Q+Q^2+Q^3+\dots\right)P=NP<br /> &=&\begin{pmatrix} \frac{21}{9} & \frac{12}{9} & \frac{4}{9} \\ \frac{15}{9} & \frac{24}{9} & \frac{8}{9} \\ \frac{9}{9} & \frac{9}{9} & \frac{12}{9} \end{pmatrix} \cdot \begin{pmatrix} 0 & \frac{1}{3} \\ 0 & 0 \\ \frac{1}{4} & \frac{1}{4} \end{pmatrix} = \begin{pmatrix} \frac{1}{9} & \frac{8}{9} \\ \frac{2}{9} & \frac{7}{9} \\ \frac{3}{9} & \frac{6}{9} \end{pmatrix} \end{eqnarray*}$

Der linke Spaltenvektor ist dein Ergebnis.

19.08.2025, 12:37

Kognitivist

Auf diesen Beitrag antworten »

RE: Markov-Kette - Übergangswahrscheinlichkeit zwischen Teilmengen
Danke für die Hilfe, sieht logisch aus.

Offenbar sind die Zellen in der 3x3 Matrix Grenzwerte, also für die erste Zeile und erste Spalte z.B.
$\begin{eqnarray*} q_{11}* = I + q_{11} von Q + q_{11} von Q^{2} + q_{11} von Q^{3} usw \end{eqnarray*}$ ?

Welche Bedeutung hat die untere Formel fn? Wird die Matrix so berechnet? Wenn ja, woher hast Du diese Formel?
Selber hergeleitet, Formelsammlung?

20.08.2025, 00:55

Scotty1701D

Auf diesen Beitrag antworten »

RE: Markov-Kette - Übergangswahrscheinlichkeit zwischen Teilmengen
Ich verstehe leider deine Frage nicht. Welche Formel bzw. welche Matrix meinst du?
Ist die Matrix-Multiplikation klar?

Die Matrix $\begin{eqnarray*} N \end{eqnarray*}$ ist die Summe einer geometrischen Reihe von Matrizen, und die Addition von Matrizen erfolgt elementweise.
Sie hat als Summe von Wahrscheinlichkeiten keine unmittelbar anschauliche Bedeutung.

20.08.2025, 01:01

Helferlein

Auf diesen Beitrag antworten »

RE: Markov-Kette - Übergangswahrscheinlichkeit zwischen Teilmengen

Zitat:

Original von Kognitivist
Welche Bedeutung hat die untere Formel fn? Wird die Matrix so berechnet? Wenn ja, woher hast Du diese Formel?

Um diese Frage kurz zu beantworten: Kognitivist meint die Formel in der Signatur. Das ist eine explizite Darstellung der Fibonacci-Folge und hat nichts mit der Aufgabe zu tun.

20.08.2025, 08:09

Scotty1701D

Auf diesen Beitrag antworten »

RE: Markov-Kette - Übergangswahrscheinlichkeit zwischen Teilmengen
Ach so! Auf die Idee bin ich jetzt gar nicht gekommen. Big Laugh

Die Formel habe ich mal aus der Fibonacci-Folge aus den Eigenwerten der Rekursion
$\begin{eqnarray*} \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \cdot \begin{pmatrix} f_{n-1} \\ f_n \end{pmatrix} = \begin{pmatrix} f_n \\ f_{n+1} \end{pmatrix} \end{eqnarray*}$
berechnet.

20.08.2025, 08:53

Kognitivist

Auf diesen Beitrag antworten »

RE: Markov-Kette - Übergangswahrscheinlichkeit zwischen Teilmengen
Sorry für die im Nachhinein dumme Frage. Gestern Abend ist mir klar geworden, dass natürlich
$\begin{eqnarray*} N = I + Q + Q^{2} + Q^{3} + Q^{4} +.....Q^{n} \end{eqnarray*}$ natürlicih auf der geometrischen Folge
beruht und deren Grenzwert für $\begin{eqnarray*} |Q| < 1 \end{eqnarray*}$ mit $\begin{eqnarray*} \frac{1}{1-Q} \end{eqnarray*}$ definiert und somit
leicht auszurechnen ist. Q kann ja als Transitions-Matrix per definitionem nur Werte zwischen 0 und 1 einnehmen, daher darf ich die Grenzwertformel der geometrischen Folge nutzen.
So ist ja N auch definiert, mit $\begin{eqnarray*} (I-Q)^{-1} \end{eqnarray*}$ . Ich stand da voll auf der Leitung. Die von Dir irrtümlich dazugebaute Fibonacci-Reihe hat dann noch zu weiterer Verwirrung beigetragen.
Danke allen Helfenden.

21.08.2025, 00:22

Scotty1701D

Auf diesen Beitrag antworten »

RE: Markov-Kette - Übergangswahrscheinlichkeit zwischen Teilmengen
Nein nein. Die Fibonacci-Folge ist kein Irrtum.
Das ist meine Signatur Big Laugh

22.08.2025, 10:14

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Kognitivist
Gesucht ist jetzt die Übergangswahrscheinlichkeit dieser Teilmenge s3,s4,s5 in die andere Teilmenge s1, s2, und zwar nur in den Zustand s1.

Die Bezeichnung "Übergangswahrscheinlichkeit" ist hier etwas irreführend, denn dieser Begriff ist bei Markovketten üblicherweise für was anderes reserviert. Es geht stattdessen darum, welcher der beiden Zustände s1 oder s2 zuerst erreicht wird (d.h. vor dem anderen) - konkret um die Wahrscheinlichkeit dafür, dass dies s1 ist.

Neue Frage »

Antworten »

Markov-Kette - Übergangswahrscheinlichkeit zwischen Teilmengen

Verwandte Themen