The algorithm of the Birthday Problem

This example demonstrates the implementation and application of an algorithm that solves the generalized birthday problem — determining the minimum number of people in a group at which the probability of matching the birthdays of a certain number of people exceeds a given one.

Introduction

What is the "Birthday Challenge"?

The "birthday problem" is a classic problem in probability theory, which is formulated as follows: what is the probability that at least two people in a group have the same birthday?

Usually, the task is studied for groups of people who are interested in the minimum number at which this probability exceeds 50%. However, it can be expanded: you can search, for example, for the minimum number of people to match the birthdays of three, four, etc.

The original problem has important applications in cryptography and randomness testing, where it is used to assess the likelihood of collisions.

The main part

A function for calculating the probability that a group of groupsize a person at least sharers a person has the same birthday. The Monte Carlo method with the number of repetitions is used. 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

equalbirthdays

We start with a group of 2 people, assuming a minimum size.

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

2 людей в группе из 22 имеют общий день рождения с вероятностью 0.511
3 людей в группе из 86 имеют общий день рождения с вероятностью 0.501
4 людей в группе из 181 имеют общий день рождения с вероятностью 0.504
5 людей в группе из 305 имеют общий день рождения с вероятностью 0.502

Conclusion

We have considered the implementation of an algorithm that solves a generalized birthday problem: calculating the minimum number of people required to have a given probability (in this case, more than 50%) of matching birthdays. k human.

The algorithm uses the Monte Carlo method for statistical probability estimation, which makes it applicable in the case of complex or analytically difficult-to-calculate formulas.

This approach is useful not only in probability theory, but also in other areas where it is important to assess the likelihood of coincidences or collisions (for example, in hashing).

The example was developed using materials from Rosetta Code