Ein Spiel als Markov Kette

19.03.2009, 22:03

martingale

Auf diesen Beitrag antworten »

Ein Spiel als Markov Kette

Hallo zusammen,

Ich muss folgende Aufgabe am Rechner modellieren. Leider weiß ich nicht wie ich zum Ansatz kommen kann. Kann mir jemand Hinweise geben wie ich die gesuchte Grössen berechnen kann?

Zunächst die Aufgabe:

Spieler A und B werfen eine Münze und notieren beim Ausgang „Kopf“ eine 0 und beim Ausgang “Zahl“ eine 1. Spieler A wartet auf die Sequenz 1100 in aufeinander folgendenWürfen, Spieler B wartet auf 000. Es handelt sich um eine faire Müunze, d.h. P(„Kopf“)=P(„Zahl“)=0,5. Das Spiel endet, sobald eine der beiden Sequenzen notiert worden ist. Sieger ist der Spieler, dessen Sequenz zuerst erscheint. (Nach dem Erscheinen einer der beiden Sequenzen ist das Spiel beendet.)

a) Beschreiben Sie die zeitliche Entwicklung durch eine Markovkette. Verwenden Sie hierbei als Zustandsraum die 4 jeweils zuletzt notierten Wurfergebnisse. Geben Sie den Zustandsraum und die Übergangsmatrix (verständlich beschrieben und formatiert) aus.

b) Zeichnen Sie den resultierenden Übergangsgraphen und markieren Sie die absorbierenden Zustände.

c) Zeigen Sie mit Hilfe einer Programmsequenz: Obwohl A auf die längere Sequenz warten muss, ist seine Gewinnwahrscheinlichkeit größer als die von B.

d) Warum scheint dieses Ergebnis zunächst verblüffend? (Wie löst sich dieser scheinbare Widerspruch auf?)

e) Zeigen Sie wieder mit Hilfe einer Programmsequenz: Es dauert im Mittel 9 1/3 Würfe bis entweder 1100 oder 000 erscheint.

g) Angenommen, Sie dürften (als Spieler C) mitspielen. Sie dürfen Ihre 4-stellige Sequenz frei wählen. Welche Sequenzen kommen dabei für Sie in Frage, wenn Sie Ihre Gewinnwahrscheinlichkeit maximieren wollen? (Begründung wieder durch Programmsequenz)

Meine Überlegung:

- Übergangsgraph

http://img25.imageshack.us/img25/1743/drawing1h.jpg
-Transformationsmatrix

http://img14.imageshack.us/img14/9292/ausgabe1.jpg

Ich habe Schwirigkeiten mit den Teilaufgaben c, d, e und g. Kann mir jemand Hinweis(s) geben, wie ich zum Ansatz komme? So viel ich weiss, die gesuchte Grössen berechnen sich mittels Lösen von LGSen.

Vielen Dank im Voraus !

Grüsse,
Marko

20.03.2009, 09:10

AD

Auf diesen Beitrag antworten »

Eine kleine Änderung bei der Wahl der Zustände schlage ich noch vor: Den Zustand 1000 würde ich weglassen - besser gesagt: Mit Zustand x000 vereinigen, dann hast du einen einheitlichen absorbierenden Zustand, der den Sieg von B repräsentiert.

Zu c)

Sei $\begin{eqnarray*} p_n \end{eqnarray*}$ der Vektor der Aufenthaltswahrscheinlichkeiten nach genau $\begin{eqnarray*} n \end{eqnarray*}$ Schritten, und $\begin{eqnarray*} p^* = \lim\limits_{n\to\infty} p_n \end{eqnarray*}$ dessen Grenzverteilung. Für den Vektor $\begin{eqnarray*} p^* \end{eqnarray*}$ musst du dir nun folgendes klarmachen:

1) dass er existiert (d.h. der Grenzwert),
2) dass nur die Komponenten der beiden absorbierenden Zustände ungleich Null sind, und
3) dass diese Komponenten gerade die Siegwahrscheinlichkeiten der beiden Spieler darstellen!

Bleibt dann noch die Berechnung von $\begin{eqnarray*} p^* \end{eqnarray*}$ . Augenzwinkern

Augenzwinkern

EDIT: Bei genauerer Überlegung könntest du es dir vom Umfang her einfacher machen, indem du nicht die letzten 4, sondern nur die letzten 3 Wurfergebnisse im Zustand erfasst, zuzüglich des absorbierenden Siegzustandes 1100 für Spieler A. Allerdings scheint ja laut Formulierung in Aufgabenstellung a) die Verwendung von 4 Zuständen für dich vorgeschrieben zu sein - schade.

