Задача про Збирача Купонів: Чому для Завершення Потрібно N ln N Витяжок

Задача

Припустимо, бренд снеків кладе один із N різних колекційних купонів у кожну коробку, випадково вибираючи кожен раз, і незалежно. Скільки коробок потрібно купити, щоб зібрати всі N? Це задача про збирача купонів, одна з найдавніших навчальних задач дискретної ймовірності, яка зустрічається в тестуванні програмного забезпечення (скільки випадкових входів потрібно, перш ніж спрацює кожен гілку), секвенуванні геному та оцінці завантаження хеш-таблиць.

Ключ до розв’язання полягає у розділенні процесу на N етапів. Етап i починається в момент, коли ви володієте рівно i-1 різними купонами, і закінчується в момент, коли ви витягуєте свій i-тий унікальний купон. Під час етапу i, витяг є «успіхом» (новий купон) з ймовірністю p_i = (N - i + 1)/N, оскільки N - i + 1 типів ще відсутні.

Чому відповідь пов’язана з гармонічним числом

Кількість витяжок на кожному етапі i є геометричною випадковою величиною із ймовірністю успіху p_i, тому її очікуване значення дорівнює 1/p_i = N/(N-i+1). Підсумовуючи по всіх N етапах і переіндексуючи k = N-i+1, отримуємо точне очікуване загальне число:

E[T] = ∑_(i=1..N) N / (N - i + 1) = N ∑_(k=1..N) 1/k = N * H_N, де H_N = 1 + 1/2 + 1/3 + ... + 1/N H_N, гармонічне число N-го порядку, не має замкненої форми, але зростає приблизно як ln N + &гама (константа Ейлера-Масчероні, ≈ 0.5772). Таким чином, очікувана кількість ящиків становить E[T] ≈ N*ln N + &гама*N + 1/2 - для N=50 це приблизно 225 ящиків для завершення набору з 50 елементів, що приблизно в 4.5 рази більше за кількість відмінних предметів.

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

Варіація та хвіст

Останній купон домінує у варіації: його ймовірність успіху становить 1/N, тому очікуване час для отримання лише цього купона становить N витяжок і має дисперсію, близьку до N². Загальна дисперсія T асимптотично дорівнює π²/6 * N², що означає, що стандартне відхилення масштабується з N, а не з √N, як у більшості сум незалежних членів – безпосередній результат того, що останні кілька купонів є непропорційно рідкісними та повільно знаходяться.

Це пояснює, чому гістограма часу завершення в демо має довгий правий хвіст, незважаючи на те, що середнє значення добре прогнозується N * H_N: невелика, але реальна частка випадків потрапляє в несприятливу ситуацію щодо останнього купона та займає значно більше часу, ніж у середньому.

Двойка з двох Dixie cup та удосконалення Ердоша і Рені

Пов'язане питання - скільки витяжок потрібно, щоб мати m копій кожного купона (а не лише однієї) - це задача про подвійну Dixie cup, вирішена Ньюменом та Шеппом; її очікуване значення дорівнює N ln N + (m-1) N ln(ln N) + O(N) для заданого m. Пізніше Ердош і Рені уточнили результат з однією копією, сформулювавши його як твердження концентрації: T/(N ln N) збігається за ймовірністю до 1, а коливання навколо N ln N сходяться до розподілу Гембеля - той самий закон екстремальних значень, що керує максимумом багатьох незалежних випадкових величин, оскільки завершення набору є справжнім перегоном за пошук одного найповільнішого купону, який з'являється.

Проведення моделювання

Функція `trial(N)` виконує наступне: const seen = new Set(); let draws = 0; while (seen.size < N) { seen.add(Math.floor(Math.random() * N)); draws++; } return draws;

// Середнє значення результатів моделювання обчислюється шляхом проведення багатьох викликів `trial(N)` та порівняння їх із теоретичним результатом N * H_N, а також з наближеним розрахунком N * ln(N) + γN. На цій сторінці симуляція виконує цей цикл тисячі разів на секунду, заповнюючи динамічну сітку при першому спостереженні кожного типу купона та відображаючи середнє значення, отримане емпірично, а також точні теоретичні прогнози (N * H_N) та наближений розрахунок (N * ln(N) + γN), щоб ви могли спостерігати за збіжністю оцінки Монте-Карло.

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

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Coupon Collector і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.