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

[spamsink]

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

А теперь вопрос наоборот: сколько людей должно быть в группе, чтобы с вероятностью больше 50% среди них нашёлся человек, чей день рождения - 31 августа (в предположении, что все дни рождения равновероятны, разумеется)?

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

Upd (thx to utnapishti): сколько человек должно быть в группе, чтобы с вероятностью больше 50% каждый день в году был чьим-нибудь днём рождения?

Comments

[vmozgutuman]

254?

[spamsink]

Как получено именно это значение?

[vmozgutuman]

посмотрел на калькуляторе когда 364/365 ** n становится меньше половины.

[spamsink]

А если более аккуратно посчитать, через логарифмы?

[sobriquet9]

Тогда 253 получится, ln(0.5)/ln(364/365) и округляем вверх. Но число такое тоже не помню.

[spamsink]

Верно. А как насчет задачи в апдейте?

[vmozgutuman]

2285

[spamsink]

Близко, но неточно. Получено симуляцией?

[vmozgutuman]

зачем симуляцией? "влоб" посчитал. я думаю там просто из-за округлений потерялось.

np.log2(1 - 2 ** (-1/365))/np.log2(364/365)

[spamsink]

Там другая формула получается, и ответ будет чуть выше.

[spamsink]

Виноват, для моей формулировки это правильный ответ. Это у ожидаемого размера группы формула сложнее.

[vmozgutuman]

А мне кажется я глупость написал. События-то не независимы.

[spamsink]

Я подтвердил симуляцией. На одном из запусков 50 тысяч экспериментов, разброс для достижения 365 разных значений составляет от 1259 до 6206, среднее 2362.61854 (ну почти теоретические 2364 с копейками), а медиана как раз 2285.

У меня заняло некоторое время сформулировать это дело на естественном языке:
Вероятность того, что в группе из n человек ни у одного из них день рождения не приходится на один конкретный день года равна (1-1/365)^n (это для удобства копипаста из коммента sobriquet9 ниже). Вероятность, что у кого-нибудь день рождения на на этот конкретный день придётся, равна 1-(1-1/365)^n. Дней в году 365, поэтому возводим в 365-ю степень (для каждого дня года верно, что такой день рождения найдётся), и приравниваем 1/2. После упрощений выходит log(log(2)/365)/log(364/365), чтд.

А для матожидания будет n*HarmonicNumber(n), как написано в https://en.wikipedia.org/wiki/Coupon_collector%27s_problem

[sobriquet9]

2404

[spamsink]

А это как получено? Правильный ответ чуть ниже.

[sobriquet9]

Вероятность того, что в группе из n человек ни у одного из них день рождения не приходится на один конкретный день года равна (1-1/365)^n. Дней в году 365, поэтому умножаем на 365 (в этом месте скорее всего косяк), приравниваем 1/2 и решаем.

[spamsink]

...поэтому вычитаем выражение для конкретного дня года из единицы, возводим в 365-ю степень (для каждого дня года верно, что такой день рождения найдётся хотя бы у одного), и приравниваем 1/2. После упрощений выходит log(log(2)/365)/log(364/365) = 2284.1, округляя вверх для гарантии - 2285.

А я сначала ступил и подумал, что формулировка в https://en.wikipedia.org/wiki/Coupon_collector%27s_problem эквивалентна, но нет - распределение настолько кривое, что медиана сильно отличается от матожидания больше, чем на полсотни. Матожидание равно HarmonicNumber(365)*365 = 2364.6, т. е. 2365.

Симуляция подтверждает оба значения.

[ircicq]

183

[spamsink]

Нет, конечно.

[nicolas83]

Я легко вычислю вероятность для 31 сентября!

[dijifi]

Для вас может и теория, а мне в седьмом классе пришлось одну четверть проучиться в другой школе. А там — ! Да ещё и сосед по парте.

[spamsink]

А уж он-то как удивился!

[dijifi]

Я удивился вторым.

[nicolas83]

Там ФАКТОРИАЛ??

[vak]

22 человека выходит.

[spamsink]

Ты не в ту сторону округлил.