Problem zbieracza kuponów: Dlaczego potrzeba N ln(N) prób do ukończenia

Problem

Załóżmy, że firma z rodzaju cereali umieszcza w każdym opakowaniu jeden z N różnych kuponów kolekcjonerskich, wybrany losowo i niezależnie za każdym razem. Ile opakowań należy kupić, aby zebrać wszystkie N? Jest to problem zbieracza kuponów, jedno z najstarszych instrukcyjnych pytań w prawdopodobieństwie dyskretnym, które pojawia się w testowaniu oprogramowania (ile losowych wejść przed uruchomieniem każdego gałęzi), sekwencjonowaniu genomu i szacunkach obciążenia tabeli hash.

Kluczem jest podzielenie procesu na N etapów. Etap i rozpoczyna się w momencie, gdy posiadasz dokładnie i-1 różnych kuponów, a kończy w momencie, gdy losujesz swój i-ty różny kupon. Podczas etapu i, puskiel jest 'sukcesem' (nowy kupon) z prawdopodobieństwem p_i = (N-i+1)/N, ponieważ N-i+1 typów nadal brakuje.

Dlaczego odpowiedź wykorzystuje harmoniczny ciąg liczbowy

Liczba prób w każdym etapie i jest zmienną losową geometryczną o prawdopodobieństwie sukcesu p_i, więc jej wartość oczekiwana wynosi 1/p_i = N/(N-i+1). Sumując po wszystkich etapach N i ponownie indeksując k = N-i+1, otrzymujemy dokładną oczekiwaną całkowitą liczbę:

E[T] = ∑_(i=1..N) N / (N - i + 1) = N * ∑_(k=1..N) 1/k = N * H_N, gdzie H_N = 1 + 1/2 + 1/3 + ... + 1/N H_N, czyli N-ty harmoniczny ciąg liczbowy, nie ma zamkniętej postaci, ale rośnie podobnie jak ln N + γ (stała Eulera-Mascheroniego, ≈ 0.5772). Zatem oczekiwana liczba pudełek wynosi E[T] ≈ N * ln N + γN + 1/2 - dla N=50 jest to około 225 pudełek do zebrania zestawu 50 elementów, co stanowi w przybliżeniu 4.5 razy więcej niż liczba różnych przedmiotów.

E[T] = ∑_(i=1..N) N / (N - i + 1)
     = N · ∑_(k=1..N) 1/k
     = N · H_N,   where H_N = 1 + 1/2 + 1/3 + ... + 1/N

Zmienność i ogon

Ostatni kupon dominuje w zmienności: jego etap ma prawdopodobieństwo sukcesu 1/N, więc oczekiwane czekanie na niego zajmuje N prób i ma zmienność zbliżoną do N². Całkowita zmienność T asymptotycznie wynosi π²/6 * N², co oznacza, że odchylenie standardowe skaluje się wraz z samym N, a nie z √N, jak w przypadku większości sum niezależnych wyrazów – bezpośredni rezultat faktu, że ostatnie kilka kuponów jest dysproporcjonalnie rzadkie i trudne do znalezienia.

Dlatego też histogram czasu ukończenia w demo ma długi ogon prawy, mimo że średnia jest dobrze przewidywana przez N * H_N: niewielka, ale realna część przebiegów kończy się niepowodzeniem na ostatnim kuponie i zajmuje znacznie dłużej niż średnio.

Dwukomorowy Dixie Cup i Uściślone Rozwiązania Erdosa i Renyi

Powiązane pytanie – ile prób wykonanych trzeba dokonać, aby posiadać m kopii każdego kuponu (nie tylko jednego) – to problem dwukomorowego Dixie Cupa, rozwiązany przez Newmana i Sheppa; jego wartość oczekiwana wynosi N ln N + (m-1) N ln(ln N) + O(N) dla ustalonego m. Erdos i Renyi później uściśliły wynik dla pojedynczej kopii, sformułując go jako stwierdzenie o koncentracji: T/(N ln N) zbiega się z prawdopodobieństwem do 1, a wahania wokół N ln N zbliżają się do rozkładu Gumbela – tej samej ekstremalnej-wartościowej zależności, która rządzi maksimum wielu niezależnych zmiennych losowych, ponieważ zebranie pełnego zestawu jest w zasadzie wyścigiem o znalezienie pojedynczego najwolniej pojawiającego się kupona.

Symulacja

Funkcja `trial(N)` działa zgodnie z tym schematem: const seen = new Set(); let draws = 0; while (seen.size < N) { seen.add(Math.floor(Math.random() * N)); draws++; } return draws;

Symulacja na tej stronie uruchamia dokładnie ten pętlę tysiące razy na sekundę, wypełniając dynamiczną siatkę za każdym razem, gdy pojawia się nowy typ kuponu, a następnie nakładając na nią bieżącą średnią empiryczną oraz prognozy analityczne (dokładnie `N * H_N` i przybliżenie `N * ln N + γN`), dzięki czemu można obserwować, jak oszacowanie Monte Carlo zbliża się do wartości rzeczywistej.

function trial(N) {
  const seen = new Set();
  let draws = 0;
  while (seen.size < N) {
    seen.add(Math.floor(Math.random() * N));
    draws++;
  }
  return draws;
}
// average many trials(N) and compare against N * H_N

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Coupon Collector i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.