Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Rückkehrzeit Markovkette

Rückkehrzeit Markovkette

Universität / Fachhochschule

Tags: Markoff, Markov-Kette, Markov-Prozess, Rückkehrzeit

Johnny85 aktiv_icon

13:55 Uhr, 23.06.2013

Aufgabe:

Sie werfen fortlaufend eine Münze. Bei “Kopf” bekommen Sie einen Spielstein von Höhe 2cm, bei “Zahl” einen von Höhe 3 cm. Zielsetzung: zwei Stapel zu bauen, die möglichst schnell gleich hoch sind. Am Anfang ist jeder Stapel leer. Jeder neue Stein soll auf einen der beiden Stapel gelegt werden. Welche Strategie ist im Erwartungswert besser?
Strategie

1 :

Jeder neue Stein wird auf den bisher kleineren Stapel gelegt.
Strategie

2 :

Wie Strategie

1,

außer: ist der Höhenunterschied der Stapel 1 cm und der neue Stein hat Höhe 2 cm, so wird er auf den höheren Stapel gelegt.
Benutzen Sie jeweils ein Markoffmodell, dessen Zustände

0,1,2,3

der absolute Höhenunterschied der Stapel ist.

Liebes Forum,

ich bin davon ausgegangen, dass ich diese Aufgabe recht schnell lösen kann. Allerdings hänge ich am Schluss. Entweder habe ich vorher schon Fehler gemacht oder ich bin zu blöd ein lineares Gleichungssystem zu lösen. Hier mein Vorgehen:

Markovkette mit 4 Zuständen:

1 :=

Höhenunterschied ist gleich;

2 :=

Höhenunterschied 2cm, auf gleiche Höhe wird der kleine Stein gesetzt;

3 :=

Höhenunterschied 3cm, auf gleiche Höhe wird der große Stein gesetzt,

4 :=

Höhenunterschied 1cm

Dann habe ich mir für beide Strategien die Übergangswahrscheinlichkeiten überlegt, ein Übergangsgraphen gezeichnet und die Übergangsmatrix aufgeschrieben. Dann möchte ich die invariante Verteilung bestimmen und den Erwartungswert der Rückkehrzeit zum Zustand 1 berechnen.

Strategie

1 :

(\begin{matrix} 0 & \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & 0 & \frac{1}{2} \\ \frac{1}{2} & 0 & 0 & \frac{1}{2} \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} \end{matrix})

Strategie

2 :

(\begin{matrix} 0 & \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & 0 & \frac{1}{2} \\ \frac{1}{2} & 0 & 0 & \frac{1}{2} \\ 0 & \frac{1}{2} & \frac{1}{2} & 0 \end{matrix})

In beiden Fällen sind die Einträge zeilenweise

p_{11} - p_{14}

und spaltenweise

p_{11} - p_{41}

Ja nun wollte ich jeweils die invariante (stationäre) Verteilung bestimmen, für Strategie 2 beispielsweise:

(\begin{matrix} 0 & \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & 0 & \frac{1}{2} \\ \frac{1}{2} & 0 & 0 & \frac{1}{2} \\ 0 & \frac{1}{2} & \frac{1}{2} & 0 \end{matrix}) \cdot (\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{matrix}) = (\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{matrix})

Zusätzlich gilt ja jeweils

x_{1} + x_{2} + x_{3} + x_{4} = 1

Jedenfalls sind meiner Meinung nach beide linearen Gleichungssysteme nicht lösbar. Beispielsweise bringe ich die Übergangsmatrix der Strategie 2 (zuzüglich der Gleichung

x_{1} + x_{2} + x_{3} + x_{4} = 1)

auf Stufenform:

(\begin{matrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix})

welche keine sinnvolle Lösung bringt..

Wo liegt mein Fehler? Ist mein Vorgehen zu Beginn schon falsch gedacht?

Über jeden Hinweis und jeden Lösungstip freue ich mich! Vielen Dank!

Gruß!

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Matlog aktiv_icon