20.03.2009, 12:33

martingale

Auf diesen Beitrag antworten »

Hallo Arthur Dent,

Danke für deine Hinweise ! Sei $\begin{eqnarray*} P^n \end{eqnarray*}$ das n-fache Produkt der Matrix P mit sich selbst, d.h. die Elemente $\begin{eqnarray*} p_{i,j}^n \end{eqnarray*}$ von $\begin{eqnarray*} P^n \end{eqnarray*}$ stimmen mit $\begin{eqnarray*} P(X_n = j | X_0 = i) \end{eqnarray*}$ überein und sind die n-Schritt Übergangswahrscheinlichkeiten. Ich habe das Programm mit n=10000 laufen lassen und folgende Übergangswahrscheinlichkeiten bekommen. Laut dein Hinweis:
1. exsistiert $\begin{eqnarray*} p^* \end{eqnarray*}$ .
2. Die Komponenten der absorbierenden Zustände ungleich Null sind

zu 3. welche sind die Siegwahrscheinlichkeiten?

Leider ist die Aufgabe so formuliert, dass man die vier zuletzt notierten Würfelergebnisse in der Kette mitschleppen muss.

Jetzt arbeite ich an den anderen Teilaufgaben.

Anlage: Die n-Schritt Übergangswahrscheinlichkeiten.

http://img13.imageshack.us/img13/1066/phochn.jpg

Gruß,
Marko

20.03.2009, 13:02

martingale

Auf diesen Beitrag antworten »

Hallo zusammen,

hier noch mal, die genauere Übergangswahrscheinlichkeiten.

Daher folgt für Spieler A, der auf "000" wartet eine Gewinnwahrscheinlichkeit von $\begin{eqnarray*} P( Gewinn ) = P(X_n = X000 | X_0 = XXXX) + P(X_n = 1000 | X_0 = XXXX) = 0.1250000 + 0.2916667 = 0.41666667 = 5/{12} \end{eqnarray*}$

Für Spieler B, der auf 0011 wartet, folgt eine Gewinnwahrscheinlichkeit von $\begin{eqnarray*} P( Gewinn ) = P(X_n = 0011 | X_0 = XXXX) = 0.5833333 = 7/{12} \end{eqnarray*}$

Denkst du, dass diese Lösung analytisch und ausreichend sei ? Laut Übungsleitering wird keine Simulation verlangt sondern eine analytische Lösung unterstützt duch ein Java-Programm.

Grüsse,
Marko

Anhang:
Die genauere Übergangswahrscheinlichkeiten

20.03.2009, 16:19

martingale

Auf diesen Beitrag antworten »

Hallo noch mal,

zu Teilaufgabe C): eigentlich so viel ich es verstanden habe (im Buch nachgelesen), das was ich mit den n-Schritt Übergangswahrscheinlichkeiten gezeigt habe, ist keine analytische Lösung, sondern nur eine Annährung. Die analytische Lösung bekommt man aus der stationären Verteilung, die mittels folgende LGS bestimmt werden kann.

$\begin{eqnarray*} u_j = \sum_{i \in I} u_i p_{i, j}, i \in I \end{eqnarray*}$ unter Einhaltung der Nichtnegativitaetsbedingung $\begin{eqnarray*} u_i \ge 0 \end{eqnarray*}$ und der Normierungsbedingung $\begin{eqnarray*} \sum_{i \in I} u_i = 1 \end{eqnarray*}$

Gruß,
Marko

20.03.2009, 17:05

AD

Auf diesen Beitrag antworten »

Zitat:

Original von martingale
Die analytische Lösung bekommt man aus der stationären Verteilung, die mittels folgende LGS bestimmt werden kann.

$\begin{eqnarray*} u_j = \sum_{i \in I} u_i p_{i, j}, i \in I \end{eqnarray*}$ unter Einhaltung der Nichtnegativitaetsbedingung $\begin{eqnarray*} u_i \ge 0 \end{eqnarray*}$ und der Normierungsbedingung $\begin{eqnarray*} \sum_{i \in I} u_i = 1 \end{eqnarray*}$

Das Problem bei der vorliegenden Markovkette ist aber, dass es die stationäre Verteilung hier nicht gibt, d.h., es gibt mehrere. So sind z.B. die Einpunktverteilungen auf den absorbierenden Zuständen schon vom Prinzip her stationär, das hier gesuchte $\begin{eqnarray*} p^* \end{eqnarray*}$ entspricht aber keiner dieser Einpunktverteilungen, sondern ist eine Konvexkombination davon. Welche das ist, lässt sich leider nicht einfach durch Lösen von

