Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Ein interessantes Würfelproblem

Ein interessantes Würfelproblem

Sonstiges

Tags: Anwendung, Erwartsungwert, Geometrische Reihe, Reihen, Stochastik, Wahrscheinlichkeit

anonymous

07:53 Uhr, 10.03.2008

Hallo zusammen,

ich möchte hier ein Problem vorstellen für alle, die Lust und Freude am Knobeln haben. Es handelt sich also nicht um Hausaufgaben und ist auch nicht dringend. Ich würde mich aber freuen, wenn eine Diskussion zu Stande käme:

Wie oft muss man im Schnitt mit einem idealen Würfel würfeln, bis jede Zahl mindestens einmal gefallen ist?

Gruß, Diophant

Spatzle aktiv_icon

13:35 Uhr, 10.03.2008

so oft, wie der wuerfel seiten hat.. also bei den zahlen 1-6 6 mal wuerfeln.. laut statistik soll ja jede zahl die gleiche wahrscheinlichkeit haben :)

anonymous

13:46 Uhr, 10.03.2008

Nein, das stimmt leider nicht. Es handelt sich bei dem Problem darum, für das Zufalls experiment

"Anzahl der Würfe, bis jede Zahl mindestens einmal gefallen ist"

den Erwartungswert zu bestimmen. Dieser liegt, wie man durch Versuche (Rechner mit Zufallszahlengenerator, etc.) feststellen kann, in der Gegend von 15 Würfen.

Ich habe eine Vermutung, die auf 14,7 Würfe im Durchschnitt führt. Ich würde das Problem aber gerne hier diskutieren, da ich mir auch nicht sicher bin, und es sich um eine nicht ganz alltägliche Aufgabe handelt.

Aber vielleicht hast Du ja eine Idee für die Wahrscheinlichkeit P(X=k), k>=6, wobei X die Anzahl der benötigten Würfe darastellt. Auf Basis einer solchen Vermutung könnten wir dann das Problem diskutieren.

Gruß, Diophant

DK2ZA aktiv_icon

16:31 Uhr, 10.03.2008

Mein alter Atari hat mit Hilfe seines Zufallsgenerators so lange gewürfelt, bis schließlich jede Augenzahl mindestens einmal gefallen war.

Diesen Versuch habe ich 10 Millionen mal wiederholen lassen. Durchschnittlich waren 14,69... Würfe notwendig. Der Maximalwert lag bei 88!

GRUSS, DK2ZA

m-at-he

17:21 Uhr, 10.03.2008

Hallo,

habe DK2ZA's Experiment mit anderer Hard-/Software und noch häufiger durchgeführt und habe einen Wert erhalten, der sehr nahe an 14,696938456699068589183704448235 herankam, dieser Wert ist übrigends 6*sqrt(6)! Ist das ein Zufall oder des Rätsels genaue Lösung?

anonymous

18:14 Uhr, 10.03.2008

hallo zusammen,

vielen Dank zunächst für eure Bemühungen. Ich habe einen Ansatz verfolgt, bei dem genau 14,7 Versuche herauskommen.

Die Grundidee ist die folgende: Das Experiment ist genau in dem Moment zu Ende, wenn die letzte noch nicht gefallene Zahl zum ersten Mal erscheint. Davor sind nur die anderen fünf Zahlen gefallen. Um nun die Wahrscheinlichkeit zu berechnen, dass in k-1 Würfen nur fünf von 6 Zahlen erscheinen, benötigt man die Anzahl aller Variationen aus fünf Zahlen, in denen jede Zahl mindestens einmal vorkommt.

Hierfür habe ich einen Term entwickelt, den ich vor ein paar Tagen hier zur Diskussion vorgestellt habe. Legt man diesen Term für die gesuchte Wahrscheinlichkeit zu Grunde und bildet die Summe von k=6 bis unendlich, so kommt als Grenzwert der betreffenden Reihe 1 heraus: ein starkes, aber eben kein exaktes Argument für meine Vermutung.

Berechnet man dementsprechend den Erwartungswert, ist der Grenzwert 14,7; und zwar exakt 147/100.

