Markovketten

21.01.2022, 21:34

RickMai

Auf diesen Beitrag antworten »

Markovketten

Meine Frage:
Gegeben Markovkette mit folgender Übergangsmatrix P

P=
1 0 0 0
0,1 0,2 0,5 0,2
0,1 0,4 0,4 0,1
0,2 0,2 0,3 0,3
? ?
Offenbar ist Zustand 1 ein absorbierender Zustand. Wie groß ist die Wahrscheinlichkeit, dass wir den Zustand 3 erreichen, bevor wir den absorbierenden Zustand 1 erreichen?

Meine Ideen:
Meine Idee ist, den Startvektor auf (0;0,5;0;0,5) zu setzten und dann die Matrix solange mit sich selber zu multiplizieren, bis wir zum ersten mal in den absorbierenden Zustand gelangen. Dann mit dem Anfangsvektor multiplizieren und dann die dritte Stelle des Ergebnisvektors als Antwort nehmen.

22.01.2022, 09:08

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von RickMai
Meine Idee ist, den Startvektor auf (0;0,5;0;0,5) zu setzen

Das wäre meine erste Frage gewesen: In welchem Zustand bzw. welcher Zustandsverteilung soll die Kette starten?

Du nimmst jetzt einfach Gleichverteilung in den beiden Zuständen 2 und 4 an, aber warum? Aus dem Text oben geht das nicht hervor - war diese Information zusätzlich noch gegeben? verwirrt

verwirrt

---------------------------------

Wie auch immer: Betrachte die reduzierte Ü-Matrix $\begin{eqnarray*} Q = \begin{pmatrix} 0.2 & 0.2\\ 0.2 & 0.3\end{pmatrix} \end{eqnarray*}$ nur mit den Zeilen/Spalten 2 und 4 der originalen Ü-Matrix $\begin{eqnarray*} P \end{eqnarray*}$ : Dann gibt $\begin{eqnarray*} Q^n \end{eqnarray*}$ die Übergangswahrscheinlichkeiten an, von Zustand $\begin{eqnarray*} a \end{eqnarray*}$ in Zustand $\begin{eqnarray*} b \end{eqnarray*}$ zu kommen mit $\begin{eqnarray*} a,b\in\{2,4\} \end{eqnarray*}$ , ohne dabei zwischendurch Zustand 1 oder 3 passiert zu haben.

Für eine Anfangsverteilung $\begin{eqnarray*} q_0^t = (p_2,p_4) \end{eqnarray*}$ auf diesen Zuständen 2,4 ergibt dann $\begin{eqnarray*} q_0^tQ^n\cdot \begin{pmatrix} 0.5\\ 0.3\end{pmatrix} \end{eqnarray*}$ die Wahrscheinlichkeit, in genau $\begin{eqnarray*} n+1 \end{eqnarray*}$ Schritten erstmalig nach Zustand 3 zu gelangen, ohne vorher 1 passiert zu haben. Insgesamt ergibt das die gesuchte Wahrscheinlichkeit

$\begin{eqnarray*} p = q_0^T\cdot \sum_{n=0}^{\infty} Q^n\cdot \begin{pmatrix} 0.5\\ 0.3\end{pmatrix} \stackrel{!}{=} q_0^T\cdot \left(I-Q\right)^{-1}\cdot \begin{pmatrix} 0.5\\ 0.3\end{pmatrix} \end{eqnarray*}$ .

22.01.2022, 11:04

RickMai

Auf diesen Beitrag antworten »

Ja die Frage mit dem Zustand hab ich mir auch gestellt. Nachdem da nichts in der Angabe steht, dacht ich ich muss was annehmen.

Ok wie kommst du auf die Ü-Matrix? Also die Werte sind mir klar aber warum die Ü-Matrix?

q^T0&#8901 traurig

traurig

I−Q)^−1&#8901 traurig

traurig

0.5;0.3)

Soll das heißen,

Schritt 1

I =Identitätsmatrix also Einheitsmatrix?
Q = klar
die beiden subtrahieren und davon die Inverse bilden?

Schritt 2

diese Inverse dann mit (0,5;0,3) multiplizieren

Schritt drei
die aus schritt drei dann mit qT0 multiplizieren.

Danke schonmal für die schnelle Antwort

22.01.2022, 11:10

RickMai

Auf diesen Beitrag antworten »

Zitat:

Original von RickMai
Ja die Frage mit dem Zustand hab ich mir auch gestellt. Nachdem da nichts in der Angabe steht, dacht ich ich muss was annehmen.

