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.
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
mini|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.George Pólya: Eine Wahrscheinlichkeitsaufgabe in der Kundenwerbung. ZAMM – Zeitschrift für Angewandte Mathematik und Mechanik, Band 10, Heft 1, 1930, S. 96–97. In den 1930er-Jahren erschienen Bilder von Film- oder Sportstars auf der Deckelinnenseite von Eiscremepackungen.NewsTimes: Commemorative Dixie cups can be collectibles. Abgerufen am 28. April 2016. Aber es gab auch schon früh andere Sammelobjekte, z. B. Buttons oder Figuren in Cornflakespackungen.Kellogs Memorabilia and Collectibles. Abgerufen am 28. April 2016. 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.Andrei Andrejewitsch Markow: Wahrscheinlichkeitsrechnung. Teubner, Berlin, 1912, S. 101–108. Die konkrete mathematische Behandlung begann 1930 mit George Pólya, der das Problem aus Sicht des Herstellers darstellt:
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 WahrscheinlichkeitstheorieWilliam Feller: An introduction to probability theory and its applications. Band 1: Wiley, New York 1950, ISBN 0-471-25708-7, S. 225. 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 Sammelbildern zu erhalten, wenn er auf Tauschen und Nachkaufen verzichtet und jedes Bild einzeln kauft.Norbert Henze: Stochastik für Einsteiger. 10. Auflage. Springer Spektrum, Wiesbaden 2013, ISBN 978-3-658-03076-6, S. 192ff. Schon Pólya hatte die klassische Aufgabe definiert und wie folgt begründet:
Annahmen
Im klassischen Sammelbilderproblem werden die folgenden Annahmen getroffen:Niklas Braband, Sonja Braband und Malte Braband: Das Geheimnis der Fifimatic. Junge Wissenschaft, Nr. 114, 2017, S. 26–32.
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:
mini|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 mit dem -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 . Wir betrachten die Situation vor dem -ten Kauf, die das Album füllt: ist die Wahrscheinlichkeit einer Multinomialverteilung, dass beim -ten Kauf genau ein Bild fehlt, also jedes der 3 anderen Bilder schon mindestens einmal in der Sammlung vorhanden ist:
Die Summationsindizes , , , geben jeweils die Anzahl der Exemplare der einzelnen Bilder an. ist die Anzahl der Exemplare des 1. Bilds, 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 Darstellungen summiert, sodass die Summe dieser positiven ganzen Zahlen gleich ist. Entsprechendes gilt für die anderen Einzelwahrscheinlichkeiten.
Weil die 4 Einzelwahrscheinlichkeiten für gleich sind, kann man den obigen Ausdruck vereinfachen:
Es fehlt genau ein Bild, d. h. mit dem -ten Kauf wird unabhängig vom fehlenden Bild das Album mit der Wahrscheinlichkeit gefüllt. Daraus ergibt sich die gesuchte Wahrscheinlichkeit:
Dieses Resultat kann leicht auf ein Album mit Bildern verallgemeinert werden. Für gilt dann
Diese Verteilung ist eine Verallgemeinerung der negativen BinomialverteilungNegative Binomial Distribution, Marseken, Susan F., Surhone, Lambert M., Timpledon, Miriam T., Betascript Publishing, mit welcher man das Sammelbilderproblem für den Fall beschreiben kann.
Wenn ist, kann ein Album mit Bildern mit dem -ten Kauf offensichtlich nicht vervollständigt werden. Dann ist , weil dann die durch das Summenzeichen definierte Summe leer, also gleich 0 ist.
Um die Wahrscheinlichkeit, dass das Album nicht mit dem -ten Kauf, sondern nach Käufen, also spätestens mit dem -ten Kauf, vollständig ist, zu bestimmen, muss die Summe gebildet werden. Wegen für ist . Für ist auch die summierte Wahrscheinlichkeit offensichtlich gleich 0.
Die summierte Wahrscheinlichkeit kann auch einfacher mit der Formel
berechnet werden. Die Einzelwahrscheinlichkeit, mit dem -ten Kauf das Album mit Bildern zu vervollständigen, ist also gleichSteffi Kroll: Kombinatorik
Zahlenbeispiel Die Wahrscheinlichkeit, dass das 4er-Album nach 12 Käufen vollständig ist, beträgt
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:
Verallgemeinerung für m von N Bildern Diese Formel lässt sich verallgemeinern. Die Wahrscheinlichkeit, dass nach Käufen, also spätestens mit dem -ten Kauf, der Bilder mindestens einmal vorkommen, ist
Für den Spezialfall ergibt sich die oben erwähnte summierte Wahrscheinlichkeit . Die Wahrscheinlichkeit, dass schon nach Käufen der Bilder mindestens einmal vorkommen, ist nach Definition und die Wahrscheinlichkeit, dass beim nächsten Kauf kein neues Bild hinzukommt, ist . Die Differenz ist also die Einzelwahrscheinlichkeit, mit dem -ten Kauf zum ersten Mal verschiedene Bilder zu erhalten:
Päckchen
Sammelbilder werden in der Regel nicht einzeln, sondern in Päckchen mit 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,Wolfgang Stadje: The Collector’s Problem with Group Drawings. Advances in Applied Probability, Vol. 22, No. 4 (Dec., 1990), S. 866–882. aber der Vergleich der Ergebnisse ergibt, 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 die Päckchengröße vernachlässigt werden kann, denn die Wahrscheinlichkeit für das Ereignis , dass es in einem Päckchen mindestens ein mehrfach vorkommendes Sammelbild gibt, beträgt wie beim Geburtstagsparadoxon
Die Wahrscheinlichkeit für das Gegenereignis (siehe Ereignis (Wahrscheinlichkeitstheorie) - Komplement und Differenz), dass jedes Bild der Sammelbilderserie höchstens einmal im Päckchen vorkommt, beträgt
Wartezeit bis zum nächsten neuen Bild
Die Zufallsvariable ordnet jedem Ergebnis die Anzahl der Käufe zu, die gemacht werden müssen, um nach der -ten verschiedenen Karte wieder eine neue, von den bisher gekauften verschiedene -te Karte zu bekommen. Dies entspricht der Wartezeit bis zum nächsten neuen Bild.Elke Warmuth, Walter Warmuth: Elementare Wahrscheinlichkeitsrechnung: Vom Umgang mit dem Zufall. Vieweg + Teubner 1998, ISBN 978-3-519-00225-3, S. 128–129. mini|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 . Beim Kauf des zweiten Bildes ist sie . Diese Zufallsvariable ist geometrisch verteilt. Allgemein ergibt sich:
Als Erwartungswert für ergibt sich:
Dies bedeutet insbesondere, dass man, um das letzte fehlende Bild der Sammlung zu erhalten, im Mittel 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