Irrfahrt auf einem Graphen

14.06.2020, 17:30

hello123

Irrfahrt auf einem Graphen

Meine Frage:
Hallo,

ich brauche leider bei dieser Aufgabe eure Unterstützung.

Meine Ideen:
Für a) habe ich die Übergangsmatrix bereits angeben können. Ich habe aber noch keine Ideen zu den übrigen Aufgaben. Mag mir jemand dabei helfen?

Danke im Voraus.

15.06.2020, 08:11

Huggy

Auf diesen Beitrag antworten »

RE: Irrfahrt auf einem Graphen
b) sieht doch ziemlich trivial aus. Damit die Irrfahrt ausgehend von $\begin{eqnarray*} x=0 \end{eqnarray*}$ wieder zurückkehrt, muss sie über $\begin{eqnarray*} x=1 \end{eqnarray*}$ oder $\begin{eqnarray*} x=2 \end{eqnarray*}$ laufen. Das geschieht jeweils mit der Wahrscheinlichkeit $\begin{eqnarray*} 1/3 \end{eqnarray*}$ . Wenn die Irrfahrt ausgehend von $\begin{eqnarray*} x=1 \end{eqnarray*}$ oder $\begin{eqnarray*} x=2 \end{eqnarray*}$ wieder $\begin{eqnarray*} x=0 \end{eqnarray*}$ erreicht, wurde der Punkt einmal besucht und der Erwartungswert für den Rest der Irrfahrt ist wieder $\begin{eqnarray*} E_0 \end{eqnarray*}$ . Und wegen der Symmetrie ist $\begin{eqnarray*} E_1=E_2 \end{eqnarray*}$ . Daraus ergibt sich das Gleichungssystem.

c) Die Lösung des Gleichungssystems ist ebenfalls trivial, falls man annimmt, dass die Erwartungswerte existieren.

e) Da muss doch der Parameter $\begin{eqnarray*} p=1/3 \end{eqnarray*}$ stehen und nicht $\begin{eqnarray*} p=1/2 \end{eqnarray*}$ oder verstehe ich da etwas falsch?

d) Das folgt natürlich aus e), aber so kann das nicht gemeint sein. Gibt es für Markovketten nicht den Satz, dass eine Irrfahrt genau dann unendlich oft zurückkehrt, wenn die Wahrscheinlichkeit für eine Rückkehr $\begin{eqnarray*} 1 \end{eqnarray*}$ ist? Mit der allgemeinen Theorie von Markovketten bin ich leider nicht vertraut.

15.06.2020, 15:00

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
e) Da muss doch der Parameter $\begin{eqnarray*} p=1/3 \end{eqnarray*}$ stehen und nicht $\begin{eqnarray*} p=1/2 \end{eqnarray*}$ oder verstehe ich da etwas falsch?

1/2 ist schon richtig. Wieso 1/3 ? verwirrt

15.06.2020, 15:10

Huggy

Auf diesen Beitrag antworten »

Für genau $\begin{eqnarray*} m \end{eqnarray*}$ Besuche in $\begin{eqnarray*} x=0 \end{eqnarray*}$ bin ich auf

$\begin{eqnarray*} P(A=m)=\frac 1 3 \left( \frac 2 3 \right )^m \end{eqnarray*}$

gekommen. Also verstehe ich da tatsächlich etwas falsch.

15.06.2020, 15:36

HAL 9000

Auf diesen Beitrag antworten »

Da es bei $\begin{eqnarray*} A \end{eqnarray*}$ ja nicht um die Zeitpunkte selbst geht, wo Zustand 0 besucht wird, sondern nur um die Anzahlen solcher Zeitpunkte, so ist es gleichgültig, welchen Pfad innerhalb {1,2} der Prozess nach $\begin{eqnarray*} 0\to 1 \end{eqnarray*}$ beschreitet, denn er kommt mit Wkt 1 ja aus dieser Zustandsmenge {1,2} zum Zustand 0 wieder zurück. In einer solchermaßen "verkürzten" Betrachtung für die $\begin{eqnarray*} A \end{eqnarray*}$ -Zählung bleibt man mit Wkt 1/2 in 0 und geht mit Wkt 1/2 in den Endzustand E über, damit ist $\begin{eqnarray*} A \end{eqnarray*}$ geometrisch verteilt mit Parameter 1/2, oder irre ich mich da? verwirrt

15.06.2020, 15:52

Huggy

Auf diesen Beitrag antworten »

Meine Überlegung war: Mit Wahrscheinlichkeit $\begin{eqnarray*} 1/3 \end{eqnarray*}$ kommt man von $\begin{eqnarray*} x=1 \end{eqnarray*}$ nach $\begin{eqnarray*} x=E \end{eqnarray*}$ . Mit Wahrscheinlichkeit $\begin{eqnarray*} 2/3 \end{eqnarray*}$ kommt man zu einem der Punkte $\begin{eqnarray*} x=1 \end{eqnarray*}$ oder $\begin{eqnarray*} x=2 \end{eqnarray*}$ und von da mit Wahrscheinlichkeit $\begin{eqnarray*} 1 \end{eqnarray*}$ nach $\begin{eqnarray*} x=0 \end{eqnarray*}$ zurück. Damit hat man schon mal

