Сітка колекції (зібрані — акцент, відсутні — приглушені) та крива покриття, що вирівнюється
Гістограма часів завершення по прогонах 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 спроб.