$\begin{eqnarray*} u = P\cdot u \end{eqnarray*}$

ermitteln. So einfach geht es bei ergodischen Markovketten - die vorliegende Kette ist aber nicht ergodisch. unglücklich

unglücklich

Mir fällt spontan erstmal folgendes ein: Berechne die Jordanzerlegung $\begin{eqnarray*} P = TJT^{-1} \end{eqnarray*}$ , mit Jordanscher Eigenwertmatrix $\begin{eqnarray*} J \end{eqnarray*}$ und Transformationsmatrix $\begin{eqnarray*} T \end{eqnarray*}$ . Dann ist $\begin{eqnarray*} P^n = TJ^nT^{-1} \end{eqnarray*}$ .

$\begin{eqnarray*} J^n \end{eqnarray*}$ bzw. insbesondere auch dessen Grenzwert für $\begin{eqnarray*} n\to\infty \end{eqnarray*}$ lässt sich folgendermaßen bestimmen: Die auf der Hauptdiagonale von $\begin{eqnarray*} J \end{eqnarray*}$ befindlichen Eigenwerte sind bei stochastischen Matrizen $\begin{eqnarray*} P \end{eqnarray*}$ sämtlich vom Betrag her kleiner oder gleich 1. Die "echt kleiner als 1" verschwinden beim Grenzübergang $\begin{eqnarray*} \lim\limits_{n\to\infty} J^n \end{eqnarray*}$ , die "gleich 1" bleiben...

Damit kannst du "nichtiterativ" den Grenzwert von $\begin{eqnarray*} P^n \end{eqnarray*}$ ausrechnen, und mit $\begin{eqnarray*} p^*=\lim\limits_{n\to\infty} P^np_0 \end{eqnarray*}$ hast du dann die gesuchte Grenzverteilung. Dabei kennzeichnet $\begin{eqnarray*} p_0 \end{eqnarray*}$ die Anfangsverteilung, das ist bei dir einfach die Einpunktverteilung im Zustand XXXX.

Anzeige

20.03.2009, 18:22

martingale

Auf diesen Beitrag antworten »

Hallo Arthur Dent,

Danke für deine Hilfe ! Ich habe es bemerkt, das es so einfach leider nicht geht... Ich habe in meinem Buch ein Beispiel gefunden, wo man die Kette in rekurrenten Klassen aufteilt und dann mehrere stationaere Verteilungen ausrechnet, schliesslich werden die Klassen wieder zusammengeführt, und so bekommt man am Ende die gesamte stationaere Verteilung. Denkst du, dass es so funktionieren wuerde? Wegen Copy Right Rechte kann ich die eingescannte Seiten nicht hier posten. Ich habe sie dir ueber PN geschickt.

Gruß,
Marko

20.03.2009, 18:27

AD

Auf diesen Beitrag antworten »

Ja, danke, so genau kenne ich mich da eben auch nicht aus. Wenn auch vielleicht umständlicher, sollte auch der von mir im letzten Beitrag skizzierte Weg zum Erfolg führen, wie ich mich mit einem kleinen MuPad-Skript überzeugt habe. Augenzwinkern

Augenzwinkern

20.03.2009, 18:32

martingale

Auf diesen Beitrag antworten »

Hallo,

es ist bestimmt ein guter Weg, aber ich muss es schließlich in Java programmieren und das ist meiner Meinnung nach nicht so einfach. smile

smile

Gruß

20.03.2009, 18:42

AD

Auf diesen Beitrag antworten »

Das ist wahr - ich hatte nur angenommen, dir steht eine LinAlg-Bibliothek zur Verfügung. Selber möchte ich eine komplette Jordan-Zerlegung gewiss auch nicht programmieren. Big Laugh

Big Laugh

20.03.2009, 18:57

martingale

Auf diesen Beitrag antworten »

Ich habe gleich gesehen, dass ich eine Bibliothek für die Jordan-Zerlegung zur Verfügung habe. Ich werde es mal ausprobieren. smile

smile

Wenn du möchtest kannst du dein Script hier pasten, Link: http://nopaste.info/

21.03.2009, 15:37

Huggy

Auf diesen Beitrag antworten »

Fand die Aufgabe interessant und habe deshalb versucht, die Diskussion zu verfolgen, obwohl ich mit Markov-Ketten nicht vertraut bin. Bin aber dann bei der Frage steckengeblieben:

Für was wird denn eine analytische Lösung gesucht?

Dachte zuerst, es geht um eine analytische Lösung für die Gewinnwahrscheinlichkeiten der Spieler A und B. Da man die aber leicht ausrechnen kann, ist es das wohl nicht.