Ok wie kommst du auf die Ü-Matrix? Also die Werte sind mir klar aber warum die Ü-Matrix?

q^T_{0}*(I−Q)^{-1}*\begin{pmatrix} 0,5 \\ 0,3 \end{pmatrix}

Soll das heißen,

Schritt 1

I =Identitätsmatrix also Einheitsmatrix?
Q = klar
die beiden subtrahieren und davon die Inverse bilden?

Schritt 2

diese Inverse dann mit (0,5;0,3) multiplizieren

Schritt drei
die aus schritt drei dann mit qT0 multiplizieren.

Danke schonmal für die schnelle Antwort

22.01.2022, 11:15

RickMai

Auf diesen Beitrag antworten »

Ja die Frage mit dem Zustand hab ich mir auch gestellt. Nachdem da nichts in der Angabe steht, dacht ich ich muss was annehmen.

Ok wie kommst du auf die Ü-Matrix? Also die Werte sind mir klar aber warum die Ü-Matrix?

q^T_{0}*(I−Q)^{-1}*\begin{pmatrix} 0,5 \\ 0,3 \end{pmatrix}

Soll das heißen,

Schritt 1

I =Identitätsmatrix also Einheitsmatrix?
Q = klar
die beiden subtrahieren und davon die Inverse bilden?

Schritt 2

diese Inverse dann mit (0,5;0,3) multiplizieren

Schritt drei
die aus schritt drei dann mit qT0 multiplizieren.

Danke schonmal für die schnelle Antwort

22.01.2022, 11:28

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von RickMai
Ok wie kommst du auf die Ü-Matrix? Also die Werte sind mir klar aber warum die Ü-Matrix?

Hab ich doch erklärt: Es geht (bis auf den letzten Schritt, d.h., den Übergang zum Zustand 3) nur um Übergänge innerhalb der Zustands-Teilmenge $\begin{eqnarray*} \{2,4\} \end{eqnarray*}$ . Und die werden nun mal durch so ein $\begin{eqnarray*} Q \end{eqnarray*}$ , welches aus Zeilen- und Spaltenstreichung aus $\begin{eqnarray*} P = \begin{pmatrix}1 & 0 & 0 & 0\\ 0.1 & {\color{red}0.2} & {\color{blue}0.5} & {\color{red}0.2}\\ 0.1 & 0.4 & 0.4 & 0.1\\ 0.2 & {\color{red}0.2} & {\color{blue}0.3} & {\color{red}0.3}\end{pmatrix} \end{eqnarray*}$ entsteht beschrieben.

Was die Reihe betrifft: Es gilt (ähnlich wie bei der geometrischen Folge/Reihe) die Gleichung $\begin{eqnarray*} \left(I-Q\right)\cdot \sum_{n=0}^{k-1} Q^n = I - Q^k \end{eqnarray*}$ .

Im Grenzübergang $\begin{eqnarray*} k\to\infty \end{eqnarray*}$ bedeutet dies $\begin{eqnarray*} \left(I-Q\right)\cdot \sum_{n=0}^{\infty} Q^n = I \end{eqnarray*}$ zumindest dann, wenn $\begin{eqnarray*} \lim_{k\to\infty} Q^k = 0 \end{eqnarray*}$ ist. Und das ist für eine solche substochastische Matrix wie unser $\begin{eqnarray*} Q \end{eqnarray*}$ erfüllt. Und daraus folgt nun mal direkt $\begin{eqnarray*} \sum_{n=0}^{\infty} Q^n = \left(I-Q\right)^{-1} \end{eqnarray*}$ .

Schritt 1 + Schritt 2 ergibt übrigens mit $\begin{eqnarray*} \left(I-Q\right)^{-1}\cdot \begin{pmatrix} 0.5\\ 0.3\end{pmatrix} \end{eqnarray*}$ den Wahrscheinlichkeitsvektor für die gesuchten Wahrscheinlichkeiten, wenn man mit 2 bzw. 4 startet (d.h. für die "reinen" statt gemischten Startverteilungen).

Anzeige

22.01.2022, 11:48

RickMai

Auf diesen Beitrag antworten »

Ok verstehe.

Aber wie bekomme ich dann den Wahrscheinlichkeitsvektor für die gemischten Startverteilungen???

22.01.2022, 11:58

HAL 9000

Auf diesen Beitrag antworten »

Hmm, du stehst auf Wiederholungen - und mit einem Hang zum Drama (gleich drei Fragezeichen): Durch das Dranmultiplizieren mit $\begin{eqnarray*} q_0^T \end{eqnarray*}$ .

