Sammelbilderproblem

Das Sammelbilderproblem, Sammler-Problem, Sammelalben-Problem oder nach der englischen Bezeichnung Coupon Collector's-Problem befasst sich mit der Frage, wie viel zufällig ausgewählte Bilder einer Sammelbildserie zu kaufen sind, um eine komplette Bildserie zu erhalten.

Anschauung

Wie viele Überraschungsbilder muss man im Mittel kaufen, um eine vollständige Serie von n Bildern zu erhalten, wenn Tauschen ausgeschlossen ist und jedes Bild in der Überraschungstüte gleich wahrscheinlich ist?

Die Wahrscheinlichkeit, bei der ersten zufälligen Auswahl ein neues Bild zu erhalten, ist 1. Bei der zweiten zufälligen Auswahl eines weiteren Bildes ist sie (n−1)/n, der dritten (n−2)/n, bei der letzten 1/n.

Um ein zweites Bild zu erhalten, das neu ist, muss man im Mittel n/(n−1) Bilder kaufen, für das dritte n/(n−2) und so fort. Benötigt man im Mittel S Bilder, so gilt:

S = n/n + n/(n−1) + n/(n−2) + ... + n/1

S = n·H_n

$\text{mit } H_n=\sum_{k=1}^n \frac{1}{k}$

H_n ist die Summe der beschränkten harmonischen Reihe.

Beispielsweise werden durchschnittlich 837 Sammelbilder benötigt, um ein Sammelalbum mit n = 150 Bildern zu füllen.^[1]

Beispiel

Es gibt 150 verschiedene Motive auf den Pokémon-Karten, die man kaufen muss ohne die Motive zu kennen (Die Karten sind einzeln verpackt!). Wenn man davon ausgeht, dass vom Hersteller jedes Motiv gleich oft verpackt wird, wie viele Karten müssen die Eltern ihrem Kind im Durchschnitt kaufen bis es alle Motive besitzt?

Lösung:

Wir definieren zuerst den Ergebnisraum:

$\Omega:=\{\omega=(\omega_1,\omega_2,\dots)\,:\, \omega_i\in \{1,2,\dots,150\}\,\}$

Nun definieren wir Zufallsvariablen X_i(ω). Diese Zufallsvariable soll jedem Ergebnis $\omega\in\Omega$ die Anzahl der Käufe zuordnen, die gemacht werden müssen, um nach der (i-1)-ten verschiedenen Karte wieder eine neue, von den bisher gekauften verschiedene i-te Karte zu bekommen.

---

Hierzu ein Beispiel:

$\omega=(11,11,30,11,30,30,7,\dots)$

Dann ist X₃ = 4, da als erstes die Karte mit Nummer 11 gekauft wird. Die nächste davon verschiedene Karte trägt die Nummer 30. Danach sind noch vier Käufe nötig, bis eine neue (die dritte) verschiedene Karte, in diesem Fall die Nummer 7, erworben wird.

---

Nun bestimmen wir die Wahrscheinlichkeit dafür, dass X_i = 1 ist, also die Wahrscheinlichkeit dafür, dass bei jedem Kauf eine noch nicht vorhandene Karte erworben wird. P(X₁ = 1) = 1, da vor dem ersten Kauf keine Karten vorhanden sind. Dann ist P(X₂ = 1) = 149 / 150. Nur die bereits erworbene (erste) Karte wäre doppelt vorhanden. Führen wir diese Überlegung weiter, so finden wir schließlich allgemein:

$P(X_i=1)=\frac{150-i+1}{150}$

Diese Zufallsvariable ist geometrisch verteilt. Dann ergibt sich:

$P(X_i=k)=\left(\frac{i-1}{150}\right)^{k-1}\, \left(\frac{150-i+1}{150}\right)$

Als Erwartungswert für X_i erhalten wir:

$E\left(X_i\right)=\frac{150}{151-i}$

Definieren wir nun eine neue Zufallsvariable

$X:=\sum\limits_{i=1}^{150} X_i$

die angibt, wie viele Käufe gemacht werden müssen um alle 150 Karten zu besitzen. Da die einzelnen Erwartungswerte der X_i existieren, existiert auch der Erwartungswert für die neue Zufallsvariable:

$E(X)=\sum\limits_{i=1}^{150} E(X_i)\approx 838,677$

Daher wissen wir nun, dass die Eltern im Durchschnitt 839 Karten kaufen müssen, bis ihr Kind alle 150 Karten besitzt.

Literatur

• Philippe Flajolet, Danièle Gardy, Loÿs Thimonier Birthday paradox, coupon collectors, caching algorithms and self-organizing search., Discrete Applied Mathematics, Vol. 39, (1992), S. 207–229
• Elke Warmuth, Walter Warmuth: Elementare Wahrscheinlichkeitsrechnung: Vom Umgang mit dem Zufall. Vieweg + Teubner 1998, ISBN 9783519002253, S. 128-129
• Hans-Otto Georgii: Stochastik: Einführung in die Wahrscheinlichkeitstheorie und Statistik. Walter de Gruyter 2004, ISBN 9783110182828, S. 116-117

Weblinks

• Holger Dambeck: WM-Album. So teuer kommt der Sammelbildwahn auf Spiegel Online am 30. Juni 2011
• Coupon Collector Problem, Simulation mit einem Java Applet.
• Doron Zeilberger: How Many Singles, Doubles, Triples, Etc., Should The Coupon Collector Expect?.

Einzelnachweise

1. ↑ Denn: H_n(1..150) ≈ log(150) + 0.577 = 5,59 und damit H_n · n = 150 · 5,59 ≈ 837