생일 문제

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 확률 계산
- 2.1. 기본 계산
- 2.2. 근사
3. 일반화
4. 응용
5. 기타 변형 문제
6. 한국 문화 속의 생일 문제
참조

1. 개요

생일 문제는 임의의 집단에서 생일이 같은 두 사람이 존재할 확률에 대한 문제이다. 366명 이상이 있다면 비둘기집 원리에 따라 생일이 같은 두 사람이 반드시 존재하며, 365명 이하의 경우, n명의 사람이 있을 때 생일이 같은 사람이 적어도 두 명 이상 있을 확률을 계산할 수 있다. 23명일 때 생일이 같은 사람이 있을 확률이 약 50%를 넘고, 50명일 때는 약 97%가 된다. 이러한 확률 계산은 순열을 통해서도 동일하게 계산할 수 있으며, 지수 함수를 이용한 근사식으로도 나타낼 수 있다. 생일 문제는 일반화된 형태로도 나타낼 수 있으며, 암호 시스템의 생일 공격, 해시 함수, 의사 난수 생성기 등 다양한 분야에 응용된다.

더 읽어볼만한 페이지

우연 - 링컨과 케네디의 공통점
링컨과 케네디의 공통점은 암살, 부통령의 대통령직 승계, 흑인 인권 문제 관여 등 두 미국 대통령 사이의 여러 우연의 일치로 여겨지지만, 단순한 우연이거나 아포페니아 현상일 수 있다는 비판도 있다.
확률론의 역설 - 몬티 홀 문제
몬티 홀 문제는 세 개의 문 중 하나를 선택한 후 진행자가 상품이 없는 문을 열어 보여줄 때, 선택을 바꾸는 것이 유리한지를 묻는 확률 문제로, 직관과 달리 선택을 바꾸는 것이 당첨 확률을 높이는 전략임을 보여주는 확률 역설이며, 의사 결정 방식에 대한 통찰을 제공한다.
확률론의 역설 - 상트페테르부르크의 역설
상트페테르부르크의 역설은 기대값이 무한대인 도박 게임에서 사람들이 기대값보다 훨씬 적은 금액을 지불하려 하는 현상을 보이는 확률론의 역설로, 동전 던지기 게임을 통해 설명되며, 기대 효용 이론, 유한한 상트페테르부르크 복권, 확률 가중치 등의 개념으로 설명하려는 시도가 있다.
응용확률론 - 자급자족
자급자족은 개인이 스스로 생산한 것만 소비하며 자립적 건축, 지속 가능한 농업, 재생 에너지 등을 통해 실현되는 지속 가능한 삶의 방식이다.
응용확률론 - 진폭 편이 방식
진폭 편이 방식(ASK)은 반송파의 진폭을 변화시켜 데이터를 표현하는 변조 방식이며, 온오프 변조와 다치 ASK가 있으며, 오류 확률은 다양한 요인에 의해 영향을 받는다.

생일 문제
개요
이름	생일 문제
다른 이름	생일 역설
유형	확률
관련 개념	비둘기집 원리
문제 설명
질문	임의의 n명의 사람들 중에서 적어도 두 사람의 생일이 같을 확률은 얼마인가?
역설	23명만 되어도 생일이 같은 두 사람이 존재할 확률이 50%를 넘는다는 사실은 직관과 모순된다.
확률 계산
가정	1년은 365일이다. (윤년은 고려하지 않음) 각 날짜에 태어날 확률은 동일하다.
계산 방법	모든 사람의 생일이 다를 확률을 계산한 후, 1에서 빼는 방식으로 계산한다. n명이 있을 때, 모든 사람의 생일이 다를 확률은 (365/365) * (364/365) * (363/365) * ... * ((365-n+1)/365) 이다.
공식	P(n) = 1 - (365! / ((365 - n)! * 365^n))
확률 값
n = 10	11.7%
n = 20	41.1%
n = 22	47.6%
n = 23	50.7%
n = 30	70.6%
n = 50	97.0%
n = 57	99.0%
n = 70	99.9%
일반화
d일	d개의 가능한 생일이 있는 경우, n명이 있을 때 두 사람이 같은 생일을 가질 확률은 다음과 같다.
일반화 공식	1 - (d! / ((d - n)! * d^n))
응용
해시 함수	해시 함수의 충돌 확률을 계산하는 데 사용될 수 있다.
생물학	DNA 서열 분석에서 특정 패턴이 우연히 나타날 확률을 계산하는 데 사용될 수 있다.
통계학	무작위 표본 추출에서 중복된 표본이 나올 확률을 계산하는 데 사용될 수 있다.
참고 자료
참고 문헌	http://www.math.ucsd.edu/~crypto/Monty/birthday.html http://www.cut-the-knot.org/do_you_know/birthday.shtml
관련 항목	비둘기집 원리