Bei deinem Vorschlag dann eben mit $\begin{eqnarray*} q_0^T = \left(\frac{1}{2},\frac{1}{2}\right) \end{eqnarray*}$ .

22.01.2022, 12:29

RickMai

Auf diesen Beitrag antworten »

Doppelt hält besser ^^

ok also dann wäre das Ergebnis

(I-Q)^-1
(0,8. -0,2)^-1
(-0,2. 0,7)

(1,35 0,38)
(0,38 1,54)

* (0,5;0,3)= (0,789;0,652)
*(0,5;0,5)= 0,7205

Die Wahrscheinlichkeit das wir Zustand 3 erreichen bevor wir den absorbierenden Zustand 1 erreichen liegt bei 72,05%.

Stimmt das so?

22.01.2022, 12:43

HAL 9000

Auf diesen Beitrag antworten »

Naja, das exakte Ergebnis ist $\begin{eqnarray*} \frac{75}{104}\approx 0.7211 \end{eqnarray*}$ - soviel zur Vertrauenswürdigkeit einer Angabe von vier Nachkommastellen bei auf drei Stellen gerundeten Zwischenergebnissen. Augenzwinkern

Augenzwinkern

22.01.2022, 12:52

RickMai

Auf diesen Beitrag antworten »

Nice, ich dank dir vielmals Lehrer

Lehrer

Prost

22.01.2022, 12:54

RickMai

Auf diesen Beitrag antworten »

Ich hab noch eine Aufgabe aber die ist schon älter aber ich glaub eine sehr bekannte.
Wir sind damals auch nicht richtig auf die Lösung gekommen die aber Safe nicht schwer ist.

Guck mal

Ich besitze 4 Regenschirme, einige zu Hause und einige im Büro. Ich bewege mich zwischen Büro und zu Hause hin und her und nehme jeweils einen Regenschirm nur dann mit, wenn es regnet. Wenn es nicht regnet, dann lasse ich den Regenschirm zurück (zu Hause oder im Büro). Dabei kann es vorkommen, dass alle 4 Regenschirme an einem Ort sind und ich am anderen Ort. Wenn es dann regnet, werde ich auf meinem Weg nass.

a) Wie lautet ein sinnvoller Zustandsraum?
b) Male das Markov-Diagramm und gebe die Übergangsmatrix an.

a) Ist das der Zustandsraum Z={1,2,3,4}?

zu b) verwirrt

verwirrt

22.01.2022, 12:57

RickMai

Auf diesen Beitrag antworten »

hab eine mögliche Lösung noch:

so sah das damals aus.

Ausschnitt

$\begin{eqnarray*} \begin{pmatrix} 1-q & a_2 & a_3 \\ b_1 & 1-q & b_3 \\ c_1 & c_2 & 1-q \end{pmatrix} \end{eqnarray*}$

22.01.2022, 12:59

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von RickMai
a) Ist das der Zustandsraum Z={1,2,3,4}?

Na die 0 gehört sicher auch noch dazu.

Zitat:

Original von RickMai
b) Male das Markov-Diagramm und gebe die Übergangsmatrix an.

Da keine Regenwahrscheinlichkeit angegeben ist, soll die wohl ein zunächst noch offener Parameter sein?

EDIT (zu deinem nachgeschobenen Post 12:57): Wieso hast du dort nur 3 Zustände?

Entweder geht es da um weniger als 4 Schirme. Oder aber um eine modifizierte Strategie: Etwa die, dass man einen Schirm mitnimmt, wenn es regnet ODER am Zielort kein Schirm mehr vorhanden ist - sozusagen die Methode "auf Nummer sicher, nie nass zu werden".

22.01.2022, 13:19

RickMai

Auf diesen Beitrag antworten »

Ok also Zustandsraum
Z={0,1,2,3,4}

Das weiß ich auch nicht warum da nur 3 Zustände sind Hammer

Hammer

Dann vergessen wir die Matrix lieber ^^

Ne ne also da gehts schon um 4 Schirme das war wahrscheinlich nur falsch.

22.01.2022, 13:29

HAL 9000

Auf diesen Beitrag antworten »

Außerdem muss man noch klarstellen, was der Zustand überhaupt bedeutet: Eine Möglichkeit wäre "Anzahl der Regenschirme am Ausgangsort (!) des Weges". Dabei muss man berücksichtigen, dass bei jedem Weg "Heim -> Büro" oder "Büro -> Heim" die Rolle des Ausgangsortes wechselt!!! Insofern hat man bei Regenwahrscheinlichkeit $\begin{eqnarray*} r \end{eqnarray*}$ die Ü-Matrix

