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 Bilder einer Sammelbildserie zu kaufen sind, um eine komplette Bildserie zu erhalten.

Beim klassischen Sammelbilderproblem wird davon ausgegangen, dass alle Bilder gleichverteilt sind. Dies ist aber zum Beispiel bei Trading Card Games nicht erfüllt, hier gibt es Karten, die seltener als andere vorkommen. Weiter ist es wichtig, zu unterscheiden, ob Karten nachgekauft oder getauscht werden können. Außerdem kann berücksichtigt werden, ob die Bilder einzeln oder in Päckchen gekauft werden.

Das klassische Sammelbilderproblem[Bearbeiten]

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

Wie viele Sammelbilder muss ein Einzelsammler im Mittel kaufen, um eine vollständige Serie von n Bildern zu erhalten, wenn Tauschen und Nachkaufen ausgeschlossen ist und man jedes Bild einzeln kauft? Wir definieren zuerst den Ergebnisraum:

\Omega:=\{\omega=(\omega_1,\omega_2,\dotsc): \omega_i\in \{1,2,\dotsc,n\}\}.

Wartezeit auf das nächste neue Bild[Bearbeiten]

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, d. h. wir betrachten hier die Wartezeiten auf das nächste neue Bild.

Da man beim ersten Kauf sicher ein neues Bild erhält, ist P(X_1=1)=1 . Beim Kauf des zweiten Bildes ist sie P(X_2=1)=(n-1)/n. Diese Zufallsvariable ist geometrisch verteilt. Allgemein ergibt sich:

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

Als Erwartungswert für X_i erhalten wir:

E\left(X_i\right)=\frac{n}{n-i+1}.

Erwartungswert[Bearbeiten]

Definieren wir nun eine neue Zufallsvariable

X:=\sum\limits_{i=1}^{n} X_i,

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

 S=E(X)=\sum\limits_{i=1}^{n} E(X_i).

Dann 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. H_n ist also der Faktor, der angibt, wie viel mal mehr Bilder man kaufen muss im Vergleich zur Größe des Sammelalbums. Für große n gilt die Näherung: H_n\approx \ln n + 0{,}577.

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}.

Vergleicht man die Formeln, so erkennt man, dass der Effekt der Päckchen eher gering ist, wenn die Päckchengröße im Verhältnis zur Gesamtzahl der Sammelbilder klein ist. Dies bedeutet für die meisten praktischen Anwendungen, dass man die Päckchengröße vernachlässigen kann, denn die Wahrscheinlichkeit, dass es in einem Päckchen mindestens eine doppelte Karte gibt, beträgt wie beim Geburtstagsparadoxon

D = 1- \left( \frac{n}{n} \cdot\frac{n-1}{n} \cdot \frac{n-2}{n} \dots \frac{n-p+1}{n}\right).

Varianz[Bearbeiten]

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

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) für die Varianz V der Anzahl der zu sammelnden Bilder

V= \frac{1-q_1}{q_1^2} + \frac{1-q_2}{q_2^2} +  \cdots + \frac{1-q_n}{q_n^2}

In der Abbildung kann man erkennen, dass die Standardabweichung stark mit n wächst.

Nachkaufen[Bearbeiten]

Die meisten Hersteller bieten an, dass eine bestimmte Anzahl von Bildern K nachgekauft werden kann, in der Regel zu einem erhöhten Preis. Außerdem kann man bestimmte Sammelbilder kaufen, z. B. in speziellen Sammlerbörsen oder bei eBay. Die wichtige Frage ist dann, wann sich Nachkaufen lohnt.

Fehlen einem Sammler noch x Bilder und wird ihm ein bestimmtes Bild zum Preis von k angeboten, so lohnt sich der Kauf, wenn er im Mittel weniger Geld als für das Warten auf das nächste Bild beim normalen Sammeln ausgeben müsste. Sei b der normale Preis einen einzelnen Bildes, so lohnt sich der Kauf, wenn

