Парадоксальное наоборот

[spamsink]

Все (интересующиеся подобными вещами) помнят хрестоматийный ответ на вопрос, сколько людей должно быть в группе, чтобы с вероятностью больше 50% среди них нашлось два человека с совпадающим днём (числом и месяцем) рождения: этот ответ - 23, что на первый взгляд довольно парадоксально, учитывая более чем на порядок большее количество дней в году.

А

Comments

[utnapishti]

(1) М.б. это не так известно, потому что формула элементарная. Ну и да, нет ощущения парадокса: понятно, что число, близкое к 1, нужно в большую степень возвести, чтобы получить 1/2.

(2) По идее, "наоборот" это не это, а сколько людей должно быть в группе, чтобы с вероятностью >50% покрыть все дни.

Как быстро функция перестаёт быть injective vs. как быстро она начинает быть surjective.

[spamsink]

(1) Ну да, здесь не столько парадокс, сколько неинтуитивная оценка этой большой степени.

(2) Около 2300, но точной формулы я не выведу.

[utnapishti]

Это называется Coupon collector's problem.

[spamsink]

Спасибо; это словосочетание я когда-то видел, но успел позабыть.

Интересно, что русский вариант статьи отсутствует.

[ak_47]

Потому что вкладывать какие-то купоны в коробки с кукурузными хлопьями, и вообще, есть непонятно что на завтрак - это очень не по-русски. :)

[spamsink]

Я согласен, но математика должна быть выше этого!

[ak_47]

Все говорят, что мы, математики - сухари. Это ложь! Мы кукурузные хлопья!

[urease]

Да. Помню, жил на бананах, рамене и химию колол за деньги, ео купоны не собирал - дурацкая русская натура

[vsparrow]

Хорошая статья. Но более интересно, как посчитать вероятность при разных количествах купонов?
Скажем, есть котики Pusheen - их всего 8 разновидностей, но выпущено их очевидно разное количество (проклятый маркетинг). Есть часто встречающиеся модели, есть редко. Вот интересно, можно ли посчитать "необходимое" количество купленных упаковок, если примерно понятно соотношение? Например, если самый распространенный Pusheen встречается в 5 раз чаще самого редкого (это не обязательно так, просто пример)?

[spamsink]

Насколько я помню из мельком проходимого курса случайных процессов, формально это делается составлением матрицы вероятностей перехода из состояния "имеется такой-то набор разновидностей" в состояние имеется сякой-то набор разновидностей" (в данном случае размерность матрицы будет 256 на 256) при приобретении очередного предмета, и возведением этой матрицы в степень до тех пор, пока начальный вектор состояния, обозначающий "набор пуст", умноженный на матрицу в N-й степени, не даст желаемую вероятность состояния "набор полон". Понятно, что это можно сделать двоичным поиском, так что много времени не займёт.

Возможно, с тех пор, как я закончил институт, нашлись и более эффективные алгоритмы, но я их не знаю.

[vsparrow]

ой мама...
ну бог с ним, что я ничего не понял. это обычное дело. так ещё я почему-то думал, что должно быть примерно такое: "для не сильно больших отклонений в кол-ве выпущенных пушинов (например, соотношение между максимально и минимально выпущенным не превышает 1/10) подставляем вот сюда кол-во моделей, сюда соотношение, и получаем кол-во покупок с точностью до N*k, к примеру, где N - кол-во моделей пушинов, а k невелико". Скажем, разброс "купи от 22 яиц (столько дает упомянутая статья на 8 моделей, если все модели выпущены в одинаковом кол-ве) до 55 яиц, ежели самый редкий пушин встречается в 10 раз реже самого частого" меня вполне бы устроил. Хотя бы как оценка, что не надо настраиваться на покупку 10 000 яиц. Это конечно не к вам вопрос, а так, признание в собственной дурости.
А маркетологи молодцы, конечно. Отличный способ продать много дерьмового "шоколада" (обычно пушины живут в шоколадных яйцах).

[spamsink]

Как оказывается, не это, хотя ответы не сильно отличаются. В задаче собирателя купонов просят найти матожидание, а мы хотим медиану.