Sammelbilderproblem

Grundidee und klassische Annahmen

Das Sammelbilderproblem fragt, wie viele zufällig gekaufte Bilder nötig sind, um eine Serie vollständig zu sammeln. Es ist mathematisch wichtig, weil die benötigte Zahl wegen der vielen Doppelten deutlich größer als die Zahl n der verschiedenen Bilder sein kann. Ohne Tauschen oder Nachkaufen ist besonders das letzte fehlende Bild teuer: Im Mittel müssen dafür noch n Bilder gekauft werden.

Im klassischen Modell kauft ein Einzelsammler Bilder einzeln. Es gelten drei Annahmen: A1: Bilder werden zufällig auf Päckchen verteilt. A2: Alle Bilder kommen gleich häufig vor. A3: In einem Päckchen kommt kein Bild doppelt vor. Mathematisch ist dies ein Urnenmodell mit Zurücklegen: Jede gezogene Zahl aus {1,2,…,n} steht für ein Bild und ist diskret gleichverteilt. Gesucht ist die Zahl der Ziehungen, bis jede Zahl mindestens einmal vorkam.

Die Annahmen sind in der Praxis nicht stets erfüllt. Bei Trading Card Games unterscheiden sich die Häufigkeiten einzelner Karten stark. Untersuchungen fanden zudem systematische Muster beim Verpacken von Topps- und Panini-Bildern. Für die deutsche Ausgabe des WM-Albums 2014 ließen sich laut Christian Hesse die festgestellten Unterschiede in 8,33 Millionen Einträgen nicht allein durch Zufall erklären; bei der separat produzierten Schweizer Edition waren 2,36 Millionen registrierte Sticker gleichmäßig häufig. Die Verpackungsmuster bei Panini wirken sich jedoch nicht nachteilig für Sammler aus.

Wartezeiten, Erwartungswert und Streuung

Sei Xᵢ die Zahl der Käufe, die nach dem Erhalt von i−1 verschiedenen Bildern bis zum nächsten neuen, i-ten Bild nötig ist. Xᵢ ist geometrisch verteilt. Es gilt

P(Xᵢ = k) = ((i−1)/n)^(k−1) · ((n−i+1)/n)

und E(Xᵢ) = n/(n−i+1). Beim ersten Kauf erhält man sicher ein neues Bild; für das letzte fehlende Bild beträgt die mittlere Wartezeit n Käufe.

Die Gesamtzahl X aller nötigen Käufe ist X = ∑ᵢ₌₁ⁿ Xᵢ. Da Erwartungswerte addiert werden können, gilt

E(X) = n · Hₙ, mit Hₙ = ∑ₖ₌₁ⁿ 1/k.

Hₙ ist die n-te Partialsumme der harmonischen Reihe. Für große n gilt Hₙ ≈ ln(n) + γ mit der Euler-Mascheroni-Konstante γ ≈ 0,577. Daher ist E(X) ≈ n · (ln(n) + 0,577). Will man nur m von n verschiedenen Bildern erhalten, lautet der Erwartungswert E(Xₙ,ₘ) = n · (Hₙ − Hₙ₋ₘ) ≈ n · (ln(n) − ln(n−m)).

Die Varianz, also ein Maß für die Streuung der benötigten Käufe, ist

Var(X) = n² · ∑ᵢ₌₁ⁿ 1/i² − n · Hₙ < n² · π²/6 − n · ln(n) − n · γ − O(1).

Die Standardabweichung wächst stark mit n. Deshalb kann die tatsächlich benötigte Zahl erheblich vom Mittelwert abweichen.

Wahrscheinlichkeiten und verschiedene Bilder

Die Wahrscheinlichkeit, ein Album mit N Bildern spätestens nach k Käufen vollständig zu haben, ist

Pₙ,ₖ = ∑ᵢ₌₁ᴺ (−1)^(N−i) · (N über i) · (i/N)^k.

Die Wahrscheinlichkeit, es genau mit dem k-ten Kauf zu vervollständigen, ist Pₙ,ₖ − Pₙ,ₖ₋₁. Für k < N ist sie 0, da nicht mehr verschiedene Bilder gesammelt werden können als Käufe gemacht wurden. Für ein 4er-Album gilt P₄,₁₂ ≈ 0,875: Nach 12 Käufen ist es mit etwa 87,5 % Wahrscheinlichkeit vollständig. Die Wahrscheinlichkeit, dass gerade der 12. Kauf das Album vervollständigt, beträgt etwa 0,0408.

