Wie oft muss man ziehen, bis man den Inhalt der Urne kennt?           Die Lösung steht im unteren Teil der Seite. Die Überschrift muss natürlich präzisiert werden. Hier geht es um eine Urne mit endlich vielen paarweise unterscheidbaren Kugeln, die mit Zurücklegen gezogen werden  –  und zwar solange, bis jede Kugel mindestens einmal gezogen wurde. Stellen Sie sich z.B. vor, dass Sie vor dem Ziehen darüber informiert wurden, dass die Urne \(~m~\) Kugeln in \(~m~\) paarweise verschiedenen Farben enthält. Sie möchten wissen, um welche Farben es sich handelt und ziehen solange, bis Sie alle Farben kennen.

Man kann sich am Würfel-Beispiel orientieren und der Einfachheit halber den Farben die Zahlen \(~1,~...,~m~\) zuordnen, z.B. alphabetisch. Notiert man, welche Zahlen gezogen werden, erhält man eine Folge, in der alle Zahlen zwischen \(~1~\) und \(~m~\) vorkommen, davon möglicherweise manche mehrfach, aber die letzte nur einmal.

Die Frage aus der Überschrift zerfällt in zwei Probleme:

• Wie groß ist die Wahrscheinlichkeit, dass man genau \(~n~\) Ziehungen benötigt, bis man alle Farben gesehen hat?


• Wieviele Ziehungen benötigt man im Mittel?

Lösung

(1)  Die gesuchte Wahrscheinlichkeit in der ersten Frage sei \(~p_{n,m}~\),  mit \(~1\le m\le n~\).  Ist \(~a_{n,m}~\) die Anzahl aller Folgen der Länge \(~n~\),  die alle Zahlen in \(~\{1,~...,~m\}~\) (und sonst keine Elemente) enthalten und in denen das letzte Element nur einmal vorkommt, gilt \[p_{n,m} = \frac{a_{n,m}}{m^n}\] (denn \(~m^n~\) ist die Anzahl aller möglichen Folgen).

(2)  Zieht man beim \(~j-\)ten Versuch die \(~i-\)te Farbe, so kann man das als \(~f(j)=i~\) schreiben. So erhält man eine surjektive Abbildung \(~f:_~\{1,~...,~n\}~~\rightarrow~~\{1,~...,~m\}.~~(f(j))_{j=1..n}~\) ist dann eine der Folgen aus (1); insbesondere ist \(~f(n)_~\) eindeutig.

(3)  Wir schauen zuerst zwei triviale Fälle an:

\(a_{1,1} = 1\)

\(a_{n,1} = 0~\) für \(~n\ge 2\)

Wir werden nun \(~2\le m\le n~\) betrachten.

(4)  Für \(~f(n)~\) gibt es \(~n~\) Möglichkeiten.  –  Der "Rest" \(~f(1),~...,~f(n-1)~\) führt auf eine surjektive Abbildung von \(~\{1,~...,~n-1\}~\) nach \(~\{1,~...,~m\}~ \setminus~\{f(n)\}~\).

(5)  Die Anzahl \(~M_{r,s}~\) surjektiver Abbildungen von einer \(~r-\)elementigen zu einer \(~s-\)elementigen Menge ist (→ Quelle): \[M_{r,s} = \sum_{i_~=_~1}^s (-1)^{s-i} \binom{s}{i}~i^{_~r}\] (6)  Die Formel in (5) führt zusammen mit (4) und (2) auf \[a_{n,m} = m\cdot \sum_{i_~=_~1}^{m-1} (-1)^{m-1-i} \binom{m-1}{i}~i^{_~n-1}\] (7)  (6) lässt sich leicht mit (3) zusammenfassen, indem man die Summe bei \(~0~\) beginnen lässt: \[a_{n,m} = m\cdot \sum_{i_~=_~0}^{m-1} (-1)^{m-1-i} \binom{m-1}{i}~i^{_~n-1}~~~\text{für alle}~~~1\le m\le n~.\] Dies lässt sich einfacher mit Stirling-Zahlen 2. Art \(~S_2(r,s)~\) schreiben: \[~~~~~~~~S_2(r,s) = \frac{1}{s_~!}\cdot \sum_{i_~=_~0}^s (-1)^{s-i} \binom{s}{i}~i^{_~r}\] \[a_{n,m} = m_~!\cdot S_2(n-1,m-1)~\] (8)  Dies führt mit (1) zur Lösung für die erste Frage:

Die Wahrscheinlichkeit, dass man genau \(~n~\) Ziehungen benötigt, bis man alle \(~m~\) Farben gesehen hat, beträgt \[p_{n,m} = \frac{1}{m^{n-1}}\cdot \sum_{i_~=_~0}^{m-1} (-1)^{m-1-i} \binom{m-1}{i}~i^{_~n-1}~=~\frac{m_~!}{m^n}\cdot S_{2~}(n-1,~m-1)\] Die zugehörige Wahrscheinlichkeitsverteilung ist definiert für \(~n\in \{m,~m+1,~m+2,~...\}~\).

Bild 1 zeigt die Verteilung für \(~m=9~\).

Bild 1    \(m=9~\)   Erwartungswert \(\approx~25,46~\) (siehe Tabelle weiter unten)    Median \(=~23~\)    Modus \(=~20\)

Nun zur 2. Frage nach dem Erwartungswert der Verteilung.

• Man benötigt \(~1~\) Ziehung, bis die \(~1\). Zahl erscheint.


• Die Wahrscheinlichkeit, eine andere als die \(~1\). Zahl zu ziehen, beträgt \(~(m-1)/m~\);  das gilt für alle Ziehungen nach der \(~1\). Ziehung, bis die \(~2\). Zahl erscheint. Im Mittel benötigt man dafür \(~m/(m-1)~\) Ziehungen (in der Aufgabenstellung gab es dazu den Hinweis auf ein → Lemma).


• Induktiv: Die Wahrscheinlichkeit, eine andere als die ersten \(~i~\) Zahlen zu ziehen, beträgt \(~(m-i)/m~\);  das gilt für alle Ziehungen nach der Ziehung der \(~i-\)ten Zahl, bis die \(~(i+1)\)te Zahl erscheint. Im Mittel benötigt man dafür \(~m/(m-i)~\) Ziehungen.


• Das geht bis zur letzten fehlenden Zahl: Für diese beträgt die Wahrscheinlichkeit \(~1/m~\);  das gilt für alle Ziehungen nach der Ziehung der \(~(m-1)\)ten Zahl, bis die \(~m-\)te Zahl erscheint. Im Mittel benötigt man dafür \(~m~\) Ziehungen.


• Insgesamt ergibt das im Mittel \(~m\cdot \sum_{j_~\le_~m} {_~}1/j~\) Ziehungen, bis alle Zahlen bzw. Farben erschienen sind. Das ist die Lösung für die zweite Frage.


• In den Erwartungswerten treten die Partialsummen der harmonischen Reihe auf, die sich asymptotisch wie \(~\text{ln}~m~+~\gamma~\) verhalten. \(~\gamma~\) ist die Euler-Mascheroni-Konstante mit \(~\gamma \approx 0,5772~\).


• Hier ist eine kleine Tabelle für die Erwartungswerte:
  
  

  m	erw. Anz. Ziehungen	asymptotisch
  1	1	0,57722
  2	3	2,54073
  3	5,5	5,02748
  4	8,333	7,85404
  5	11,4167	10,9333
  6  Würfel	14,7	14,2139
  7	18,15	17,6619
  8	21,7429	21,2533
  9  Bild 1	25,4607	24,97
  10	29,2897	28,798
  50	224,96	224,462
  100	518,738	518,239
  500	3396,41	3395,91
  1000	7485,47	7484,97

Erweiterungen zu diesem Problem und zugehörige OEIS-Folgen findet man in Blog # 49.

Publiziert 2026-06-29          Stand 2025-03-11

voriges Problem   |   Liste aller Probleme mit Lösungen