Парадокс дней рождения
maximsidorovАлгоритм задачи дней рождения (Birthday Problem)
Этот пример демонстрирует реализацию и применение алгоритма, решающего обобщённую задачу дней рождения — определение минимального количества людей в группе, при котором вероятность совпадения дней рождения у определённого числа человек превышает заданную.
Введение
Что такое "Задача дней рождения"?
"Задача дней рождения" — классическая задача теории вероятностей, которая формулируется следующим образом: какова вероятность того, что хотя бы у двух человек из группы совпадают дни рождения?
Обычно задача изучается для групп людей, где интересуются минимальным количеством, при котором эта вероятность превышает 50%. Однако она может быть расширена: можно искать, например, минимальное количество людей для совпадения дней рождения у троих, четверых и т.д.
Исходная задача имеет важное применение в криптографии и тестировании случайности, где используется для оценки вероятности возникновения коллизий.
Основная часть
Функция для вычисления вероятности того, что в группе из groupsize человек как минимум sharers человек имеют одинаковый день рождения. Используется метод Монте-Карло с числом повторений nrep.
function equalbirthdays(sharers::Int, groupsize::Int; nrep::Int = 10000)
eq = 0 # Счётчик случаев, когда найдено нужное совпадение
for _ in 1:nrep
# Генерируем случайные дни рождения для всех людей в группе
group = rand(1:365, groupsize)
# Преобразуем массив в множество - чтобы убрать повторы
grset = Set(group)
# Условие: дубликатов должно быть достаточно, чтобы
# хотя бы `sharers` человек имели одинаковый день рождения
if groupsize - length(grset) ≥ sharers - 1 &&
any(count(x -> x == d, group) ≥ sharers for d in grset)
eq += 1
end
end
return eq / nrep # Возвращаем частоту успеха
end
Начинаем с группы из 2 человек, предполагая минимальный размер
gsizes = [2]
# Для каждого числа людей, у которых должен совпадать день рождения
for sh in (2, 3, 4, 5)
local gsize = gsizes[end] # Начальное приближение
local freq # Переменная для хранения частоты события
# Первый этап: грубый поиск (меньше итераций для быстрой оценки)
while equalbirthdays(sh, gsize; nrep = 100) < 0.5
gsize += 1
end
# Второй этап: более точный поиск в небольшом диапазоне
for gsize in trunc(Int, gsize - (gsize - gsizes[end]) / 4):(gsize + 999)
if equalbirthdays(sh, gsize; nrep = 250) > 0.5
break
end
end
# Третий этап: точный подсчёт с высокой точностью
for gsize in (gsize - 1):(gsize + 999)
freq = equalbirthdays(sh, gsize; nrep = 50000)
if freq > 0.5
break
end
end
# Сохраняем найденное число людей
push!(gsizes, gsize)
# Вывод результата
@printf("%i людей в группе из %s имеют общий день рождения с вероятностью %5.3f\n", sh, gsize, freq)
end
Заключение
Мы рассмотрели реализацию алгоритма, решающего обобщённую задачу дней рождения: вычисление минимального числа людей, требуемого для того, чтобы с заданной вероятностью (в данном случае — более 50%) совпадали дни рождения у k человек.
Алгоритм использует метод Монте-Карло для статистической оценки вероятности, что делает его применимым в случае сложных или аналитически трудно вычислимых формул.
Такой подход полезен не только в теории вероятностей, но и в других областях, где важно оценить вероятность возникновения совпадений или коллизий (например, в хэшировании).
Пример разработан с использованием материалов Rosetta Code