$\begin{eqnarray*} P(A=0)=\frac 1 3 \end{eqnarray*}$

Wenn man zurückgekommen ist, geht es wieder mit Wahrscheinlichkeit $\begin{eqnarray*} 1/3 \end{eqnarray*}$ zur Absorption, also

$\begin{eqnarray*} P(A=1)= \frac 1 3 \frac 2 3 \end{eqnarray*}$

So geht es weiter. Ich bin verwirrt, was daran nicht stimmt.

15.06.2020, 17:08

HAL 9000

Auf diesen Beitrag antworten »

Vielleicht sollten wir uns erstmal auf die Ü-Matrix für $\begin{eqnarray*} X \end{eqnarray*}$ einigen: Ich gehe bei mehreren ausgehenden Pfeilen im obigen Zustandsgraphen von diskreter Gleichverteilung der beschreitbaren Wege aus, damit ist (mit Zustandsreihenfolge 0,1,2,E)

$\begin{eqnarray*} P = \begin{pmatrix} 0 & \frac{1}{2} & 0 & \frac{1}{2}\\ 0 & 0 & 1 & 0\\ \frac{1}{2} & \frac{1}{2} & 0 & 0\\ 0 & 0 & 0 & 1\end{pmatrix} \end{eqnarray*}$

Sieht so aus, als gäbe es da schon unterschiedliche Auffassungen.

15.06.2020, 17:51

Huggy

Auf diesen Beitrag antworten »

Nachdem sich meine Verwirrung zunächst noch gesteigert hatte, ist jetzt Klarheit eingetreten. Ich hatte nicht bemerkt, dass die Übergangslinien in dem Diagramm mit kleinen Pfeilen versehen sind. Daher hatte ich angenommen, dass man von $\begin{eqnarray*} x=0 \end{eqnarray*}$ auch direkt nach $\begin{eqnarray*} x=2 \end{eqnarray*}$ kommen kann und nicht nur nach $\begin{eqnarray*} x=1 \end{eqnarray*}$ und $\begin{eqnarray*} x=E \end{eqnarray*}$ . Das ändert natürlich die Sache. Ich muss meine Brille mal gründlich putzen. Im Nachhinein ist auch klar, dass es bei meiner Interpretation des Diagramms überflüssig wäre, 1 und 2 mit zwei Linien zu verbinden.

15.06.2020, 17:57

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
Ich muss meine Brille mal gründlich putzen.

Ich empfehle Ultraschall - aber hast du bestimmt schon. smile

15.06.2020, 19:27

hello123

Auf diesen Beitrag antworten »

HAL9000 hat völlig recht, der Parameter 1/2 ist schon korrekt.
Wie würdet ihr bei b) das Gleichungssystem aufstellen? Etwa ein lineares Gleichungssystem, welches durch die Stationarität vP=v entsteht? Und bei c) dann die stationäre Verteilung berechnen?

16.06.2020, 08:36

Huggy

Auf diesen Beitrag antworten »

Durch Ansehen des Diagramms, allerdings mit geputzter Brille Big Laugh

$\begin{eqnarray*} (1) \quad E_0 = \frac 1 2 E_1 \end{eqnarray*}$

$\begin{eqnarray*} (2) \quad E_1=E_2 \end{eqnarray*}$

$\begin{eqnarray*} (3)\quad E_2=\frac 1 2 (1+E_0)+ \frac 1 2 E_1 \end{eqnarray*}$

16.06.2020, 09:02

HAL 9000

Auf diesen Beitrag antworten »

Hmm, was den Zustand 0 betrifft sehe ich das etwas anders: Laut Definition $\begin{eqnarray*} A:=\sum_{n={\color{red}0}}^{\infty} 1_{\{X_n=0\}} \end{eqnarray*}$ wird ja auch der Startzustand (d.h. zum Zeitpunkt $\begin{eqnarray*} {\color{red}0} \end{eqnarray*}$ ) mitgezählt, sofern er gleich 0 ist. Daher lauten nach meinem Dafürhalten die Gleichungen (1) und (3) abweichend so

$\begin{eqnarray*} (1) \quad E_0 = 1 + \frac 1 2 E_1 \end{eqnarray*}$
$\begin{eqnarray*} (3)\quad E_2= \frac 1 2 E_0+ \frac 1 2 E_1 \end{eqnarray*}$ .

D.h., "mein" $\begin{eqnarray*} E_0 \end{eqnarray*}$ ist um 1 größer als dein $\begin{eqnarray*} E_0 \end{eqnarray*}$ , ansonsten stimmen die Betrachtungen überein.