17:46 Uhr, 23.06.2013

Hier scheinen mir einige Bemerkungen notwendig:

1)

In der Aufgabenstellung wurden die Zustände bereits benannt

(0,1,2

und

3)

.
Wieso gibst Du denen jetzt neue Namen, die auch noch schlechter nachzuvollziehen sind?
Aber das ist ja nur Kosmetik.

2)

Prinzipiell gibt es zwei Möglichkeiten, mit Hilfe einer Matrix den Übergang von einem Zustand zum nächsten darzustellen.
Zeilenvektor

\cdot

Matrix=Zeilenvektor oder
Matrix

\cdot

Spaltenvektor=Spaltenvektor,
wobei in einem Fall die Matrix der transponierten Matrix aus dem anderen Fall entspricht.

Deine Notation zur Bestimmung der stationären Verteilung lässt auf die zweite Version mit den Spaltenvektoren schließen. Deine Matrix passt aber nicht dazu. Hier musst Du Zeilen und Spalten vertauschen.
(Bei Strategie 2 ist es egal, da die Matrix symmetrisch ist.)

3)

Mir ist (noch) nicht klar, warum Du eine stationäre Verteilung bestimmen willst.

4)

Wie bist Du auf diese Stufenform gekommen?
Kann es sein, dass Du die rechten Seiten der Gleichungen völlig außer Acht gelassen hast?

Johnny85 aktiv_icon

18:54 Uhr, 23.06.2013

Vielen Dank für deine Hilfe!

Also ich habe die Zustandsnamen willkürlich gewählt. Aber du hast recht, es ist anschaulicher die Zustandsnamen

0,1,2,3

zu verwenden für die jeweiligen cm-Differenzen.

Ich denke, dass ich irgendetwas mit den Zeilen und Spalten verdrehe. Ich habe es eigentlich so kennengelernt, dass eine

4 x 4

Übergangsmatrix mit den Zuständen

0,1,2,3

so aussieht:

(\begin{matrix} p_{00} & p_{01} & p_{02} & p_{03} \\ p_{10} & p_{11} & p_{12} & p_{13} \\ p_{20} & p_{21} & p_{22} & p_{23} \\ p_{30} & p_{31} & p_{32} & p_{33} \end{matrix})

Nun wähle ich mal die bessere Bezeichnung für die Zustände:

0 =

0cm,

1 =

1cm,

2 =

2cm,

3 =

3cm. Dann erhalte ich für die Strategie 1 diese Matrix:

(\begin{matrix} 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 \end{matrix})

Nun wollte ich die stationäre Verteilung bestimmen, indem ich das folgende Gleichungssystem löse:

x_{3} + x_{4} = 2 x_{1}

x_{2} + x_{3} = 2 x_{2}

x_{1} + x_{2} = 2 x_{3}

x_{1} + x_{2} = 2 x_{4}

(Entspricht der Matrix, jede Zeile mit 2 multipliziert)

Aus den Zeilen 3 und 4 ergibt sich

x_{3} = x_{4},

aus der Zeile 2 ergibt sich

x_{3} = x_{2} = x_{4}

und aus der Zeile 1 dann

x_{1} = x_{2} = x_{3} = x_{4}

und mit der Summe 1 dann schließlich, dass alle den Wert

\frac{1}{4}

haben müssen. Aber das kann doch nicht sein? Außerdem wäre dies für die zweite Strategie genauso? Das versteh ich leider nicht.

Schließlich brauche ich die stationäre Verteilung da

E (T_{i}) = \frac{1}{π} (i)

wobei

T_{i}

die Rückkehrzeit zum Zusatnd

i

ist und

π

die stationäre Verteilung.

Gruß

Matlog aktiv_icon

19:06 Uhr, 23.06.2013

Machen wir mal ein einfaches Beispiel zur Matrix von Strategie 1:
Wir befinden uns gerade in Zustand

1,

was ja dem Vektor