2. 확률 계산

생일이 같은 두 사람이 존재할 확률을 직접 계산하는 것은 어렵기 때문에, 모든 사람의 생일이 다를 확률을 계산하여 전체 확률(1)에서 빼는 방법이 사용된다.

366명 이상이 모이면 비둘기집 원리에 따라 생일이 같은 두 사람이 반드시 존재한다.^[27]

(내용 생략 - '기본 계산', '근사' 하위 섹션과 중복)

23명으로 이루어진 그룹에서 생일이 겹치지 않을 확률을 ''A''라고 하고, 최소 두 명의 생일이 같을 확률을 ''B''라고 하면, ''B'' = 1 - ''P''(''A'')가 된다. 순열을 사용하면, ''P''(''A'')는 다음과 같이 계산할 수 있다.

: $\begin{align} V_{nr} &= \frac{365!}{(365-23)!} \\[8pt] V_t &= 365^{23} \\[8pt] P(A) &= \frac{V_{nr}}{V_t} \approx 0.492703 \\[8pt] P(B) &= 1 - P(A) \approx 0.507297 \quad (50.7297\%)\end{align}$

폴 할모스는 자서전에서 생일 문제의 계산 방식보다 추상적인 수학적 개념을 사용하는 것이 더 중요하다고 강조했다. 그는 부등식을 이용해 1~2분 안에 확률을 구할 수 있지만, 곱셈은 더 오래 걸리고 오류가 발생하기 쉽다고 지적했다.

2. 1. 기본 계산

n

명의 사람이 있을 때, 모든 사람의 생일이 다를 확률은 다음과 같이 계산된다.

:

\bar p(n) = 1 \times \left(1-\frac{1}{365}\right) \times \left(1-\frac{2}{365}\right) \times \cdots \times \left(1-\frac{n-1}{365}\right) = { 365! \over 365^n (365-n)!}

여기서, n≤365 인 자연수이고, !는 계승 (수학)을 의미한다.

따라서, 생일이 같은 사람이 적어도 두 명 이상 있을 확률

p(n)

은

:

p(n) = 1 - { 365! \over 365^n (365-n)!}

가 된다.

이 식을 이용해 계산하면, 23명일 때 확률이 약 50.7%, 50명일 때 약 97.0%가 된다.

n	p(n)
1	0.0%
5	2.7%
10	11.7%
20	41.1%
23	50.7%
30	70.6%
40	89.1%
50	97.0%
60	99.4%
70	99.9%
100	99.99997%
200	99.9999999999999999999999999998%
300	(100 − (6×10⁻⁸⁰))%
350	(100 − (3×10⁻¹²⁹))%
365	(100 − (1.45×10⁻¹⁵⁵))%
366	100%
367	100%

2. 2. 근사

비둘기집 원리에 따라 366명 이상이 모이면 생일이 같은 두 사람이 반드시 존재한다.^[27] 365명 이하일 경우, n명의 사람이 있을 때 생일이 같은 사람이 두 명 이상 있을 확률을 p(n)이라 하면, 모든 사람의 생일이 다를 확률 $\bar p(n)$은 $1-p(n)$이다. $\bar p(n)$을 먼저 구하면 다음과 같다.

:

\begin{align} \bar p(n) &= 1 \times \left(1-\frac{1}{365}\right) \times \left(1-\frac{2}{365}\right) \times \cdots \times \left(1-\frac{n-1}{365}\right) \\ &= { 365 \times 364 \times 363 \times \cdots \times (365-n+1) \over 365^n } \\ &= { 365! \over 365^n (365-n)!} \end{align}

따라서 생일이 같은 사람이 두 명 이상 있을 확률 p(n)은

:

\begin{align} p(n) &= 1 - { 365! \over 365^n (365-n)!} \end{align}

가 된다. 여기서 n≤365 인 자연수이고, !는 계승 (수학)을 의미한다.

특정 n 값에 대해 p(n)을 계산하면 다음과 같다.

n	p(n)
1	0.0%
5	2.7%
10	11.7%
20	41.1%
23	50.7%
30	70.6%
40	89.1%
50	97.0%
60	99.4%
70	99.9%
100	99.99997%
200	99.9999999999999999999999999998%
300	(100 − (6×10⁻⁸⁰))%
350	(100 − (3×10⁻¹²⁹))%
365	(100 − (1.45×10⁻¹⁵⁵))%
366	100%
367	100%

즉, 50명만 모여도 생일이 같은 두 명 이상이 있을 확률은 97%이고, 100명이 모이면 거의 1에 가까워진다.

지수 함수의 테일러 급수 전개 (상수 e ≈ 2.718281828)는 다음과 같다.

: $e^x = 1 + x + \frac{x^2}{2!}+\cdots$

|x| << 1일 때 e^x에 대한 1차 근사를 제공한다.

: $e^x \approx 1 + x.$

이 근사를 사용하여, $\bar p(n)$을 근사할 수 있다.

: $\begin{align}\bar p(n) & \approx 1 \cdot e^{-1/365} \cdot e^{-2/365} \cdots e^{-(n-1)/365} \\[6pt]& = e^{-\big(1+2+ \,\cdots\, +(n-1)\big)/365} \\[6pt]& = e^{-\frac{n(n-1)/2}{365}} = e^{-\frac{n(n-1)}{730}}.\end{align}$

따라서,

: $p(n) = 1-\bar p(n) \approx 1 - e^{-\frac{n(n-1)}{730}}.$

더욱 단순화된 근사식은 다음과 같다.

: $p(n)\approx 1-e^{-\frac{n^2}{730}}$

푸아송 분포를 이용한 근사도 가능하다. 23명의 그룹에 대해 푸아송 근사를 적용하면 다음과 같다.

: $\operatorname{Poi}\left(\frac{\binom{23}{2}}{365}\right) =\operatorname{Poi}\left(\frac{253}{365}\right) \approx \operatorname{Poi}(0.6932)$

따라서

: $\Pr(X>0)=1-\Pr(X=0) \approx 1-e^{-0.6932} \approx 1-0.499998=0.500002.$

이 근사는 $e^x \approx 1 + x$를 사용하는 테일러 전개에 기반한 위의 근사와 동일하다.

윤년, 쌍둥이 등은 고려하지 않고, 365일 모두 동일한 확률이라고 가정한다.^[4]^[5] 실제 생일 분포는 균등하지 않지만, 근사적으로 계산할 때는 이 가정을 사용한다.

3. 일반화

Birthday problem|생일 문제^영어는 일반적인 경우로 확장될 수 있다. d일을 가진 해를 기준으로, '''일반화된 생일 문제'''는 n명의 무작위로 선택된 사람들 집합에서 생일이 일치할 확률이 최소 50%가 되도록 하는 최소 숫자 n(d)를 묻는 문제이다. 즉, n(d)는 다음을 만족하는 최소 정수 n이다.

: $1-\left(1-\frac{1}{d}\right)\left(1-\frac{2}{d}\right)\cdots\left(1-\frac{n-1}{d}\right)\geq \frac{1}{2}.$

따라서 고전적인 생일 문제는 n(365)를 결정하는 것과 같다. n(d)에 대한 여러 경계 및 공식이 발표되었다.^[9] 어떤 d ≥ 1에 대해, 숫자 n(d)는 다음을 만족한다.^[10]

: $\frac{3-2\ln2}{6}$