Leider habe ich heute Abend keine Zeit mehr, meinen Ansatz nochmal ausführlicher darzustellen. Wenn ihr weiter an einer Diskussion des Problems interessiert seid, würde ich mich natürlich sehr über ein dementsprechendes Feedback freuen.

Gruß, Diophant

m-at-he

11:09 Uhr, 11.03.2008

Hallo,

davon mal abgesehen, daß bei mir 147/100 nicht 14,7 sondern 1,47 sind habe ich das Experiment mal mit anderen Zahlen als der 6 laufen lassen. Interessanterweise liegen die Ergebnisse IMMER sehr nah an n*sqrt(n). Ich will mich in Deine Berechnungen nicht unnötig vertiefen, aber was erhältst Du denn z.B. für n=4 (ich erhalte ziemlich genau 8 = 4*sqrt(4) = 4*2) oder für n=9 (ich erhalte ziemlich genau 27 = 9*sqrt(9) = 9*3) aber auch für n=5 und n=7 liege ich mit meinen experimentellen Zahlen immer sehr stark in der Nähe von 5*sqrt(5) und 7*sqrt(7). Um ehrlich zu sein. Ich habe mir lange Gedanken über eine analytische Lösung gemacht, sehe aber immer sehr schnell sehr komplexe Berechnungen und würde fast darauf wetten, daß das für n=6 niemals eine so glatte Lösung wie 14,7 ergeben kann!

anonymous

19:20 Uhr, 11.03.2008

Hallo m-at-he,

vielen Dank für dein Interesse an dem Problem. Natürlich ist mir bei dem angegebenen Wert eine Null zuviel reingerutscht. Es handelt sich um den exakten Grenzwert 14,7.

Auf einen Term zur Berechnung der Wahrscheinlichkeit, dass man k Würfe benötigt, kommt man, wenn man die Wahrscheinlichkeit berechnet, dass in k-1 Würfen nur fünf von sechs Zahlen fallen. Die Wahrscheinlichkeit für den letzten Wurf beträgt 1/6, für die fünf vorhergehenden Zahlen gibt es (6 über 5) = 6 Möglichkeiten, was sich eliminiert.

Die gesuchte Wahrscheinlichkeit ist dann exakt die Wahrscheinlichkeit, dass in k-1 Würfen nur fünf vorgegebene Zahlen mindestens einmal fallen. Für die Anzahl der günstigen Fälle habe ich einen Term entwickelt, der auf folgender rekursiver Überlegung fußt:

Die Variationen, in denen jedes Element mindestens einmal vorkommt, ist gleich der Anzahl aller Variationen minus der Anzahl der Variationen, in denen vier von fünf zahlen mindesten einmal vorkommt. Für dies gilt wieder, Anzahl vier von fünf minus Anzahl drei von fünf, usw. So kommt man rekursiv zu der in meinem Beitrag "Variationen am Urnenmodell" vorgestellten Formel. Ich bin mir der Herleitung und Richtigkeit meiner Überlegungen auch nicht ganz sicher, aber Tatsache ist, dass wenn man diesen Term für die hier gesuchte Wahrscheinlichkeit P(X=k) verwendet und die Summe von k=6 bis k=inf bildet, so erhält man exakt 1. Dies lässt mich vermuten, dass mein Ansatz doch richtig sein könnte.

Leider habe ich heute und die nächsten drei Tage wenig Zeit. Ich würde meinen kompletten Ansatz am Wochenende hier vorstellen und mich sehr über ein Feedback freuen!

Gruß, Diophant

anonymous

13:24 Uhr, 16.03.2008

Hallo zusammen,

hier nun wie angekündigt meine Idee zur Lösung des vorgestellten Problems:

Wie oft muss man mit einem idealen Würfel im Schnitt würfeln, bis jede Zahl mindestens einmal gefallen ist"

Behauptung:

Man muss im Schnitt genau 14,7-mal würfeln.

Beweis:

Das geschilderte Zufallsexperiment ist genau in dem Moment zu Ende, wenn die letzte noch nicht erschienene Zahl zum ersten Mal fällt. Für die Wahrscheinlichkeit, dass man dafür k Würfe benötigt, gilt dann:

P (X = k) = (\binom{6}{5}) \cdot \bar{P} (X = k - 1) \cdot \frac{1}{6}

