Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Aufgabe mit Wahrscheinlichkeiten elegant lösen

Aufgabe mit Wahrscheinlichkeiten elegant lösen

Universität / Fachhochschule

Tags: Eigenwert, Markov-Ketten, Matrzienk, stationäre Vektoren

IB361 aktiv_icon

22:47 Uhr, 10.12.2024

Hi there
Aufgabe Urnen und Kugeln:
Zwei Spieler treten gegeneinander an. Jeder Spieler hat eine weisse Urne mit zwei schwarzen Bällen und eine schwarze Urne mit zwei weissen Bällen. In jeder Runde nimmt der erste Spieler
zufällig einen Ball aus jeder seiner Urnen und tauscht sie aus, während der zweite Spieler zufällig einen Ball aus seiner weissen Urne nimmt, ihn in seine schwarze Urne legt und dann zufällig einen Ball aus seiner schwarzen Urne nimmt und ihn in seine weisse Urne legt.
Der erste Spieler, der die weissen Bälle in seiner weissen Urne und die schwarzen Bälle in seiner schwarzen Urne hat, gewinnt. Bei einem Unentschieden haben beide Spieler
gewonnen.
Wie hoch ist die Wahrscheinlichkeit, dass der erste Spieler gewinnt? Geben Sie die Antwort in Form eines nicht reduzierbaren Bruchs an.

3 Zustände:
1 die Urne enthält 2 Kugeln anderer Farbe als die Urne
2 Die Urne enthält je eine weisse und eine schwarze Kugel
3 die Urne enthält 2 Kugeln der gleichen Farbe wie die Urne (Spiel endet)

Da 2 Spieler

\to 7

Zustände

(1

. Ziffer Urne1, 2. Ziffer Urne2):

1 : 11

2 : 21

3 : 22

4 : 12

5 : 1

. Spieler gewinnt

(31, 32)

6 : 2

. Spieler gewinnt

(13, 23)

7: Beide Spieler gewinnen

(33)

Das ergibt ein schönes Diagramm, inkl. Wahrscheinlichkeiten Zustandsänderungen, siehe Bild 1.

System lässt sich abbilden mit einer

7 x 7

Matrix
Die Summe der Spalten ergeben immer 1.
Lösung: Diese Matrix mit Startvektor

1,0,0,0,0,0,0

(Das System startet im Zustand

11)

multiplizieren. Resultierender Vektor wiederum mit Matrix multiplizieren und so weiter, unendlich mal

\to

Lösung

= v 5 + v 7

.
Die Werte für

v 1 . . v 4

müssen 0 sein, denn wenn wir unendlich oft wiederholen bleibt das System in den "absorbierenden" Zustände

5, 6

und 7 "gefangen".

Jetzt habe ich im Internet über Markov-Ketten und stationäre Vektoren gelesen:
Betrachten wir den Lösungsvektor

v 1 . . v 7

. Dann gilt:
v*Matrix

= v

Lösungsvektor mit der Matrix multipliziert

\to

resultiert derselbe Lösungsvektor, daher wird der auch "stationärer Vektor" genannt. So folgt also ein Gleichungssystem mit 7 Unbekannten und 7 Gleichungen und alles sollte gut sein.

Mein Problem:
Das Gleichungssystem ergibt rasch, dass

v 1, v 2, v 3

und

v 4 = 0

sind, was ja auch korrekt ist.
jetzt weiss ich nur noch, dass

v 5, v 6

und

v 7 = 1

sein müssen.
Mehr Informationen über diese Variablen erhalte ich mittels Gleichungssystem nicht.
Kann mir bitte jemand helfen? Besten Dank.
(Natürlich kann ich die Lösung programmieren und erhalte knapp

68 %

. Gefragt ist aber ein nicht reduzierbarer Bruch, also eine exakte Lösung...).

Sorry, ich kriege die beiden Bilder nicht hoch.
Ich gebe sie an bei Datei auswählen - funktioniert nicht, mit jpg oder bmp probiert...

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)

calc007

00:04 Uhr, 11.12.2024

Hallo
Deine Ansätze sind ja schon aussichtsreich und (im Überfliegen) richtig.
Ich bin näher an's Ziel gekommen, indem ich über die von dir beschriebenen 7 Zustände für den zweiten Spieler noch Zwischen-Stände beschrieben habe,

d . h

. den Zustand, in dem der zweite Spieler schon eine Kugel in die schwarze Urne gezogen hat, aber noch nicht zurück.
Diese Zwischenzustände für den zweiten Spieler lauten demnach:

a)

er hat in der weißen Urne eine schwarze Kugel, und in der schwarzen Urne zwei weiße und eine schwarze Kugel;

b)

er hat in der weißen Urne eine weiße Kugel, und in der schwarzen Urne eine weiße und zwei schwarze Kugeln;

Jetzt tust du dir leichter / übersichtlicher, wie für diesen zweiten Spieler

>

diese Zwischenstände aus den Endständen nach jeder Runde zustande kommen,

>

die Endstände nach jeder vollen Runde aus den Zwischenständen zustande kommen.

IB361 aktiv_icon

06:52 Uhr, 11.12.2024

Danke für die Antwort.
Genau, der zweite Spieler macht immer zwei Teilschritte für eine Zustandsänderung.
Mein Zustandsdiagramm bildet immer nur die ganzen Zustände ab, ohne Teilschritte.
Ich sehe grad nicht, wie ich weiterkommen soll, indem ich die Teilschritte in meine Überlegungen mit einbeziehe?

Da ich die Bilder nicht hochladen kann, hier wenigstens noch meine Matrix:

0, \frac{1}{12}, \frac{1}{24}, 0,0,0,0

\frac{1}{3}, \frac{1}{6}, \frac{1}{12}, \frac{1}{6}, 0,0,0

\frac{2}{3}, \frac{1}{3}, \frac{1}{3}, \frac{2}{3}, 0, 0, 0

0, \frac{1}{6}, \frac{1}{6}, 0, 0, 0, 0

0, \frac{1}{4}, \frac{5}{24}, 0, 1, 0, 0

0, 0, \frac{1}{8}, \frac{1}{6}, 0, 1, 0

0, 0, \frac{1}{24}, 0, 0, 0, 1

So zu lesen, 1. Spalte:

p

von Zustand

11

nach

11

ist 0 (der erste Spieler wird von 1 immer zu 2 wechseln).

p

von Zustand

11

nach

21

ist

\frac{1}{3}

p

von Zustand

11

nach

22

ist

\frac{2}{3}

Die anderen Zustände

12,

nur Spieler 1 gewinnt, nur Spieler 2 gewinnt und beide gewinnen sind ebenfalls nicht erreichbar, da eben der Zustand des 1. Spielers 2 sein muss

\to 0

2. Spalte:

p

von Zustand

21

zurück zu Zustand

11

ist

\frac{1}{12}

p,

dass ich bei Zustand

21

bleibe ist

\frac{1}{6}

usw.
verständlich?

HAL9000

12:35 Uhr, 11.12.2024

Deine drei Zielzustände "1 gewinnt", "2 gewinnt" und "unentschieden" sind ja absorbierende Markovketten-Zustände. Mit welcher Wahrscheinlichkeit die angenommen werden, kann man so berechnen:

de.wikipedia.org/wiki/Absorbierender_Zustand#Berechnung_der_Absorptionswahrscheinlichkeiten

Geht man so vor, bekommt man die exakten Wahrscheinlichkeiten

\frac{269}{451}

\frac{145}{451}

bzw.

\frac{37}{451}

für Gewinn 1, Gewinn 2 bzw. Unentschieden (ohne Gewähr).

IB361 aktiv_icon

07:12 Uhr, 12.12.2024

Besten Dank, Hal9000
Der Wiki-Eintrag ist für mich wenig verständlich, zu kryptisch.
So habe ich mich an das Beispiel der 5x5-Matrix gehalten.
Ich erhalte für diese Matrix die Eigenwerte

1, - 1, 0.2, - 0.2

korrekt?
Für den Eigenwert 1 erhalte ich beispielsweise den Eigenvektor

1,1,1,1,1

Wenn ich den Eigenvektor mit der Matrix multipliziere sehe ich sehr schnell, dass das wieder diesen Eigenvektor gibt, das sollte also stimmen, nicht?
Ich habe gedacht, der Eigenraum wird durch die Eigenvektoren aufgespannt.
Die beiden angegebenen Vektoren sind jedoch

- 11, - 1,0,1,1

und

12,2,1,0,0

.
Ich habe das jetzt

3 h

versucht zu verstehen und komme da schon nicht weiter.
Kannst Du mir helfen, wie man auf die beiden Vektoren kommt und warum nicht beispielsweise

1,1,1,1,1

?
Danke.

HAL9000

