Spieltheorie / Verteilung Problem (überarbeitet) < Stochastik < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 09:32 Mo 28.06.2004 | | Autor: | uamini |
Hallo...
Ich habe folgendes Problem..
Ein Spieler beginnt mit 2 Credits und wiederholt ein Spiel unendlich, bis er keine Credits mehr hat. Er gewinnt dabei jedes Mal mit Wahrscheinlichkeit 0.5 einen Credit und verliert mit gleicher Wahrscheinlichkeit einen. Sobald er 9 Credits erreicht, wird 1 Credit abgezogen (gilt nicht als Spiel) und das Spiel geht mit 8 Credits weiter.
Ich soll hierzu zunächst eine Verteilung der Gesamtanzahl an Spielen herausfinden, weiss aber nicht, wie ich dieses Problem bearbeiten soll.
Mein 1. Ansatz war es, den Spielablauf als 100110etc-Run zu betrachten. Offensichtlich müssen die zwei letzten Spiele verloren werden (also 0 in dem Modell), da der Spieler danach keine Credits mehr hat. Somit wäre z. B. P(X=8) gleich der Anzahl an möglichen 1/0-Runs auf den restlichen 6 Feldern geteilt durch [mm] 2^8. [/mm] Dies stimmt aber nicht ganz, weil außerdem die Anzahl an Nullen nie größer als die Anzahl an Einsen + 1 sein darf (bei 2 Startcredits wär er dann nämlich schon frühzeitig pleite). Sehe also nicht ganz, wie ich so etwas modellieren kann. Die Beachtung der Grenze von 9 Credits wäre dann der zweite Schritt, wobei mir das noch unklarer erscheint. Kennt sich hier jemand mit so etwas aus?
Ich habe diese Frage in keinem weiteren Forum gestellt.
Leichtes Update, es sind weitere Fragen zur Problemstellung hinzugekommen:
a) Angenommen, das Spiel wird mit 2 Credits begonnen, mit welcher Wahrscheinlichkeit erreicht der Spieler N Credits, ohne davor pleite zu gehen? (wobei das Spiel bei erstmaligem Erreichen beendet wird)...Spezialfälle wie N=5,6,7, etc wären dabei natürlich auch schon mal hilfreich; die Geschichte mit den 9 Credits als Obergrenze soll hier aussen vor gelassen werden
b) Der Spieler spielt solange, bis er keine Credits mehr hat. Jedes Mal, wenn der Spieler 9 Credits erreicht, wird ihm ein Credit abgezogen, dafür bekommt er 50 . Berechne eine Verteilung seines Geldgewinnes.
Ich arbeite selber an den Fragen, sollte ich also etwas finden, werde ich es sofort posten.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:50 Di 29.06.2004 | | Autor: | Julius |
Hallo!
Also, ich würde hier einen Markovschen Ansatz wählen.
Für alle $n [mm] \ge 1,\, [/mm] 1 [mm] \le [/mm] m [mm] \le [/mm] 7$ gilt:
$P(X=n|C=m) = [mm] \frac{1}{2} \cdot [/mm] P(X=n+1|C=m-1) + [mm] \frac{1}{2} \cdot [/mm] P(X=n+1|C=m+1)$,
und für $m=8$:
$P(X=n|C=8) = [mm] \frac{1}{2} \cdot [/mm] P(X=n+1|C=7) + [mm] \frac{1}{2} \cdot [/mm] P(X=n+1|C=8)$,
wobei $X$ die Restspiele und $C$ den Kontostand misst.
Natürlich kann man dieses unendliche Gleichungssystem nicht so ohne weiteres lösen.
Man braucht in jedem Fall noch Randbedingungen.
Diese lauten:
$P(X=0|C=0) = 1$,
$P(X=0|C=m) = 0$, $1 [mm] \le [/mm] m [mm] \le [/mm] 8$,
$P(X=n|C=0) = 0$, $n [mm] \ge [/mm] 1$.
Jetzt weiß ich aber auch nicht genau, wie man das Gleichungssystem dann löst. 
Es ist nur als Idee zu verstehen, als erster Ansatz sozusagen.
Liebe Grüße
Julius
P.S. Diese Frage gehört aber in kein Schulforum, oder??
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:12 Di 29.06.2004 | | Autor: | uamini |
Richtig, das Uni-Stochastik Forum wäre wohl ein passenderer Ort gewesen, das hatte ich bloß nicht gesehen...typischer Anfängerfehler halt :)
Aber danke für den Ansatz, ich schau mir den gleich mal an...mit Markow-Ketten hatte ich auch rumprobiert und damit zumindest rausbekommen, wie der Erwartungswert für die verschiedenen Credit-Stände ist (Spieler dürfte während des Spiels je 2-mal einen und 9 Credits haben so wie je 4-mal alle anderen Stände)...das lässt sich auch induktiv nachweisen..
|
|
|
| |
|
Hallo!
Ich habe mal ein wenig mit Matlab gearbeitet, und so kommt man zumindest auf Ergebnisse, ohne sich einen Knoten ins Gehirn zu denken.
Die Übergangsmatrix der Markovkette ist ja
[mm]P=\begin{pmatrix}1&0&0&0&0&0&0&0&0\\
\frac{1}{2}&0&\frac{1}{2}&0&0&0&0&0&0\\
0&\frac{1}{2}&0&\frac{1}{2}&0&0&0&0&0\\ 0&0&\frac{1}{2}&0&\frac{1}{2}&0&0&0&0\\
0&0&0&\frac{1}{2}&0&\frac{1}{2}&0&0&0\\ 0&0&0&0&\frac{1}{2}&0&\frac{1}{2}&0&0\\
0&0&0&0&0&\frac{1}{2}&0&\frac{1}{2}&0\\ 0&0&0&0&0&0&\frac{1}{2}&0&\frac{1}{2}\\ 0&0&0&0&0&0&0&\frac{1}{2}&\frac{1}{2}\end{pmatrix}[/mm]
(Dank an Paulus, dass die Matrix jetzt lesbar ist!!!)
Dabei nehme ich die Zustände von
0 bis 8 an. Der erste Eintrag der Matrix ist beispielsweise die Wahrscheinlichkeit für einen Übergang von 0 nach 0, nach Voraussetzung beträgt diese 1.
Geht man nun von der Startverteilung [mm] $\pi_0=(0,0,1,0,0,0,0,0,0)^T$ [/mm] aus (d.h. wir beginnen sicher im Zustand 2 Credits), ergeben sich die Wahrscheinlichkeiten für den Zustand nach $n$ Spielen als Einträge des Vektors
[mm]\pi_n^T=\pi_0^T \cdot P^n[/mm]
Uns interessiert ja eigentlich nur [mm] $P(X_n=0)$, [/mm] also im absorbierenden Zustand zu landen. Diese ist gerade der erste Eintrag von [mm] $\pi_n$.
[/mm]
Die Rechnerei erledigt z.B. Matlab. Um die Wahrscheinlichkeit zu bestimmen, dass das Spiel genau in der $n$-ten Runde vorbei ist, muss man lediglich
den ersten Eintrag von [mm] $\pi_n$ [/mm] minus den ersten Eintrag von [mm] $\pi_{n-1}$ [/mm] berechnen. Denn im Ereignis [mm] $\{X_n=0\}$ [/mm] steckt ja das Ereignis [mm] $\{X_{n-1}=0\}$ [/mm] drin, deshalb muss man das abziehen.
Als Ergebnis erhalte ich bis $n=30$ für die Zufallsvariable $A$ (Anzahl der Spielrunden) die Verteilung:
P(A=2) = 0.2500
P(A=3) = 0
. 0.1250
. 0
. 0.0781
0
0.0547
0
0.0410
0
0.0322
0
0.0262
0.0000
0.0218
0.0001
0.0185
0.0003
0.0160
0.0004
0.0140
0.0007
0.0124
0.0009
0.0111
0.0011
0.0100
0.0014
0.0090
Ich finde, die Werte sehen vernünftig aus. Vielleicht kann man aus dem Matrizenansatz auch eine geschlossene Formel für die Wahrscheinlichkeiten herleiten. Aber ich gebe zu, mit Matlab ist es natürlich geschummelt
Liebe Grüße
Brigitte
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:34 Di 29.06.2004 | | Autor: | Paulus |
Sieht die Matrix so aus?
$ [mm] P=\begin{pmatrix}1&0&0&0&0&0&0&0&0\\\frac{1}{2}&0&\frac{1}{2}&0&0&0&0&0&0\\0&\frac{1}{2}&0&\frac{1}{2}&0&0&0&0&0\\ 0&0&\frac{1}{2}&0&\frac{1}{2}&0&0&0&0\\0&0&0&\frac{1}{2}&0&\frac{1}{2}&0&0&0\\ 0&0&0&0&\frac{1}{2}&0&\frac{1}{2}&0&0\\0&0&0&0&0&\frac{1}{2}&0&\frac{1}{2}&0\\ 0&0&0&0&0&0&\frac{1}{2}&0&\frac{1}{2}\\ 0&0&0&0&0&0&0&\frac{1}{2}&\frac{1}{2}\end{pmatrix}$
[/mm]
Mit lieben Grüssen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:40 Di 29.06.2004 | | Autor: | uamini |
>Sieht die Matrix so aus?
>
>
Die Matrix ist nicht ganz korrekt, denn von Zustand 9 kommen wir mit Wahrscheinlichkeit 1 in Zustand 8.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:09 Di 29.06.2004 | | Autor: | Julius |
Hallo!
> Die Matrix ist nicht ganz korrekt, denn von Zustand 9
> kommen wir mit Wahrscheinlichkeit 1 in Zustand 8.
Doch, die Matrix ist korrekt. Der Zustand $9$ ist ja gar nicht in der Matrix abgebildet, es geht ja mit Zustand $0$ los und endet bei Zustand $8$. Der Übergang $8 [mm] \to [/mm] 9$ muss ja gar nicht modelliert werden, da man auf $8$ zurückspringt (ohne zusätzliches Spiel). Das hat Brigitte also zu recht als Übergang $8 [mm] \to [/mm] 8$ gewertet (wie ich das ja auch schon in meinem Beitrag gemacht hatte).
Liebe Grüße
Julius
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:51 Di 29.06.2004 | | Autor: | uamini |
Die Ergebnisse stimmen auch mit meinen (abgezählten) Proben überein, erscheinen mir also plausibel. Allerdings ist P(A=1) natürlich 0, es wird mindestens 2 Spiele geben. Für diesen Abschnitt des Problems würde ich mich mit den Werten zufrieden geben, sollte also niemand einen Geistesblitz haben, wäre es ab jetzt sinnvoller, sich mit den weiteren Fragen auseinander zu setzen.
Danke im Voraus :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:09 Di 29.06.2004 | | Autor: | Brigitte |
Hallo nochmal!
Dein Einwand mit $A=1$ ist berechtigt. War da ein bisschen vorschnell.
Die Matrix stimmt aber schon so. Die Zustände, die ich betrachte, sind ja nur zwischen 0 und 8. Von der 8 aus kann ich runterfallen auf die 7 oder zur 9 kommen, was ja dann im gleichen Moment auf 8 zurückgestuft wird. Also taucht die 9 bei mir gar nicht auf.
Wenn ich heute abend Zeit habe, wage ich mich noch mal an die anderen Teilaufgaben. Aber für explizite Lösungen habe ich wenig Hoffnung :-(
Liebe Grüße
Brigitte
Viele Grüße
Brigitte
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:23 Di 29.06.2004 | | Autor: | Julius |
Hallo!
Wenn du daraus jetzt eine explizite Darstellung bekommen wolltest, müsstest du von dieser Matrix die Jorgansche Normalform (JNF) bilden, mit deren Hilfe sich die Potenzen leicht bilden lassen. Daraus kannst du dann induktiv eine explizite Darstellung nachweisen.
Die Frage ist: Lohnt sich die Arbeit? Denn es ist mit Sicherheit viel Arbeit, von dieser $9 [mm] \times [/mm] 9$-Matrix die JNF zu berechnen.
Aber es würde so klappen!
Liebe Grüße
Julius
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:56 Di 29.06.2004 | | Autor: | uamini |
Zu Abschnitt a) habe ich wohl jetzt die Lösung.
Habe mich ein wenig mit Markow-Ketten befasst und bin dabei auf den richtigen Ansatz gestoßen.
Definiert man 0 und N als absorbierende Zustände, so benötigt man einfach eine Methode, um die Wahrscheinlichkeit zu berechnen, vom Zustand 2 in die absorbierenden Zustände zu gelangen.
Auf http://www.atlis.com/services/composition/samples/Quark%20Sample%20Pages/Winston-1076.ch05.pdf ist dies im Abschnitt "absorbing chains" sehr verständlich erklärt (am Ende ist es eine Matrizen-Multiplikation: (I-Q)^(-1)*R).
Falls jemand seine Ergebnisse vergleichen will, ich komme auf folgende Werte:
N=3 => W'keit ist 2/3
N=4 => W'keit ist 1/2
N=5 => W'keit ist 2/5
N=6 => Wkeit ist 1/3
N=7 => W'keit ist 0,2857
N = 15 => W'keit ist 0,1333
N=25 => W'keit ist 0,08
Bleibt also nur noch Frage b) übrig, dort wird die Obergrenze aber nicht als absorbierender Zustand definiert werden können...man müsste irgendwie berechnen können, mit welcher Wahrscheinlichkeit ein Zustand n-Mal durchlaufen wird, allerdings ist mir auf Anhieb kein Weg bekannt.
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion | | Datum: | 10:13 Do 01.07.2004 | | Autor: | uamini |
Ich glaube, auch b) gelöst zu haben, bitte aber um Feedback, ob meine Idee korrekt ist.
Ich definiere die Zustände 0 und 9 als absorbierend. Wie bereits erwähnt, bin ich in der Lage, die Wahrscheinlichkeit zu errechnen, von jedem Zustand zur 9 zu gelangen. Somit wäre der Fall "9 wird einmal erreicht" gelöst. Von der 9 kommt man automatisch zur 8. Wenn ich weiter so tue, als ob 9 absorbierend wäre, weiß ich also auch, mit welcher Wahrscheinlichkeit man von der 8 zur 9 kommt. Somit wäre
P("9 wird n-mal erreicht") = P("9 wird von 2 aus erreicht") * P("9 wird von 8 aus erreicht") ^ (n-1) * P("0 wird von 8 aus erreicht") und der Geldgewinn dann 50 für jedes Erreichen.
Die Frage ist also, ob man das Hauptroblem in Teilprobleme vom Typ "erreiche absorbierenden Zustand 9" zerlegen kann und bei jedem Erfolg das Ganze von der 8 aus wiederholt.
Klingt meines Erachtens gut, aber vielleicht hab ich was übersehen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:29 So 04.07.2004 | | Autor: | Julius |
Hallo uamini!
Deine Idee klingt plausibel und gut, ich finde auch keinen Fehler. Aber ich möchte nicht meine Hand dafür ins Feuer legen, weil alles doch sehr intuitiv angedacht ist und nicht etwa mathematisch belegt. Im Moment bin ich allerdings nicht mehr so sehr mit Markov-Ketten vertraut, dass ich jetzt ad hoc einen mathematischen Beweis liefern könnte.
Ich wollte dir halt nur ein Feedback geben, dass es dein Ansatz intuitiv logisch klingt.
Liebe Grüße
Julius
|
|
|
|
