Rückkehrzeit Markovkette < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:03 Sa 22.06.2013 | | Autor: | johnny23 |
| 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öhenunter- schied 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.
Strategie 1:
[mm] \pmat{ 0 & \bruch{1}{2} & \bruch{1}{2} & 0 \\ \bruch{1}{2} & 0 & 0 & \bruch{1}{2} \\ \bruch{1}{2} & 0 & 0 & \bruch{1}{2} \\ 0 & \bruch{1}{2} & 0 & \bruch{1}{2}}
[/mm]
Strategie 2:
[mm] \pmat{ 0 & \bruch{1}{2} & \bruch{1}{2} & 0 \\ \bruch{1}{2} & 0 & 0 & \bruch{1}{2} \\ \bruch{1}{2} & 0 & 0 & \bruch{1}{2} \\ 0 & \bruch{1}{2} & \bruch{1}{2} & 0}
[/mm]
In beiden Fällen sind die Einträge zeilenweise [mm] p_{11} [/mm] - [mm] p_{14} [/mm] und spaltenweise [mm] p_{11} [/mm] - [mm] p_{41}
[/mm]
Ja nun wollte ich jeweils die invariante (stationäre) Verteilung bestimmen, für Strategie 1 beispielsweise:
[mm] \pmat{ 0 & \bruch{1}{2} & \bruch{1}{2} & 0 \\ \bruch{1}{2} & 0 & 0 & \bruch{1}{2} \\ \bruch{1}{2} & 0 & 0 & \bruch{1}{2} \\ 0 & \bruch{1}{2} & 0 & \bruch{1}{2}} \* \vektor{x_{1} \\ x_{2} \\ x_{3} \\ x_{4}} [/mm] = [mm] \vektor{x_{1} \\ x_{2} \\ x_{3} \\ x_{4}}
[/mm]
Zusätzlich gilt ja jeweils [mm] x_{1} [/mm] + [mm] x_{2} [/mm] + [mm] x_{3} [/mm] + [mm] x_{4} [/mm] = 1
Jedenfalls sind meiner Meinung nach beide linearen Gleichungssysteme nicht lösbar. Beispielsweise bringe ich die Übergangsmatrix der Strategie 2 (zuzüglich der Gleichung [mm] x_{1} [/mm] + [mm] x_{2} [/mm] + [mm] x_{3} [/mm] + [mm] x_{4} [/mm] = 1) auf Stufenform:
[mm] \pmat{ 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0} [/mm]
welche keine sinnvolle Lösung bringt.
Schließlich brauche ich die invariante Verteilung [mm] \pi [/mm] um den Erwartungswert der Rückkehrzeit [mm] T_{1} [/mm] zu berechnen: [mm] E(T_{1}) [/mm] = [mm] \bruch{1}{\pi (1)}
[/mm]
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ß!
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 14:38 So 23.06.2013 | | Autor: | johnny23 |
Hallo,
hat denn keiner eine Idee? Also ich finde leider keinen Fehler.. Sofern die Matrizen korrekt sind, erhalte ich immer x1=x2=x3=x4 und wegen x1+x2+x3+x4=1 wäre das bei beiden Strategien 1/4. Das kann doch nicht sein.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:36 So 23.06.2013 | | Autor: | argon7 |
Deine Matrizen sind schon falsch, sowohl als auch deine Vorgehensweise der Bestimmung einer Invarianten Verteilung. Warum auch immer du die Zustände neu deklarieren willst, wenn schon in der Aufgabenstellung steht 0,1,2,3 und du 1,2,3,4 drauß machen willst ist mir nicht klar.
Damit du selbst etwas nachdenkst, laut der Matrix deiner Strategie 1 ist es möglich laut dir, dass man vom "gleichhohen" Zustand in den Zustand wechselt mit 1 cm Unterschied! Dieses Beispiel sollte dir eigentlich den Rest erklären und [mm] \pi [/mm] P = [mm] \pi [/mm] hast du falsch berechnet!!! [mm] \pi [/mm] wird links an die Matrix als transponierter Vektor multipliziert!
|
|
|
| |
|
Hallo,
wie argon bereits geschrieben hat, sind deine Matrizen falsch.
Um die Übersicht zu wahren, schlage ich stattdessen folgende Zustände vor:
0 = Höhenunterschied 0 cm
1 = Höhenunterschied 1 cm
2 = Höhenunterschied 2 cm
3 = Höhenunterschied 3 cm
Dann sieht die Matrix der Strategie 1 so aus:
P = [mm] \begin{pmatrix}
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{pmatrix}
[/mm]
Eine stationäre Verteilung erhältst du über
[mm] $\pi [/mm] = [mm] \pi \cdot [/mm] P$,
bzw.
[mm] $\pi [/mm] = [mm] P^{T}\pi$.
[/mm]
Du suchst also nach Eigenvektoren von [mm] $P^{T}$ [/mm] zum Eigenwert 1.
Viele Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:36 So 23.06.2013 | | Autor: | johnny23 |
Zunächst vielen Dank für eure Hilfe!
Ich verstehe nicht ganz, wieso meine Matrizen falsch sind. Vertausche ich Zeilen und Spalten? Wie ich bereits geschrieben habe, habe ich es so kennengelernt, dass die erste Zeile von [mm] p_{11} [/mm] bis [mm] p_{14} [/mm] läuft und die erste Spalte von [mm] p_{11} [/mm] bis [mm] p_{41}.
[/mm]
Für die Strategie 1 in meinem ersten Post hieße das:
1. Zeile [mm] (0,\bruch{1}{2},\bruch{1}{2},0): [/mm] Der Wechsel vom Zustand "Gleichhoch" zu "Gleichhoch" ist unmöglich. Wechsel mit Wkeit [mm] \bruch{1}{2} [/mm] in "2cm" und mit Wkeit [mm] \bruch{1}{2} [/mm] in "3cm". Und natürlich Wechsel in "1cm" unmöglich.
Steppenhahn, wenn ich deine Bezeichnung der Zustände wähle, dann erhalte ich auch eine andere Matrix für die Strategie 1 als du. In deiner Matrix ist nach obiger Auffassung die Wkeit für ein Wechsel von "2cm" zu "1cm" gleich 0 (3.Zeile, 2. Spalte)?
Gruß
|
|
|
| |
|
Hallo,
> Ich verstehe nicht ganz, wieso meine Matrizen falsch sind.
> Vertausche ich Zeilen und Spalten? Wie ich bereits
> geschrieben habe, habe ich es so kennengelernt, dass die
> erste Zeile von [mm]p_{11}[/mm] bis [mm]p_{14}[/mm] läuft und die erste
> Spalte von [mm]p_{11}[/mm] bis [mm]p_{41}.[/mm]
Ja.
> Für die Strategie 1 in meinem ersten Post hieße das: 1.
> Zeile (0,1/2,1/2,0): Der Wechsel vom Zustand "Gleichhoch"
> zu "Gleichhoch" ist unmöglich. Wechsel mit Wkeit 1/2 in
> "2cm" und mit Wkeit 1/2 in "3cm". Und natürlich Wechsel in
> "1cm" unmöglich.
Ja, deine Matrizen sind doch alle richtig. Sorry.
Wir hatten uns vermutlich beide noch irgendwie von deinen Definitionen verwirren lassen :)
> Steppenhahn, wenn ich deine Bezeichnung der Zustände
> wähle, dann erhalte ich auch eine andere Matrix für die
> Strategie 1. In deiner Matrix ist nach obiger Auffassung
> 3.Zeile: Wkeit für ein Wechsel von "2cm" zu "1cm" gleich 0
Ja, auch ich hatte mich da vertan... Kein guter Tag heute für mich.
Ich habe es korrigiert.
Evtl. liegt das Problem bei deiner Rechnung der stationären Verteilungen [mm] $\pi$ [/mm] darin, dass du nur die Übergangsmatrizen P umformst.
Du musst aber (z.B. Strategie 2) den Kern von
[mm] $P^T [/mm] - I = [mm] \pmat{ -1 & \bruch{1}{2} & \bruch{1}{2} & 0 \\ \bruch{1}{2} & -1 & 0 & \bruch{1}{2} \\ \bruch{1}{2} & 0 & -1 & \bruch{1}{2} \\ 0 & \bruch{1}{2} & \bruch{1}{2} & -1} [/mm] $
bestimmen!
Viele Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:28 So 23.06.2013 | | Autor: | johnny23 |
Ok. Also dann noch einmal mit der "besseren" Zustandsbezeichnung:
Strategie 1:
P = [mm] \pmat{ 0 & 0 & \bruch{1}{2} & \bruch{1}{2} \\ 0 & \bruch{1}{2} & \bruch{1}{2} & 0 \\ \bruch{1}{2} & \bruch{1}{2} & 0 & 0\\ \bruch{1}{2} & \bruch{1}{2} & 0 & 0}
[/mm]
Dann [mm] \pi \*P [/mm] = [mm] \pi [/mm] lösen. Zeilenvektor von links an die Matrix P multiplizieren "vertauscht" Zeilen und Spalten. Ergibt die erweiterte Koeffizientenmatrix:
[mm] \pmat{ -1 & 0 & \bruch{1}{2} & \bruch{1}{2} & 0\\ 0 & -\bruch{1}{2} & \bruch{1}{2} & \bruch{1}{2} & 0 \\ \bruch{1}{2} & \bruch{1}{2} & -1 & 0 & 0 \\ \bruch{1}{2} & 0 & 0 & -1 & 0}
[/mm]
Diese ergibt keine eindeutige Lösung:
[mm] x_{1} [/mm] = [mm] 2x_{4}, x_{2} [/mm] = [mm] 4x_{4}, x_{3}=3x_{4}
[/mm]
Da die Summe 1 sein muss ergibt sich für die stationäre Verteilung
[mm] \pi [/mm] = [mm] (\bruch{2}{10},\bruch{4}{10},\bruch{3}{10},\bruch{1}{10})
[/mm]
Mit [mm] E(T_{i}) [/mm] = [mm] \bruch{1}{\pi(i)} [/mm] ergibt sich als Erwartungswert [mm] E(T_{0}) [/mm] = 5
Ich hoffe, dies ist korrekt?! Analog bin ich bei Strategie 2 vorgegangen und erhalte da allerdings [mm] x_{1} [/mm] = [mm] x_{2} [/mm] = [mm] x_{3} [/mm] = [mm] x_{4} [/mm] und somit [mm] E(T_{0}) [/mm] = 4.
Gruß
|
|
|
| |
|
Hallo,
> Ok. Also dann noch einmal mit der "besseren"
> Zustandsbezeichnung:
>
> Strategie 1:
>
> P = [mm]\pmat{ 0 & 0 & \bruch{1}{2} & \bruch{1}{2} \\ 0 & \bruch{1}{2} & \bruch{1}{2} & 0 \\ \bruch{1}{2} & \bruch{1}{2} & 0 & 0\\ \bruch{1}{2} & \bruch{1}{2} & 0 & 0}[/mm]
>
> Dann [mm]\pi \*P[/mm] = [mm]\pi[/mm] lösen. Zeilenvektor von links an die
> Matrix P multiplizieren "vertauscht" Zeilen und Spalten.
> Ergibt die erweiterte Koeffizientenmatrix:
>
> [mm]\pmat{ -1 & 0 & \bruch{1}{2} & \bruch{1}{2} & 0\\ 0 & -\bruch{1}{2} & \bruch{1}{2} & \bruch{1}{2} & 0 \\ \bruch{1}{2} & \bruch{1}{2} & -1 & 0 & 0 \\ \bruch{1}{2} & 0 & 0 & -1 & 0}[/mm]
>
> Diese ergibt keine eindeutige Lösung:
> [mm]x_{1}[/mm] = [mm]2x_{4}, x_{2}[/mm] = [mm]4x_{4}, x_{3}=3x_{4}[/mm]
>
> Da die Summe 1 sein muss ergibt sich für die stationäre
> Verteilung
> [mm]\pi[/mm] =
> [mm](\bruch{2}{10},\bruch{4}{10},\bruch{3}{10},\bruch{1}{10})[/mm]
>
> Mit [mm]E(T_{i})[/mm] = [mm]\bruch{1}{\pi(i)}[/mm] ergibt sich als
> Erwartungswert [mm]E(T_{0})[/mm] = 5
> Ich hoffe, dies ist korrekt?!
Ja, das ist nun alles richtig. ![[ok]](/images/smileys/ok.gif "[ok]")
> Analog bin ich bei Strategie
> 2 vorgegangen und erhalte da allerdings [mm]x_{1}[/mm] = [mm]x_{2}[/mm] =
> [mm]x_{3}[/mm] = [mm]x_{4}[/mm] und somit [mm]E(T_{0})[/mm] = 4.
Auch richtig.
Aber was bedeuten diese Erwartungswerte?
Was ist nun die bessere Strategie?
Weil bei der Strategie 1 [mm] $\pi(0) [/mm] = 1/5$ gilt, bedeutet das, dass man nur mit Wahrscheinlichkeit 1/5 auf eine Situation trifft, bei welcher der Höhenunterschied Null ist.
Bei Strategie 2 ist es [mm] $\pi(0) [/mm] = 1/4$, also trifft man mit einer höheren Wahrscheinlichkeit auf Höhenunterschied Null. Man könnte also argumentieren, dass Strategie 2 besser ist.
Ich weiß aber nicht, ob die Aufgabe so gedacht ist. Evtl. meint "im Erwartungswert besser" auch, dass du den Erwartungswert des Höhenunterschieds bei den stationären Verteilungen bestimmen sollst und gucken, wo der kleiner ist. Mach das mal!
Viele Grüße,
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:03 Mo 24.06.2013 | | Autor: | johnny23 |
Super! Vielen Dank für deine Hilfe Stefan.
Ich denke, es ist so gemeint, dass nach dem Erwartungswert beurteilt werden soll, welche Strategie schneller zum Sieg führt. Um möglichst schnell zu gewinnen, also möglichst schnell zwei Stapel zu bauen, die gleich hoch sind, empfehle ich daher die Strategie 2, da man im Mittel nach 4 Spielzügen das Ziel erreicht hat, während man bei der Strategie 1 im Mittel 5 Züge benötigt um zum ursprünglichen Zustand "gleichhoch" zurück zukehren.
Gruß
|
|
|
|
