Hallo kurze Frage, die sich aus einem Videospiel ergibt:
In einer Urne liegen 107 verschiedene Kugeln.
Jede Woche werden 2 Kugeln mit zuruecklegen gezogen.
Wie lange dauert es, bis jede Kugel mindestens einmal gezogen wurde im Durchschnitt?
Hallo Zera,
ich bin zwar kein Experte in dem Gebiet und hatte bis her nur Kombinatorik (ist doch im Prinzip das Gleiche 
) , falls ich was falsches antworte mögen mich die Experten bitte verbessern und du nimmst es mir hoffentlich nicht übel
Also dann:
Ich würde sagen das ist das gleiche Phänomen wie beim Lotto nur dort heißt es 6 aus 49. und hier heißt es 2 aus 107 (bei Interesse vergleiche Pascalsches Dreieck) nun zum wesentlichen. 2 aus 107 ist ein Binominalkoeffizent und er berechnet sich wie folgt:
n!/(k! * (n-k)!) = 107!/(2*105!) = 5671
Für alle die es nicht wissen, es aber dennoch intressiert: n! = gesprochen „n Fakultät“ ist nichts anderes als:
n! = 1 * 2 * … * n
Nun zur Antwort:
wenn es also 5671 Möglichkeiten gibt 2 aus 107 Kugeln zu ziehen, dann hätte man nach 5671 Wochen alle Kombinationen durch. Solch eine Aussage gilt allerdings nur nach einer hohen Anzahl an Durchgängen. Gleiches wie beim Würfel, wenn du zwei mal hintereinander eine 3 würfelst sagt du ja auch nicht der Würfel liefert nur 3en die Wahrscheinlichkeit für jede Zahl ist bei einem sechsseitigen Würfel für jede Zahl 1/6.
Ich hoffe ich konnte helfen und hab kein unsinn erzählt 
Liebe Grüße Matthias
Hallo Matthias,
ich bin zwar kein Experte in dem Gebiet
ja.
Also dann:
Ich würde sagen das ist das gleiche Phänomen wie beim Lotto
nur dort heißt es 6 aus 49. und hier heißt es 2 aus 107
Nein, denn du hast die Frage nicht richtig aufgenommen, denn dies war nicht gefragt:
wenn es also 5671 Möglichkeiten gibt 2 aus 107 Kugeln zu
ziehen, dann hätte man nach 5671 Wochen alle Kombinationen
durch.
Ich hoffe ich konnte helfen und hab kein Unsinn erzählt
Entsprechend der Frage doch.
Aus 107 Kugeln eine zu ziehen, da gibt es eben nur 107 Möglichkeiten.
Und wenn ich gleich zwei ziehe ? Dann wird die Trefferwahrscheinlichkeit für ein
Ereignis (die Ziehung) größer für eine Zahl.
Unklar ist in der Frage nur, ob die Rücklage der jeweils gezogenen Kugel sofort erfolgt
oder erst nachdem die zweite Kugel gezogen wurde.
Gruß Viktor
Hallo Viktor,
schade dass ich nicht helfen konnte, immerhin glaube ich zu verstehen was das unbekannte Problem bei der Aufgabe ist.
Meine Antwort wäre nur richtig wenn nach der Anzahl der verschiedenen Zahlen Paare (erste_Kugel, zweite_Kugel) gefragt wäre, richtig?
Der einfache Fall, den du ja schon angesprochen hast, wäre wenn man eine Kugel zieht und diese direkt nach dem ziehen wieder in die Urne legt. Dort wäre es dann gerade 107 wie du schon gesagt hast.
Wäre der zweite Fall dann nicht einfach die Hälfte? Also aufgerundet 54 Wochen.
Liebe Grüße Matthias
@Viktor gut nachgefragt: Man zieht jeweils 2 Kugeln auf ein mal und legt dann diese zwei Kugeln zuerueck.
@Brayn Ich sehe nicht, wie die Anzahl der „5671 Möglichkeiten“ relevant ist.
Beispiel:
Es gibt Ereignis a) Kugel 1&2
Ereignis b) Kugel 2&3
Ereignis c) Kugel 1&3
Nur zwei dieser Ereignisse brauchen einzutreten, damit alle drei Kugeln mindestens ein mal gezogen werden.
@Bryan2. Es kann theoretisch 54 Wochen dauern, wenn man jedes mal 2 neue Kugeln zieht, aber höchstwahrscheinlich erwischt man manchmal eine (oder zwei) Kugel(n), auf welche man in den vorigen Wochen schon mal gestoßen war. Deshalb wird der Erwartungswert deutlich höher als 54 ausfallen.
Zureuck zum Thema: Vielleicht hilft euch das Coupon Collector’s Problem bei der Loesung:
http://en.wikipedia.org/wiki/Coupon_collector%27s_pr…
Außerdem hat jemand folgende Rechnung vorgeschlagen.
Nach der ersten Woche hat man 107 - 2 * (107/107) = 105 Kugeln nicht gezoen.
Nach der zweiten woche 105 - 2 * (105/107) Kugeln usw.
So kann man für jede Woche bestimmen, wie viele Kugeln einem noch fehlen. Möglicherweise kann das hilfreich sein für die Bestimmung der Zeit, welche man im Durchschnitt braucht, um jede Kugel mindestens ein mal gezogen zu haben.
Hallo Mattias,
Der einfache Fall, den du ja schon angesprochen hast, wäre
wenn man eine Kugel zieht und diese direkt nach dem ziehen
wieder in die Urne legt. Dort wäre es dann gerade 107 wie du
schon gesagt hast.
Das ist aber hier nicht gefragt.Es werden ja immer 2 Kugeln je Ereignis gezogen.
Wäre der zweite Fall dann nicht einfach die Hälfte? Also aufgerundet 54 Wochen.
Es gibt da zwei Möglichkeiten
- die erste Kugel wird zurück gelegt
Dann ist für jede Entnahme einer Kugel die Trefferwahrscheinlichkeit 1/107
Auch die zurück gelegte Kugel kann ja nochmals gezogen werden, also zwei Treffer je
Ziehung, wenn auch (bezogen auf eine bestimmte Zahl) nur mit einer Wahrscheinlichkeit
von 1/107^2
Es müßte deine Überlegung zutreffen. - die erste Kugel wird nicht zurück gelegt bzw. es werden zwei Kugeln gleichzeitig
gezogen. Hier ist die (durchschnittliche)Trefferwahrscheinlichkeit also geringer.
Ich habe jetzt nicht gerechnet sondern nur qualitative Überlegungen gebracht.
Gruß Viktor
Hallo,
bei n Kugeln lautet die näherungsweise Antwort auf Deine Frage
E(n) = \frac{1}{2} \left(n \ln(n) + \gamma n + \frac{1}{2}\right)
worin γ die Euler-Mascheroni-Konstante bezeichnet (γ ≈ 0.557215…). Die Näherung ist umso besser, je größer n ist, und für n = 107 ist sie schon sehr gut. Das Ergebnis für Deinen Fall ist E(107) ≈ 281, d. h. Du musst im Mittel etwa 281Ziehungen abwarten.
http://en.wikipedia.org/wiki/Coupon_collector%27s_pr…
Der Faktor 1/2 vor der großen Klammer in der obigen Formel rührt daher, dass bei einer Ziehung wie von Dir beschrieben zwei Kugeln gezogen werden. Eine Diskussion darüber, ob die dabei paarweise-gleichzeitig gezogen und paarweise wieder zurückgelegt, oder einzeln hintereinander gezogen und zurückgelegt werden, ist hier übrigens ziemlich sinnfrei, denn das spielt für das Ergebnis bei n = 107 praktisch keine Rolle (erst bei sehr kleinen n sähe das anders aus).
Gruß
Martin
Hallo Mattias,
- die erste Kugel wird nicht zurück gelegt bzw. es werden zwei Kugeln gleichzeitig
gezogen. Hier ist die (durchschnittliche)Trefferwahrscheinlichkeit also geringer.
Diese „Feststellung“ von mir ist unzutreffend (bezogen auf 1))
Es ist umgekehrt.Bezogen auf jeweils eine Ziehung (das war ja gefragt) ist die
Trefferwahrscheinlichkeit bei 2) größer.
Folgendes Beispiel zeigt dies:
Man hat nur zwei Kugeln (statt 107)und zieht jeweils 2.
Legt man nicht zurück ist die Trefferquote 100%, je Ziehung für eine Zahl.
Legt man zurück ist die Trefferquote 75%, da in 4 möglichen Kombinationen jeweils in 3
die 1 oder 2 enthalten ist.
Gruß Viktor
PS.
Ich hoffe ich habe mich nicht wieder vertan.
Hallo Martin,
Du musst im Mittel etwa 281Ziehungen abwarten.
diese Aussage solltest du nochmals überdenken - Formel hin oder her (passt diese ?)
Du sagst doch hiermit, daß die Trefferwahrscheinlichkeit je Ziehung für jeweils eine
Zahl aus 107, wenn bei jeder Ziehung 2 Zahlen gezogen werden nur 1/281 beträgt !
Oder habe ich dich hier falsch verstanden ?
Gruß Viktor
Danke fuer die Antwort. Auf dem Windoof Rechner nachgetippt komme ich aber auf das Doppelte also 560. Wo war mein Fehler?
http://s14.directupload.net/images/141010/ahtmf3zj.png
Hallo Viktor,
Du musst im Mittel etwa 281Ziehungen abwarten.
diese Aussage solltest du nochmals überdenken - Formel hin oder her (passt diese ?)
was soll denn bitte „Formel hin oder her“ heißen? Die Formel passt zur Aufgabenstellung und sie liefert für n = 107 den Wert 281 – Punkt. Kann ja sein, dass Du mit der 281 irgendein Problem hast; nur liegt dessen Ursache dann ziemlich sicher nicht in der Formel.
Du sagst doch hiermit, daß die Trefferwahrscheinlichkeit je Ziehung für jeweils eine
Zahl aus 107, wenn bei jeder Ziehung 2 Zahlen gezogen werden nur 1/281 beträgt !
Nein. Ich sagte das, was oben steht: Bis alle 107 Kugeln wenigstens einmal dranwaren, muss man im Mittel 281Ziehungen veranstalten. Ich habe sogar noch die Standardabweichung für Dich ausgerechnet: Sie beträgt (nach der Formel im verlinkten Wikipedia-Artikel) 97 und ist damit relativ hoch, was ich auch intuitiv so erwartet hätte.
Oder habe ich dich hier falsch verstanden ?
Vermutlich.
Gruß
Martin
PS: Warum hast Du denn „im Mittel“ fett hervorgehoben?
Du hast vergessen, ganz am Schluss die [=]-Taste zu drücken.
Bevor Du es nochmal eintippst, löse bitte zuerst die Aufgabe „0.5 * (8 + 6)“ mit dem Windows-Taschenrechner (das Ergebnis ist natürlich 7), um seine komische Eingabelogik kennenzulernen (viel Vergnügen…)
Alles klar danke nochmal an Alle jetzt kann ich wieder beruhigt einschläfern.
Hallo Martin
Nein. Ich sagte das, was oben steht: Bis alle 107 Kugeln
wenigstens einmal dran waren, muss man im Mittel 281Ziehungen
veranstalten…Oder habe ich dich hier falsch verstanden ?
Vermutlich.
es ist nicht nur vermutlich sondern ich habe hier tatsächlich die Fragestellung nicht richtig
aufgenommen.
Um weiter „Feinheiten“ zu ergründen, zu deren Zugang mir die math.Kenntnisse fehlen habe ich die Situation in einer Simulation empirisch ausgewertet.
Es ergab im Mittel tatsächlich 281 Ziehungen (2 Kugeln je Ziehung) um alle Kugeln jeweils
mind. einmal zu ziehen - wenn man jede Kugel einzeln zurücklegt.
Zieht man beide Kugeln gleichzeitig braucht man ca 280 Ziehungen.
Die Extremwerte lagen hier bei etwa Minimum=115 und Maximum 1100. Diese weichen
natürlich stärker ab bei weniger Ziehungen.(theoret. Minimum ist hier wohl 54 - oder ?)
Ich habe hier mehrfach jeweils 1000000000 „Kugeln“ gezogen und abgestuft nach unten
bis zu 1000000. Hier werden sie Ergebnisse aber grober.
Gruß Viktor
Kurze Nachfrage auf Wikipedia findet man Martins Formel wieder, allerdings mit „+o1“ angehängt.
Was bedeuted das?
http://upload.wikimedia.org/math/c/0/a/c0a2f7b01c01c…
Hallo Viktor,
da siehst Du mal: In diesem Brett wird gar nicht so viel dummes Zeug geschrieben…
… habe ich die Situation in einer Simulation empirisch ausgewertet.
Sehr gut! Ich weiß, wieviel Spaß solche Simulationen machen können
(theoret. Minimum ist hier wohl 54 - oder ?)
Ja, im besten Fall bist Du trivialerweise schon nach 54 Ziehungen fertig (weil 54 die kleinste Zahl ist, deren Doppeltes größergleich 107 ist), aber dieser Fall dürfte wahrlich selten eintreten. Die Zufallsvariable „Anzahl der Ziehungen“ hat also unten einen Cutoff und kann daher genaugenommen auch nicht normalverteilt sein. Sie ist es nur näherungsweise, wobei die Näherung für große n sehr gut ist (immer dasselbe…).
Ich habe hier mehrfach jeweils 1000000000 „Kugeln“ gezogen und
abgestuft nach unten bis zu 1000000. Hier werden sie Ergebnisse aber grober.
Versteh ich nicht. Wozu derart viele Kugeln? Oder meinst Du mit den 1000000000 die Anzahl der Simulationsläufe, die so groß ist, um einen möglichst guten Mittelwert zu bekommen?
Schönes WE
Martin
Hallo Martin
Ich habe hier mehrfach jeweils 1000000000 „Kugeln“ gezogen und
abgestuft nach unten bis zu 1000000. Hier werden sie Ergebnisse aber grober.Versteh ich nicht. Wozu derart viele Kugeln?
Quark.
Oder meinst Du mit den 1000000000 die Anzahl der Simulationsläufe,
Nein, da habe ich nur ein paar gemacht mit eben jeweils einer großen Anzahl von Ziehungen - von Kugeln, was sonst, steht doch oben -oder was meintest du.
Die Extremwerte werden ja hier erst bei einer großen Anzahl deutlicher - bei hier 107 Zahlen.
Bei nur 1 Million Ziehungen weichen sie über 50% ab. Auch die Mittelwerte sind nur bei
einer großen Zahl relativ genau. Mir kam es auch darauf an, die Abweichung zur Ziehung
von gleichzeitig zwei Kugeln genau zu ermitteln, welche ja von deiner Formel nicht erfaßt
werden. Hast du dazu überhaupt eine ?
Gruß Viktor
Hallo Viktor,
Ich habe hier mehrfach jeweils 1000000000 „Kugeln“ gezogen
Versteh ich nicht. Wozu derart viele Kugeln?
Quark.
dann klär mich bitte darüber auf, was Du mit dem Satz
Ich habe hier mehrfach jeweils 1000000000 „Kugeln“ gezogen
ausdrücken wolltest.
Nein, da habe ich nur ein paar gemacht mit eben jeweils einer großen Anzahl von Ziehungen
- von Kugeln, was sonst, steht doch oben -oder was meintest du.
Beschreib bitte mal, was Du unter „Ziehung“ verstehst. Mir scheint, Du verwendest den Begriff in einer anderen Bedeutung als ich. Wir sollten darüber erst Klarheit schaffen.
Gruß
Martin
Hallo Martin,
Ich habe hier mehrfach jeweils 1000000000 „Kugeln“ gezogen
Versteh ich nicht. Wozu derart viele Kugeln?
Quark.
dann klär mich bitte darüber auf, was Du mit dem Satz
Ich habe hier mehrfach jeweils 1000000000 „Kugeln“
gezogen
ausdrücken wolltest.
Das habe ich schon - verscheißern kann ich mich selbst.
…Simulationen…
Nein, da habe ich nur ein paar gemacht mit eben jeweils einer großen Anzahl von Ziehungen
- von Kugeln, was sonst, steht doch oben -oder was meintest du.
Beschreib bitte mal, was Du unter „Ziehung“ verstehst.
Aus der Frage des UP:
_ Jede Woche werden 2 Kugeln mit zuruecklegen gezogen_
Mir scheint, Du verwendest den Begriff in einer anderen Bedeutung als ich. Wir sollten :darüber erst Klarheit schaffen…
Warum fängst du dann nicht an wenn du jetzt etwas anderes als der UP interpertierst ?
Bisher bezog sich deine Angabe des „Mittelwertes“ von 281 doch auch genau auf
Ziehungen von jeweils 2 Kugeln. Meine Einlassungen dazu auch.
Was rührst du hier rum und schaffst Verwirrung ?
Mit Wichtigtuerei hat mich noch nie jemand beeindruckt.
Gruß Viktor
PS
Nun - vielleicht weißt du nicht wie ich „empirisch“ die Angaben geprüft bzw. ermittelt habe
und möchtest das wissen. Frag doch gleich danach.
Ich habe eben z.Bsp. 1 Milliarde (1/2=Ziehungen) Zufallszahlen zw. 1 u.107 generiert und
die Anzahl der „Abschnitte“ ermittelt in denen jede Ziffer von 1-107 mind. einmal vorkommt.
(nur ein kleines Computerprogramm, ein paar Programmzeilen).Daraus wurde der Mittelwert
der erforderlichen Ziehungen errechnet was eben diesen Wert (ca 281,1) entsprechend
deiner Berechnung ergibt - dazu noch die Extremwerte aus dieser Menge.
Hallo Viktor,
danke für Deine Antwort.
Nun - vielleicht weißt du nicht wie ich „empirisch“ die Angaben geprüft bzw. ermittelt habe
Natürlich nicht. Woher sollte ich das auch wissen? Du hast dazu bisher ja nichts gesagt. Die Beschreibung der Methode Deiner Simulation hat mir aber klargemacht, dass wir unter „Ziehung“ glücklicherweise dasselbe verstehen. Also kein Grund zur Aufregung.
Gibt es jetzt eigentlich noch was zu diskutieren?
Gruß
Martin