= \bar{P} (X = k - 1)

Darin bezeichne

\bar{P} (X = k - 1)

die Wahrscheinlichkeit dafür, dass in k-1 Würfen fünf (vorgegebene) von sechs Zahlen fallen. Mit der Definition der Wahrscheinlichkeit "Anzahl günstige Ergebnisse : Anzahl mögliche Ergebnisse" folgt:

\bar{P} (X = k - 1) = \frac{\bar{V} (5, k - 1)}{5^{k - 1}}

\bar{V} (N, K)

sei die Anzahl der Variationen K. Ordnung aus N Elementen, in denen jedes Element (mindestsens einmal) vorkommt. Diese Anzahl soll nun untersucht werden:

Satz:

\bar{V} (N, K) = \sum_{i = 1}^{N} (- 1)^{i + N} \cdot (\binom{N}{i}) \cdot i^{K}

Beweis:

Für die Anzahl K-wertiger Variationen aus N Elementen gilt

V = N^{K}

Es sei nun

{\bar{V}}_{1} = N \cdot 1^{K} = N

die Anzahl aller Variationen, die aus genau einem Element bestehen. Es sei

{\bar{V}}_{2} = V_{2} - {\bar{V}}_{1}

= (\binom{N}{2}) \cdot 2^{K} - (\binom{N}{1}) \cdot 1^{K}

die Anzahl aller Variationen, die aus genau 2 Elementen gebildet sind. Diese besteht aus der Anzahl der Variationen, die aus insgesamt 2 Elementen gebildet werden können, minus die Anzahl derjenigen V. die aus genau einem Element bestehen.
Setzt man diese Überlegung rekursiv fort, so ergibt sich für die Anzahl der Variationen k. Ordnung aus i Elementen

{\bar{V}}_{i} = V_{i} - {\bar{V}}_{i - 1}

= V_{i} - (V_{i} - {\bar{V}}_{i - 2})

= V_{i} - V_{i - 1} + V_{i - 2} - {\bar{V}}_{i - 3}

usw.

und daher

\bar{V} (N, K) = V_{N} - V_{N - 1} + V_{N - 2} - . . . \pm V_{1}

= (\binom{N}{N}) \cdot N^{K} - (\binom{N}{N - 1}) \cdot (N - 1)^{K} + (\binom{N}{N - 2}) \cdot (N - 2)^{K} - . . . \pm (\binom{N}{1}) \cdot 1^{K}

= (- 1)^{2 N} \cdot (\binom{N}{N}) \cdot N^{K} + (- 1)^{2 N - 1} \cdot (\binom{N}{N - 1}) \cdot (N - 1)^{K} + (- 1)^{2 N - 2} \cdot (\binom{N}{N - 2}) \cdot (N - 2)^{K} + . . . + (- 1)^{2 N - (N + 1)} \cdot (\binom{N}{1}) \cdot 1^{K}

und damit die Behauptung.

Sei nun

P (X = k) = \frac{\bar{V} (5, k - 1)}{5^{k - 1}}

= \sum_{i = 1}^{5} \frac{(- 1)^{i + 5} \cdot (\binom{5}{i}) \cdot i^{k - 1}}{5^{k - 1}}

so ist, wie man (etwas mühevoll, aber es geht) nachrechnet

\sum_{k = 6}^{\infty} P (X = k) = 1

und

E (X) = \sum_{k = 6}^{\infty} X \cdot P (X = k) = 14, 7

So, jetzt würde ich mich (nach dieser Mammut-LaTEX-Sitzung) sehr freuen, wenn mir jemand hier zu dieser Idee ein Feedback schreiben könnte. Die Grenzwerte stimmen (sagen auch meine drei CAS-Systeme) aber der Ansatz zur Ermittlung von P(X=k), da würde ich gerne wissen, ob man das wirklich so machen kann.

Vielen Dank für jede Antwort!

Gruß, Diophant

anonymous

18:43 Uhr, 03.05.2008

Da ich mittlerweile sicher bin, dass die Formel stimmt, beende ich hiermit diese Thread. Vielen Dank an alle, die sich darüber den Kopf zerbrochen haben!

Gruß, Diophant

510486

501465

	Status: nicht eingeloggt	Noch nicht registriert?