[하버드 확률론 기초 : Statistics 110] 3강- Birthday Problem과 확률의 특성 (Birthday Problem, Properties of Probability)

• Birthday Problem
  k명 중에 2명 이상이 같은 생일을 가질 확률 (일별 출생 확률은 동일하고 각각의 사건은 독립적으로 발생한다고 가정한다)

  k가 몇 명 이상이어야 같은 생일을 가진 사람들이 있을 확률이 50%일까?

  $k≤365$ 라 할 때,

  $\mathrm{P}(\mathrm{k}$ 명의 생일이 모두 다름 $)=\frac{365 \times 364 \times \ldots \times(365-k+1)}{365^k}$

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

  직관적으로 푸는 방법?
  → $\begin{aligned} \left(\begin{array}{c} 23 \\ 2 \end{array}\right)=253 \end{aligned}$ 개의 '짝'이 나옴

• 확률의 Non-naive한 정의
  • 공리
  1. $P(\phi)=0, P(S)=1$
  2. $P\left(\cup_{n-1}^{\infty}=\sum_{n=1}^{\infty} P\left(A_m\right)\left(A_i, A j\right.\right.$ 는 서로소인 사건이다 $)$

• 확률의 특징
  • $P\left(A^C\right)=1-P(A)$
    • 증명) $1=P(S)=P\left(A \cup A^C\right)$
      $\left.=P(A)+P\left(A^C\right) \ldots \text { (공리 } 2\right) \quad$
      $P\left(A \cap A^C\right)=\phi \ldots(\text { 공리 } 1)$
  • $A \subset B$ 인 경우, $P(A) \leq P(B)$
    - 증명) $B=A \cup\left(B \cap A^C\right)$ (두 사건은 서로소)
    $\begin{aligned} & P(B)=P(A)+P\left(B \cup A^C\right) \geq P(A) \\ \end{aligned}$
  • $\begin{aligned} P(A \cup B)=P(A)+P(B)- P(A \cap B) = P(A)+P\left(B \cap A^C\right) \end{aligned}$
    이 때, $P(B)-P(A \cap B)=P\left(B \cap A^C\right)$ 인 경우 등식 성립
    $P(A \cap B)+P\left(A^C \cap B\right)=P(B) \ldots(\text { 공리 } 2)$
    이므로 성립

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

  • 공식:

    $\begin{aligned} & P\left(A_1 \cup A_2 \cup \ldots \cup A_n\right) \\ & =\sum_{j=1}^n P\left(A_j\right)-\sum_{i<j} P\left(A_i \cap A_j\right)+\sum_{i<j<k} P\left(A_i \cap A_j \cap A_k\right)-\ldots+(-1)^n P\left(A_1 \cap A_2\right. \end{aligned}$

    예제) deMontmort's Problem(1713): 카드가 놓인 위치(첫번째, 두번째,...)와 카드에 쓰여있는 숫자가 일치할 확률은 얼마인가?

    무작위로 서여 있는 카드 $1,2, \ldots, \cap$ 중에서, 카드 $j$ 가 $j$ 번째 순서에 놓이는 사건을 $A_j$ 라고 할 때,

    $\begin{aligned} & P\left(A_j\right)=\frac{1}{n} \quad \rightarrow n \text { 가지 } \\ & P\left(A_1 \cap A_2\right)=\frac{(n-2) !}{n !}=\frac{1}{n(n-1)} \rightarrow\left(\begin{array}{l} n \\ 2 \end{array}\right)=\frac{\mathrm{n}(n-1)}{2} \text { 가지 } \\ & \ldots \\ & P\left(A_1 \cap A_2 \cap \ldots \cap A_n\right)=\frac{(n-k) !}{n !} \\ & \end{aligned}$

    그러므로 구하고자 하는 확률인 $P\left(A_1 \cup A_2 \cup \ldots \cup A_m\right)$ 는

    $\begin{aligned} &=P\left(A_1\right)+P\left(A_2\right)+\ldots+P\left(A_n\right)-P\left(A_1 \cup A_2\right)-\ldots+P\left(A_1 \cup A_2 \cup A_3\right)+\ldots \\ &= n \times \frac{1}{n}-\frac{n(n-1)}{2 !} \times \frac{1}{n(n-1)}+\frac{n(n-1)(n-2)}{3 !} \times \frac{1}{n(n-1)(n-2)}-\ldots \\ &= 1-\frac{1}{2 !}+\frac{1}{3 !}-\ldots+(-1)^{n-1} \frac{1}{n !} \rightarrow(\text { 테일러 시리즈 }) \\& \approx 1-\frac{1}{e} \end{aligned}$

    에 근사한다.

본 포스트의 학습 내용은 boostcourse 내의 [하버드] 확률론 기초: Statistics 110 (Prof. Joe Blitzstein) 강의 내용을 바탕으로 작성되었습니다.
(https://www.edwith.org/ai152)