Wie oft muss man durchschnittlich eine aus n Kugeln ziehen, bis man jede einmal hatte?

20.02.2016, 00:48

quence

Wie oft muss man durchschnittlich eine aus n Kugeln ziehen, bis man jede einmal hatte?

Meine Frage:
Ich bin heute im "Alltag" über ein Problem gestolpert, dass ich danach zwar schon mit anderen diskutiert habe, nicht aber habe lösen können. Ich habe versucht es möglichst einfach darzustellen:

In einem Topf befinden sich n Kugeln. Wie oft muss man durchschnittlich eine Kugel aus dem Topf blind ziehen und zurücklegen, bis man jede Kugel mindestens einmal in der Hand hatte?

Meine Ideen:
Ich habe mein Problem zunächst auf zwei Kugeln (A und B) heruntergebrochen und ein Baumdiagramm dazu erstellt. Rot markiert sind die beiden Fälle jeder Runde, in denen ich "gewinne".

https://imgur.com/g2g2FCZ
[attach]40947[/attach]

Nach 2 Runden "gewinne" ich bei AB sowie BA. Chance 1/2
Nach 3 Runden gewinne ich bei AAB sowie BBA. Chance 1/4
Hierbei lasse ich ABA, ABB, BAA und BAB aus, weil diese Pfade im Baumdiagramm ja bereits alle nach zwei Runden schon abgeschlossen waren.
Nach 4 Runden gewinne ich bei AAAB sowie BBBA. Chance 1/8
Das Muster setzt sich hier so fort. Ich habe also versucht den Erwartungswert zu errechnen:

$\begin{eqnarray*} E=\frac{1}{2} \cdot 2+ \frac{1}{4} \cdot 3+\frac{1}{8} \cdot 4 + ... = \sum\limits_{k=2}^{\infty} k\cdot 2^{1-k} =3 \end{eqnarray*}$

Den letzten Schritt musste mir aufgrund meiner Unfähigkeit zwar Wolfram Alpha abnehmen, aber nun gut. Das Problem mit zwei Kugeln scheint mir gelöst. Interessant auch deswegen, weil jeder Siebtklässler mir hierbei sagen kann wie groß die Chance ist nach Runde x zu gewinnen, die durchschnittlichen Versuche bis zum "Sieg" mir jetzt aber schwerer zu ermitteln vorkamen. Vorausgesetzt ich habe mich nicht allzu dumm angestellt.

Ich habe danach versucht das Problem auf drei Kugeln auszuweiten, was sich erheblich schwieriger gestaltet hat, auch weil eine Grafik quasi unmöglich ist, weil bereits in Spalte vier 81 verschiedene Pfade stehen. Vor allem aber gibt es erheblich mehr Variationen von je zwei Kugeln, die in Runde n dann um die dritte Kugel ergänzt werden können. Pfade also, die zwar vorher noch nicht abgeschlossen waren, aber eben nicht einfach AA....AA oder BB....BB lauten.

Ich habe versucht für die ersten paar Runden die Wahrscheinlichkeiten zu ermitteln:

Nach 3 Runden gewinne ich bei ABC, ACB, BAC, BCA, CAB sowie CBA. Das ergibt eine Chance von 6/27 = 2/9.
Nach 4 Runden komme ich interessanterweise wieder auf 2/9. Das habe ich auch mehrfach überprüft, garantieren kann ich aber für nichts.
Nach 5 Runden ein erster Rückgang auf eine Wahrscheinlichkeit von 14/81 dafür in genau dieser Runde die letzte fehlende Kugel zu ziehen.

Da mir langsam der Kopf platzt und ich hier kein System mehr erkenne (und außerdem ursprünglich wissen wollte wie viele Versuche ich bei acht "Kugeln" brauche) wende ich mich also mal an das Matheboard. Wie genau geht man vor? Vor allem bei n Kugeln?

MfG
quence

edit von sulo: Grafik eingefügt.

20.02.2016, 08:47

HAL 9000

Auf diesen Beitrag antworten »

