Проблема сборщика купонов - Coupon collector's problem

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

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

Решение

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

Пусть время T будет количеством розыгрышей, необходимых для сбора всех n купонов, и пусть t _i будет временем получения i-го купона после того  , как будет собран i - 1 купон. Тогда . Думайте о T и t _i как о случайных величинах . Обратите внимание, что вероятность получения нового купона равна . Следовательно, имеет геометрическое распределение с ожиданием . По линейности ожиданий имеем: ${\ 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}}.}$

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

${\ displaystyle {\ begin {align} \ operatorname {E} (T_ {k}) & {} = \ operatorname {E} (t_ {k + 1} + t_ {k + 2} + \ cdots + t_ {n }) \\ & {} = n \ cdot \ left ({\ frac {1} {1}} + {\ frac {1} {2}} + \ cdots + {\ frac {1} {nk}} \ вправо) \\ & {} = n \ cdot H_ {nk} \ end {выровнено}}}$

И когда тогда мы получим исходный результат. ${\ displaystyle k = 0}$

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

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

${\ 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 \ left ({\ 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 <n \ log n + cn) \ to e ^ {- e ^ {- c}}, {\ text {as}} n \ to \ infty.}$

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

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

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

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

${\ displaystyle \ operatorname {P} \ left (T_ {m} <n \ log n + (m-1) n \ log \ log n + cn \ right) \ to e ^ {- e ^ {- c} / ( m-1)!}, {\ text {as}} n \ to \ infty.}$

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

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

Это равно

${\ Displaystyle \ OperatorName {E} (T_ {m}) = \ sum _ {q = 0} ^ {m-1} (- 1) ^ {m-1-q} \ sum _ {| J | = q } {\ frac {1} {1-P_ {J}}}}$

где м означает число купонов должны быть собраны, а Р _J обозначая вероятность получения какой - либо купон в наборе купонов J .

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

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

Примечания

использованная литература

внешние ссылки

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