$\begin{eqnarray*} P = \begin{pmatrix} 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 1-r & r\\ 0 & 0 & 1-r & r & 0\\ 0 & 1-r & r & 0 & 0\\ 1-r & r & 0 & 0 & 0\end{pmatrix} \end{eqnarray*}$ .

Und nass wird man genau dann, wenn man im Zustand 0 ist und es dann regnet.

22.01.2022, 13:40

RickMai

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Naja, das exakte Ergebnis ist $\begin{eqnarray*} \frac{75}{104}\approx 0.7211 \end{eqnarray*}$ - soviel zur Vertrauenswürdigkeit einer Angabe von vier Nachkommastellen bei auf drei Stellen gerundeten Zwischenergebnissen. Augenzwinkern

Augenzwinkern

Jetzt hätte ich nochmal eine Frage dazu.

Vergessen wir mal meinen Vorschlag mit den 0,5!

Wie würde das Ergebnis aussehen, wenn ich die Einzelwahrscheinlichkeiten für jeden Zustand angeben müsste?

22.01.2022, 13:50

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Schritt 1 + Schritt 2 ergibt übrigens mit $\begin{eqnarray*} \left(I-Q\right)^{-1}\cdot \begin{pmatrix} 0.5\\ 0.3\end{pmatrix} \end{eqnarray*}$ den Wahrscheinlichkeitsvektor für die gesuchten Wahrscheinlichkeiten, wenn man mit 2 bzw. 4 startet (d.h. für die "reinen" statt gemischten Startverteilungen).

Mit Ergebnis $\begin{eqnarray*} \left(I-Q\right)^{-1}\cdot \begin{pmatrix} 0.5\\ 0.3\end{pmatrix} = \begin{pmatrix} \frac{41}{52}\\ \frac{17}{26}\end{pmatrix}\approx \begin{pmatrix} 0.7885\\ 0.6538\end{pmatrix} \end{eqnarray*}$ . Aber das hattest du doch oben schon mal ausgerechnet? verwirrt

verwirrt

22.01.2022, 14:11

RickMai

Auf diesen Beitrag antworten »

Cheeses ^^

da hat er die Lösungen für beide Gott

Gott

Sehr sehr geil ich dank dir nochmals ^^

Ist mir auch grad aufgefallen ^^

22.01.2022, 14:13

RickMai

Auf diesen Beitrag antworten »

Und das Diagramm sieht aber dann schon so aus, dass man von Zustand 1 zu 5 mit Wk.1.
Und von Zustand 2 zu 5 mit r und zu 4 mit 1-r geht oder?

22.01.2022, 14:34

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von RickMai
Und das Diagramm sieht aber dann schon so aus, dass man von Zustand 1 zu 5 mit Wk.1.

Vom Zustand 0 zu Zustand 4 mit Wahrscheinlichkeit 1, richtig:

Wenn man 0 Schirme vorfindet, hat man keine Wahl: Man kann keinen mitnehmen, ob es regnet oder nicht. Und am Zielort findet man vier Schirme vor, was dann der Ausgangszustand für den nächsten Weg ist.

Zitat:

Original von RickMai
Und von Zustand 2 zu 5 mit r und zu 4 mit 1-r geht oder?

Vom Zustand 1 ausgehend
a) kann es regnen (mit Wkt r): Dann nimmt man den einen Schirm mit und hat am Zielort vier Schirme, oder
b) es regnet nicht (mit Wkt 1-r), dann lässt man den einen Schirm liegen und hat am Zielort drei Schirme.

Usw., ich denke das Prinzip ist jetzt klar.

22.01.2022, 15:16

RickMai

Auf diesen Beitrag antworten »

[attach]54383[/attach][attach]54383[/attach]

So müsste dass dann aussehen odeR?

22.01.2022, 15:41

HAL 9000

Auf diesen Beitrag antworten »

Der Pfeil 0->0 mit Wkt 1-r sollte wohl eher einer sein 4->0 ...

22.01.2022, 16:00

RickMai

Auf diesen Beitrag antworten »

Oh stimmt

jetzt müsste das Markov Diagramm passen?

22.01.2022, 16:05

HAL 9000

Auf diesen Beitrag antworten »

Ja, so sollte es hinkommen.

22.01.2022, 16:14

RickMai

Auf diesen Beitrag antworten »

Rock

Rock

Rock

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »