Werfen Sie einen fairen Würfel, bis alle sechs Seiten erschienen sind; die erwartete Zahl der Würfe ist 14.7 (erster und zweiter Link, dieselbe Summe faktorisiert und ausmultipliziert). Die Überlegung ist eine Zeile: Solange k Seiten noch fehlen, hat jeder Wurf die Wahrscheinlichkeit k/6, neu zu sein, das Warten auf die nächste neue Seite ist also ein geometrischer Versuch mit Erwartungswert 6/k, und die Summe ist 6/1 + 6/2 + 6/3 + 6/4 + 6/5 + 6/6. Der dritte Link führt das Problem mit fünf Coupons aus und erhält 11.416666666667. Der vierte, 6⁶ = 46656, ist die Zahl der möglichen Folgen von sechs Würfen – das falsche Werkzeug für diese Frage, aber der richtige Nenner für eine verwandte: Die Chance, dass die ersten sechs Würfe schon alle sechs Seiten zeigen, ist 6!/46 656, kaum über 1.5 Prozent.
Die Form der Antwort zählt mehr als die Zahl: n·H_n wächst wie n ln n, die Kosten liegen also fast ganz in den letzten paar Coupons. Hundert von etwas kosten 100·H₁₀₀ = 518.7 Versuche, wovon der letzte allein hundert ausmacht; der erste ist ein einziger Wurf. Diese Asymmetrie ist der Grund, warum Gratis-Token-Systeme sich anfühlen, als stockten sie am Ende, warum die letzte Figur in einem Satz Sammelkarten die teure ist und warum randomisierte Algorithmen, die jeden Wert sehen müssen, denselben harmonischen Preis zahlen. Die Streuung geht in dieselbe Richtung – die Verteilung der umskalierten Wartezeit nähert sich dem Gumbel-Gesetz, das einen langen rechten Schwanz hat, der unglückliche Sammler ist also um einen großen und vorhersagbaren Betrag unglücklich.
Antwort
14.7
So lesen Sie sie
Sechs mal die sechste harmonische Zahl. Der zweite Link ist dieselbe Summe Glied für Glied, der dritte fünf Coupons statt sechs, der vierte alle Folgen von sechs Würfen.
Quelle
the coupon collector's problem in Feller, 'An Introduction to Probability Theory and Its Applications', volume 1 (1950), where it is posed as the baseball-card question; the expectation n·H_n and the Gumbel limit of the rescaled waiting time are standard
Im Rechner durchrechnen
Diese Links öffnen den passenden Rechner mit den bereits eingegebenen Zahlen dieser Aufgabe. Die Zeile darüber ist das, was der Bildschirm anzeigen sollte – prüfen Sie selbst.