16.06.2020, 10:06

Huggy

Auf diesen Beitrag antworten »

Klar, wenn man den Ausgangszustand als Besuch mitrechnet. Da habe ich auch die Definition von $\begin{eqnarray*} A \end{eqnarray*}$ nicht sorgfältig gelesen. Das kann ich nicht auf die Brillle schieben. Dieser Thread wird mir allmählich peinlich.

16.06.2020, 12:47

hello123

Auf diesen Beitrag antworten »

Ich hoffe, ihr habt mit E den Erwartungswert gemeint? Ausgedrückt mit $\begin{eqnarray*} h_0(x) \end{eqnarray*}$ würde ich dann folgendes Gleichungssystem erhalten:
(1) $\begin{eqnarray*} h_0(0) = 1+\frac{1}{2}h_0(1) \end{eqnarray*}$
(2) $\begin{eqnarray*} h_0(1) = h_0(2) \end{eqnarray*}$
(3) $\begin{eqnarray*} h_0(2) = \frac{1}{2}h_0(0)+\frac{1}{2}h_0(1) \end{eqnarray*}$
Wenn ich nach $\begin{eqnarray*} h_0(0) \end{eqnarray*}$ umstelle, dann erhalte ich $\begin{eqnarray*} h_0(0) = \frac{1}{3}h_0(1)+\frac{4}{3} \end{eqnarray*}$ . Wie kann ich alle Lösungen des Gleichungssystems bestimmen, wenn sie abhängig von einer anderen Variable sind? Oder kann ich bei $\begin{eqnarray*} h_0(0) \end{eqnarray*}$ etwas für $\begin{eqnarray*} h_0(1) \end{eqnarray*}$ einsetzen, um für $\begin{eqnarray*} h_0(0) \end{eqnarray*}$ einen Wert herauszubekommen?

16.06.2020, 13:04

HAL 9000

Auf diesen Beitrag antworten »

Also wenn du es so nicht hinkriegst, dann überführe es in die Standardform eines linearen 3x3-Gleichungssystems und löse es wie immer du auch lineare Gleichungssysteme löst. Jedenfalls kommt am Ende die eindeutige Lösung $\begin{eqnarray*} h_0(0)=h_0(1)=h_0(2)=2 \end{eqnarray*}$ heraus.

16.06.2020, 14:17

hello123

Auf diesen Beitrag antworten »

Vielen Dank! Das Lösen des Gleichungssystems habe ich doch noch hinbekommen! Aber ist mit $\begin{eqnarray*} 2 \end{eqnarray*}$ schon "alle Lösungen des Gleichungssystems" gemeint? Oder gibt es noch weitere?
Fragen zu d): Wie würde die Beweisskizze dafür lauten, dass die Funktion $\begin{eqnarray*} h_0 \end{eqnarray*}$ nur endliche Werte annimmt? Folgt das daraus, dass der die Markovkette transient ist?

16.06.2020, 14:50

HAL 9000

Auf diesen Beitrag antworten »

Das irritiert mich jetzt: Wenn

Zitat:

Original von hello123
Das Lösen des Gleichungssystems habe ich doch noch hinbekommen!

WIRKLICH stimmt, dann ist die Fragerei

Zitat:

Original von hello123
Aber ist mit $\begin{eqnarray*} 2 \end{eqnarray*}$ schon "alle Lösungen des Gleichungssystems" gemeint? Oder gibt es noch weitere?

irgendwie ziemlich sinnfrei: Als Ergebnis der Gleichungssystem-Betrachtung sollte herauskommen, dass es nur genau diese eine Lösung (2,2,2) gibt.

16.06.2020, 15:20

hello123

Auf diesen Beitrag antworten »

Ja, das habe ich mir schon gedacht, aber in der Aufgabe hörte es sich so an, als gäbe es mehrere Lösungen.
Mag mir jemand noch bei d) helfen?

16.06.2020, 16:08

HAL 9000

Auf diesen Beitrag antworten »

Ah, Ok, nach Durchlesen von d) jetzt verstehe ich auch erst den Sinn von c):

Es gäbe natürlich theoretisch auch noch die "uneigentliche Lösung" $\begin{eqnarray*} h_0(0)=h_0(1)=h_0(2)=\infty \end{eqnarray*}$ des aufgestellten Gleichungssystems, denn die obige Gleichungssystemlösung erfasst ja nur die wirklich reellen Lösungen, und $\begin{eqnarray*} \infty \end{eqnarray*}$ ist keine reelle Zahl.

Naja, man könnte sich auf den Standpunkt stellen: Ich bearbeite erstmal e), dann habe ich den Beweis für die Endlichkeit von $\begin{eqnarray*} h_0(0) \end{eqnarray*}$ , und damit dann über das Gleichungssystem auch d). Augenzwinkern

Neue Frage »

Antworten »

Irrfahrt auf einem Graphen

Verwandte Themen