09:04 Uhr, 12.12.2024

Die Ü-Matrix deiner Markov Kette ist

P = (\begin{array}{ccccccc} 0 & \frac{1}{3} & \frac{2}{3} & 0 & 0 & 0 & 0 \\ \frac{1}{12} & \frac{1}{6} & \frac{1}{3} & \frac{1}{6} & \frac{1}{4} & 0 & 0 \\ \frac{1}{24} & \frac{1}{12} & \frac{1}{3} & \frac{1}{6} & \frac{5}{24} & \frac{1}{8} & \frac{1}{24} \\ 0 & \frac{1}{6} & \frac{2}{3} & 0 & 0 & \frac{1}{6} & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array})

(du hattest oben die zugehörige transponierte Matrix

P^{T}

richtig dargestellt). Die letzten drei Zustände sind absorbierend, aufgeteilt in drei Klassen zu je einem Zustand.

Die Absorptionswahrscheinlichkeiten von Zustand

i \in {1, 2, 3, 4, 5}

ausgehend in einen festgelegten Zustand

k \in {5, 6, 7}

lassen sich bestimmen durch Lösung des Gleichungssystems

P \cdot a = a

mit

a = {(a_{1}, \dots, a_{7})}^{T}

, wobei schon festgelegt wird

a_{k} = 1

sowie

a_{j} = 0

für

j \in {5, 6, 7} \ {k}

. Mit Einheitsmatrix

I

umgeschrieben heißt das

(P - I) \cdot a = 0

.

In deinem Beispiel konkret für Absorptionszustand

k = 5

heißt das

(P - I) \cdot a = (\begin{array}{ccccccc} - 1 & \frac{1}{3} & \frac{2}{3} & 0 & 0 & 0 & 0 \\ \frac{1}{12} & - \frac{5}{6} & \frac{1}{3} & \frac{1}{6} & \frac{1}{4} & 0 & 0 \\ \frac{1}{24} & \frac{1}{12} & - \frac{2}{3} & \frac{1}{6} & \frac{5}{24} & \frac{1}{8} & \frac{1}{24} \\ 0 & \frac{1}{6} & \frac{2}{3} & - 1 & 0 & \frac{1}{6} & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}) \cdot (\begin{array}{c} a_{51} \\ a_{52} \\ a_{53} \\ a_{54} \\ 1 \\ 0 \\ 0 \end{array}) = (\begin{array}{c} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{array}) (*)

Die letzten drei Zeilen sind offenbar automatisch erfüllt, es verbleibt das 4x4-System

(\begin{array}{cccc} - 1 & \frac{1}{3} & \frac{2}{3} & 0 \\ \frac{1}{12} & - \frac{5}{6} & \frac{1}{3} & \frac{1}{6} \\ \frac{1}{24} & \frac{1}{12} & - \frac{2}{3} & \frac{1}{6} \\ 0 & \frac{1}{6} & \frac{2}{3} & - 1 \end{array}) \cdot (\begin{array}{c} a_{51} \\ a_{52} \\ a_{53} \\ a_{54} \end{array}) = (\begin{array}{ccccccc} 0 \\ - \frac{1}{4} \\ - \frac{5}{24} \\ 0 \end{array}) (* *)

mit der Lösung

a_{51} = \frac{269}{451}, a_{52} = \frac{306}{451}, a_{53} = \frac{501}{902}, a_{54} = \frac{218}{451}

, uns interessiert natürlich nur

a_{51}

, weil wir ja in Zustand 1 starten.

Für

k = 6

sowie

k = 7

ersetzt man in (*) entsprechend

(\begin{array}{c} a_{61} \\ a_{62} \\ a_{63} \\ a_{64} \\ 0 \\ 1 \\ 0 \end{array})

sowie

(\begin{array}{c} a_{71} \\ a_{72} \\ a_{73} \\ a_{74} \\ 0 \\ 0 \\ 1 \end{array})

, was in entsprechende Gleichungssysteme (**) mit anderer rechter Seite mündet. Für die Summe der drei Wahrscheinlichkeits-Vektoren haben wir dann tatsächlich

(\begin{array}{c} a_{51} \\ a_{52} \\ a_{53} \\ a_{54} \\ 1 \\ 0 \\ 0 \end{array}) + (\begin{array}{c} a_{61} \\ a_{62} \\ a_{63} \\ a_{64} \\ 0 \\ 1 \\ 0 \end{array}) + (\begin{array}{c} a_{71} \\ a_{72} \\ a_{73} \\ a_{74} \\ 0 \\ 0 \\ 1 \end{array}) = (\begin{array}{c} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{array})

