Das Coupon Collector’s Problem (CCP)
Beim Coupon Collector’s Problem (CCP) geht es darum, eine Sammlung von n verschiedenen Objekten (z. B. Sticker, Sammelkarten, Codes) zufällig zu vervollständigen. Jedes Mal erhält man ein neues zufälliges Objekt, wobei Wiederholungen möglich sind. Die Frage lautet:
Wie viele Ziehungen sind im Durchschnitt nötig, um die Sammlung zu vervollständigen?
Unser Tool simuliert dieses Problem und ermöglicht verschiedene Einstellungen:
- Anzahl der Objekte (k) → Wie viele verschiedene Sammelobjekte gibt es?
- Anzahl der Durchläufe (N) → Wie oft wird die Simulation durchgeführt?
- Maximal fehlende Karten (f) → Wird die Sammlung schon als „vollständig“ betrachtet, wenn noch f Sticker fehlen? (Hintergrund: oft kann man einige letzte Sticker zu einem teuren Preis gezielt erwerben)
- Päckchengröße (p) → Kann man nur mehrere Sticker auf einmal ziehen?
- Sticker einzigartig in Päckchen? → Enthält jedes Päckchen nur verschiedene Sticker?
- Zusätzlich bietet das Tool mathematische Näherungen (Normal/Gumbel-Verteilung) und ermöglicht den Vergleich der Simulation mit der Theorie.
Aufgaben – von einfach bis forschungsnah
1) Basissimulation
Wähle k = 100 (100 verschiedene Sticker).
Führe die Simulation mit N = 10.000 Durchläufen durch.
Notiere den Mittelwert der benötigten Ziehungen und das 90%-Quantil.
Vergleiche die Simulation mit der Gumbel-Näherung: Wie genau ist sie?
Wie sehr schwanken die Werte, wenn man das Experiment mehrmals wiederholt?
2) Einfluss der Anzahl der Objekte
Simuliere für k = 10, 50, 100, 250, 1000.
Wie verändert sich der Mittelwert der benötigten Ziehungen? Kann man einen einfachen Zusammenhang erkennen?
Was bewirken Änderungen an der Zahl der Durchläufe N?
3) Vervollständigung mit fehlenden Karten
Setze k = 100 und f = 10.
Wie viele Ziehungen benötigt man jetzt nur noch, um 90 statt 100 Sticker zu sammeln?
Wie stark sinkt die Anzahl der Ziehungen? Probiere einige weitere Werte aus!
Mittelschwere Aufgaben (4–9)
4) Sammeln in Päckchen
Setze k = 100 und vergleiche p = 1, p = 5 und p = 25.
Wie verändert sich der Mittelwert?
Wieso hilft p > 1 nicht so stark, wie man erwarten könnte?
5) Einzigartige Sticker in Päckchen
Simuliere mit k = 50 und p = 5, einmal mit und einmal ohne "Sticker einzigartig".
Welche Auswirkungen hat das auf die Sammeldauer? Experimentiere mit weiteren Werten!
6) Theoretische Normalverteilung vs. Gumbel
Wähle k = 250 und N = 10000, vergleiche die Simulation mit beiden Näherungen.
Welche Verteilung passt besser?
Kannst du einen Grund dafür angeben?
Wie sieht das aus, wenn man nur 80% (50%) sammelt?
7) Intervallwahrscheinlichkeiten
Wähle k = 100 und bestimme experimentell die Wahrscheinlichkeit für 800 ≤ X ≤ 900.
Vergleiche mit den Näherungen (Normal/Gumbel).
8) Einfluss der Stickeranzahl auf das 90%-Quantil
Simuliere k = 100, 200, 500, 1000 und notiere das 90%-Quantil.
Formuliere eine Faustregel zur Abschätzung des 90%-Quantils.
9) Einfluss der maximal fehlenden Karten (f)
Setze k = 100 und bestimme das 90%-Quantil für f = 0, 5, 10, 20.
Wie stark sinkt der Mittelwert / das 90%-Quantil im Vergleich?
Wenn eine Sammelkarte 10ct kostet, wieviel könnte man jeweils für eine auswählbare Karte bezahlen um noch zu sparen?
Schwierige Aufgaben (10–12)
10) Simulation großer Sammlungen
Wähle k = 250, 500, 1000 und simuliere mit N = 100.000.
Überprüfe, ob die Näherungen gut passen.
11) Reale Welt
Recherchiere reale Sammelalbum-Daten (z. B. Panini-Sticker).
Versuche, die Verteilung echter Sammler nachzubauen.
Gibt es einen Unterschied zwischen realen und idealen Bedingungen?
12) Export
Über die Export-Funktion kannst du die Daten einzelner Simulationen exportieren.
Diese kannst du in Desmos einbinden.
Informiere die über die Gumbel-Funktion und stelle eigene Versuche an.
Findest du bessere Parameter als die der Simulation?
Diese Simulation wurde in meiner Freizeit entwickelt. Dank KI-Unterstützung und einiger Vorarbeit war das in etwa drei Tagen zu schaffen.
Viel Spaß beim Ausprobieren!
Februar 2025, Martin Resch