Задача о сборщике купонов

Задача о сборщике купонов — это классическая проблема теории вероятностей, которая помогает понять, сколько попыток в среднем требуется для сбора полного набора различных предметов. Эта задача имеет практическое применение в азартных играх, лотереях и маркетинговых акциях, где участники собирают купоны или призы. Математический анализ показывает, что ожидаемое количество попыток растёт логарифмически с увеличением количества различных купонов.

Задача теории вероятностей

В теории вероятностей задача о сборщике купонов относится к математическому анализу конкурсов типа «собери все купоны и выиграй». Она ставит следующий вопрос: если каждая упаковка товара (например, хлопьев для завтрака) содержит купон, и существует n различных типов купонов, какова вероятность того, что потребуется купить более t упаковок, чтобы собрать все n купонов? Альтернативная формулировка: имея n купонов, сколько купонов в среднем нужно вытащить с возвращением, прежде чем получить каждый купон хотя бы один раз? Математический анализ показывает, что ожидаемое количество попыток растёт как Θ(n log n). Например, при n = 50 в среднем требуется около 225 попыток, чтобы собрать все 50 купонов. Иногда задача формулируется в терминах n-гранного кубика.

Решение

Вычисление математического ожидания

Пусть T — количество попыток, необходимых для сбора всех n купонов, а t_i — время сбора i-го купона после того, как собрано i − 1 купонов. Тогда T = t₁ + ⋯ + t_n. Рассмотрим T и t_i как случайные величины. Вероятность получить i-й новый купон равна p_i = (n − i + 1)/n. Следовательно, t_i имеет геометрическое распределение с математическим ожиданием 1/p_i = n/(n − i + 1). По линейности ожидания:

E(T) = n · H_n

где H_n — n-е гармоническое число. Используя асимптотику гармонических чисел:

E(T) = n log n + γn + 1/2 + O(1/n)

где γ ≈ 0,5772156649 — постоянная Эйлера-Маскерони (Euler-Mascheroni constant).

Применяя неравенство Маркова:

P(T ≥ cnH_n) ≤ 1/c

Если уже собрано k купонов, то:

E(T_k) = n · H_{n-k}

При k = 0 получаем исходный результат.

Вычисление дисперсии

Используя независимость случайных величин t_i:

Var(T) = Var(t₁) + Var(t₂) + ⋯ + Var(t_n) < π²n²/6

так как π²/6 = 1/1² + 1/2² + ⋯ + 1/n² + ⋯ (см. Базельскую задачу).

Применяя неравенство Чебышёва:

P(|T − nH_n| ≥ cn) ≤ π²/(6c²)

Числа Стирлинга

Пусть случайная величина X — количество бросаний кубика до появления всех граней.

Вероятность того, что все грани выпали в пределах k-го броска:

P(X ≤ k) = n^{k}/n^k

где n^{k} обозначает число сюръекций из k элементов на n элементов.

Вероятность того, что потребуется ровно k бросаний:

P(X = k) = (n−1)^{k−1}/n^{k−1}

Производящие функции

Для k > 0:

E[X^k] = n∑(n choose i)(−1)^{n−i}i(i−1)^{k−1}/(n+1−i)^{k+1}

Сырые моменты распределения можно получить из падающих моментов через преобразование Стирлинга.

Оценки хвостов

Более сильная оценка верхнего хвоста получается следующим образом. Пусть Z_i^r — событие, что i-й купон не был выбран в первых r попытках. Тогда:

P[Z_i^r] = (1 − 1/n)^r ≤ e^{−r/n}

Для r = βn log n имеем P[Z_i^r] ≤ n^{−β}. По объединению границ над n купонами:

P[T > βn log n] ≤ n^{−β+1}

Расширения и обобщения

• Пьер-Симон Лаплас (Pierre-Simon Laplace), а также Пол Эрдёш (Paul Erdős) и Альфред Реньи (Alfréd Rényi) доказали предельную теорему для распределения T:

P(T < n log n + cn) → e^{−e^{−c}} при n → ∞

что является распределением Гумбеля.

• Дональд Ньюман (Donald J. Newman) и Лоренс Шепп (Lawrence Shepp) обобщили задачу на случай, когда нужно собрать m копий каждого купона. Они показали, что математическое ожидание в этом случае удовлетворяет:

E(T_m) = n log n + (m−1)n log log n + O(n) при n → ∞

где m фиксировано. При m = 1 получается исходная формула.

• Общее обобщение, также принадлежащее Эрдёшу и Реньи:

P(T_m < n log n + (m−1)n log log n + cn) → e^{−e^{−c}/(m−1)!} при n → ∞

• В общем случае неравномерного распределения вероятностей, согласно Филипу Флажоле (Philippe Flajolet) и соавторам:

E(T) = ∫₀^∞ (1 − ∏ᵢ₌₁^m (1 − e^{−p_i t})) dt

что равно

E(T) = ∑_{q=0}^{m−1} (−1)^{m−1−q} ∑_{|J|=q} 1/(1 − P_J)

где m — количество купонов для сбора, а P_J — вероятность получить любой купон из набора J.

Математическая суть задачи о сборщике купонов