이 경계는 n(d) - 가 임의로 (3-2ln2)/6 ≈ 0.27에 가까워진다는 점에서 최적이다. 반면, d < 43 에 대해 최댓값으로 9 - ≈ 1.28을 갖는다.

이 경계는 대부분의 경우 n(d)의 정확한 값을 제공할 만큼 충분히 좁다. 예를 들어, d = 365에 대해, 이러한 경계는 22.7633 < n(365) < 23.7736임을 의미하며, 23이 해당 범위의 유일한 정수이다. 일반적으로, 이러한 경계로부터 n(d)는 항상 다음 중 하나와 같다.

: $\left\lceil\sqrt{2d\ln2}\,\right\rceil \quad\text{또는}\quad \left\lceil\sqrt{2d\ln2}\,\right\rceil+1$

여기서 는 천장 함수를 나타낸다.

다음 공식

: $n(d) = \left\lceil\sqrt{2d\ln2}\,\right\rceil$

은 모든 정수 d의 73%에 대해 성립한다.^[11] 공식

: $n(d) = \left\lceil\sqrt{2d\ln2}+\frac{3-2\ln2}{6}\right\rceil$

은 거의 모든 d, 즉 점근 밀도가 1인 정수 집합 d에 대해 성립한다.^[11]

다음 공식

: $n(d)=\left\lceil \sqrt{2d\ln2}+\frac{3-2\ln2}{6}+\frac{9-4(\ln2)^2}{72\sqrt{2d\ln2}}\right\rceil$

은 모든 d ≤ 10¹⁸에 대해 성립하지만, 이 공식에 대한 반례가 무한히 많을 것으로 추측된다.^[12]

다음 공식

: $n(d)=\left\lceil \sqrt{2d\ln2}+\frac{3-2\ln2}{6}+\frac{9-4(\ln2)^2}{72\sqrt{2d\ln2}}-\frac{2(\ln2)^2}{135d}\right\rceil$

은 모든 d ≤ 10¹⁸에 대해 성립하며, 이 공식이 모든 d에 대해 성립할 것으로 추측된다.^[12]

n(d)의 처음 99개 값은 다음 표와 같다.

d	1–2	3–5	6–9	10–16	17–23	24–32	33–42	43–54	55–68	69–82	83–99
n(d)	2	3	4	5	6	7	8	9	10	11	12

유사한 계산을 통해 d가 341–372 범위에 있을 때 n(d) = 23임을 알 수 있다.

3. 1. 여러 명이 생일을 공유할 확률

정신적 계산에 사용할 수 있는 좋은 경험 법칙은 다음과 같다.^[7]

:

p(n,d) \approx \frac{n^2}{2d}

이는 다음과 같이 쓸 수도 있다.

:

n \approx \sqrt { 2d \times p(n)}

이것은 확률이 1/2 이하일 때 잘 작동한다. 이 방정식에서 d는 1년의 일수이다.

예를 들어, 생일이 같을 확률이 1/2인 경우 필요한 사람 수를 추정하려면 다음과 같다.

:

n \approx \sqrt{ 2 \times 365 \times \tfrac12} = \sqrt{365} \approx 19

이것은 정확한 답인 23과 크게 다르지 않다.

다음과 같은 공식을 사용하여, 생일이 일치할 확률이 1/2 이상이 되기 위한 ''사람 수''를 근사할 수 있다.

:

n \geq \tfrac{1}{2} + \sqrt{\tfrac{1}{4} + 2 \times \ln(2) \times 365} = 22.999943.

이것은 1/k의 확률을 가진 사건이 k ln 2번 반복될 경우, 적어도 한 번 발생할 확률이 1/2이라는 좋은 근사에서 비롯된다.

집단 내에서 생일을 공유하는 사람이 3명, 4명, 5명 등이 될 확률이 50%를 초과하려면 얼마나 많은 사람이 필요할지 질문할 수 있다.

처음 몇 가지 값은 다음과 같다. 생일을 공유하는 3명의 사람이 있을 확률이 50%를 초과하려면 88명이 필요하고, 생일을 공유하는 4명의 사람이 있을 확률이 50%를 초과하려면 187명이 필요하다.^[13]

