В теории вероятностей , в проблеме купонов коллекционной описывает «собрать все купоны и выиграть» конкурсы. В нем задается следующий вопрос: если в каждой коробке марки зерновых есть купон и есть n различных типов купонов, какова вероятность того, что потребуется купить более t коробок, чтобы собрать все n купонов? Альтернативное утверждение: учитывая n купонов, сколько купонов, по вашему мнению, вам нужно будет вытянуть с заменой, прежде чем вы будете использовать каждый купон хотя бы один раз? Математический анализ проблемы показывает, что ожидаемое количество необходимых испытаний растет по мере роста.. [a] Например, при n = 50 для сбора всех 50 купонов в среднем требуется около 225 [b] попыток.
Решение
Расчет ожидания
Пусть время T будет количеством розыгрышей, необходимых для сбора всех n купонов, и пусть t i будет временем сбора i-го купона после того , как будет собран i - 1 купон. потом. Думайте о T и t i как о случайных величинах . Обратите внимание, что вероятность получения нового купона равна. Следовательно,имеет геометрическое распределение с ожиданием. По линейности ожиданий имеем:
Здесь Н п является п -го номера гармоники . Используя асимптотику гармонических чисел, получаем:
где - постоянная Эйлера – Маскерони .
Теперь можно использовать неравенство Маркова, чтобы оценить желаемую вероятность:
Расчет дисперсии
Используя независимость случайных величин t i , получаем:
поскольку (см. Базельскую проблему ).
Теперь можно использовать неравенство Чебышева, чтобы оценить желаемую вероятность:
Оценки хвоста
Другая верхняя граница может быть получена из следующего наблюдения. Позволять обозначают событие, которое -й купон не был выбран в первом испытания. Потом:
Таким образом, для , у нас есть .
Расширения и обобщения
- Лаплас , но и Эрдёш и Рение , доказали предельную теорему для распределения Т . Этот результат является дальнейшим расширением предыдущих оценок.
- Дональд Дж. Ньюман и Лоуренс Шепп дали обобщение проблемы сборщика купонов, когда необходимо собрать m копий каждого купона. Пусть T m будет первым сбором m копий каждого купона. Они показали, что ожидание в этом случае удовлетворяет:
- Здесь m фиксировано. Когда m = 1, мы получаем предыдущую формулу математического ожидания.
- Общее обобщение, также принадлежащее Эрдешу и Реньи:
- В общем случае неравномерного распределения вероятностей, согласно Филиппу Флажоле , [1]
- Это равно
- где м означает число купонов должны быть собраны, а Р J обозначая вероятность получения какой - либо купон в наборе купонов J .
Смотрите также
Заметки
- ^ Здесь и в этой статье «логарифм» относится к натуральному логарифму, а не к логарифму с другим основанием. Использованиеthetas здесь вызывает большие обозначения O .
- ^ E (50) = 50 (1 + 1/2 + 1/3 + ... + 1/50) = 224,9603, ожидаемое количество попыток собрать все 50 купонов. Приближение для этого ожидаемого числа дает в этом случае .
Рекомендации
- ^ Flajolet, Филипп; Гарди, Даниэль; Thimonier, Loys (1992), "День рождения парадокс, купонные коллекторы, кэширование алгоритмы и самоорганизующиеся поиск", дискретное Прикладная математика , 39 (3): 207-229, CiteSeerX 10.1.1.217.5965 , DOI : 10.1016 / 0166-218x (92) 90177-в
- Блом, Гуннар; Холст, Ларс; Санделл, Деннис (1994), «7.5 Купонный сбор I, 7.6 Купонный сбор II и 15.4 Купонный сбор III», Проблемы и снимки из мира вероятностей , Нью-Йорк: Springer-Verlag, стр. 85–87, 191, ISBN 0-387-94161-4, Руководство по ремонту 1265713.
- Докинз, Брайан (1991), "Проблема Шивон: купонная коллектор вновь", Американский Статистик , 45 (1): 76-82, DOI : 10,2307 / 2685247 , JSTOR 2685247.
- Эрдеш, Пол ; Реньи, Альфред (1961), «О классической проблеме теории вероятностей» (PDF) , Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei , 6 : 215–220, MR 0150807.
- Лаплас, Пьер-Симон (1812), Аналитическая теория вероятностей , стр. 194–195..
- Ньюман, Дональд Дж .; Shepp, Лоуренс (1960), "Двойная Dixie проблема чашка", American Mathematical Monthly , 67 (1): 58-61, DOI : 10,2307 / 2308930 , JSTOR 2308930 , MR 0120672
- Флажолет, Филипп ; Гарди, Даниэль; Thimonier, Loys (1992), "День рождения парадокс, купонные коллекторы, кэширование алгоритмы и самоорганизующийся поиск" , дискретная прикладная математика , 39 (3): 207-229, DOI : 10.1016 / 0166-218X (92) 90177-C , Руководство по ремонту 1189469.
- Исаак, Ричард (1995), «8.4 Проблема коллекционера купонов решена», The Pleasures of Probability , Undergraduate Texts in Mathematics , New York: Springer-Verlag, pp. 80–82, ISBN 0-387-94415-X, Руководство по ремонту 1329545.
- Мотвани, Раджив ; Рагхаван, Прабхакар (1995), «3.6. Проблема коллекционера купонов», рандомизированные алгоритмы , Кембридж: Cambridge University Press, стр. 57–63, ISBN 9780521474658, Руководство по ремонту 1344451.
Внешние ссылки
- « Проблема коллекционера купонов » Эда Пегга-младшего , Демонстрационный проект Вольфрама . Пакет Mathematica.
- Сколько одиночных, двойных, тройных и т. Д. Следует ожидать сборщику купонов? , короткая заметка Дорон Зейлбергер .