UK 
EnglishТипова
Polski🎟️ Задача колекціонера купонів — скільки спроб до повного набору
Зберіть усі N купонів випадковими спробами: дивіться, як заповнюється сітка, порівнюйте емпіричне середнє з E[T]=N·H_N та N·ln N+γN і гістограму часів завершення.
Про задачу колекціонера купонів
Задача колекціонера купонів — класичний результат теорії ймовірностей, що запитує: якщо кожне випадкове витягування дає один із N рівноймовірних типів купонів, скільки витягувань в середньому потрібно, щоб зібрати хоча б один купон кожного типу? Точне очікуване число дорівнює E[T] = N · HN, де HN = 1 + 1/2 + 1/3 + … + 1/N — N-е гармонічне число. Ця симуляція дозволяє спостерігати процес збору в реальному часі, простежувати сповільнення кривої покриття та порівнювати емпіричне середнє за сотнями випробувань з теоретичним передбаченням.
Задача має практичне значення всюди, де випадкова вибірка має досягти повного покриття: заповнення альбомів наліпок і колекцій карток, генерація випадкових тестових вхідних даних, що охоплюють кожен шлях коду, вимірювання різноманітності схем випадкового хешування та оцінка зусиль, необхідних для вибірки кожного елемента популяції хоча б раз.
Часті запитання
Яка очікувана кількість витягувань для збору всіх N купонів?
Точне очікування дорівнює E[T] = N · HN, де HN — N-е гармонічне число (сума 1 + 1/2 + 1/3 + … + 1/N). Оскільки HN зростає як ln(N) + γ (стала Ейлера-Маскероні γ ≈ 0,5772), це спрощується до відомого наближення E[T] ≈ N · ln(N) + γ · N. Наприклад, для N = 20 купонів очікувана кількість витягувань становить близько 71,9.
Як користуватися цією симуляцією?
Використайте повзунок N, щоб обрати кількість різних типів купонів (2–50), потім натисніть «Play run», щоб побачити анімований процес збору: сітка підсвічує кожен тип, коли він вперше з'являється, а крива покриття показує зібрану частку з часом. Натисніть «Run 100 trials» для миттєвого пакетного симулювання багатьох завершень і побудови гістограми, яка має скупчуватися навколо зеленої лінії E[T]. Повзунок швидкості контролює, скільки витягувань обробляється за кадр анімації.
Чому крива покриття вирівнюється ближче до кінця?
Коли у вас вже є k з N типів, кожне нове витягування потрапляє на відсутній тип з імовірністю лише (N − k) / N. Коли k наближається до N, ця ймовірність зменшується до 1/N, тож кожен новий унікальний купон стає значно важче знайти. Очікувана кількість витягувань від k до k+1 дорівнює N / (N − k), що зростає необмежено, коли k → N. Цей ефект «спадної віддачі» вирівнює криву покриття й створює довгий правий хвіст на гістограмі часу завершення.
Як виводиться формула гармонічного числа?
Виведення використовує лінійність математичного сподівання. Після збору k різних купонів час очікування наступного нового геометрично розподілений з імовірністю успіху p = (N − k) / N, тож його середнє дорівнює N / (N − k). Сумуючи за k = 0, 1, …, N−1, отримуємо E[T] = N/N + N/(N−1) + … + N/1 = N · (1 + 1/2 + … + 1/N) = N · HN. Дисперсія також відома: Var[T] = N2 · Σ(1/k2) ≈ N2 · π2/6 для великих N.
Які реальні приклади задачі про колекціонера купонів?
Альбоми наліпок Panini — найвідоміший приклад: альбом Чемпіонату світу 2018 року мав 682 наліпки, і колекціонерам у середньому потрібно було близько 4832 покупок пакетів наліпок для завершення (купуючи пакети по 5). У програмній інженерії випадковий фаззинг має генерувати достатньо тестових вхідних даних, щоб досягти кожної гілки коду; при N гілках очікувані зусилля зростають як N · ln(N). Мережеві протоколи, що призначають випадкові ID, стикаються з подібною дуальною задачею днів народження.
Чи є хибним уявлення, що потрібно рівно N витягувань для збору N купонів?
Так — це було б правдою лише якби можна було гарантувати відсутність повторів, як при витягуванні без повернення. З поверненням (незалежні випадкові витягування) дублікати неминучі. Очікувана загальна кількість зростає як N · ln(N), а не N, бо останні кілька купонів кожен вимагають багато повторних витягувань, перш ніж з'явиться відсутній тип. Для N = 50 очікувана кількість витягувань становить близько 225, а не 50.
Хто першим вивчав задачу про колекціонера купонів і коли?
Задача має корені у комбінаториці 18 століття. Абрахам де Муавр вивчав пов'язані задачі про заповнення у своїй роботі 1718 року «Вчення про шанси». Сучасне формулювання й розв'язок через гармонічні числа стали відомими завдяки підручникам з теорії ймовірностей середини 20 століття. Назва «колекціонер купонів» стала популярною, коли фізичні набори купонів і колекційні картки стали поширеними споживчими товарами на початку 20 століття.
Які пов'язані задачі теорії ймовірностей чи симуляції пов'язані з цією темою?
Задача про колекціонера купонів тісно пов'язана із задачею про дні народження (яка запитує, коли вперше трапляється збіг, а не коли заповнені всі слоти), задачами про заповнення в комбінаториці та аналізом випадкових хеш-функцій. Це дуальна задача до колекціонування купонів: одна запитує про перший повтор, інша — про повне покриття. Пов'язані симуляції включають парадокс днів народження, задачі покриття випадкового блукання та інтегрування методом Монте-Карло.
Як задача про колекціонера купонів використовується в комп'ютерних науках та інженерії?
У тестуванні програмного забезпечення задача кількісно визначає, скільки випадкових тестових вхідних даних потрібно для повного покриття шляхів коду — еталон для випадкового (фаззинг) проти систематичного генерування тестів. У розподілених системах вона моделює, скільки широкомовних повідомлень потрібно, перш ніж кожен вузол мережі отримає хоча б одне. Балансувальники навантаження та хеш-таблиці використовують подібний аналіз заповнення.
Що відбувається, коли купони не рівноймовірні або з'являються групами?
Коли типи купонів мають нерівні ймовірності, формула гармонічного числа більше не застосовується. Очікуваний час завершення натомість визначається найрідкіснішим купоном: якщо найменш ймовірний тип має ймовірність pmin, очікувана кількість витягувань зростає щонайменше так само швидко, як 1/pmin. Це вивчається під назвою «нерівномірний колекціонер купонів» і може бути значно гіршим за рівномірний випадок. Коли купони надходять пакетами (як з альбомами наліпок), задача стає варіантом із корельованими витягуваннями.