Дочка попросила объяснить "парадокс" дней рождения без использования высшей математики (которую она пока не знает). Попробую.
Итак, в чём "парадокс"? Пусть в году 365 дней (пренебрежём високосными) и дни рождения распределены более или менее однородно. Ясно, что если в группе больше 365 человек, то дни рождения хотя бы у двоих точно совпадут: просто нет ни одного варианта без совпадений, не хватает дней. С другой стороны, вероятность, что у двоих (в группе из двух человек) дни рождения совпадут, маленькая: 1/365.
В самом деле, число способов выбрать два дня из 365, независимо, есть 365²: на каждый вариант первого дня есть 365 вариантов второго. Число же "благоприятных" вариантов, то есть когда дни рождения совпали, равно 365: первый день любой, второй совпадает с первым. Делим одно на другое и получаем 1/365. Эта вероятность меньше, чем вероятность, с которой монета восемь раз подряд упадет одной стороной. Но больше, чем если девять.
Наша интуиция, привыкшая к линейности, предполагает, что вероятность ½ получится где-то на середине интервала, то есть на группах порядка 180 человек. Но парадокс в том, что интуиция грубо ошибается и пограничное число 22-23 человека.
Что это значит? Если вы возьмете много-много групп по 22-23 человека, то примерно в половине найдётся хотя бы одна пара человек с совпадающим днём рождения. А примерно в половине не найдётся.
Почему же так мало? Почему вероятность сначала так быстро растёт: от маленького числа 1/365 для n=2 до примерно 0.5 для n=22, а потом так медленно растёт до 1 при n=366?
Ну, предположим, что при n=180 эта вероятность примерно 0.5. Чуть меньше. Вероятность, что совпадений нет, тогда чуть больше.
Увеличим группу на единицу. Вероятность, что совпадений по-прежнему нет, есть вот то число "0.5 или чуть больше", умноженное на вероятность, что новичок ни с кем не совпал. У нас уже 180 дней заняты, то есть свободны еще 185: около половины. Вероятность наугад попасть примерно 0.5. То есть вероятность СРАЗУ вдвое сдулась, просто от добавления одного человека в группу!
Ясно, что убавление одного человека вероятность почти вдвое увеличит, а это сразу делает невозможным наше предположение.
При больших n вероятность, что совпадений нет, очень мала. Увеличение группы на одного человека её ещё очень сильно понижает. Если n=365, то вероятность, что совпадений нет, чрезвычайно мала: надо поделить число способов выбрать 365 дней из 365 возможных без совпадений, это 365! (факториал), на число способов выбрать 365 дней из 365 возможных вообще, это 365³⁶⁵. По формуле Стирлинга, факториал близок к √(2∙365∙π)365³⁶⁵/e³⁶⁵. Поэтому вероятность имеет порядок 50exp(-365), что невероятно мало. Примерно такую вероятность имеет событие "монета выпала 520 раз одной стороной".
При малых же n вероятность, что совпадений нет, уменьшается при увеличении группы несильно: на вероятность попасть на, скажем один из 350 дней, выбирая из 365. Вот она и снижается, потихоньку, до 0.5 к n=22 или 23.
В общем, причина в том, что при равномерном выборе очень трудно не повторяться. И, кстати, в реальной случайной последовательности повторы (как правило) встречаются чаще, чем в псевдослучайной, которую человек пытается выдать за случайную.
Давайте возьмем десять вариантов и будем равновероятно их выхватывать. Загадывать числа о 0 до 9, например. Поначалу, для первых двоих-троих, можно быть почти уверенным, что твоё число никто не загадал. Но если вас 10 человек, и вы загадываете последним, то ни с кем не совпасть шансы уже малы: если никто пока что не совпал, то вам надо выбрать единственное незагаданное числоЮ одно из десяти. Не очень вероятно.
Но давайте проследим за тем, как ведет себя эта вероятность.
Для группы из двух человек: 0.9
Для группы из трех человек: 0.72
Для группы из четырех человек: 0.504
Для группы из пяти человек: 0.30
Для группы из шести человек: 0.15
Далее 0.06, 0.018, 0.0036 и 0.00036.
Мы видим, что шестой, у которого ровно половина незагаданных и половина загаданных чисел (при условии, что совпадений пока нет), пополам предыдущую вероятность и делит. А десятый делит не на два, а на десять, так как ему, чтобы сохранить отсутствие совпадений, надо выбрать единственное (из десяти) незагаданное число.
На этом простом примере мы видим, как "неровно" меняется вероятность с ростом численности группы, и понимаем, почему так. Хотя именно в этом примере примерно 0.5 достигается примерно на середине (хотя всё-таки при 4, а не при 5).