Wäre nett, wenn ihr mich aufklären könntet.

25.03.2009, 11:50

martingale

Auf diesen Beitrag antworten »

Hallo Huggy,

da ich diese Aufgave als Java Programm implementieren musste, kommte auch eine Lösung als Simulation in Frage. D.h. dieser Versuch 10^6 oder 10^7 mal wiederholen, und die empirische Ergebnisse auswerten. Bei so vielen Wiederholungen, bekommt man eine sehr gute Schätzung der gesuchten Werte. Aber so eine Simulation (ich denke sie heißt Monte Carlo - Simulation) wird hier nicht verlangt. Was verlangt wurde ist eine analytische Lösung, wo man die Lösung durch Anwenden der Sätze ausrechnet. Alles lässt sich durch Lösen von LGSe ausrechnen. Für mich ein ganz kommisches Ergebniss ist, das aus der Teilaufgabe g), wo mann sich eine vierstellige Sequenz aussuchen soll, so dass die Gewinnchancen maximal werden.

Hier das Ergebniss:

Wahl Spieler 3:
Zustand: 0010 Speiler A: 0,333333 Spieler B: 0,500000 Spieler C: 0,166667
Zustand: 0011 Speiler A: 0,384615 Spieler B: 0,423077 Spieler C: 0,192308
Zustand: 0100 Speiler A: 0,187500 Spieler B: 0,468750 Spieler C: 0,343750
Zustand: 0101 Speiler A: 0,325000 Spieler B: 0,400000 Spieler C: 0,275000
Zustand: 0110 Speiler A: 0,359375 Spieler B: 0,296875 Spieler C: 0,343750
Zustand: 0111 Speiler A: 0,359375 Spieler B: 0,296875 Spieler C: 0,343750
Zustand: 1001 Speiler A: 0,343750 Spieler B: 0,437500 Spieler C: 0,218750
Zustand: 1010 Speiler A: 0,250000 Spieler B: 0,416667 Spieler C: 0,333333
Zustand: 1011 Speiler A: 0,355263 Spieler B: 0,276316 Spieler C: 0,368421
Zustand: 1101 Speiler A: 0,300000 Spieler B: 0,350000 Spieler C: 0,350000
Zustand: 1110 Speiler A: 0,343750 Spieler B: 0,218750 Spieler C: 0,437500
Zustand: 1111 Speiler A: 0,375000 Spieler B: 0,375000 Spieler C: 0,250000

Gruß

25.03.2009, 14:21

Huggy

Auf diesen Beitrag antworten »

Danke für die Info!

Zitat:

Original von martingale
Was verlangt wurde ist eine analytische Lösung, wo man die Lösung durch Anwenden der Sätze ausrechnet. Alles lässt sich durch Lösen von LGSe ausrechnen.

So hatte ich mir das auch vorgestellt, bis mich die Diskussion über Jordanzerlegung etc. in Verwirrung stürzte.

Zitat:

Für mich ein ganz kommisches Ergebniss ist, das aus der Teilaufgabe g), wo mann sich eine vierstellige Sequenz aussuchen soll, so dass die Gewinnchancen maximal werden.

Die überraschenden Gewinnwahrscheinlichkeiten machten die Aufgabe für mich so interessant.

25.03.2009, 17:23

AD

Auf diesen Beitrag antworten »

Zitat:

Original von martingale
Hier das Ergebniss:

Wahl Spieler 3:
Zustand: 0010 Speiler A: 0,333333 Spieler B: 0,500000 Spieler C: 0,166667
Zustand: 0011 Speiler A: 0,384615 Spieler B: 0,423077 Spieler C: 0,192308
Zustand: 0100 Speiler A: 0,187500 Spieler B: 0,468750 Spieler C: 0,343750
Zustand: 0101 Speiler A: 0,325000 Spieler B: 0,400000 Spieler C: 0,275000
Zustand: 0110 Speiler A: 0,359375 Spieler B: 0,296875 Spieler C: 0,343750
Zustand: 0111 Speiler A: 0,359375 Spieler B: 0,296875 Spieler C: 0,343750
Zustand: 1001 Speiler A: 0,343750 Spieler B: 0,437500 Spieler C: 0,218750
Zustand: 1010 Speiler A: 0,250000 Spieler B: 0,416667 Spieler C: 0,333333
Zustand: 1011 Speiler A: 0,355263 Spieler B: 0,276316 Spieler C: 0,368421
Zustand: 1101 Speiler A: 0,300000 Spieler B: 0,350000 Spieler C: 0,350000
Zustand: 1110 Speiler A: 0,343750 Spieler B: 0,218750 Spieler C: 0,437500
Zustand: 1111 Speiler A: 0,375000 Spieler B: 0,375000 Spieler C: 0,250000

