Сітка колекції (зібрані — акцент, відсутні — приглушені) та крива
покриття, що вирівнюється
Гістограма часів завершення по прогонах vs очікуване значення E[T]
📖 Теорія — гармонічні числа
Припустимо, що кожна спроба дає один із
N типів купонів
з однаковою ймовірністю. Коли ви вже маєте k різних
купонів, шанс, що нова спроба дасть той, якого бракує, дорівнює
(N − k) / N. Тому кількість спроб до наступного нового
купона має геометричний розподіл із середнім
N / (N − k). Підсумовуючи по
k = 0 … N − 1, отримуємо очікуваний загальний час
E[T] = N·(1/N + 1/(N−1) + … + 1/1) = N·H_N, де
H_N — N-те гармонічне число.
📐 Останній купон домінує ~ N·ln N
Оскільки
H_N ≈ ln N + γ (зі сталою Ейлера–Маскероні
γ ≈ 0,5772), сподівання дорівнює
E[T] ≈ N·ln N + γN. Найбільший окремий внесок дає
останній купон: коли бракує лише одного типу, кожна спроба влучає в
нього з ймовірністю 1/N, тож цей останній купон сам по
собі коштує в середньому близько N спроб. Це ефект
«спадної віддачі» — крива покриття вирівнюється, а довгий хвіст часів
завершення майже повністю зумовлений очікуванням на останній один-два
купони.
🃏 Застосування
Та сама математика керує багатьма реальними ситуаціями: збір набору
колекційних карток чи альбому з наклейками з випадкових пакунків,
відкриття лутбоксів заради кожного предмета та оцінка того, скільки
випадкових тестових вхідних даних потрібно, щоб задіяти кожен шлях у
коді (покриття тестами). Усюди, де ви багаторазово тягнете випадково
й хочете зібрати кожен різний результат, очікувані зусилля зростають
як
N·ln N — значно швидше, ніж наївна оцінка
N спроб.