Rzucaj uczciwą kostką, aż pojawi się wszystkie sześć ścianek; oczekiwana liczba rzutów to 14.7 (pierwszy i drugi link, ta sama suma w postaci iloczynowej i rozwiniętej). Rozumowanie mieści się w jednym wierszu: dopóki brakuje k ścianek, każdy rzut ma prawdopodobieństwo k/6, że będzie nowy, więc oczekiwanie na następną nową ściankę to próba geometryczna o wartości oczekiwanej 6/k, a suma to 6/1 + 6/2 + 6/3 + 6/4 + 6/5 + 6/6. Trzeci link rozwiązuje problem dla pięciu kuponów i daje 11.416666666667. Czwarty, 6⁶ = 46656, to liczba możliwych ciągów sześciu rzutów — niewłaściwe narzędzie do tego pytania, ale właściwy mianownik do pokrewnego: szansa, że pierwsze sześć rzutów pokaże już wszystkie sześć ścianek, to 6!/46 656, czyli ledwie ponad 1.5 procent.
Kształt odpowiedzi znaczy więcej niż sama liczba: n·H_n rośnie jak n ln n, więc koszt prawie w całości siedzi w ostatnich kilku kuponach. Sto czegoś kosztuje 100·H₁₀₀ = 518.7 prób, z czego na ostatnią przypada sto; pierwsza to jeden rzut. Ta asymetria sprawia, że programy z darmowymi żetonami zdają się zacinać na końcu, że ostatnia figurka w zestawie kart kolekcjonerskich jest tą drogą, i że algorytmy losowe, które muszą zobaczyć każdą wartość, płacą tę samą harmoniczną cenę. Rozrzut idzie w tę samą stronę — rozkład przeskalowanego czasu oczekiwania zbliża się do prawa Gumbela, które ma długi prawy ogon, więc pechowy kolekcjoner ma pecha o wielką i przewidywalną kwotę.
Odpowiedź
14.7
Jak to czytać
Sześciokrotność szóstej liczby harmonicznej. Drugi link to ta sama suma wyraz po wyrazie, trzeci pięć kuponów zamiast sześciu, czwarty wszystkie ciągi sześciu rzutów.
Źródło
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
Rozwiąż w kalkulatorze
Te linki otwierają właściwy kalkulator z już wpisanymi liczbami tego zadania. Powyższa linia to to, co powinien pokazać ekran — sprawdź sam.