너와 나의 생일이 같을 확률은? 생일 문제(Birthday Problem)

생일 문제란?

N명이 있을 때, 두 명 이상이 같은 생일을 가질 확률을 구하는 문제이다. 이제, 1년 365일 중에서 N명이 생일을 랜덤 하게 가질 때, 같은 생일이 발생할 확률을 구한다.

• M = 가능한 생일 개수 (1년 365일)
• N = 사람 인원수

회사에 팀원이 한 사람씩 새로 들어왔을 때 생일이 같을 확률을 구한다고 생각하면 이해가 빠르다.

생일 문제 공식

두 명 이상이 같은 생일을 가질 확률을 계산하는 공식은 다음과 같다.

우선, 생일이 중복되지 않을 확률을 곱해주고 1을 빼주면 우리가 원하는 생일이 중복될 확률을 얻을 수 있다.

(*이는 여사건의 확률(Complement Rule)이라고 한다.)

또는 지수 함수 근사 공식을 사용하여:

• N = 사람 수 (생일을 가지는 사람의 수)
• M = 가능한 생일 개수 (365일)

예제 코드

class Test
{
    static void Main(string[] args)
    {

        Console.WriteLine($"people | collision probablilty");
        Console.WriteLine($"--------------------------------");
        for (int i = 1; i <= 50; i++)
        {
            var result = CalculateBirthDayCollision(i, 365);
            Console.WriteLine($"{i,6} | {result:P2}%");
        }
    }

    static double CalculateBirthDayCollision(int N, int M)
    {
        double probability = 1;

        for (int i = 0; i < N; i++)
        {
            probability *= (double)(M - i) / (double)M;
        }

        return (1 - probability);
    }
}

코드 설명

• M = 365 (1년 365일)
• N명이 있을 때, 모두 다른 생일 가질 확률을 계산 후 1 - P로 같은 생일을 가질 충돌 확률을 구함

지수 함수 근사 공식을 사용한 예제

위의 예제는 for 구문을 사용하여 확률을 구하지만, 지수 함수를 활용한 근사 공식을 사용하면 속도가 더 빠르다.

class Test
{
    static void Main(string[] args)
    {
        Console.WriteLine($"people | collision probablilty");
        Console.WriteLine($"--------------------------------");
        for (int i = 1; i <= 50; i++)
        {
            var result = CalculateBirthDayCollisionApprox(i, 365);
            Console.WriteLine($"{i,6} | {result:P2}%");
        }
    }

    static double CalculateBirthDayCollisionApprox(int N, int M)
    {
        // P ≈ 1 - e^(-N^2 / (2M))
        double exponent = -((double)(N * N) / (2 * M));

        return (1 - Math.Exp(exponent));
    }
}

함께 읽으면 좋은 글

생일 역설 (Birthday Paradox)