Birthday Problem Probability

Problem

Compute the probability in the birthday problem: given n people, what is the probability that at least two share the same birthday? Assume 365 equally likely birthdays.

Solution

def birthday_probability(n: int, days: int = 365) -> float:
    """
    n: number of people
    days: number of possible birthdays (default 365)
    Returns: probability that at least two people share a birthday
    """
    if n > days:
        return 1.0
    if n <= 1:
        return 0.0

    # P(no collision) = (365/365) * (364/365) * ... * ((365-n+1)/365)
    p_no_collision = 1.0
    for i in range(n):
        p_no_collision *= (days - i) / days

    return round(1.0 - p_no_collision, 6)

Explanation

1. It is easier to compute the complement: the probability that all n people have different birthdays.
2. Person 1 can have any birthday: 365/365. Person 2 must differ: 364/365. And so on.
3. P(no shared birthday) = product of (365-i)/365 for i = 0 to n-1.
4. P(at least one shared) = 1 - P(no shared birthday).
5. The famous result: with just 23 people, the probability exceeds 50%.

Complexity

• Time: O(n) where n is the number of people
• Space: O(1)