den von dir angesprochenen simplen Eigenvektor, der inhaltlich eigentlich nur die Trivialität "mit Sicherheit gelangt man irgendwann in einen der drei absorbierenden Zustände" aussagt. ;-)

P.S.: Es besteht keine Notwendigkeit, die Eigenwerte alle auszurechnen - das Verfahren bestimmt lediglich spezielle Eigenvektoren zum Eigenwert 1 (der ja Eigenwert jeder stochastischen Matrix ist) - da hast du wohl ziemlich schlecht quergelesen.

IB361 aktiv_icon

17:29 Uhr, 13.12.2024

Herzlichen Dank, HAL9000, so wird das klar und praktikabel, ich bin sehr froh um Deine verständliche Antwort! In Wiki haben sie eben diese "aufspannenden" Vektoren als Teil Ihrer Lösung verwendet, daher meinte ich, Eigenwert und -vektoren werden benötigt. Aber wie ich erleichtert feststelle, ist alles viel einfacher (und glaube mir, ich habe das nicht überflogen, ich habe mich wirklich bemüht, das nachvollziehen zu können. Und ja, jetzt sehe ich auch, dass das mit dem Einheitsvektor nicht sehr intelligent war

IB361 aktiv_icon

17:29 Uhr, 13.12.2024

6,7

auf

0,

dann haben wir die Werte, wenn ich im Zustand 5 lande.
Warum die Absorptionswahrscheinlichkeiten so doch recht elegant ermittelt werden können, verstehe ich nicht wirklich. Das System könnte theoretisch tausende von Zustandsänderungen machen, bevor es von einem Absorptionszustand "aufgesaugt" wird. Und all diese Wahrscheinlichkeiten, auch wenn sie klein sind, müssen berücksichtigt werden.
So hätte ich eine Summe von Wahr'keiten erwartet, von 1 bis unendlich und nicht ein relativ einfach zu lösendes, statische Gleichungssystem.
Darf ich mir diese Frage noch erlauben? Besten Dank

HAL9000

18:09 Uhr, 13.12.2024

Eigentlich steht das alles sehr gut in dem Wiki-Beitrag beschrieben - ich kann es nur nochmal wiederholen und vielleicht noch etwas ausschmückend erläutern:

τ_{k}^{i}

sei der zufällige Zeitpunkt, bei dem erstmals der absorbierende Zustand

k

erreicht wird, wenn die Kette in Zustand

i

startet. Dabei steht

τ_{k}^{i} = \infty

für das Ereignis, es gar nicht in

k

zu schaffen (und damit offenbar dann in einen anderen absorbierenden Zustand).

Ganz offenbar ist

N \to P (τ_{k}^{i} < N)

eine monoton wachsende Funktion, außerdem sind die Werte nach oben durch 1 beschränkt - ergo existiert der Grenzwert

lim_{N \to \infty} P (τ_{k}^{i} < N) = : a_{k}^{i}

. (*)

Sein

T

die Menge der transienten Zustände der Kette, dann gilt für jeden endlichen Zeitpunkt

N

gemäß Formel der totalen Wahrscheinlichkeit sowie Startzustand

i \in T

die Gleichung

P (τ_{k}^{i} < N + 1) = p_{i k} + \sum_{j \in T} p_{i j} P (τ_{k}^{j} < N)

, (**)

denn: Entweder schafft man es im ersten Schritt bereits in Zustand

k

, oder man geht wieder in einen transienten Zustand über und muss es dann in einem Schritt weniger schaffen. Wegen (*) kann man in (**) zum Grenzwert

N \to \infty

übergehen und bekommt dann jenes

a_{k}^{i} = p_{i k} + \sum_{j \in T} p_{i j} a_{k}^{j}

über das wir die ganze Zeit sprechen. Was daran ist unverständlich???

IB361 aktiv_icon

18:33 Uhr, 13.12.2024

Knopf gelöst, wir haben ja tatsächlich die Summe bis nach unendlich und wie bei einer konvergierenden Reihe

(z . B

. Leibniz-Reihe für PI/4) wird der Grenzwert berechnet, hier im stationären Vektor des Endzustandes, alles klar, gutes Wochenende und nochmals besten Dank!

1589181

1589154

	Status: nicht eingeloggt	Noch nicht registriert?