3. 2. 특정 생일을 공유할 확률

Birthday problem|생일 문제^영어에서는 다른 사람과 생일이 같은 특정한 사람(예: 당신)이 있을 확률을 다룬다. ''n''명의 다른 사람이 있는 방에서 적어도 한 명이 당신과 같은 생일을 가질 확률 ''q''(''n'')는 다음과 같다.

:

q(n) = 1 - \left( \frac{365-1}{365} \right)^n

일반적인 ''d''일(날짜)의 경우 다음을 따른다.

:

q(n;d) = 1 - \left( \frac{d-1}{d} \right)^n.

''d'' = 365 (일반적인 경우)에서 ''n'' = 23을 대입하면 약 6.1%가 되는데, 이는 16번 중 1번 미만의 확률이다. ''n''명의 사람이 있는 방에서 적어도 한 명의 다른 사람이 당신과 같은 생일을 가질 확률이 50% 이상이 되려면, ''n''은 최소 253명이 되어야 한다. 이 숫자는 365/2 = 182.5 보다 훨씬 크다. 그 이유는 방 안의 다른 사람들 사이에 생일이 일치하는 경우가 있을 가능성이 높기 때문이다.

어떤 집단에서 ''n''명의 사람이 있을때, "당신"이 들어갔을 경우 당신과 같은 생일을 가진 사람이 있을 확률 ''p''₃는 다음과 같다.

:

p_3(n) = 1- \left( \frac{364}{365} \right)^n

''n'' = 23이라면, ''p''₃ = 0.0611…이다. ''n''이 253일 때 처음으로 ''p''₃가 0.5 이상이 된다.

3. 3. 최근접 생일

k^영어일 이내로 생일이 가까운 사람이 있을 확률은 다음과 같이 계산할 수 있다.^[18]

:

p(n,k,d) = 1 - \frac{ (d - nk -1)! }{ d^{n-1} \bigl(d - n(k+1)\bigr)!}

여기서

n

은 그룹 내 사람 수,

k

는 생일 간격 (일),

d

는 가능한 생일 수(보통 365)이다.

어떤 쌍의 생일이

k

일 이내일 확률이 50%를 초과하기 위해 필요한 사람의 수는 다음 표와 같다.

$k$	$n$ ( $d$ = 365 일 때)
0	23
1	14
2	11
3	9
4	8
5	8
6	7
7	7

표에서 볼 수 있듯이, 무작위로 선택된 7명의 그룹에서는 그들 중 두 명이 서로 일주일 이내에 생일을 가질 확률이 50%를 넘는다.^[18]

4. 응용

생일 문제는 암호화 해시 함수의 충돌 가능성을 이용한 암호학의 생일 공격(Birthday attack)에 응용될 수 있다. 해시값이 N비트인 암호화 해시 함수에서 특정 해시값을 갖는 메시지를 찾는 원상 공격의 기댓값은 2^N-1이지만, 같은 해시값을 갖는 두 개의 다른 메시지를 찾는 충돌 공격(생일 공격)의 기댓값은 생일 문제에 의해 2^N/2으로 훨씬 작다. 따라서 암호화 해시 함수의 사용 목적에 따라 필요한 해시값의 크기에 주의해야 한다.

블록 암호 알고리즘을 CTR 모드로 사용한 의사 난수 생성기에도 생일 문제가 응용된다. 블록 길이를 L이라고 할 때, 2^L/2 정도의 블록 분량의 난수 출력을 수행하면 1/2의 확률로 진정한 난수와 구별할 수 있다.

통계학에서 표지-재포획법은 호수 내 물고기 개체 수 추정에 사용된다.^[8]

4. 1. 생일 공격

(b^영어)해시 공간 크기
(2^b)적어도 하나의 해시 충돌 확률이 p^영어가 되도록 해시된 요소의 수p^영어 = 10^-18p^영어 = 10^-15p^영어 = 10^-12p^영어 = 10^-9p^영어 = 10^-6p^영어 = 0.001p^영어 = 0.01p^영어 = 0.25p^영어 = 0.50p^영어 = 0.758322222.99316646.13212864256128512