(\begin{matrix} 0 \\ 1 \\ 0 \\ 0 \end{matrix})

entspricht.
Wie berechnest Du jetzt mit Hilfe der Matrix den Folgezustand?

Matlog aktiv_icon

11:46 Uhr, 24.06.2013

Ich wollte Dir mit meinem Beispiel nur zeigen, dass sich bei Multiplikation Deiner Matrix mit meinem Spaltenvektor Unsinn ergibt!

Zurück zur Bestimmung der stationären Verteilung. Hier hast Du zwei mögliche Ansätze (Beachte bitte die unterschiedliche Anordnung der Zeilen und Spalten in den beiden Matrizen!):

(\begin{matrix} p_{00} & p_{10} & p_{20} & p_{30} \\ p_{01} & p_{11} & p_{21} & p_{31} \\ p_{02} & p_{12} & p_{22} & p_{32} \\ p_{03} & p_{13} & p_{23} & p_{33} \end{matrix}) \cdot (\begin{matrix} x_{0} \\ x_{1} \\ x_{2} \\ x_{3} \end{matrix}) = (\begin{matrix} x_{0} \\ x_{1} \\ x_{2} \\ x_{3} \end{matrix})

oder

(x_{0}, x_{1}, x_{2}, x_{3}) \cdot (\begin{matrix} p_{00} & p_{01} & p_{02} & p_{03} \\ p_{10} & p_{11} & p_{12} & p_{13} \\ p_{20} & p_{21} & p_{22} & p_{23} \\ p_{30} & p_{31} & p_{32} & p_{33} \end{matrix}) = (x_{0}, x_{1}, x_{2}, x_{3})

Beides ergibt dieselben Gleichungen. Aber Deine Mischung aus beidem geht (meistens) schief!

Johnny85 aktiv_icon

14:06 Uhr, 24.06.2013

Ja vielen Dank für deine Hilfe!

Du hattest recht. Mein Fehler lag in der falschen Berechnung der invarianten Verteilung. Zeilen und Spalten sind durcheinander gekommen, sodass dies am Schluss keine sinnvolle Lösung ergab.

Ich habe die Aufgabe noch einmal gerechnet und die Zustände "sinnvoller" bezeichnet.

0 :=

0cm

1 :=

1cm

2 :=

2cm

3 :=

3cm Höhenunterschied

Dann die Übergangsmatrizen gebildet. Für Strategie 1 beispielsweise:

(\begin{matrix} 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ 0 & \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 \end{matrix})

Dann den Zeilenvektor

π = (x_{1}, x_{2}, x_{3}, x_{4})

von links an diese Matrix multipliziert und mit demselben Vektor gleichgesetzt, also den Eigenvektor der Matrix zum Eigenwert 1 bestimmt. Ich erhalte folgende erweiterte Koeffizientenmatrix:

(\begin{matrix} - 1 & 0 & \frac{1}{2} & \frac{1}{2} & 0 \\ 0 & - \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & \frac{1}{2} & - 1 & 0 & 0 \\ \frac{1}{2} & 0 & 0 & - 1 & 0 \end{matrix})

und erhalte dann die stationäre Verteilung

π = (\frac{2}{10}, \frac{4}{10}, \frac{3}{10}, \frac{1}{10})

und somit schließlich mit

E (T_{i}) = \frac{1}{π (i)}

den Erwartungswert

E (T_{0}) = 5

.

Analog bin ich bei Strategie 2 vorgegangen und erhalte

π = (\frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{4})

und schließlich

E (T_{0}) = 4

.

Man sollte daher die zweite Strategie verwenden, wenn man möglichst schnell (wieder) die Steine auf gleicher Höhe liegen haben möchte.

Also wenn dies korrekt ist, dann nochmals vielen Dank!
Gruß.

Matlog aktiv_icon

14:52 Uhr, 24.06.2013

Ja, das sollte jetzt alles stimmen!

1103007

1102745

	Status: nicht eingeloggt	Noch nicht registriert?