🎟️ Sammelbilderproblem — Erwartete Ziehungen, um alle zu sammeln

Die exakte Erwartung ist E[T] = N · H_N, wobei H_N die N-te harmonische Zahl ist (die Summe 1 + 1/2 + 1/3 + … + 1/N). Da H_N wie ln(N) + γ wächst (mit der Euler-Mascheroni-Konstante γ ≈ 0,5772), vereinfacht sich dies zur bekannten Näherung E[T] ≈ N · ln(N) + γ · N. Bei N = 20 Sammelbildern beträgt die erwartete Anzahl der Ziehungen beispielsweise etwa 71,9.

Nutzen Sie den N-Schieberegler, um die Anzahl der verschiedenen Sammelbildtypen zu wählen (2–50), und klicken Sie dann auf Lauf abspielen, um einen animierten Sammelvorgang zu beobachten: Das Raster leuchtet für jeden Typ auf, sobald er zum ersten Mal gezogen wird, und die Abdeckungskurve zeigt den gesammelten Anteil über die Zeit. Klicken Sie auf 100 Versuche starten, um viele Vervollständigungen sofort im Stapel zu simulieren und das Histogramm aufzubauen, das sich um die grüne E[T]-Linie häufen sollte. Der Geschwindigkeitsregler steuert, wie viele Ziehungen pro Animationsbild verarbeitet werden.

Wenn Sie bereits k von N Typen besitzen, trifft jede neue Ziehung einen fehlenden Typ nur mit Wahrscheinlichkeit (N − k) / N. Nähert sich k dem Wert N, schrumpft diese Wahrscheinlichkeit gegen 1/N, sodass jedes neue einzigartige Sammelbild viel schwerer zu finden ist. Die erwartete Anzahl von Ziehungen, um von k zu k+1 zu gelangen, ist N / (N − k), was unbegrenzt wächst, wenn k → N. Dieser Effekt des „abnehmenden Ertrags“ flacht die Abdeckungskurve ab und erzeugt den langen rechten Ausläufer im Histogramm der Vervollständigungszeit.

Die Herleitung nutzt die Linearität des Erwartungswerts. Nach dem Sammeln von k verschiedenen Sammelbildern ist die Wartezeit bis zum nächsten neuen geometrisch verteilt mit Erfolgswahrscheinlichkeit p = (N − k) / N, sodass ihr Mittelwert N / (N − k) ist. Summiert man über k = 0, 1, …, N−1, ergibt sich E[T] = N/N + N/(N−1) + … + N/1 = N · (1 + 1/2 + … + 1/N) = N · H_N. Auch die Varianz ist bekannt: Var[T] = N² · Σ(1/k²) ≈ N² · π²/6 für große N.

Panini-Sammelalben sind das bekannteste Beispiel: Ein WM-2018-Album hatte 682 Sticker, und Sammler benötigten durchschnittlich etwa 4.832 Sticker-Käufe, um es zu vervollständigen (bei Packungen zu 5 Stück). In der Softwareentwicklung muss zufälliges Fuzzing genug Testeingaben erzeugen, um jeden Zweig zu erreichen; bei N Zweigen wächst der erwartete Aufwand als N · ln(N). Netzwerkprotokolle, die zufällige IDs vergeben, stehen vor demselben dualen Geburtstagsproblem: wie schnell eine Kollision auftritt versus wie viele IDs nötig sind, um ein Set abzudecken.

Ja — das wäre nur wahr, wenn man garantieren könnte, dass keine Wiederholungen auftreten, wie beim Ziehen ohne Zurücklegen. Mit Zurücklegen (unabhängige zufällige Ziehungen) sind Duplikate unvermeidlich. Die erwartete Gesamtzahl wächst als N · ln(N), nicht als N, weil die letzten paar Sammelbilder jeweils viele wiederholte Ziehungen erfordern, bevor der fehlende Typ erscheint. Für N = 50 beträgt die erwartete Anzahl der Ziehungen etwa 225, nicht 50. Das Histogramm zeigt auch einen langen rechten Ausläufer, was bedeutet, dass gelegentlich viel mehr als der Durchschnitt benötigt werden.

Das Problem hat Wurzeln in der Kombinatorik des 18. Jahrhunderts. Abraham de Moivre untersuchte verwandte Belegungsprobleme in seinem Werk „The Doctrine of Chances“ von 1718. Die moderne Formulierung und die Lösung mit harmonischen Zahlen wurden durch Wahrscheinlichkeitslehrbücher Mitte des 20. Jahrhunderts bekannt. Der Name „Sammelbilderproblem“ wurde populär, als physische Sammelbilder-Sets und Sammelkarten im frühen 20. Jahrhundert zu gängigen Konsumgütern wurden, was eine natürliche Analogie zum abstrakten Belegungsproblem darstellt.

Das Sammelbilderproblem ist eng mit dem Geburtstagsproblem verwandt (das fragt, wann die erste Kollision auftritt, statt wann alle Plätze gefüllt sind), Belegungsproblemen in der Kombinatorik und der Analyse zufälliger Hashfunktionen. Es ist das Duale des Sammelns: das eine fragt nach der ersten Wiederholung, das andere nach vollständiger Abdeckung. Verwandte Simulationen umfassen das Geburtstagsparadoxon, Abdeckungsprobleme bei Zufallswanderungen und Monte-Carlo-Integration, die alle Wartezeiten in Zufallsprozessen betreffen.

Im Softwaretest quantifiziert das Problem, wie viele zufällige Testeingaben nötig sind, um vollständige Codepfad-Abdeckung zu erreichen — ein Maßstab für zufälliges (Fuzzing) versus systematisches Testgenerieren. In verteilten Systemen modelliert es, wie viele Broadcast-Nachrichten nötig sind, bevor jeder Knoten in einem Netzwerk mindestens eine erhalten hat. Load-Balancer und Hashtabellen verwenden verwandte Belegungsanalysen, um vorherzusagen, wann alle Buckets nicht-leer sind. Die N · ln(N)-Schranke erscheint auch in randomisierten Algorithmen für Mengen-Überdeckungsprobleme.

Bei ungleichen Wahrscheinlichkeiten der Sammelbildtypen gilt die Formel mit den harmonischen Zahlen nicht mehr. Die erwartete Vervollständigungszeit wird stattdessen vom seltensten Sammelbild bestimmt: Hat der unwahrscheinlichste Typ die Wahrscheinlichkeit p_min, wächst die erwartete Anzahl der Ziehungen mindestens so schnell wie 1/p_min. Dies wird unter dem „nicht-uniformen Sammelbilderproblem“ untersucht und kann dramatisch schlechter sein als der uniforme Fall. Kommen Sammelbilder in Packungen (wie bei Aufkleberalben), wird das Problem zu einer Variante mit korrelierten Ziehungen, die über erzeugende Funktionen und Simulation analysiert wird und zeigt, dass Packungsstrukturen die erwarteten Gesamtkosten je nach Packungsgröße und Überlappungsregeln leicht erhöhen oder verringern können.