Allgemeiner beschreibt Pₙ,ₖ,ₘ die Wahrscheinlichkeit, nach k Käufen mindestens einmal genau m der N Bilder erhalten zu haben:

Pₙ,ₖ,ₘ = (N über m) · ∑ᵢ₌₁ᵐ (−1)^(m−i) · (m über i) · (i/N)^k.

Nach k Käufen ist die Wahrscheinlichkeit, ein bestimmtes Bild zu besitzen, Pₖ = 1 − ((n−1)/n)^k. Die mittlere Zahl Yₖ verschiedener Bilder lautet daher E(Yₖ) = n · (1 − ((n−1)/n)^k).

Päckchen, Nachkaufen und Tauschen

Päckchen enthalten meist s Bilder, wobei der Hersteller innerhalb eines Päckchens keine Doppelten garantiert. Ist s klein gegenüber n, ist der Einfluss von Päckchen auf das klassische Ergebnis gering. Falls Bilder zufällig gewählt würden, wäre die Wahrscheinlichkeit für mindestens ein doppeltes Bild im Päckchen

P_M = 1 − n!/(n^s · (n−s)!).

Gezieltes Nachkaufen lohnt sich bei noch x fehlenden Bildern zum Preis k pro Bild, wenn b · n/x > k gilt; b ist dabei der normale Preis eines Bildes. Kann man K Bilder nachkaufen, ist es am vorteilhaftesten, sie erst am Ende zu kaufen. Die erwartete Zahl gekaufter Bilder sinkt auf

S = n · (Hₙ − H_K) + K ≈ n · ln(n/K) + K.

Beim fairen Tauschen tauschen m kooperierende Sammler jeweils ein Bild gegen ein anderes, bis alle Alben gefüllt sind. Eine geschlossene Lösung gibt es dafür nicht. Für feste m gilt asymptotisch Sₘ = n · ln(n) + (m−1) · n · ln(ln(n)) + O(n). Der erste Sammler benötigt im Mittel n · ln(n) Karten, jeder weitere nur n · ln(ln(n)) zusätzlich. Für zwei Tauschpartner betragen die Kosten ungefähr 60 % der Kosten eines Einzelsammlers.

Als optimierte Strategie wird empfohlen: ein Display kaufen, weitere Päckchen kaufen und möglichst viel tauschen, dann die maximal erlaubte Zahl fehlender Bilder beim Hersteller nachkaufen. Bei D Bildern im Display, davon d verschiedenen, und K Nachkaufbildern gilt S = n · (Hₙ₋d − H_K) + D + K. Können T fehlende Bilder getauscht werden, mit t = T/(n−d−K), gilt näherungsweise S ≈ n · ln((n−d)/K)^(1−t) + D + K.

Allgemeiner Fall und Beispiele

Im allgemeinen Sammelbilderproblem haben Bilder unterschiedliche Wahrscheinlichkeiten pᵢ. Der Mittelwert der benötigten Karten ohne Nachkaufen ist dann

S = ∫₀^∞ (1 − ∏ᵢ₌₁ⁿ (1 − e^(−pᵢt))) dt.

Diese Formel ist besonders für Trading Card Games mit unterschiedlich seltenen Karten relevant.

Ein Würfel veranschaulicht das klassische Problem mit n = 6: Um jede Augenzahl mindestens einmal zu erhalten, braucht man durchschnittlich S = 6 · H₆ = 147/10 = 14,7 Würfe. Bei 150 gleich häufigen Pokémon-Motiven wären für einen Einzelsammler ohne Nachkaufen im Mittel etwa 839 Karten nötig. Wenn 30 von 150 Karten halb so häufig vorkommen, steigt der Mittelwert auf etwa 1213; bei 10 Karten, die zehnmal seltener vorkommen, auf etwa 4372.

Beim Panini-Album zur Fußball-Europameisterschaft 2016 mit 680 Bildern gilt H₆₈₀ ≈ 7,1. Ohne Tauschen und Nachkaufen sind im Mittel etwa 4828 Bilder beziehungsweise 965,5 Päckchen nötig, bei 14 Cent pro Bild rund 676 €. Die Standardabweichung beträgt 869 Bilder; in etwa 95,4 % der Fälle werden zwischen 3090 und 6566 Bilder benötigt. Mit 50 nachgekauften Bildern sinkt der Mittelwert auf ungefähr 1768 regulär gekaufte plus 50 Nachkaufkarten und etwa 257 €. Das Beispiel zeigt, warum Tauschen und Nachkaufen die Kosten stark senken können.