Das ist mathematisch äquivalent zum sogenannten Sammelbilderproblem.

Wenn es dir nur um den Erwartungswert der nötigen Anzahl geht, ist das relativ leicht, der ist $\begin{align*} E(X_n) = n\sum_{k=1}^n \frac{1}{k} \end{align*}$ .

Für große $\begin{align*} n \end{align*}$ gilt damit approximativ $\begin{align*} E(X_n)\approx n(\ln(n)+\gamma) \end{align*}$ mit der Euler-Mascheroni-Konstante $\begin{align*} \gamma\approx 0.577 \end{align*}$ .

Zitat:

Original von quence
Ich habe versucht für die ersten paar Runden die Wahrscheinlichkeiten zu ermitteln:

Nach 3 Runden gewinne ich bei ABC, ACB, BAC, BCA, CAB sowie CBA. Das ergibt eine Chance von 6/27 = 2/9.
Nach 4 Runden komme ich interessanterweise wieder auf 2/9. Das habe ich auch mehrfach überprüft, garantieren kann ich aber für nichts.
Nach 5 Runden ein erster Rückgang auf eine Wahrscheinlichkeit von 14/81 dafür in genau dieser Runde die letzte fehlende Kugel zu ziehen.

Die Wartezeit $\begin{align*} X_{n,k}\sim G\left(\frac{n+1-k}{n}\right) \end{align*}$ bis zur $\begin{align*} k \end{align*}$ -ten neuen Kugel ergibt in der Summe $\begin{align*} X_n=\sum_{k=1}^n X_{n,k} \end{align*}$ die Gesamtwartezeit. Die genaue Verteilung von $\begin{align*} X_n \end{align*}$ ergibt sich als Faltung dieser $\begin{align*} n \end{align*}$ beteiligten geometrischen Verteilungen. So ergibt sich

$\begin{align*} P(X_2=k) = \frac{1}{2^{k-1}} \end{align*}$ für alle $\begin{align*} k\geq 2 \end{align*}$

$\begin{align*} P(X_3=k) = \frac{2^{k-1}-2}{3^{k-1}} \end{align*}$ für alle $\begin{align*} k\geq 3 \end{align*}$

Insofern kann ich für $\begin{align*} n=3 \end{align*}$ deine Werte 2/9, 6/27=2/9, 14/81 bestätigen, es geht weiter mit 30/243=10/81, 62/729, 126/2187=14/243, ...

Über einen anderen Zugang (Siebformel) kann man

$\begin{align*} P(X_n\leq k) = \frac{1}{n^k} \sum_{j=0}^{n-1} (-1)^j\binom{n}{j} (n-j)^k \end{align*}$

nachweisen, woraus über $\begin{align*} P(X_n=k) = P(X_n\leq k) - P(X_n\leq k-1) \end{align*}$ dann

$\begin{align*} P(X_n=k) = \frac{1}{n^{k-1}}\sum_{j=0}^{n-2} (-1)^j\binom{n-1}{j} (n-1-j)^{k-1} \end{align*}$ für alle $\begin{align*} k\geq n \end{align*}$

folgt. Die obigen Formeln für n=2,3 ordnen sich natürlich in diesen allgemeineren Kontext ein.

20.02.2016, 13:20

quence

Auf diesen Beitrag antworten »

Vielen Dank für deine Hilfe! Freude

Ich sehe mich zwar leider überhaupt nicht in der Lage die Herkunft der Formel nachzuvollziehen, aber der Hinweis auf das Sammelbilderproblem hilft mir schon sehr viel weiter!

Vielleicht versuche ich später nochmal den Einstieg, bis dato bin ich aber auch mit der einfachen Formel sehr zufrieden. Ich bin außerdem positiv überrascht, dass meine drei Seiten Geschmiere tatsächlich auf die richtigen Lösungen für n=3 geführt haben. smile

Neue Frage »

Antworten »

Wie oft muss man durchschnittlich eine aus n Kugeln ziehen, bis man jede einmal hatte?

Verwandte Themen