Ostatni brakujący element kolekcji może zająć więcej prób niż zebranie większości
W problemie kolekcjonera kuponów za każdym razem losujemy jeden z n typów z jednakowym prawdopodobieństwem i pytamy, ile losowań potrzeba średnio, aby zobaczyć wszystkie typy. Odpowiedź to nH_n = n(1+1/2+…+1/n), czyli w przybliżeniu n ln n. Początek idzie szybko: prawie każdy los daje coś nowego. Końcówka zwalnia dramatycznie, bo gdy brakuje jednego typu, szansa sukcesu w pojedynczej próbie wynosi tylko 1/n, więc na sam ostatni brakujący element czeka się średnio n kolejnych losowań. Największym kosztem okazuje się właśnie pogoń za ostatnimi brakującymi typami.
Pierwszy kupon jest darmowy, ostatni kosztowny
Na początku każdy wylosowany typ jest nowy. Gdy mamy już k różnych typów, szansa, że następny los da nowy, wynosi (n-k)/n. Oczekiwany czas czekania na kolejny nowy typ jest więc odwrotnością tej szansy: n/(n-k). Kolejne etapy kosztują średnio 1, n/(n-1), n/(n-2), …, n prób. Ich suma tworzy n razy liczbę harmoniczną H_n.
Dlaczego n ln n zamiast po prostu n
Gdyby każdy los zawsze dawał nowy typ, wystarczyłoby dokładnie n prób. Powtórzenia stają się jednak coraz bardziej dominujące. Suma 1+1/2+…+1/n rośnie mniej więcej jak ln n, dlatego pełna kolekcja wymaga około n ln n losowań. Ten dodatkowy czynnik logarytmiczny jest ceną za końcówkę procesu, w której coraz trudniej trafić coś jeszcze nieobserwowanego.
Przykład z kostką
Dla sześciu równoprawdopodobnych ścian kostki oczekiwany czas zobaczenia wszystkich wyników wynosi 6H_6 = 6(1+1/2+1/3+1/4+1/5+1/6)=14,7 rzutu. To znacznie więcej niż sześć. Intuicja często skupia się na tym, że „mamy tylko sześć możliwości”, ale problemem nie jest liczba możliwości sama w sobie — tylko rosnąca liczba powtórek, gdy większość została już zebrana.
Końcówka ma nieproporcjonalny wpływ
Gdy brakuje tylko jednego typu, pojedynczy etap ma średni czas n. Gdy brakuje dwóch, średni czas do zdobycia jednego z nich to n/2. Ostatnie kilka składników szeregu harmonicznego odpowiada więc za dużą część całkowitego oczekiwania. To częsty motyw w procesach losowych: dojście do 90% celu może być łatwe, a usunięcie ostatnich kilku braków dominować koszt.
Od naklejek do informatyki
Model pojawia się wszędzie tam, gdzie próbkujemy losowo z wielu kategorii i chcemy zobaczyć wszystkie: testowanie stanów systemu, zbieranie próbek, haszowanie, epidemiologia czy analiza różnorodności. Nie każde zastosowanie spełnia oczywiście założenie równych i niezależnych typów, ale podstawowy problem pokazuje, dlaczego „pokrycie wszystkiego” może być znacznie trudniejsze niż zebranie dużej większości.
Średnia nie jest gwarancją
Wartość nH_n jest wartością oczekiwaną, nie terminem, w którym kolekcja „powinna” być gotowa. Rzeczywisty czas ma rozkład i może istotnie odbiegać od średniej. Mimo to wzór bardzo dobrze ujawnia strukturę problemu: kolejne brakujące typy tworzą etapy o coraz mniejszym prawdopodobieństwie sukcesu. To mechanizm, a nie sama liczba n ln n, jest najciekawszą częścią tego rezultatu.
Połowa kolekcji i pełna kolekcja to różne skale problemu
Zdobycie dużej części typów jest relatywnie łatwe. Jeśli mamy k różnych kuponów, szansa nowego w kolejnym losie wynosi (n−k)/n. Dopóki brakuje stały procent kolekcji, ta szansa pozostaje rzędu stałej i kolejne nowe typy pojawiają się regularnie. Dopiero gdy liczba brakujących spada do kilku, prawdopodobieństwo sukcesu staje się rzędu 1/n. To dlatego przejście od „prawie wszystko” do „wszystko” zmienia skalę czasu. W algorytmach podobny efekt ostrzega, że testy oparte na losowym próbkowaniu mogą bardzo szybko pokryć większość stanów, ale potrzebować nieproporcjonalnie dużo czasu, aby uzyskać pełne pokrycie.