Markowkette mit Rückkopplung < stoch. Prozesse < Stochastik < Hochschule < Mathe < Vorhilfe
|
Bei dem folgenden Problem stimmen die Ergebnisse einer theoretischen Betrachtung und einer Computersimulation nicht überein, aber ich kann den Fehler nicht finden. Man findet eine Darstellung in dem Film "Absurde Mathematik" unter <http://www.youtube.com/watch?v=dW4puvH-A3g > Beginn bei 10:10 Minuten, Ende bei 14:25 Minuten. - Muss man aber nicht sehen.
Zwei Personen spielen folgendes Gewinnspiel: A bestimmt eine Sequenz fester Länge aus 0-en und 1-en , z.B. "101010110", seine Gewinnsequenz. Danach bestimmt B eine andere Sequenz derselben Länge, z.B. "101001010", die Gewinnsequenz von B. Dann wird eine Münze geworfen, bei der man z.B. Kopf als 0 und Zahl als 1 interpretiert, und zwar so lange, bis in der Münzwurfserie zum ersten Mal die Gewinnsequenz von A oder B auftaucht. Es gewinnt derjenige, dessen Sequenz als erstes auftaucht.
Obwohl für alle möglichen Gewinnsequenzen die W. (Wahrscheinlichkeit) gleich groß ist, zuerst aufzutauchen, hat B einen deutlichen Vorteil gegenüber A, weil er dessen Sequenz schon kennt: Er wählt als erstes beliebig eine 0 oder 1 und hängt daran die gesamte Auswahl von A an, wobei er die letzte Ziffer weglässt. In obigem Beispiel also "X10101011", wobei X = 0 oder 1 ist. Wenn jetzt die Sequenz "10101011" auftaucht, hat B schon gewonnen, bevor die letzte Ziffer von A erscheint – vorausgesetzt, dass vor dem Auftreten der Sequenz die Ziffer X auftrat. Dies ist aber in 50 % der Fälle gegeben, so dass B "automatisch" in 50 % der Fälle gewinnt. Tauchte X aber nicht auf, so kann B nicht gewinnen. In diesen restlichen 50 % der Fälle gewinnt A aber auch nicht automatisch, sondern nun muss noch die letzte Ziffer passen, und das ist nur mit 50%iger W. der Fall. A gewinnt also nur in 25 % der Fälle, in denen "10101011" auftaucht, B in 50 % der Fälle, in den anderen Fällen geht das Wettrennen weiter. Also ist die Gewinnw. für B doppelt so hoch wie für A.
In dem o.a. Film wird nun gesagt, dass B für X nicht eine beliebige Ziffer aussuchen soll, sondern die Invertierung der zweiten Ziffer von A, also in unserem Beispiel dann eine 1. In wiefern sich dies bemerkbar macht, kann man nun dem Flussdiagramm entnehmen. Dabei stellt man fest, dass je nachdem, ob die beiden ersten Ziffern von A gleich oder verschieden gewählt werden, völlig unterschiedliche Wahrscheinlichkeiten entstehen – bei der Computersimulation aber nicht.
[Dateianhang nicht öffentlich]
Dieses Bild lässt sich vereinfachen durch Abkürzen zu
[Dateianhang nicht öffentlich]
Zunächst die Rechnung, wenn A 2 verschiedene Anfangsziffern wählt, beispielsweise "10". Danach kommt ein weiterer Sequenzteil, der "Rest" R und dann noch eine Endziffer k, die bei B fehlt.
B wählt nun zunächst die invertierte zweite Ziffer von A und dann die gesamte Sequenz von A, bis auf die Endziffer k. Die Wahrscheinlichkeit für jede Ziffer ist [mm] \bruch{1}{2}, [/mm] die W. dafür, dass die gesamte Sequenz R durchlaufen wird, sei p, und 1-p = q.
Die Gewinnwahrscheinlichkeit für A sei x, die für B sei y.
Dann gewinnt A auf folgenden Wegen:
Direkt durch Durchlaufen des oberen Zweiges bis zum Ende mit der W. [mm] \bruch{1}{2}*p*\bruch{1}{2} [/mm] = [mm] \bruch{p}{4}.
[/mm]
Indirekt auf folgende Weise: A gelangt nicht direkt zum Ziel, aber auf einem anderen Weg wieder zum Start zurück und dann (direkt oder wieder indirekt) zum Ziel. Hierzu stehen ihm folgende Wege offen:
oberer Zweig hinter "0" mit W. [mm] \bruch{1}{2}*q, [/mm] hinter "R" mit W. [mm] \bruch{1}{2}*p*\bruch{1}{2};
[/mm]
Unterer Zweig hinter "0" mit W. [mm] \bruch{1}{2}*q.
[/mm]
Somit gelangt A mit der Gesamtw. [mm] \bruch{1}{2}*q [/mm] + [mm] \bruch{1}{2}*p*\bruch{1}{2} [/mm] + [mm] \bruch{1}{2}*q [/mm] = q + [mm] \bruch{p}{4} [/mm] zum Startpunkt zurück. Da die uns noch unbekannte W., von hier aus zu gewinnen, wieder x ist, ist die Gesamtwahrscheinlichkeit, zum Start zurückzukehren und dann doch noch zu gewinnen, (q + [mm] \bruch{p}{4})*x.
[/mm]
Daraus ergibt sich: x = [mm] \bruch{p}{4} [/mm] + (q + [mm] \bruch{p}{4})*x
[/mm]
x*(1-q - [mm] \bruch{p}{4})=\bruch{p}{4}
[/mm]
x*(p - [mm] \bruch{p}{4})=\bruch{p}{4}
[/mm]
x*0,75 p = 0,25 p
x = [mm] \bruch{1}{3} [/mm] für A
Analog erhält man für den direkten Gewinnweg von B die W. [mm] \bruch{p}{2}, [/mm] die W. für die Rückkehr zum Start ist dieselbe wie bei A, und daraus ergibt sich genau wie oben für y der Wert
y*0,75 p = 0,5 p
y = [mm] \bruch{2}{3} [/mm] für B,
also doppelt so hoch,in Übereinstimmung mit obiger intuitiver Vorhersage.
----------------------------------------------------------------
Wählt nun aber A zu Anfang dieselben beiden Ziffern, z.B. "11", so ändert sich die Vorhersage dramatisch.
[Dateianhang nicht öffentlich]
Vom oberen Gewinnweg für A zweigt nach der ersten "1" der Weg zu B ab. Die zweite "1" und damit den Gewinnweg ohne Abzweigung zu B erreicht A nur mit der W. [mm] \bruch{1}{2}*\bruch{1}{2}=\bruch{1}{4}, [/mm] während B zur ersten "0" über zwei Wege mit der W. [mm] \bruch{1}{2} [/mm] und [mm] \bruch{1}{2}*\bruch{1}{2}, [/mm] also insgesamt mit der W. [mm] \bruch{3}{4} [/mm] gelangt. Wieder abgekürzt ergibt sich folgendes Bild:
[Dateianhang nicht öffentlich]
Nach obigem Verfahren erhält man nun für A:
W. für direkten Weg: [mm] \bruch{1}{4}*p*\bruch{1}{2}=\bruch{p}{8},
[/mm]
W. für Rückkehr zu Start: [mm] \bruch{1}{4}*q [/mm] + [mm] \bruch{1}{4}*p*\bruch{1}{2} [/mm] (oberer Zweig) + [mm] \bruch{3}{4}*q [/mm] (unterer Zweig) = q + [mm] \bruch{p}{8}
[/mm]
und damit wie oben: x = [mm] \bruch{p}{8} [/mm] + (q + [mm] \bruch{p}{8})*x
[/mm]
x*(1-q - [mm] \bruch{p}{8})= \bruch{p}{8}
[/mm]
x*(p - [mm] \bruch{p}{8})= \bruch{p}{8}
[/mm]
[mm] x*\bruch{7*p}{8}= \bruch{p}{8}
[/mm]
x = [mm] \bruch{1}{7} [/mm] für A
Für B ergibt sich im direkten Durchgang die W. zu [mm] \bruch{3}{4}*p, [/mm] die W. für die Rückkehr zum Start wie bei A zu q + [mm] \bruch{p}{8} [/mm] und damit
[mm] y*\bruch{7*p}{8}= \bruch{3p}{4}
[/mm]
y = [mm] \bruch{6}{7} [/mm] für A
Toll!
Wenn ich eine Computersimulation mit 100 000 Gewinnspielen durchführe, bei denen A zwei Ziffern zu Anfang wählt (gleiche oder verschiedene), den Rest aber zufällig (R und k), so erhalte ich für A und B das Gewinnverhältnis 1:1,92 bei einer Länge von 8 Zeichen für die Gewinnsequenz, das sich dann mit Verkürzung der Gewinnsequenz bis auf 1:1 (bei Länge 3) verschlechtert, wenn B NICHT mit dem Inversen der 2. Ziffer von A beginnt. Dies ist allerdings oben nicht berechnet worden und dient nur zur Abrundung des Gesamtbildes.
Wenn B nun mit dem Inversen der 2. Ziffer von A beginnt, passiert Folgendes:
Bei verschiedenen Anfangsziffern von A ist das Gewinnverhältnis unabhängig von der Sequenzlänge ca. 1:2 in Übereinstimmung mit der Theorie.
Wenn ich aber für A zwei gleiche Ziffern wähle, so erhalte ich für Gewinnsequenzen der Länge 8 aber nur das Verhältnis 1:2,18 statt 1:6, das sich dann zwar mit zunehmender Kürze (bis auf Länge 3 der Gewinnsequenz) bis auf ein Verhältnis von 1:4,3 verbessert, aber nie 1:6 wird.
Wieso ist im letzten Fall das Gewinnverhältnis so stark von der Länge der Gewinnsequenz abhängig, und wieso kommt es nicht mal in die Nähe von 1:6?
Was ist in meinen theoretischen Überlegungen falsch?
Dateianhänge:
Anhang Nr. 1 (Typ: JPG) [nicht öffentlich]
Anhang Nr. 2 (Typ: JPG) [nicht öffentlich]
Anhang Nr. 3 (Typ: JPG) [nicht öffentlich]
Anhang Nr. 4 (Typ: JPG) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Mo 17.03.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
