Математика / Вероятность и статистика

Задача коллекционера купонов: среднее время полной коллекции

Если каждый из n типов купонов появляется независимо и равновероятно, среднее число покупок для полной коллекции равно nH_n. Последние недостающие типы дают основную задержку.

Опубликовано: 6 ноября 2026 г.Обновлено: 6 ноября 2026 г.

Формула

\mathbb E[T]=nH_n=n\sum_{j=1}^{n}\frac1j

Схема Ожидание каждого нового типа

При n=4 этапы ожидания равны 1,4/3,2,4 покупки; последний этап наиболее долгий.

Обозначения

$n$: число равновероятных типов, шт.
$T$: число покупок до полной коллекции, покупки
$H_n$: гармоническая сумма1+1/2+…+1/n, безразмерно

Условия применения

Каждая покупка даёт один тип, независимый от предыдущих, с вероятностью 1/n для любого типа. Уже полученные типы могут повторяться. Счёт покупок включает покупку последнего нового типа, а начальная коллекция пуста.

Ограничения

При неравных вероятностях типов среднее обычно другое и зависит от всего распределения. Упаковки с несколькими зависимыми купонами не соответствуют одиночной модели. Среднее время не является сроком с заданной вероятностью завершения и не означает, что каждая коллекция завершится за округлённое число покупок.

Подробное объяснение

После получения j−1 различных типов остаётся n−j+1 новых из n, поэтому среднее ожидание следующего нового типа равно n/(n−j+1). Складывая этапы j=1,…,n, получаем n(1+1/2+…+1/n).

Формула предполагает независимые покупки и одинаковую вероятность каждого типа. Если редкие купоны встречаются реже, гармоническая сумма уже не описывает процесс.

Ожидание — среднее по множеству коллекций, а не гарантия срока. Хвост распределения длинный: отдельная серия может закончиться намного позже nH_n.

Модель полезна для оценки времени покрытия всех категорий, тестирования случайного генератора и анализа количества случайных выборок до полного набора.

Этапные времена можно складывать по линейности математического ожидания. Для этого самого шага не требуется доказывать их независимость: достаточно знать среднее каждого этапа. Независимость покупок используется раньше, когда ожидание нового типа определяется геометрической вероятностью.

Как пользоваться формулой

Проверьте, что все n типов равновероятны и каждая независимая покупка даёт ровно один купон с возможными повторениями.
Вычислите гармоническую сумму H_n=1+1/2+…+1/n, сохраняя дроби или достаточную точность промежуточных значений.
Умножьте H_n на n и укажите единицу результата — среднее число покупок, которое может оказаться нецелым.
Проверьте сумму по этапам: ожидания новых типов равны n/n,n/(n−1),…,n/1, особенно выделив последний тип.

Историческая справка

Задача коллекционера купонов стала классическим примером случайного покрытия конечного набора. Её учебная ценность связана с разложением сложного времени остановки на последовательные ожидания: после каждого нового типа задача повторяется с другой вероятностью успеха.

В современных курсах вероятностного анализа алгоритмов ту же структуру используют для заполнения ячеек, хеширования и случайного выбора меток. Учебная страница Tufts выводит ожидание через вероятность очередного нового купона, а материалы Johns Hopkins сопоставляют сбор купонов с фильтрами Блума. Здесь важен не исторический сюжет рекламной коллекции, а воспроизводимый переход от геометрических ожиданий к гармонической сумме.

Историческая линия формулы

Формула принадлежит классической задаче о равномерном сборе типов и не требует приписывания современному производителю карточек. Источники университетских курсов подтверждают этапный вывод. Слово «купон» обозначает тип случайного результата, а не обязательную денежную ценность.

Пример

В коллекции n=4 равновероятных типа, каждая покупка независима. Гармоническая сумма H₄=1+1/2+1/3+1/4=25/12. Среднее время полного сбора равно 4·25/12=25/3≈8,333333 покупки. Независимая проверка по этапам: первый новый тип появляется сразу, ожидание второго равно 4/3, третьего 2, четвёртого 4. Сумма 1+4/3+2+4=25/3 совпадает. Ответ: в среднем 8⅓ покупки. Не нужно округлять математическое ожидание до 9 как будто это гарантированный срок. Последний тип один занимает в среднем 4 покупки, почти половину общей длительности. При уже собранных трёх типах вероятность нового в каждой следующей покупке 1/4, поэтому ожидание 4 объясняется геометрическим законом.

Частая ошибка

Не заменяйте nH_n на n: повторения неизбежны. Не складывайте одинаковые ожидания для всех этапов: шанс нового типа уменьшается по мере заполнения коллекции. Не трактуйте среднее как гарантированный максимум. Не применяйте формулу равномерной модели к редким и частым типам с разными вероятностями.

Практика

Задачи с решением

Три типа

Условие. Найдите среднее полное время для n=3.

Решение. 3(1+1/2+1/3)=3·11/6=11/2.

Ответ. 5,5 покупки.

Пять типов

Условие. Найдите среднее полное время для n=5.

Решение. H₅=137/60; умножаем на 5, получаем 137/12.

Ответ. 137/12≈11,4166667 покупки.

Дополнительные источники

https://www.cs.tufts.edu/comp/250P/classpages/coupon.html
https://www.cs.jhu.edu/~langmea/resources/lecture_notes/120_bloom_and_coupon_pub.pdf

Связанные формулы

Математика

Математическое ожидание биномиального распределения

$M(X)=np$

Формула «Математическое ожидание биномиального распределения» задает численную характеристику вероятностной модели. Она переводит исходы, вероятности или наблюдения в показатель, который удобно считать, сравнивать и проверять.

Математика

Отрицательное биномиальное распределение

$P(X=k)=\binom{k-1}{r-1}p^r(1-p)^{k-r}$

Отрицательное биномиальное распределение задаёт вероятность того, что r-й успех случится ровно на k-м независимом испытании. Число успехов фиксировано, а длина серии до остановки случайна.

Информатика

Фильтр Блума: вероятность ложного срабатывания

$p_{\mathrm{FP}}\approx\left(1-e^{-kn/m}\right)^k$

Фильтр Блума допускает ложноположительный ответ о наличии элемента. В стандартной вероятностной модели его частоту оценивают через число битов m, хеш-функций k и вставленных элементов n.