Sammelbilderproblem

Das Sammelbilderproblem, Sammlerproblem, Sammelalbenproblem oder Problem der vollständigen Serie befasst sich mit der Frage, wie viele Bilder einer Serie, die man einzeln nicht gezielt, sondern nur als zufällige Auswahl kaufen kann, zu erwerben sind, um ein Sammelalbum zu vervollständigen. Es kann als mathematisches Problem formuliert und seine Lösung versucht werden.

Sport-Sammelbilder

Beim klassischen Sammelbilderproblem geht man davon aus, dass alle Bilder zufällig gemischt und verdeckt gekauft werden und alle Motive gleich häufig vorkommen. Die letztere Voraussetzung ist aber beispielsweise bei Sammelkartenspielen nicht erfüllt, da hier das Vorkommen einzelner Karten stark variiert. Es konnte zudem nachgewiesen werden, dass bei vielen Sammelbilderserien die Bilder nicht zufällig gemischt werden. Eine weitere wichtige Rolle spielt die Möglichkeit des Nachkaufens und Tauschens von Karten. Das klassische Sammelbilderproblem ist in dieser allgemeinen Problemstellung bisher noch nicht gelöst worden.

Mit Hilfsmitteln der Wahrscheinlichkeitstheorie sowie Monte-Carlo-Simulationen können Sammelstrategien optimiert werden, um das Sammelalbum möglichst kostengünstig zu füllen. Für eine optimierte Sammelstrategie konnte eine Lösung unter veränderten, praxisrelevanten Annahmen gefunden werden.

Das Sammelbilderproblem ist aufgrund der Beliebtheit der Fußball-Sammelalben eines der wenigen mathematischen Probleme, über die regelmäßig in den Massenmedien berichtet und diskutiert wird.

Geschichte

Historisches Eishockey-Sammelbild

Die Tradition von Sammelbildern reicht bis in das 19. Jahrhundert zurück, wo sie als Produktzugaben z. B. bei Schokolade oder Zigaretten aufkamen. Eine Variante bestand darin, dass Coupons gesammelt werden mussten und der Sammler nach Einsendung einer vollständigen Serie eine Prämie erhielt. In den 1930er-Jahren erschienen Bilder von Film- oder Sportstars auf der Deckelinnenseite von Eiscremepackungen. Aber es gab auch schon früh andere Sammelobjekte, z. B. Buttons oder Figuren in Cornflakespackungen. Erst in den 1960er-Jahren haben sich vermehrt Sammelalben etabliert, bei denen die Bilder verdeckt in Tüten oder Päckchen verkauft werden, d. h. ohne dass der Sammler weiß, welche Bilder er erhält. Mit der Einführung von Fußballsammelalben, vorangetrieben durch die Firma Panini, wurde das Sammeln zu einem Massenphänomen, insbesondere zu Welt- oder Europameisterschaften. Mittlerweile sind Sammelalben zu Standard-Merchandising-Artikeln z. B. für Kinofilme geworden.

Die grundlegenden kombinatorischen Betrachtungen gehen bereits auf Markow zurück. Die konkrete mathematische Behandlung begann 1930 mit George Pólya, der das Problem aus Sicht des Herstellers darstellt:

„Jede Packung unserer Ware enthält zwei verschiedene Blumenbilder; die volle Kollektion umfasst 72 verschiedene Blumenbilder. Wer eine volle Kollektion sammelt und einsendet, erhält kostenlos eine Prämie. Der Verkäufer, der solche Reklame macht, muss sich vernünftigerweise die Frage vorlegen: Wie groß ist die Durchschnittszahl der verkauften Packungen pro Prämie?“

Diese Arbeit prägte daher den Namen als Coupon Collector’s Problem. Teilweise wurde es auch als Dixie Cup Problem bezeichnet (nach den Eiscremebechern, die nach der Herstellerfirma als Dixie Cup bezeichnet wurden). Beginnend mit William Fellers Standardwerk zur Wahrscheinlichkeitstheorie haben sich zahlreiche Mathematiker mit dem Sammelbilderproblem beschäftigt. Dadurch hat sich das Sammelbilderproblem als klassische mathematische Aufgabe etabliert.

Manchmal wird die Aufgabe auch als Sammelbilderparadoxon bezeichnet, weil überraschend viele Bilder benötigt werden, um das Album ohne Tauschen oder Nachkaufen zu vervollständigen. Für Pólyas Blumenbilderkollektion muss man im Durchschnitt 174 Päckchen, also 348 Blumenbilder sammeln (bei nur 72 unterschiedlichen Bildern), für das Sammelalbum zur Fußball-Europameisterschaft 2016 benötigt man sogar 4828 Bilder (bei 680 unterschiedlichen Bildern) – offenbar wächst das Verhältnis der im Mittel benötigten Bilder zur Anzahl der unterschiedlichen Bilder stärker als linear.

Das klassische Sammelbilderproblem

Das klassische Sammelbilderproblem stellt die Frage, wie viele Sammelbilder ein Einzelsammler im Mittel kaufen muss, um eine vollständige Serie von $n$ Sammelbildern zu erhalten, wenn er auf Tauschen und Nachkaufen verzichtet und jedes Bild einzeln kauft. Schon Pólya hatte die klassische Aufgabe definiert und wie folgt begründet:

„Die Käufer tauschen ihre Bilder aus oder werfen sie fort, der Verkäufer kann ein Bild vorenthalten usw. Wie man sieht, kann die Nichterfüllung der Voraussetzungen sowohl die eine als auch die andere Partei begünstigen und eben deshalb scheint mir die Berechnung der Durchschnittszahl unter den besagten Voraussetzungen zumindest als erste Orientierung einen gewissen Wert zu haben.“

Annahmen

Im klassischen Sammelbilderproblem werden die folgenden Annahmen getroffen:

• A1: Die Bilder werden bei der Herstellung gut gemischt, d. h. rein zufällig auf die Päckchen verteilt.
• A2: Alle Bilder kommen gleich häufig vor.
• A3: In einem Päckchen kommt kein Bild doppelt vor.

Der Ergebnisraum kann als Menge der möglichen Sammelbilderfolgen definiert werden:

$\Omega :=\{\omega =(\omega _{1},\omega _{2},\ldots ):\omega _{i}\in \{1,2,\ldots ,n\}\}$

Urnenmodell des Sammelbilderproblems mit sechs Bildern

Mathematisch entspricht das Sammelbilderproblem einem Urnenmodell mit Zurücklegen, und zwar bedeuten die gezogenen Zahlen die Nummern der Sammelbilder. Gesucht wird die Anzahl der Ziehungen, die nötig ist, bis jede Zahl mindestens einmal gezogen wurde. Dies bedeutet, dass die einzelnen gezogenen Nummern der Sammelbilder eine diskrete Gleichverteilung besitzen.

Wahrscheinlichkeitsverteilung der Füllung eines 4er-Albums

Gesucht ist die Wahrscheinlichkeit $W_{4,k}$ mit dem $k$-ten Kauf ein 4er-Album zu füllen. Die Bilder kommen beim Kauf gleich häufig vor. Die Wahrscheinlichkeit, ein bestimmtes Bild zu kaufen, ist also $p=p_{1}=p_{2}=p_{3}=p_{4}={\frac {1}{4}}$. Wir betrachten die Situation vor dem $k$-ten Kauf, die das Album füllt: $W_{4,k-1}^{*}$ ist die Wahrscheinlichkeit einer Multinomialverteilung, dass beim $k-1$-ten Kauf genau ein Bild fehlt, also jedes der 3 anderen Bilder schon mindestens einmal in der Sammlung vorhanden ist:

${\begin{aligned}W_{4,k-1}^{*}&=\sum _{n_{1}+n_{2}+n_{3}=k-1}{\frac {(k-1)!}{n_{1}!\cdot n_{2}!\cdot n_{3}!}}\cdot \left({\frac {1}{4}}\right)^{k-1}\\&+\sum _{n_{1}+n_{2}+n_{4}=k-1}{\frac {(k-1)!}{n_{1}!\cdot n_{2}!\cdot n_{4}!}}\cdot \left({\frac {1}{4}}\right)^{k-1}\\&+\sum _{n_{1}+n_{3}+n_{4}=k-1}{\frac {(k-1)!}{n_{1}!\cdot n_{3}!\cdot n_{4}!}}\left({\frac {1}{4}}\right)^{k-1}\\&+\sum _{n_{2}+n_{3}+n_{4}=k-1}{\frac {(k-1)!}{n_{2}!\cdot n_{3}!\cdot n_{4}!}}\cdot \left({\frac {1}{4}}\right)^{k-1}\end{aligned}}$

Die Summationsindizes $n_{1}$, $n_{2}$, $n_{3}$, $n_{4}$ geben jeweils die Anzahl der Exemplare der einzelnen Bilder an. $n_{1}$ ist die Anzahl der Exemplare des 1. Bilds, $n_{2}$ ist die Anzahl der Exemplare des 2. Bilds usw. Die Summationsindexe sind natürliche Zahlen größer oder gleich 1. Zur Berechnung der ersten Einzelwahrscheinlichkeit wird über alle ${\tbinom {k-2}{N-2}}={\tfrac {(k-2)!}{(N-2)!\cdot (k-N)!}}$ Darstellungen $n_{1}+n_{2}+n_{3}$ summiert, sodass die Summe dieser $N-1=3$ positiven ganzen Zahlen gleich $k-1$ ist. Entsprechendes gilt für die anderen Einzelwahrscheinlichkeiten.

Weil die 4 Einzelwahrscheinlichkeiten für $W_{4,k-1}^{*}$ gleich sind, kann man den obigen Ausdruck vereinfachen:

$W_{4,k-1}^{*}={\frac {(k-1)!}{4^{k-2}}}\sum _{i_{1}+i_{2}+i_{3}=k-1}{\frac {1}{i_{1}!\cdot i_{2}!\cdot i_{3}!}}$

Es fehlt genau ein Bild, d. h. mit dem $k$-ten Kauf wird unabhängig vom fehlenden Bild das Album mit der Wahrscheinlichkeit ${\tfrac {1}{4}}$ gefüllt. Daraus ergibt sich die gesuchte Wahrscheinlichkeit:

$W_{4,k}={\frac {1}{4}}\cdot W_{4,k-1}^{*}={\frac {(k-1)!}{4^{k-1}}}\sum _{i_{1}+i_{2}+i_{3}=k-1}{\frac {1}{i_{1}!\cdot i_{2}!\cdot i_{3}!}}$

Dieses Resultat kann leicht auf ein Album mit $N$ Bildern verallgemeinert werden. Für $p=p_{1}=\ldots =p_{N}={\frac {1}{N}}$ gilt dann

$W_{N,k}={\frac {(k-1)!}{N^{k-1}}}\sum _{i_{1}+...+i_{N-1}=k-1}{\frac {1}{\prod _{j=1}^{N-1}(i_{j})!}}$

Diese Verteilung ist eine Verallgemeinerung der negativen Binomialverteilung, mit welcher man das Sammelbilderproblem für den Fall $N=2$ beschreiben kann.

Wenn $k<N$ ist, kann ein Album mit $N$ Bildern mit dem $k$-ten Kauf offensichtlich nicht vervollständigt werden. Dann ist $W_{k}=0$, weil dann die durch das Summenzeichen definierte Summe leer, also gleich 0 ist.

Um die Wahrscheinlichkeit, dass das Album nicht mit dem $k$-ten Kauf, sondern nach $k$ Käufen, also spätestens mit dem $k$-ten Kauf, vollständig ist, zu bestimmen, muss die Summe $\sum \limits _{i=1}^{k}W_{i}$ gebildet werden. Wegen $W_{k}=0$ für $k<N$ ist $\sum \limits _{i=1}^{k}W_{i}=\sum \limits _{i=N}^{k}W_{i}$. Für $k<N$ ist auch die summierte Wahrscheinlichkeit offensichtlich gleich 0.

Die summierte Wahrscheinlichkeit kann auch einfacher mit der Formel

$P_{N,k}=\sum \limits _{i=1}^{N}(-1)^{N-i}\cdot {\binom {N}{i}}\cdot \left({\frac {i}{N}}\right)^{k}$

berechnet werden. Die Einzelwahrscheinlichkeit, mit dem $k$-ten Kauf das Album mit $N$ Bildern zu vervollständigen, ist also gleich

$P_{N,k}-P_{N,k-1}=\sum \limits _{i=1}^{N}(-1)^{N-i}\cdot {\binom {N}{i}}\cdot \left({\frac {i}{N}}\right)^{k-1}\cdot \left({\frac {i}{N}}-1\right)$

Zahlenbeispiel

Die Wahrscheinlichkeit, dass das 4er-Album nach 12 Käufen vollständig ist, beträgt

$P_{4,12}=\sum \limits _{i=1}^{4}(-1)^{4-i}\cdot {\binom {4}{i}}\cdot \left({\frac {i}{4}}\right)^{12}\approx 0{,}875$

Die Einzelwahrscheinlichkeit, das 4er-Album mit dem 12. Kauf zu vervollständigen, ergibt sich als Differenz aus dieser und der Wahrscheinlichkeit, dass das Album schon nach dem 11. Kauf vollständig ist:

$P_{4,12}-P_{4,11}=\sum \limits _{i=1}^{4}(-1)^{4-i}\cdot {\binom {4}{i}}\cdot \left({\frac {i}{4}}\right)^{11}\cdot \left({\frac {i}{4}}-1\right)\approx 0{,}0408$

Verallgemeinerung für m von N Bildern

Diese Formel lässt sich verallgemeinern. Die Wahrscheinlichkeit, dass nach $k$ Käufen, also spätestens mit dem $k$-ten Kauf, $m$ der $N$ Bilder mindestens einmal vorkommen, ist

$P_{N,k,m}={\binom {N}{m}}\cdot \sum \limits _{i=1}^{m}(-1)^{m-i}\cdot {\binom {m}{i}}\cdot \left({\frac {i}{N}}\right)^{k}$

Für den Spezialfall $m=N$ ergibt sich die oben erwähnte summierte Wahrscheinlichkeit $P_{N,k}$. Die Wahrscheinlichkeit, dass schon nach $k-1$ Käufen $m$ der $N$ Bilder mindestens einmal vorkommen, ist nach Definition $P_{N,k-1,m}$ und die Wahrscheinlichkeit, dass beim nächsten Kauf kein neues Bild hinzukommt, ist ${\frac {m}{N}}\cdot P_{N,k-1,m}$. Die Differenz ist also die Einzelwahrscheinlichkeit, mit dem $k$-ten Kauf zum ersten Mal $m$ verschiedene Bilder zu erhalten:

$P_{N,k,m}-{\frac {m}{N}}\cdot P_{N,k-1,m}={\binom {N}{m}}\cdot \sum \limits _{i=1}^{m}(-1)^{m-i}\cdot {\binom {m}{i}}\cdot \left({\frac {i}{N}}\right)^{k-1}\cdot {\frac {i-m}{N}}$

Päckchen

Sammelbilder werden in der Regel nicht einzeln, sondern in Päckchen mit $s$ Bildern, häufig auch Tüten oder Booster genannt, verkauft. Dabei wird vom Hersteller garantiert, dass innerhalb eines Päckchens kein Bild mehrfach vorkommt.

Es wurde bewiesen, dass Annahme A3 für die Sammelbilder der Firma Panini aufgrund des speziellen Verpackungsprozesses mit der Verpackungsmaschine Fifimatic erfüllt ist.

Die allgemeine Lösung ist komplizierter, aber der Vergleich der Ergebnisse ergibt, dass der Effekt der Päckchen eher gering ist, wenn die Päckchengröße $s$ im Verhältnis zur Gesamtzahl $n$ der Sammelbilder klein ist. Dies bedeutet für die meisten praktischen Anwendungen, dass die Päckchengröße vernachlässigt werden kann, denn die Wahrscheinlichkeit $P_{M}$ für das Ereignis $M$, dass es in einem Päckchen mindestens ein mehrfach vorkommendes Sammelbild gibt, beträgt wie beim Geburtstagsparadoxon

$P_{M}=1-{\frac {n!}{n^{s}\cdot (n-s)!}}=1-{\frac {\prod _{i=n-s+1}^{n}i}{n^{s}}}=1-\prod _{i=n-s+1}^{n}{\frac {i}{n}}=1-\left({\frac {n}{n}}\cdot {\frac {n-1}{n}}\cdot {\frac {n-2}{n}}\cdot \ldots \cdot {\frac {n-s+1}{n}}\right)$

Die Wahrscheinlichkeit $P_{\overline {M}}$ für das Gegenereignis ${\overline {M}}$ (siehe Ereignis (Wahrscheinlichkeitstheorie) - Komplement und Differenz), dass jedes Bild der Sammelbilderserie höchstens einmal im Päckchen vorkommt, beträgt

$P_{\overline {M}}={\frac {n!}{n^{s}\cdot (n-s)!}}$

Wartezeit bis zum nächsten neuen Bild

Die Zufallsvariable $X_{i}(\omega )$ ordnet jedem Ergebnis $\omega \in \Omega$ die Anzahl der Käufe zu, 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. Dies entspricht der Wartezeit bis zum nächsten neuen Bild.

Histogramm einer Simulation (100.000 Realisierungen) am Beispiel von 150 Karten. Man erkennt die große Streuung: Im schlechtesten Fall mussten 2522 Karten gekauft werden.

Da beim ersten Kauf sicher ein neues Bild kommt, ist die Wahrscheinlichkeit $P(X_{1}=1)=1$. Beim Kauf des zweiten Bildes ist sie $P(X_{2}=1)={\tfrac {n-1}{n}}$. Diese Zufallsvariable ist geometrisch verteilt. Allgemein ergibt sich:

$P(X_{i}=k)=\left({\frac {i-1}{n}}\right)^{k-1}\cdot \left({\frac {n-i+1}{n}}\right)$

Als Erwartungswert für $X_{i}$ ergibt sich:

$\operatorname {E} (X_{i})={\frac {n}{n-i+1}}$

Dies bedeutet insbesondere, dass man, um das letzte fehlende Bild der Sammlung zu erhalten, im Mittel $n$ Bilder kaufen muss. Das sind aber genauso viele Bilder, wie man überhaupt sammeln muss, und erklärt, warum das Sammeln ohne Tauschen und Nachkaufen so teuer ist.

Wahrscheinlichkeitsverteilung für die Anzahl der Käufe

Die Zufallsvariable

$X:=\sum \limits _{i=1}^{n}X_{i}$

gibt an, wie viele Käufe gemacht werden müssen, um alle $n$ Karten zu besitzen. Dies ist die Summe der Wartezeiten (Anzahl der Käufe) für die 1., 2., 3. …, $n$-te Karte, die von den bisher gekauften Karten verschieden ist. Die stochastisch unabhängigen Zufallsvariablen $X_{i}$ sind jeweils geometrisch verteilt. Ihre Summe $X$ besitzt eine diskrete Phasenverteilung. Die Wahrscheinlichkeitsverteilung kann durch Auswertung der zugehörigen Markow-Kette oder rekursiv berechnet werden.

Im allgemeineren Fall gibt die Zufallsvariable

$X_{n,m}:=\sum \limits _{i=1}^{m}X_{i}$

an, wie viele Käufe gemacht werden müssen, um genau $m$ der $n$ Karten zu besitzen.

Erwartungswert

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

Weil die einzelnen Erwartungswerte $\operatorname {E} (X_{i})$ existieren, existiert auch der Erwartungswert $\operatorname {E} (X)$ für die neue Zufallsvariable:

$\operatorname {E} (X)=\operatorname {E} \left(\sum \limits _{i=1}^{n}X_{i}\right)=\sum \limits _{i=1}^{n}\operatorname {E} (X_{i})$

Das folgt aus der Linearität des Erwartungswerts.

Dann gilt:

$\operatorname {E} (X)={\frac {n}{n}}+{\frac {n}{n-1}}+{\frac {n}{n-2}}+\ldots +{\frac {n}{1}}=n\cdot H_{n}\quad {\text{mit}}\quad H_{n}=\sum _{k=1}^{n}{\frac {1}{k}}$

$H_{n}$ ist die $n$-te Partialsumme der harmonischen Reihe. $H_{n}$ ist also der Faktor, der angibt, wie viel Mal mehr Bilder man kaufen muss im Vergleich zur Größe $n$ des Sammelalbums. Für große $n$ gilt die Näherung durch den natürlichen Logarithmus: $H_{n}\approx \ln(n)+\gamma$ mit der Euler-Mascheroni-Konstante $\gamma \approx 0{,}577$, also

$\operatorname {E} (X)\approx n\cdot (\ln(n)+0{,}577)$

Der Erwartungswert für die Wartezeit im allgemeineren Fall, dass genau $m$ der $n$ Karten vorkommen, ist

$\operatorname {E} (X_{n,m})=\operatorname {E} \left(\sum \limits _{i=1}^{m}X_{i}\right)=\sum \limits _{i=1}^{m}\operatorname {E} (X_{i})={\frac {n}{n}}+{\frac {n}{n-1}}+{\frac {n}{n-2}}+\ldots +{\frac {n}{n-m+1}}=n\cdot (H_{n}-H_{n-m})\approx n\cdot (\ln(n)-\ln(n-m))$

