Речь пойдет об известном парадоксе "23-х гостей". Встретил статью на Дзене написанную каким-то дилетантом. Решил написать об этом парадоксе еще раз, на этот раз правильным языком, используя правильный метод теории вероятности для решения.
Итак, о чем же речь? Представьте, что вы находитесь на вечеринке и гости решили узнать дату рождения каждого из присутствующих. Какова вероятность события, что найдется хотя бы одна пара гостей, родившихся в один день, т.е. в один день и месяц (год рождения не рассматривается)?
На первый взгляд, это весьма редкое событие. В году 365 дней и если гостей немного, например, 10, то, казалось бы, грубая оценка дает в этом случае "приблизительный ответ" 10/365 = менее 3%. А для 20 человек 5,5%.
Разумеется, более-менее искушенные в комбинаторной вероятности люди не станут делать такие грубые (и совершенно ни на чем не основанные) "оценки". Но "здравый смысл" упорно предлагает нечто подобное. Собственно, поэтому подобные феномены и называются парадоксами. Наше первое, "естественное" предположение, основанное на интуиции, оказывается очень далеким от истины.
Итак, формулируем задачу: Начиная с какого k вероятность совпадения дат рождения (день/месяц) хотя бы у двух людей из группы в k человек превышает 50%?
Попробуйте задать этот вопрос коллегам на работе или друзьям. Какие ответы вы получите? 180? 100? 50? Оказывается, ответ - 23 человека! Т.е. в компании из 23 человек скорее найдется пара людей с совпадающим днем рождения, чем нет. Таким образом, в каждом школьном классе, в каждой учебной группе в институте, численность которых, как правило, ближе к 30, очень вероятно найти двух человек, празднующих день рождения одновременно.
Теперь посчитаем, "ученые кроты", как говаривали персонажи из мультфильма "Дюймовочка":
При решении задач по теории вероятности всегда важно понять, что такое "элементарное событие" и что такое совокупность этих событий, называемая "пространство элементарных событий". Обозначим через N число дней в году, N = 365. Обозначим через k число гостей на нашей вечеринке, посвященной решению задач по теории вероятности. Что такое "элементарное событие"? Это конкретная реализация набора дней рождений в случайном эксперименте.
Ах, да, еще у нас есть понятие "эксперимент". Если мы бросаем монетку, то каждый подброс - это "эксперимент". Результат эксперимента герб "Г" или решка "Р". В рассматриваемой задаче один "эксперимент" это один конкретный набор дней рождений некоторой компании из k человек. Если договоримся обозначить день рождения первого участника вечеринки как ДР1, второго - ДР2 и т.д., то результат эксперимента будет набор длиной k, вектор:
(ДР1, ДР2, ДР3,...,ДРk).
Совокупность всех таких упорядоченных наборов и есть наше пространство элементарных событий. Я подчеркиваю слово упорядоченных, потому что это важно. Я буду решать задачу исходя из того, что порядок людей в группе зафиксирован и порядок ДРi в наборе имеет значение. Если набор считается упорядоченным, то для k = 2 пара (01-января, 01-июля) и пара (01-июля, 01-января) считаются различными. Можно решать задачу, рассуждая о неупорядоченных наборах. Решение будет практически таким же, но мы должны "договориться на берегу", о каких наборах мы говорим. От этого зависит мощность пространства элементарных событий. В статье я выбрал упорядоченные наборы.
Итак, если у нас есть k перенумерованных участников вечеринки, от 1 до k, и одно элементарное событие это набор (ДР1, ДР2, ДР3,...,ДРk), то какова мощность пространства всех элементарных событий? Сколько всего таких наборов?
Вопрос простой. Первый участник имеет 365 возможностей для своего ДР1. Т.е. на первом месте нашего набора мы имеем N = 365 вариантов. То же самое можно сказать про второго участника. Мы имеем 365*365 вариантов для набора длиной 2. Для набора длиной k мы имеем N*N*N*...*N = N^k (N в степени k) вариантов. Итак, всего у нас N^k всевозможных упорядоченных k-векторов, каждый из которых - одна из возможных реализаций для случайной компании из k участников.
Теперь вспомним о том, что же мы хотим подсчитать? Мы хотим подсчитать вероятность некоторого события. А именно, вероятность того, что какие-то два ДРi и ДРj совпали. Обозначим это событие буквой А. Мы хотим подсчитать вероятность Р(А) (Р - от слова probability). Для этого нам нужно как-то подсчитать все наборы (ДР1,...,ДРk), в которых есть совпадающие (хотя бы два) элементы. Но совпадать может не два, а три элемента, или 4, или все k элементов!
В принципе, не особая проблема подсчитать все эти совпадения "в лоб", но мы воспользуемся стандартным приемом теории вероятности. Подсчитаем вероятность обратного события. Это сильно упрощает расчет.
Обратное событие к А - это дополнение к событию А, "не А". Если В - событие, обратное к А, то В наступает тогда и только тогда, когда не наступает А. В нашем случае событие В заключается в том, что в наборе (ДР1,...,ДРk) нет повторяющихся элементов.
Действительно, рассмотрим любой набор ДР длиной k. Если в нем есть хотя бы два совпадающих элемента, то он относится к событию А. В противном случае он относится к событию В. Таким образом, события А и В непересекающиеся и в совокупности составляют полное пространство элементарных событий.
И тогда Р(А) + Р(В) = 1. Поэтому будем считать Р(В). А какие элементарные события, k-векторы, входят в событие В? Те упорядоченные наборы, которые не имеют повторяющихся элементов. Такие наборы называются "размещениями из N по k". Выведем формулу для числа размещений "из N по k":
Для первого элемента мы имеем N вариантов выбора.
Для второго элемента на 1 меньше, (N-1), так как второй элемент не может совпадать с первым, который уже выбран.
Для третьего элемента остается (N-2) возможности.
Для k-го элемента останется (N-(k-1)) = (N-k+1) возможностей.
Итого мы имеем N*(N-1)*(N-2)*…*(N-k+1) вариантов для построения набора длины k из N возможных элементов. Обычно эта формула записывается в следующем виде:
A(N, k) = N!/(N-k)!, где восклицательный знак "!" обозначает операцию "факториал", т.е. произведение последовательных натуральных чисел от 1 до N.
Ну вот, почти все готово. Формально говоря, все готово. Мы знаем мощность события В. Следовательно, мы знаем вероятность события Р(В).
Р(В) = (мощность В)/(мощность пространства элементарных событий)
Р(В) = A(N, k)/(N^k)
Ну и самое последнее:
Р(А) = 1 - Р(В).
Готово?
Однако, теория вероятности - практическая наука, особенно когда речь идет о комбинаторике. Мы получили формулу Р(В), давайте посмотрим на нее:
Р(В) = N*(N-1)*…*(N-k+1)/(N*N*...*N)
В числителе k множителей, в знаменателе так же k множителей. Как это подсчитать практически, как получить число, вероятность в процентах? Ведь нам еще нужно ответить на вопрос статьи. А для этого нам придется подсчитать Р(А) для различных k. Как? Подсчитать "в лоб" не получится. Не хватит не только калькулятора, но и старый добрый Excel посмотрит на вас с укоризной, если вы попытаетесь возвести 365 в 20-ю степень. Что же делать?
Для начала, перепишем формулу, перегруппировав множители:
Р(В) = P(B, k) = (N/N)*((N-1)/N)*((N-2)/N)*…*((N-k+1)/N)
Напомню, что N = 365, наша константа. А k - переменная. И наша вероятность Р(В) есть функция от переменной k. Как же ведет себя функция Р(В, k) при изменении k? Смотрим на последнюю запись формулы и замечаем, что каждое увеличение k на единицу добавляет к формуле новый множитель. Причем первый множитель в формуле (N/N) = 1, а вот все последующие меньше 1.
Таким образом наша функция вероятности события В убывает с ростом k. Вспоминаем, что есть В? Это вероятность того, что в компании из k человек нет совпадающих дней рождения. Чем больше компания, тем менее вероятно такое событие. Все верно. А раз наше основное событие А есть обратное к событию В, то его вероятность растет с ростом k. Чем больше людей в компании, тем вероятнее, что найдется пара с совпадающими днями рождения.
И все же, как считать будем? А вот как, последовательно! Заметим, что:
P(B, k+1) = P(B, k)*((N-k)/N)
И все!
Минимальное k, для которого задача имеет смысл, k = 2.
P(B, 2) = (365/365)*(364/365) = 99,7%
Легко рассчитываем эту вероятность, заодно тестируем нашу формулу на простом случае.
А дальше используем нашу рекуррентную связь между P(B, k+1) и P(B, k). Каждый шаг заключается в умножении уже известного значения на короткую дробь с одним числом в числителе и одним числом в знаменателе:
P(B, 3) = P(B, 2)*(363/365) = 99,2%
P(B, 4) = P(B, 3)*(362/365) = 98,4%
Такое вычисление "по цепочке" легко реализуется в любом табличном процессоре а-ля Excel. На калькуляторе считать грустно, но все-таки возможно. Но в Excel в несколько кликов получаем:
P(B, 22) = 52,4%
P(B, 23) = 49,3%, что означает
P(A, 23) = 1 - 49.3% = 50.7%
Т.е. начиная с k = 23 вероятность найти двух человек с совпадающим днем рождения превышает 50%.
Спасибо за внимание.