Birthday Problem

• 생일 문제(Birthday Problem)
  : 임의로 모인 사람들 중 생일이 같은 두 명이 존재할 확률을 구하는 문제
• Algorithms - Birthday Data.csv
  : 학생들의 이름, 서로 식별 가능한 ID, 생일 날짜 저장
• 사용 언어 : Python

생일이 같은 두 사람을 수동으로 결정하기 위해 pseudo code 작성

bd_problem 함수를 만듦
def bd_problem(총 모인 사람의 인원수):
		n_p 변수 정의
        for문 시작
        for i in range(n_p, 365):
        p 변수 정의
        n_p와 p간의 관계
        최종적인 확률을 probability 변수에 저장
    임의로 모인 사람들의 총 인원수와 그 중 2명 이상의 생일이 겹칠 확률 출력

 

k명의 학생으로 구성된 반에서 생일이 같은 학생이 두 명 이상 있을 확률을 계산하는 코드 작성 (여러 가지 다른 ks를 적용)

아래 코드를 실행하면 2명부터 365명의 학생으로 구성된 반에서 생일이 같은 학생이 두 명 이상 있을 확률을 각각 모두 출력한다.

def bd_problem():
    n_p = 1
    for i in range(1, 365):
        p = i / 365
        n_p *= (1 - p)
        probability = 1 - n_p
        print ("{0}  {1}".format(i+1,probability))

만약 'k명의 학생으로 구성된 반'과 같이 전체 인원을 특정할 경우 함수를 다음과 같이 변경한다.

def bd_problem(n):
    n_p = 1
    for i in range(1, n): //range의 범위를 365에서 n으로 변경
        p = i / 365
        n_p *= (1 - p)
        probability = 1 - n_p
    print ("{0}  {1}".format(n,probability)) //n의 확률만 출력

 

한 교실에 100명의 학생이 있는 경우 생일이 같은 한 쌍의 학생이 있을 가능성이 99.999%임을 입증 (computational experiments 수행)

• 접근 방법
  n_p : 학생들의 생일이 모두 다를 확률
  probability : 생일이 같은 한 쌍의 학생이 있을 확률

• 예시
  

  

• 함수 작성

def bd_problem(n):
    n_p = 1
    print ("{0}    {1}".format("n","probability"))
    for i in range(1, n):
        p = i / 365
        n_p *= (1 - p)
        probability = 1 - n_p
    print ("{0}  {1}".format(n,probability))

• 함수 실행

bd_problem(100) // 100명의 학생이 있는 경우

• 출력 결과

n    probability
100  0.9999996927510721

 

참고 자료

https://betterexplained.com/articles/understanding-the-birthday-paradox/
https://www.vitoshacademy.com/python-the-birthday-paradox-algorithm/