Lecture 3: Birthday Problem, Properties of Probability

✔  본 글은 Harvard Univ. Statistics 110: Probability 강의 "Lecture 3: Birthday Problem과 확률의 특성 (Birthday Problem, Properties of Probability)"를 바탕으로 정리한 내용입니다.

📌 강의 영상: YouTube

📄 강의 슬라이드: PDF 링크

---

Birthday Problem

어떤 파티에서 k명의 사람들의 그룹이 있다고 할 때 n(n>=2)명의 생일이 같을 확률이 얼마나 되는지. 그럼 몇 명의 사람이 있어야 최소한 50% 확률로 2명의 사람이 생일이 같을 수 있을까? (이는 365일 모두 동일한 확률을 가진다고 가정, 각각이 독립이라고도 가정)

 

k > 365일 때는 확률은 1일 것 (반드시 누군가와 겹치기 때문) => 이것이 비둘기 집의 원리(pigeonhole principle)

 

https://ko.wikipedia.org/wiki/%EB%B9%84%EB%91%98%EA%B8%B0%EC%A7%91_%EC%9B%90%EB%A6%AC

비둘기집 원리 - 위키백과, 우리 모두의 백과사전

 

어떤 사건의 확률을 계산할 때는 확률을 직접 찾는 것이 쉬울지 여사건을 계산하는 것이 쉬울지 생각해야 한다.

 

k <= 365일 때는 확률을 계산하기 위해 여사건(compliment)인 모두의 생일이 같지 않을 확률을 계산해 보자.

• ID의 순서대로 한 명씩 파티에 들어오면서, 곱의 법칙(전 사람들의 생일을 제외하고 생일을 가질 수 있음) 적용
• k명이 있다고 가정했으므로 총 k개의 항이 존재해야 함
• k=1 시, 생일이 같은 사람이 없을 확률은 1이므로 365-k+1

\[
P(\text{k명의 생일이 모두 다름}) = \frac{365 \times 364 \times \cdots \times (365 - k + 1)}{365^k}
\]

→  k = 23일 때 50.7%, k = 50일 때 97%, k = 100일 때 99.9%

이걸 보면, k = 23일 때 생일이 겹칠 확률이 50% 이상이며, 계산해 보면 253쌍의 조합이 생긴다. 365일 중 2명이 겹칠 조합이 253쌍이나 된다면 생일이 겹칠 가능성도 꽤 높다는 뜻이므로, 직관적으로 생일이 겹치기 어렵다 생각하지만 실제로는 적은 인원만 있어도 생일이 같을 확률이 꽤 높다는 것을 보여준다.

여기서 생일이 하루 차이 나는 경우까지 확장하면 확률은 더 올라갈 것이다.

즉, 우연, 확률, 조합의 개념이 우리 직관과 다르다는 것을 보여주는 고전적 예시다.

 

확률의 Non-naïve한 정의 (Non-naïve definition of probability)

공리

1. \[
   P(\varnothing) = 0,\quad P(S) = 1
   \]
2. \[
   P\left(\bigcup_{n=1}^\infty A_n\right) = \sum_{n=1}^\infty P(A_n) \quad \text{(단, } A_i \cap A_j = \varnothing \text{ for } i \ne j)
   \]

 

확률의 속성

• \( P(A^C) = 1 - P(A) \)
  • 여사건의 확률
  • Proof) \( 1 = P(S) = P(A \cup A^C) \)
    \( \hspace{1em} = P(A) + P(A^C) \) …(공리2)  \( P(A \cap A^C) = \varnothing \) …(공리1)
• \( A \subseteq B \) 인 경우, \( P(A) \leq P(B) \)
  • 포함 관계에 따른 확률의 크기 
  • Proof) \( B = A \cup (B \cap A^C) \) (두 사건은 서로소)  
      \( \hspace{1em} P(B) = P(A) + P(B \cup A^C) \geq P(A) \)
  • 확률의 정의에 의해 확률은 음수가 될 수 없으므로(0~1) 음수가 아닌 어떤 값을 더할 때 이 값은 P(A)보다 큰 값이 됨
• \( P(A \cup B) = P(A) + P(B) - P(A \cap B) \) 
  • 합집합의 확률 공식
  • Proof) \( P(A \cup B) = P(A \cup (B \cap A^C)) \)  
      \( \hspace{1em} = P(A) + P(B \cap A^C) \)
      이때, \( P(B) - P(A \cap B) = P(B \cap A^C) \) 인 경우 등식 성립  
      \( P(A \cap B) + P(A^C \cap B) = P(B) \) …(공리2)이므로 성립
  • 이 속성은 포함배제의 원리(Inclusion-Exclusion Principle)라 부름

 

포함배제의 원리 (Inclusion-Exclusion Principle)

A, B, C 라는 3개의 사건의 합사건의 확률을 구하기 위해서, 모든 집합을 포함하면 중복되는 부분이 생기며, 이 부분을 배제하면서 포함과 배제를 반복하는 것이다.

\( P\left( \bigcup_{i=1}^n A_i \right) \)
\( = \sum_{i=1}^n P(A_i)
- \sum_{1 \le i < j \le n} P(A_i \cap A_j)
+ \sum_{1 \le i < j < k \le n} P(A_i \cap A_j \cap A_k)
- \cdots
+ (-1)^{n+1} P\left( \bigcap_{i=1}^n A_i \right) \)

 

 

예제: 매칭 문제 (match problem, 또는 몽마르트 문제) 

카드가 놓인 위치(첫번째, 두번째, …)와 카드에 쓰여있는 숫자가 일치할 확률은 얼마인가?

• 대칭성, 포함배제의 문제가 키워드

무작위로 섞여 있는 카드 \(1, 2, \ldots, n\) 중에서, 카드 \(j\)가 \(j\)번째 순서에 놓이는 사건을 \(A_j\)라 할 때,
\[ P(A_j) = \frac{1}{n} \Rightarrow \text{ n가지} \] \[ P(A_1 \cap A_2) = \frac{(n-2)!}{n!} = \frac{1}{n(n-1)} \quad \Rightarrow \quad \binom{n}{2} = \frac{n(n-1)}{2} \text{ 가지} \] \[ \ldots \] \[ P(A_1 \cap A_2 \cap \cdots \cap A_k) = \frac{(n-k)!}{n!} \]
그러므로 구하고자 하는 확률인 \( P(A_1 \cup A_2 \cup \cdots \cup A_n) \) 는 포함배제의 원리에 의해,
\[
\begin{aligned}
P(A_1 \cup A_2 \cup \cdots \cup A_n) 
&= \sum_{j=1}^n P(A_j) - \sum_{1 \le i < j \le n} P(A_i \cap A_j) + \sum_{1 \le i < j < k \le n} P(A_i \cap A_j \cap A_k) - \cdots \\
&= n \times \frac{1}{n} - \binom{n}{2} \times \frac{1}{n(n-1)} + \binom{n}{3} \times \frac{1}{n(n-1)(n-2)} - \cdots \\
&= 1 - \frac{1}{2!} + \frac{1}{3!} - \cdots + (-1)^n \frac{1}{n!}
\end{aligned}
\]
이는 테일러 급수로부터
\[
P(A_1 \cup A_2 \cup \cdots \cup A_n) \approx 1 - \frac{1}{e}
\]
에 근사한다.