Проблема сборщиков купонов - Википедия - Coupon collectors problem

График количества купонов, п против ожидаемого количества испытаний (то есть времени), необходимого для их сбора, E (Т )

В теория вероятности, то проблема сборщика купонов описывает конкурсы «собери все купоны и выиграй». Он задает следующий вопрос: если в каждой коробке марки зерновых есть купон, и есть ли п различных типов купонов, какова вероятность того, что более т ящики нужно покупать, чтобы собрать все п купоны? Альтернативное утверждение: Дано п купонов, сколько купонов, по вашему мнению, вам нужно будет нарисовать с заменой, прежде чем использовать каждый купон хотя бы один раз? Математический анализ проблемы показывает, что ожидаемое число необходимых испытаний растет по мере ${ Displaystyle Theta (п журнал (п))}$.^[а] Например, когда п = 50 требуется около 225^[b] в среднем для сбора всех 50 купонов.

Решение

Расчет ожидания

Позволять Т пора собрать все п купоны, и пусть т_я пора собирать я-й купон после я - Собрано 1 купон. потом ${ displaystyle T = t_ {1} + cdots + t_ {n}}$. Думать о Т и т_я в качестве случайные переменные. Обратите внимание, что вероятность собрать новый купон ${ displaystyle p_ {i} = { frac {n- (i-1)} {n}} = { frac {n-i + 1} {n}}}$. Следовательно, ${ displaystyle t_ {i}}$ имеет геометрическое распределение с ожиданием ${ displaystyle { frac {1} {p_ {i}}} = { frac {n} {n-i + 1}}}$. Посредством линейность ожиданий у нас есть:

${ displaystyle { begin {align} operatorname {E} (T) & {} = operatorname {E} (t_ {1} + t_ {2} + cdots + t_ {n}) & {} = operatorname {E} (t_ {1}) + operatorname {E} (t_ {2}) + cdots + operatorname {E} (t_ {n}) & {} = { frac {1 } {p_ {1}}} + { frac {1} {p_ {2}}} + cdots + { frac {1} {p_ {n}}} & {} = { frac {n } {n}} + { frac {n} {n-1}} + cdots + { frac {n} {1}} & {} = n cdot left ({ frac {1} {1}} + { frac {1} {2}} + cdots + { frac {1} {n}} right) & {} = n cdot H_ {n}. End {выровнено }}}$

Здесь ЧАС_п это п-го номер гармоники. С использованием асимптотика гармонических чисел, получаем:

${ displaystyle operatorname {E} (T) = n cdot H_ {n} = n log n + gamma n + { frac {1} {2}} + O (1 / n),}$

куда ${ displaystyle gamma приблизительно 0,5772156649}$ это Константа Эйлера – Маскерони.

Теперь можно использовать Неравенство Маркова чтобы ограничить желаемую вероятность:

${ displaystyle operatorname {P} (T geq cnH_ {n}) leq { frac {1} {c}}.}$

Расчет дисперсии

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

${ displaystyle { begin {align} operatorname {Var} (T) & {} = operatorname {Var} (t_ {1} + cdots + t_ {n}) & {} = operatorname {Var} } (t_ {1}) + operatorname {Var} (t_ {2}) + cdots + operatorname {Var} (t_ {n}) & {} = { frac {1-p_ {1} } {p_ {1} ^ {2}}} + { frac {1-p_ {2}} {p_ {2} ^ {2}}} + cdots + { frac {1-p_ {n}} {p_ {n} ^ {2}}} & {} < left ({ frac {n ^ {2}} {n ^ {2}}} + { frac {n ^ {2}} { (n-1) ^ {2}}} + cdots + { frac {n ^ {2}} {1 ^ {2}}} right) & {} = n ^ {2} cdot слева ({ frac {1} {1 ^ {2}}} + { frac {1} {2 ^ {2}}} + cdots + { frac {1} {n ^ {2}}} справа) & {} <{ frac { pi ^ {2}} {6}} n ^ {2} end {align}}}$

поскольку ${ displaystyle { frac { pi ^ {2}} {6}} = { frac {1} {1 ^ {2}}} + { frac {1} {2 ^ {2}}} + cdots + { frac {1} {n ^ {2}}} + cdots}$ (видеть Базельская проблема ).

Теперь можно использовать Неравенство Чебышева чтобы ограничить желаемую вероятность:

${ displaystyle operatorname {P} left (| T-nH_ {n} | geq cn right) leq { frac { pi ^ {2}} {6c ^ {2}}}.}$

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

Другая верхняя граница может быть получена из следующего наблюдения. Позволять ${ displaystyle {Z} _ {i} ^ {r}}$ обозначают событие, которое ${ displaystyle i}$-й купон не был выбран в первом ${ displaystyle r}$ испытания. Потом:

${ displaystyle { begin {align} P left [{Z} _ {i} ^ {r} right] leq left (1 - { frac {1} {n}} right) ^ {r } leq e ^ {- r / n} end {выровнено}}}$

Таким образом, для ${ Displaystyle г = бета п журнал п}$, у нас есть ${ displaystyle P left [{Z} _ {i} ^ {r} right] leq e ^ {(- beta n log n) / n} = n ^ {- beta}}$.

${ Displaystyle { begin {выровнено} P left [T> beta n log n right] = P left [ bigcup _ {i} {Z} _ {i} ^ { beta n log n } right] leq n cdot P [{Z} _ {1} ^ { beta n log n}] leq n ^ {- beta +1} end {выравнивается}}}$

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

• Пьер-Симон Лаплас, но также Пол Эрдёш и Альфред Реньи, доказал предельную теорему для распределения Т. Этот результат является дальнейшим расширением предыдущих оценок.

${ displaystyle operatorname {P} (T$

• Дональд Дж. Ньюман и Лоуренс Шепп дал обобщение проблемы сборщика купонов, когда м необходимо собрать копии каждого купона. Позволять Т_м быть в первый раз м собираются копии каждого купона. Они показали, что ожидание в этом случае удовлетворяет:

${ displaystyle operatorname {E} (T_ {m}) = n log n + (m-1) n log log n + O (n), { text {as}} n to infty.}$

Здесь м фиксированный. Когда м = 1 мы получаем предыдущую формулу математического ожидания.

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

${ displaystyle operatorname {P} left (T_ {m}$

• В общем случае неравномерного распределения вероятностей согласно Филипп Флажоле,^[1]

${ displaystyle operatorname {E} (T) = int _ {0} ^ { infty} left (1- prod _ {i = 1} ^ {n} left (1-e ^ {- p_ {i} t} right) right) dt.}$

Смотрите также

• Оценка Уоттерсона
• Проблема дня рождения

Примечания

Рекомендации

внешняя ссылка

• "Проблема со сборщиком купонов " к Эд Пегг младший, то Вольфрам Демонстрационный проект. Пакет Mathematica.
• Сколько одиночных, двойных, тройных и т. Д. Следует ожидать сборщику купонов?, короткое примечание Дорон Зейлбергер.