Sammelbilderproblem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

Anschauung[Bearbeiten]

Mittlere Anzahl S benötigter Bilder für eine vollständige Serie aus n Bildern mit Standardabweichung (grau)

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 = \frac{n}{n} + \frac{n}{n-1} + \frac{n}{n-2} + \dotsb + \frac{n}{1}
S = n \cdot H_n \text{ mit } H_n=\sum_{k=1}^n \frac{1}{k}

H_n ist die n-te Partialsumme der harmonischen Reihe.

Beispielsweise muss man einen sechsseitigen Spielwürfel durchschnittlich 14,7 mal werfen, um jede Augenzahl mindestens einmal zu bekommen, denn mit n = 6 gilt

S = 6 \cdot H_6 = 6 \cdot \left(1 + \frac12 + \frac13 + \frac14 + \frac15 + \frac16\right) = \frac{147}{10} = 14{,}7.

Päckchen[Bearbeiten]

Sammelbilder werden üblicherweise nicht einzeln, sondern in Päckchen verkauft. Dabei ist garantiert, dass innerhalb eines Päckchens kein Bild mehrfach vorkommt.

Sind zum Beispiel fünf Bilder in einem Päckchen, errechnet sich die Anzahl der im Mittel zu kaufenden Bilder wie folgt:

Für das erste Bild aus dem ersten Päckchen gibt es n günstige aus n möglichen Varianten, um ein einzigartiges Bild zu erhalten. Das zweite Bild aus dem ersten Päckchen hat nun n-1 (ein Bild ist schon vorhanden) günstige aus n-1 (kein Bild wiederholt sich im Päckchen) möglichen Varianten, um ebenfalls einzigartig zu sein. Für das erste Päckchen mit 5 Bildern ergibt sich somit:

S_{P_1} = \frac nn + \frac{n-1}{n-1} + \frac{n-2}{n-2} + \frac{n-3}{n-3} + \frac{n-4}{n-4},

das zweite Päckchen:

S_{P_2} = \frac{n}{n-5} + \frac{n-1}{n-6} + \frac{n-2}{n-7} + \frac{n-3}{n-8} + \frac{n-4}{n-9}

usw.

Allgemein mit Albumgröße n und Päckchengröße p:

S=\sum_{i=0}^{n-1} \frac{n- (i\;\bmod\;p)}{n-i}.

Beispiel[Bearbeiten]

Histogramm einer Simulation (100.000 Realisierungen) des nebenstehenden Problems. Man erkennt die große Streuung: Im schlechtesten Fall mussten 2522 Karten gekauft werden.

Es gebe 150 verschiedene Motive auf den Pokémon-Karten, die man kaufen muss, ohne die Motive zu kennen (die Karten seien 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,\dotsc): \omega_i\in \{1,2,\dotsc,150\}\}.

Nun definieren wir Zufallsvariablen X_i(\omega). 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,\dotsc).

Dann ist X_3=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 wird die Wahrscheinlichkeit dafür bestimmt, dass X_i=1 ist, also die Wahrscheinlichkeit dafür, dass beim i-ten Kauf eine noch nicht vorhandene Karte erworben wird. P(X_1=1)=1, da vor dem ersten Kauf keine Karten vorhanden sind. Dann ist P(X_2=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[Bearbeiten]

Weblinks[Bearbeiten]