Kann es sein, dass du hier die Wkt-werte für Spieler A (1100) und B (000) gerade vertauscht hast? verwirrt

verwirrt

25.03.2009, 18:09

martingale

Auf diesen Beitrag antworten »

Hallo Arthur Dent,

vollkommen korrekt ! Ich hab die beide Wahrscheinlichkeiten vertauscht, irgendwie in meinem Kopf war Spieler A, der mit "000", was nicht die Aufgabenstellung entspircht. smile

smile

Hier noch mal die richtige Wahrscheinlichkeiten:

Zustand: 0010 Speiler A: 0,500000 Spieler B: 0,333333 Spieler C: 0,166667
Zustand: 0011 Speiler A: 0,423077 Spieler B: 0,384615 Spieler C: 0,192308
Zustand: 0100 Speiler A: 0,468750 Spieler B: 0,187500 Spieler C: 0,343750
Zustand: 0101 Speiler A: 0,400000 Spieler B: 0,325000 Spieler C: 0,275000
Zustand: 0110 Speiler A: 0,296875 Spieler B: 0,359375 Spieler C: 0,343750
Zustand: 0111 Speiler A: 0,296875 Spieler B: 0,359375 Spieler C: 0,343750
Zustand: 1001 Speiler A: 0,437500 Spieler B: 0,343750 Spieler C: 0,218750
Zustand: 1010 Speiler A: 0,416667 Spieler B: 0,250000 Spieler C: 0,333333
Zustand: 1011 Speiler A: 0,276316 Spieler B: 0,355263 Spieler C: 0,368421
Zustand: 1101 Speiler A: 0,350000 Spieler B: 0,300000 Spieler C: 0,350000
Zustand: 1110 Speiler A: 0,218750 Spieler B: 0,343750 Spieler C: 0,437500
Zustand: 1111 Speiler A: 0,375000 Spieler B: 0,375000 Spieler C: 0,250000

Bei 3 Spieler finde ich komisch, dass die Wahrscheinlichkeit für "1110" grösser als diese für "0111"ist, intutiv hätte ich gesagt, dass die gleich sein müssen.

Gruß

25.03.2009, 19:07

AD

Auf diesen Beitrag antworten »

Für die Freunde rationaler Zahlen das ganze mal in einer Tabelle:

$\begin{eqnarray*} \begin{array}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline &&&&&&&&&&&&&\\ \mbox{Code C} & - & 0010 & 0011 & 0100 & 0101 & 0110 & 0111 & 1001 & 1010 & 1011 & 1101 & 1110 & 1111 \\[2ex] \hline\hline &&&&&&&&&&&&&\\ p_A \quad (1100)& \displaystyle\frac{7}{12} & \displaystyle\frac{1}{2} & \displaystyle\frac{11}{26} & \displaystyle\frac{15}{32} & \displaystyle\frac{2}{5} & \displaystyle\frac{19}{64} & \displaystyle\frac{19}{64} & \displaystyle\frac{7}{16} & \displaystyle\frac{5}{12} & \displaystyle\frac{21}{76} & \displaystyle\frac{7}{20} & \displaystyle\frac{7}{32} & \displaystyle\frac{3}{8} \\[2ex] \hline &&&&&&&&&&&&&\\ p_B \quad (000) & \displaystyle\frac{5}{12} & \displaystyle\frac{1}{3} & \displaystyle\frac{5}{13} & \displaystyle\frac{3}{16} & \displaystyle\frac{13}{40} & \displaystyle\frac{23}{64} & \displaystyle\frac{23}{64} & \displaystyle\frac{11}{32} & \displaystyle\frac{1}{4} & \displaystyle\frac{27}{76} & \displaystyle\frac{3}{10} & \displaystyle\frac{11}{32} & \displaystyle\frac{3}{8} \\[2ex] \hline &&&&&&&&&&&&&\\ p_C & - & \displaystyle\frac{1}{6} & \displaystyle\frac{5}{26} & \displaystyle\frac{11}{32} & \displaystyle\frac{11}{40} & \displaystyle\frac{11}{32} & \displaystyle\frac{11}{32} & \displaystyle\frac{7}{32} & \displaystyle\frac{1}{3} & \displaystyle\frac{7}{19} & \displaystyle\frac{7}{20} & \displaystyle\frac{7}{16} & \displaystyle\frac{1}{4} \\[2ex] \hline\end{array} \end{eqnarray*}$

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »