Wie oft muss ich eine Münze werfen, bis ein mal eine Serie von X mal Kopf zu erwarten ist?
Kurzum, es geht um das nacheinanderwerfen einer Münze, und es soll so lange geworfen werden, bis man X mal (hier Beispiel: 5) hintereinander Kopf geworfen hat. Dabei ist der Wurf nicht aufzuteilen, sondern es soll einfach hintereinanderweg geworfen werden, also nicht 5 mal werfen, schauen ob alles Kopf war, wenn nicht nochmal 5 mal werfen usw...
Die Chance auf 5 x Kopf ist (1/2)^5 = 1/32, dennoch sollte keiner der beiden "naiven" Ansätz stimmen:
1) Jeder 5er-Block einzeln betrachtet, also ist das Ergebnis dass nach 32 5er-Blöcken mal eine 5er-Serien zu erwarten ist. Das ist falsch, schließlich können ja auch die letzten beiden würfe des Xten Wurf-Blocks und die ersten 3 Würfe des X+1ten Wurf-Blocks Kopf sein...
2) Würfe 1,2,3,4,5 sind ein Block, Würfe 2,3,4,5,6 sind ein Block, Würfe 3,4,5,6,7 sind ein Block etc sollte auch nicht stimmen, schließlich sind die Blöcke nicht voneinander unabhängig. Wenn 1,2,3,4,5 alles Zahl ist, dann kann 2,3,4,5,6 ja nicht alles Kopf sein und hat per se keine Chance...
Daher nun meine Frage einfach um meine Neugier zu befriedigen: Wie geht man so ein Problem an?
2 Antworten
Ja, auf seine eigene Frage Antworten ist blöd:
Idee 3)
Im Durchschnitt ist jede 16. "Serie" eine 5er-Serie (alle Serien sind mindestens 1er-Serien, jede zweite ist eine 2er, jede 4. eine 3er, jede 8. eine 4er und jede 16. eine 5er). Die durchschnittliche Serienlänge ist 2. (Erwartungswert wie viele Kopf-Würfe nach einem Kopf-Wurf noch kommen werden ist 1) Jede zweite Serie ist eine Kopf-Serie.
Ergo sollte das Ergebnis demnach sein: Bei 64 Würfen ist einmal eine 5er-Kopf-Serie zu erwarten.
Stimmt diese 3. Idee?
Ich verstehe die Frage nicht ganz... Was meinst Du mit „zu erwarten“? Bei 64 Würfen könnte ersichtlich kein einziges Mal „Kopf“ kommen...
Ist vielleicht der Erwartungswert der Wurfanzahl gesucht? Den würde ich jedenfalls mit Monte-Carlo-Simulation ermitteln, weil das ziemlich einfach und schnell und genau (ich schätze: 3 signifikante Stelle in weniger als 1h) geht...
ich habe mal ein Programm geschrieben:
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <assert.h>
#include <inttypes.h>
void A(const uint32_t x) {
const uint32_t C = 100*1000*1000;
uint64_t len = 0;
for (uint32_t l=C; l>0; l--) {
uint8_t cnt = 0;
uint32_t L = 0;
for (bool cont=true; cont; ) {
uint32_t r = random();
for (uint32_t ii=31; cont && ii>0; ii--, r>>=1) {
L++; assert(L<(1U<<30));
const uint8_t now = (r&1) ? 1 : 0;
if (now!=1) cnt=0;
else { cnt++; if (cnt==x) { len+=L; cont=false; } }
}
}
}
printf("%u games: avg. len. = %.3f\n",C,len/(double)C);
}
int main(int argc, char ** argv) {
unsigned seed; read(0,&seed,sizeof(seed)); srandom(seed);
A(atoi(argv[argc-1]));
return 0;
}
der Erwarttungswert für die Zahl der Würfe bis zu dem Ereignis „5-mal Kopf“ scheint um die 62 Würfe zu liegen...
> c++ -o a a.c -O3 && time (dd if=/dev/urandom bs=4 count=1|./a 5)
100000000 games: avg. len. = 61.984
user 1m1.868s
Diet was Ganze also Binärzahl. 1 bedeutet Kopf 0 bedeutet Zahl.
Wenn du eine n-stellige Binärzahl hast, gibt es (2^(n-x))-1 Zahlen, die MINDESTENS x Einsen hintereinander haben.
In Summe gibt es 2^n Zahlen.
Deine Wahrscheinlichkeit bei n Würfen mindestens x mal hintereinander Kopf zu werfen, beträgt also
((2^(n-x))-1)/2^n
Jetzt musst du nur noch schauen, wann dieser Wert > 0,5 ist.
In der Tat sind (2^(n-x)) die Anzahl an Kombinationen, die eine Xer-Serie am Ende haben.
Das Problem an dem Ansatz sollte sein, dass man da nicht einfach sagen kann "und genauso gibt es nochmal 2^(n-x) Kombinationen mit einer 5er-Serie an vorletzter Stelle" usw und dann einfach die möglichen Positonen der 5er-Serie durchgeht, weil die Ereignisse nicht komplett unabhängig voneinander sind, oder?
Ich nehme der Einfachheit halber für n = 8 und für x = 5.
Mein Ansatz war:
Man eine Fünferserie am Beginn, die restlichen 3 Würfe können beliebig ausfallen. 2^3 =8, daher gibt es 8 Möglichkeiten, dass eine Reihe mit einer Fünferserie beginnt.
Dann: wieviele Möglichkeiten für eine 5er-Reihe ab der zweiten Stelle gibt es? Die erste Stelle muss 0 sein, dann 5 Einsen, dann 2^2 Möglichkeiten am Schluss.
So habe ich es fortgeführt und bin so auf 8+4+2+1 = 15 = 2^(3+1)-1 Möglichkeiten gekommen.
Der Fehler dabei: wenn die Serie an 3. Stelle beginnen soll, ist die erste Stelle egal, nur die zweite muss 0 sein.
Solange die "führenden Stellen" weniger sind, als x ist das such noch einfach zu handhaben. Sobald diese aber >= x sind, wirds kompliziert.
Daher mein Vorschlag:
Man zerteile die Sequenz von 0en und 1en in "Serien", also 111001001 wäre 5 Serien, nämlich 111, 00, 1, 00, 1.
Jede 2. Serie ist eine 1er-Serie (logisch, auf jede 1er-Serie, egal wie lang sie ist, folgt eine 0er, dann wieder eine 1er etc).
Die Chance, dass eine Serie aus 1en die Länge 5 hat ist 1/(5-1)^2, denn jede Serie hat mindestens die Länge 1, zu 50% kommt danach eine weitere 1, also haben 1/2 aller Serien mindestens eine Länge von 2, 1/4 aller Serien mindestens eine Länge von 3, 1/8 von 4 und 1/16 von 5.
Jede Serie hat im Durchschnitt die Länge 2. Ist eine endlose Summe, deren Ergebnis 2 ist.
Eine 5er-Serie ist nun also zu erwarten, wenn ich 16 1er-Serien habe. 16 1er-Serien bedeutet auch 16 0er-Serien. 32 Serien haben im Schnitt die Länge 64.
Ergo: eine 5er-Serie 1en (oder Kopf) ist im Schnitt einmal alle 64 Würfe zu erwarten.
Würdest du dem zustimmen? Fehlschlüsse?
Ich bemerke gerade: dies deckt noch nicht alle Möglichkeiten ab. Da ich gerade unterwegs bin und nichts zu schreiben dabei habe, kann ich den genauen Zusammenhang noch nicht angeben