Irrfahrt auf einem gerichteten Graphen

29.06.2020, 17:36

hello123

Irrfahrt auf einem gerichteten Graphen

Meine Frage:
Wir betrachten auf dem folgenden gerichteten Graphen die Irrfahrt X mit Startpunkt $\begin{eqnarray*} v_3 \end{eqnarray*}$ :

Aufgabe:
1) Bestimme alle Kommunikationsklassen und alle absorbierenden Zustände.
2) Bestimme die Wahrscheinlichkeit, dass die Irrfahrt im Punkt $\begin{eqnarray*} v_1 \end{eqnarray*}$ bzw. im Punkt $\begin{eqnarray*} v_5 \end{eqnarray*}$ landet.

Meine Ideen:
Zu 1) würde ich sagen, dass die Kommunikationsklassen $\begin{eqnarray*} v_2 \end{eqnarray*}$ , $\begin{eqnarray*} v_3 \end{eqnarray*}$ und $\begin{eqnarray*} v_4 \end{eqnarray*}$ sind und die absorbierenden Zustände sind $\begin{eqnarray*} v_1 \end{eqnarray*}$ und $\begin{eqnarray*} v_5 \end{eqnarray*}$ .
Zu 2) habe ich leider noch keine Idee.

29.06.2020, 20:06

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von hello123
2) Bestimme die Wahrscheinlichkeit, dass die Irrfahrt im Punkt $\begin{eqnarray*} v_1 \end{eqnarray*}$ bzw. im Punkt $\begin{eqnarray*} v_5 \end{eqnarray*}$ landet.

Dazu müsste man wissen, wie groß genau die Ü-Wkten sind. Ein bloßer Pfeil bedeutet ohne Erläuterung nur, dass der zugehörige Übergang eine positive Wkt hat.

Vermutung: In jedem Zustand ist jeder der möglichen "Abgänge" gleichwahrscheinlich. D.h., von $\begin{eqnarray*} v_2 \end{eqnarray*}$ gehen drei Pfeile aus, jeder mit Wkt. 1/3 - ist das so gemeint?

29.06.2020, 20:11

hello123

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Vermutung: In jedem Zustand ist jeder der möglichen "Abgänge" gleichwahrscheinlich. D.h., von $\begin{eqnarray*} v_2 \end{eqnarray*}$ gehen drei Pfeile aus, jeder mit Wkt. 1/3 - ist das so gemeint?

Ja, das ist korrekt.

29.06.2020, 20:17

Nils Hoppenstedt

Auf diesen Beitrag antworten »

RE: Irrfahrt auf einem gerichteten Graphen
Hallo,

1) Es gibt drei Kommunikationsklassen: die offene Klasse C1 = {v2, v3, v4}, sowie die beiden abgeschlossene Klassen C2 = {v5} und C3 = {v5}. Die absorbierenden Zustände sind v1 und v5.

2) Hier würde ich versuchen ein Gleichungssystem aufzustellen.

Sei $\begin{eqnarray*} f_{xy} \end{eqnarray*}$ die Wahrscheinlichkeit von Zustand x zum Zustand y zu gelangen. Dann gilt:

$\begin{eqnarray*} f_{35} &=& \frac{1}{2}f_{45} + \frac{1}{2}f_{25}\\f_{45} &=& \frac{1}{2} + \frac{1}{2}f_{25}\\f_{25} &=& \frac{1}{3}f_{35} + \frac{1}{3}f_{35} \end{eqnarray*}$

Das sind 3 Gleichungen mit 3 Unbekannten mit einer eindeutigen Lösung für $\begin{eqnarray*} f_{35} \end{eqnarray*}$ . Ein analoges Vorgehen führt dann auf ein Gleichungssystem für $\begin{eqnarray*} f_{31} \end{eqnarray*}$

Viele Grüße,
Nils

29.06.2020, 20:35

Nils Hoppenstedt

Auf diesen Beitrag antworten »

RE: Irrfahrt auf einem gerichteten Graphen

Zitat:

[i]
1) Es gibt drei Kommunikationsklassen: die offene Klasse C1 = {v2, v3, v4}, sowie die beiden abgeschlossene Klassen C2 = {v5} und C3 = {v5}. Die absorbierenden Zustände sind v1 und v5.

Ich meinte natürlich: C2 ={v1} und C3 = {v5}

- Nils

01.07.2020, 11:09

HAL 9000

Auf diesen Beitrag antworten »

In der letzten der drei Gleichungen ist ein kleiner Indexfehler: $\begin{eqnarray*} f_{25} &=& \frac{1}{3}f_{35} + \frac{1}{3}f_{{\color{red}4}5} \end{eqnarray*}$

War wohl der Copy+Paste-Fehlerteufel. Teufel

Zitat:

Original von Nils Hoppenstedt
Ein analoges Vorgehen führt dann auf ein Gleichungssystem für $\begin{eqnarray*} f_{31} \end{eqnarray*}$

Kann nicht schaden, wenn man das auf diese Weise zur Kontrolle nochmal nachrechnet, aber es muss rauskommen:

Da alle Zustände 2,3,4 sowohl mit 1 als auch 5 verbunden sind, landet die Irrfahrt mit Wkt 1 in genau einem der beiden Zustände. Somit ist $\begin{eqnarray*} f_{k1} = 1-f_{k5} \end{eqnarray*}$ für alle $\begin{eqnarray*} k=2,3,4 \end{eqnarray*}$ .