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 # A counter for cases when the desired match was found.
    for _ in 1:nrep
        # Generating random birthdays for all people in the group
        group = rand(1:365, groupsize)
        # Converting an array into a set to remove repetitions
        grset = Set(group)
        # Condition: there must be enough duplicates to
        # at least the `sharers` of the person had the same birthday
        if groupsize - length(grset) ≥ sharers - 1 &&
            any(count(x -> x == d, group) ≥ sharers for d in grset)
            eq += 1
        end
    end
    return eq / nrep # Returning the success rate
end

equalbirthdays

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

gsizes = [2]

# For each number of people who must have the same birthday
for sh in (2, 3, 4, 5)
    local gsize = gsizes[end] # Initial approximation
    local freq # A variable for storing the frequency of an event

    # First stage: rough search (fewer iterations for quick evaluation)
    while equalbirthdays(sh, gsize; nrep = 100) < 0.5
        gsize += 1
    end

    # The second stage: a more accurate search in a small range
    for gsize in trunc(Int, gsize - (gsize - gsizes[end]) / 4):(gsize + 999)
        if equalbirthdays(sh, gsize; nrep = 250) > 0.5
            break
        end
    end

    # The third stage: accurate counting with high accuracy
    for gsize in (gsize - 1):(gsize + 999)
        freq = equalbirthdays(sh, gsize; nrep = 50000)
        if freq > 0.5
            break
        end
    end

    # Saving the found number of people
    push!(gsizes, gsize)

    # Output of the result
    @printf("%i of the people in the group of %s have a common birthday with a probability of %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