Varianz

Da die Wartezeiten auf die jeweils nächsten neuen Bilder geometrisch verteilt und unabhängig sind, ergibt sich mit $q_{i}=P(X_{i}=1)={\frac {n-i+1}{n}}$ für die Varianz $\operatorname {Var} (X)$ der Anzahl der zu sammelnden Bilder die endliche Summe

${\begin{aligned}\operatorname {Var} (X)&={\frac {1-q_{1}}{q_{1}^{2}}}+{\frac {1-q_{2}}{q_{2}^{2}}}+\ldots +{\frac {1-q_{n}}{q_{n}^{2}}}=\sum _{i=1}^{n}\left({\frac {1}{q_{i}^{2}}}-{\frac {1}{q_{i}}}\right)=\sum _{i=1}^{n}{\frac {1}{q_{i}^{2}}}-\sum _{i=1}^{n}{\frac {1}{q_{i}}}=\sum _{i=1}^{n}\left({\frac {n}{n-i+1}}\right)^{2}-\sum _{i=1}^{n}{\frac {n}{n-i+1}}\\&=\left({\frac {n^{2}}{n^{2}}}+{\frac {n^{2}}{(n-1)^{2}}}+\ldots +{\frac {n^{2}}{1^{2}}}\right)-\left({\frac {n}{n}}+{\frac {n}{n-1}}+\ldots +{\frac {n}{1}}\right)\\&=n^{2}\cdot \left({\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+\ldots +{\frac {1}{n^{2}}}\right)-n\cdot \left({\frac {1}{1}}+{\frac {1}{2}}+\ldots +{\frac {1}{n}}\right)\\&<n^{2}\cdot {\frac {\pi ^{2}}{6}}-n\cdot \ln(n)-n\cdot \gamma -{\mathcal {O}}(1)\end{aligned}}$

Die letzte Ungleichung folgt aus der Konvergenz unendlichen Reihe $\sum _{n=1}^{\infty }{\frac {1}{n^{2}}}={\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\ldots ={\frac {\pi ^{2}}{6}}$ des sogenannten Basler Problems und der asymptotischen Entwicklung der harmonischen Reihe.

Im abgebildeten Koordinatensystem wächst die Standardabweichung mit $n$ stark an.

Anzahl der verschiedenen Bilder

Die Wahrscheinlichkeit, dass der Käufer nach $k$ Käufen ein bestimmtes der $n$ Bilder besitzt, sei $P_{k}$. Am einfachsten ist es, zuerst die Wahrscheinlichkeit zu berechnen, dass das Bild nach $k$ Käufen noch nicht vorhanden ist, d. h. dass alle $k$ Karten eines der anderen $n-1$ Bilder zeigen. Diese Wahrscheinlichkeit ist $\left({\tfrac {n-1}{n}}\right)^{k}$. Gesucht ist die Wahrscheinlichkeit für das Gegenereignis, also

$P_{k}=1-\left({\tfrac {n-1}{n}}\right)^{k}$

Erwartungswert

Ist die Zufallsvariable $Y_{k}$ definiert als die Anzahl der verschiedenen Bilder, die nach $k$ Käufen vorkommen, dann ist diese Zufallsvariable binomialverteilt mit der Erfolgswahrscheinlichkeit $P_{k}$. Für den Erwartungswert gilt dann

$\operatorname {E} (Y_{k})=n\cdot P_{k}=n\cdot \left(1-\left({\tfrac {n-1}{n}}\right)^{k}\right)$

Varianz

Für die Varianz der Anzahl der verschiedenen Bilder nach $k$ Käufen gilt

$\operatorname {Var} (Y_{k})=n\cdot P_{k}\cdot (1-P_{k})=n\cdot \left({\tfrac {n-1}{n}}\right)^{k}\cdot \left(1-\left({\tfrac {n-1}{n}}\right)^{k}\right)$

Nachkaufen

Die meisten Hersteller bieten an, eine bestimmte Anzahl $K$ von Bildern, häufig 50, nachzukaufen, in der Regel zu einem erhöhten Preis. Außerdem kann man gezielt bestimmte Sammelbilder kaufen, z. B. in speziellen Sammlerbörsen oder Online-Shops. Die wichtige Frage ist, wann sich Nachkaufen lohnt.

Fehlen noch $x$ Bilder und ein bestimmtes Bild wird zum Preis von $k$ angeboten, so lohnt sich der Kauf, wenn im Mittel die Kosten geringer sind als die Kosten für das nächste Bild beim normalen Sammeln. Sei $b$ der normale Preis eines einzelnen Bildes, so lohnt sich der Kauf, wenn

$b\cdot {\frac {n}{x}}>k$

Wenn die Möglichkeit besteht, $K$ Bilder nachzukaufen, so lohnt es sich am meisten, diese komplett am Ende nachzukaufen. Man müsste sonst im Mittel

${\frac {n}{1}}+{\frac {n}{2}}+{\frac {n}{3}}+\ldots +{\frac {n}{K}}=n\cdot H_{K}$

Bilder kaufen, statt $K$ Bilder nachzukaufen, und dieser Spareffekt kann sehr groß sein.

Die erwartete Anzahl der zu kaufenden Bilder reduziert sich auf

$S=n\cdot (H_{n}-H_{K})+K\approx n\cdot (\ln(n)-\ln(K))+K=n\cdot \ln \left({\frac {n}{K}}\right)+K$

Dies bedeutet, dass der Faktor drastisch reduziert und in erster Näherung nur noch vom Verhältnis der Albumgröße zur Anzahl der Nachkaufbilder abhängt und nicht direkt von der Albumgröße. Dies ermöglicht eine vereinfachte Berechnung der mittleren Kosten des Sammelalbums.

Tauschen

Eine weitere wichtige Erweiterung ist das Tauschen von doppelt im Besitz befindlichen Karten. Dies geschieht traditionell im Freundeskreis, zunehmend aber auch in organisierten Tauschbörsen z. B. über das Internet. In der mathematischen Modellierung wird in der Regel das faire Tauschen betrachtet, d. h. es wird jeweils ein Bild gegen ein anderes getauscht. Auch wird angenommen, dass die $m$ Tauschpartner kooperieren und solange gemeinsam sammeln und fair tauschen, bis jeder Sammler sein Album gefüllt hat. Dies entspricht dem Fall, dass ein Sammler $m$ Sammelalben vervollständigt.

Für diesen Fall wurde bisher keine geschlossene Lösung gefunden; am Beispiel des WM-Albums wurde per Simulation gezeigt, dass der Effekt erheblich ist. Asymptotisch gilt für den Mittelwert bei einer festen Anzahl $m$ von Tauschpartnern

$S_{m}=n\cdot \ln(n)+(m-1)\cdot n\cdot \ln(\ln(n))+{\mathcal {O}}(n)$ für $n\to \infty$

Dies zeigt den Effekt des Tauschens: Während der erste Sammler im Mittel $n\cdot \ln(n)$ Karten kaufen muss, braucht jeder weitere Sammler im Mittel nur $n\cdot \ln(\ln(n))$ zusätzlich zu kaufen. Mit dieser Formel kann man grob abschätzen, wie viel Geld man durch das Tauschen sparen kann. Z. B. würden sich die Kosten für zwei Tauschpartner durch faires Tauschen auf etwa 60 % der Kosten eines Einzelsammlers reduzieren.

In einem Jugend-forscht-Projekt wurde für das Szenario faires Tauschen mit Nachkaufen der Faktor $f={\tfrac {S_{m}}{m\cdot n}}$ durch umfangreiche Simulationen untersucht, wobei $S_{m}$ die mittlere Anzahl insgesamt zu kaufender Bilder aller Tauschpartner ist. Der Faktor $f$ gibt mithin an, wie viel Mal mehr Bilder jeder Sammler am Ende im Mittel gekauft hat, als das vollständige Album Bilder enthält. Während ohne Tauschen und Nachkaufen der Faktor für einen Einzelsammler gut durch den natürlichen Logarithmus der Anzahl der Sammelbilder angenähert werden kann (bzw. dem doppelten Logarithmus für eine große Anzahl von Tauschpartnern), konnte plausibel experimentell belegt werden, dass bei fairem Tauschen mit Nachkaufen, bei festem Nachkaufprozentsatz, $f\to 1$ strebt, wenn die Anzahl der tauschenden Sammler $m\to \infty$ strebt.

Kritik der klassischen Annahmen

Die Annahmen des klassischen Sammelbilderproblems werden häufig als unrealistisch kritisiert und insbesondere im Internet kursieren Gerüchte, dass die Hersteller entweder Bilder künstlich verknappen oder die Bilder nicht ordentlich mischen, d. h. zu viele Doppelte vorkommen oder manche Bilder zu selten.

Ein Journalist von Spiegel online untersuchte die Annahme A2 für das Sammelalbum zur Fußball-Weltmeisterschaft 2014 zusammen mit der Website stickermanager.com. Durch die Betrachtung des aufbereiteten Datenbestandes von 8,33 Millionen Einträgen kam der Statistiker Christian Hesse zu dem Ergebnis: „Die gravierenden Unterschiede lassen sich mit dem Wirken des Zufalls allein nicht erklären“. Dabei wurde angenommen, dass die Onlineumfrage repräsentativ ist. Allerdings galt dies nur für die deutsche Edition; z. B. bei der Schweizer Edition, die separat produziert wird und optisch unterscheidbar ist, traten die 2,36 Millionen registrierten Sticker gleichmäßig häufig auf.

In einer Untersuchung des Herstellungsprozesses konnte nachgewiesen werden, dass bei der Verpackung der Sammelbilder von Topps und Panini systematische Abweichungen bzw. Muster entstehen, die sich signifikant vom zufälligen Mischen unterscheiden. Für den Verpackungsprozess der Panini-Sammelbilder konnte nachgewiesen werden, dass statt ${\tbinom {n}{m}}$ möglicher verschiedener Päckchen (unter Annahme A1 bei Päckchengröße $m$) nur maximal $4\cdot \left({\frac {n}{4\cdot m}}\right)^{m}$ verschiedene Päckchen vorkommen können. Dies wirkt sich allerdings nicht nachteilig für den Sammler aus.

Dies bedeutet, dass die Annahmen des klassischen Sammelbilderproblems, insbesondere A1, in der Praxis nicht erfüllt sind.

Optimierte Sammelstrategie

Für die Kombination von Tauschen und Nachkaufen unter den klassischen Annahmen gibt es bisher keine analytischen Ergebnisse. Per Simulation wurde nachgewiesen, dass das Potenzial solcher optimierter Strategien erheblich ist. Es wird allerdings davon ausgegangen, dass in einem Display (das sind Verpackungen für den Handel mit 50 oder 100 Päckchen) keine Doppelten vorkommen. Dies ist allerdings nur in Einzelfällen korrekt. Stattdessen wurde nachgewiesen, dass in einem Display weniger Doppelte vorkommen, als bei zufälliger Mischung erwartet würden. Außerdem sind Displays günstiger als der Kauf einzelner Päckchen.

Die Empfehlung aufgrund der Simulationsergebnisse ist die folgende optimierte Sammelstrategie:

1. Kauf eines Displays
2. Kauf weiterer Päckchen und Tausch möglichst vieler Bilder, bis nur noch die möglichen Nachkaufbilder fehlen
3. Nachkauf am Schluss der maximal erlaubten Zahl von Bildern beim Hersteller

Die optimierte Strategie und die damit verbundenen Kosten wurden in einem öffentlichen Experiment des Göttinger Tageblatts für das Sammelalbum zur Fußball-Europameisterschaft 2016 mit guter Genauigkeit bestätigt.

Sind in einem Display $D$ Bilder und kommen darunter $d$ unterschiedliche Bilder vor, so gilt

$S=n\cdot (H_{n-d}-H_{K})+D+K$

Allerdings ist die klassische Annahme der Sammelgemeinschaften heute nicht mehr realistisch, da überwiegend spontan in Tauschbörsen oder über das Internet getauscht wird. Nimmt man an, dass der Sammler $T$ fehlende Bilder nach dem Kauf des Displays vor dem Nachkaufen tauschen kann, so ergibt sich mit dem Anteil $t={\frac {T}{n-d-K}}$ der Tauschbilder

$S=n\cdot (H_{n-d}-H_{K})\cdot (1-t)+D+K\approx n\cdot \ln \left({\frac {n-d}{K}}\right)^{1-t}+D+K$

Auch die Varianz V der Anzahl der zu sammelnden Bilder kann unter diesen Annahmen bestimmt werden

${\frac {V}{n}}\approx \left(\left({\frac {n-d}{K}}-1\right)-\ln \left({\frac {n-d}{K}}\right)\right)\cdot \left(1-t\right)$

Damit können die Kosten des Sammelbilderalbums für die optimierte Sammelstrategie unter realistischen Annahmen abgeschätzt werden und das Sammelbilderproblem ist unter diesen Annahmen gelöst.

Das allgemeine Sammelbilderproblem

Im allgemeinen Sammelbilderproblem kann die Wahrscheinlichkeit für jedes Bild unterschiedlich sein, und zwar $p_{i}$. Dies ist der allgemeinste Fall einer diskreten Wahrscheinlichkeitsverteilung. Die Lösung ist nicht mehr mit elementarer Wahrscheinlichkeitsrechnung herleitbar, sondern nur mit erzeugenden Funktionen. Für den Mittelwert ergibt sich

$S=\int _{0}^{\infty }\left(1-\prod _{i=1}^{n}(1-e^{-p_{i}t})\right)dt$

Hiermit kann man für einen Sammler ohne Nachkaufen die mittlere Anzahl benötigter Karten für Trading Card Games berechnen.

Beispiele

Würfel

Spielwürfel

Für pädagogische Zwecke wird häufig das Sammelbilderproblem mit Hilfe eines normalen Spielwürfels eingeführt und veranschaulicht. In der Praxis könnte dies z. B. $n=6$ Sammelfiguren entsprechen, die einem Produkt beigemischt sind.

Man muss durchschnittlich 14,7-mal werfen, um jede Augenzahl mindestens einmal zu bekommen, denn es gilt

$S=6\cdot H_{6}=6\cdot \left(1+{\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{4}}+{\frac {1}{5}}+{\frac {1}{6}}\right)={\frac {147}{10}}=14{,}7$

Nimmt man die Päckchengröße $p=2$ an (dies entspricht Würfeln mit zwei Würfeln unter Ausschluss eines Paschs), so erhält man

$S=\left(1+1+{\frac {3}{2}}+{\frac {5}{3}}+3+5\right)={\frac {79}{6}}\approx 13{,}167$

Augenzahlen, d. h. man muss im Durchschnitt ${\tfrac {1}{2}}\cdot {\tfrac {79}{6}}\approx 6{,}583$ mal würfeln, da mit einem Wurf zwei Würfel (mit verschiedenen Augenzahlen) geworfen werden. Es gilt $P_{D}={\tfrac {1}{6}}$, d. h. man kann erwarten, durch das Päckchen im Mittel mindestens ein Bild zu sparen.

Eine einfache Erweiterung besteht darin, mit zwei unterscheidbaren Würfeln zu spielen und damit ein Sammelalbum mit $n=36$ Sammelbildern zu simulieren. Für den Einsatz im Schulunterricht wurde ein entsprechendes Sammelspiel entwickelt, mit dem verschiedene Sammelstrategien ausprobiert werden können. Dies entspricht dem von Rewe herausgegebenen offiziellen DFB-Sammelalbum zur Fußball-Europameisterschaft 2016, wobei die Sammelbilder hier eine Produktzugabe für je 10 € Einkaufswert darstellen und nicht nachgekauft werden können. Hier benötigt man als Einzelsammler zum Vervollständigen schon fast 150 Sammelbilder. Das Tauschen bekommt eine besondere Bedeutung, denn beim fairen Tauschen müsste jeder weitere Sammler dann nur etwa 67 Bilder sammeln, und das wäre gleichzeitig auch der Grenzwert bei sehr vielen Tauschpartnern.

Pokémon

Pokémon-Sammelkarten

Angenommen, es gäbe 150 verschiedene Motive auf den Pokémon-Karten, die man kaufen muss, und die Karten seien einzeln verpackt. Wenn es sich um ein klassisches Sammelalbum handelte, dann müsste ein Einzelsammler ohne Nachkaufen im Mittel ungefähr 839 Karten kaufen.

Allerdings ist Pokémon in Wirklichkeit ein Trading Card Game, d. h. es gibt mehr als 5 unterschiedliche Kartentypen mit unterschiedlichen Seltenheiten, von normal bis extrem selten. Den großen Unterschied kann man schon bei zwei Kartentypen erkennen, bei denen z. B. 30 von 150 Karten halb so häufig auftreten wie im klassischen Sammelbilderspiel. Dann müsste der Einzelsammler schon im Mittel etwa 1213 Karten kaufen. Gibt es 10 sehr seltene Karten, die zehnmal seltener auftreten, dann brauchte er sogar etwa 4372 Karten. Dies bedeutet, dass Nachkaufen und Tauschen noch eine größere Bedeutung besitzen als bei den klassischen Sammelbildern.

Fußballsammelbilder

Das Paninialbum zur Fußball-Europameisterschaft 2016 mit 680 Bildern kostet mindestens 95,20 € bei einem regulären Preis von 14 Cent pro Bild. Dies wäre gleichzeitig auch der erwartete Preis für das letzte fehlende Bild, wenn man es normal sammeln würde. Für den Faktor gilt $H_{680}\approx 7{,}1$. Dies ergibt für einen Einzelsammler ohne Tauschen und Nachkaufen eine mittlere Anzahl zu kaufender Bilder von etwa 4828 (d. h. 965,5 Päckchen) und entspricht etwa 676 €. Aber auch die Standardabweichung ist groß (869 Bilder), d. h. in etwa 95,4 % aller Fälle müsste ein Einzelsammler zwischen 3090 und 6566 Bilder sammeln. Dies verdeutlicht, dass unbedingt getauscht und nachgekauft werden sollte, um die Kosten zu verringern.

Der Einfluss der Päckchen ist gering, bei Fünfer-Päckchen beträgt $P_{D}$ nur ungefähr 0,016, d. h. bei etwa jedem 60. Päckchen müsste man ein doppeltes Bild erwarten, wenn die Karten zufällig gemischt würden. Dieser Einfluss wird häufig überschätzt oder falsch eingeschätzt. Bei exakter Rechnung muss man im Mittel etwa 963,2 Päckchen kaufen, d. h. die Ersparnis beträgt im Mittel nur 12 Bilder und kann daher auch in Anbetracht der großen Standardabweichung praktisch vernachlässigt werden.

Kann man 50 Bilder nachkaufen, spart man etwa 3060 Bilder, d. h. dann braucht man näherungsweise im Mittel nur 1768 Karten zu kaufen sowie 50 Nachkaufkarten. Dies kostet dann etwa 257 € bei 20 Cent pro Nachkaufbild (ohne Berücksichtigung des Päckchen-Effekts). Auch die Standardabweichung sinkt auf etwa 82 Bilder, d. h. in etwa 95,4 % aller Fälle müsste ein Einzelsammler zwischen 1604 und 1936 Bilder sammeln.

Bei einer unendlich großen Sammelgemeinschaft wäre der Faktor für jeden Sammler etwa 1,88, d. h. jeder müsste im Mittel etwa 1275 Bilder kaufen, was einem Preis von etwa 179 € entspricht. Für das Album zur Fußball-Weltmeisterschaft 2014 wurde abgeschätzt, dass man mit einer optimierten Sammelstrategie das Sammelalbum für etwa 125 € füllen kann. Berücksichtigt man die Preiserhöhung und die zusätzlichen Sammelbilder des EM-Albums, so ergibt sich mit dieser Strategie ein Preis von etwa 150 €. In einem öffentlichen Sammelexperiment wurde dies mit 155 € Kosten bestätigt. Im Grenzfall des konsequenten Nachkaufens mit einer unendlich großen Sammelgemeinschaft würden sich 98,20 € pro Sammler ergeben.

Das Paninialbum zur Fußball-Weltmeisterschaft 2018 unterscheidet sich mit 682 Bildern praktisch nicht vom Album zur Europameisterschaft. Der wesentliche Unterschied ist der höhere Preis mit 18 Cent pro Bild, d. h. das Album kostet regulär mindestens 122,76 €. Alle anderen klassischen Ergebnisse können durch einfache Umrechnung abgeleitet werden. Unter realistischen Annahmen, z. B. $d=450$, $t=0{,}5$ und einem Preis von 75 € pro Display, ergeben sich für die optimierte Strategie mittlere Kosten von etwa 184 €. Die Streuung ist relativ klein, 99 % der Sammler könnten unter diesen Annahmen das Album für Kosten zwischen 176 € und 193 € füllen. Verzichtet der Sammler auf das Tauschen, muss er dagegen im Mittel 276 € bezahlen. Tauscht er alle Doppelten, so braucht er im Mittel nur 111 €. Ähnliche Ergebnisse wurden per Simulation bestätigt.