b\frac{n}{x}>k.

Daran erkennt man auch sofort, dass es sich am meisten lohnt, die Bilder am Ende nachzukaufen, das heißt, solange zu sammeln, bis noch K Bilder fehlen, und diese komplett nachzukaufen. Man müsste sonst im Mittel nach Flajolet et. al. (1992)

\frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \dotsb + \frac{n}{K} = n \cdot H_K

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

Tauschen[Bearbeiten]

Die meisten Sammler tauschen Doppelte untereinander. 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. Die entspricht dem Fall, als wenn ein Sammler m Sammelalben vervollständigt.

Für diesen Fall wurde bisher keine geschlossene Lösung gefunden, Sardy und Velenik (2010) haben am Beispiel des WM-Albums per Simulation gezeigt, dass der Effekt erheblich ist. Newman und Shepp (1960) haben bewiesen, dass asymptotisch für den Mittelwert bei einer festen Anzahl m von Tauschpartnern gilt

 S_m =  n \ln n + (m-1) n \ln\ln n + O(n), \ \ \text{für}  \ n \to \infty..

Dies zeigt deutlich den Effekt des Tauschens: während der erste Sammler im Mittel  n \ln n Karten kaufen muss, braucht jeder weitere Sammler im Mittel nur  n \ln\ln n zusätzlich kaufen.

Das allgemeine Sammelbilderproblem[Bearbeiten]

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. Nach Flajolet et al. (1992) ergibt sich für den Mittelwert

S=\int_0^\infty \big(1-\prod_{i=1}^n(1-e^{-p_it})\big)dt.

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

Beispiele[Bearbeiten]

Würfel[Bearbeiten]

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

S = 6 \cdot H_6 = 6 \cdot \left(1 + \frac12 + \frac13 + \frac14 + \frac15 + \frac16\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 + \frac32 + \frac53 + 3 + 5\right) = 13\frac16 = 13{,}16,

d. h. man muss etwa 1,5 mal weniger würfeln. Es gilt D= \frac{1}{6}, d. h. man kann erwarten, durch das Päckchen im Mittel mindestens ein Bild zu sparen.

Pokémon[Bearbeiten]

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

Allerdings ist Pokémon in Wirklichkeit ein Trading Card Spiel, d. h. es gibt mehr als 5 unterschiedliche Kartentypen mit unterschiedlichen Seltenheiten, von normal bis extrem selten. Hier soll gezeigt werden, dass dies einen großen Unterschied ausmacht, und zwar betrachten wir zwei Kartentypen, 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 bräuchte man sogar etwa 4372 Karten. Dies bedeutet, dass Nachkaufen und Tauschen noch eine größere Bedeutung besitzen als bei den klassischen Sammelbildern.

WM-Album[Bearbeiten]

Für das klassische WM-Album mit 640 Bildern erhält man mit der Näherungsformel einen Faktor von ungefähr 7 und eine mittlere Anzahl zu kaufender Bilder von etwa 4505. Bei 5-er Päckchen beträgt D nur ungefähr 0,016, d. h. bei etwa jedem 60-ten Päckchen müsste man mal ein doppeltes Bild erwarten, wenn die Karten zufällig gemischt würden. Kann man 50 Bilder (zum 1,5-fachen Preis) nachkaufen, dann braucht man näherungsweise im Mittel nur 1632 Karten zu kaufen sowie 50 Nachkaufkarten.

Auch bei Fußballkarten sind Trading-Card-Spiele beliebt, z. B. ist Match Attax ein beliebtes Sammelkartenspiel. In der Bundesligasaison 2014/15 gab es unter 454 Karten z. B. 36 Star-Spieler, 36 Vereinswappen, 54 Matchwinner und 6 Club-100-Karten, die unterschiedlich häufig vorkommen.

Literatur[Bearbeiten]

Weblinks[Bearbeiten]