원본 영상: Lecture 3: Birthday Problem, Properties of Probability | Statistics 110

Birthday Problem

=> 한 그룹의 k명의 사람들 중 생일이 같은 사람이 있을 확률.(365일이 equally likely)
만약 k > 365인 경우 확률은 1이다.(비둘기집의 원리)
k $\leq$ 365인 경우, 직접적으로 구하는 데에는 어려움이 있기 때문에, complement(여사건)을 이용해서 구할 것이다.
Ex. 2명의 생일이 다를 확률 $\frac{365}{365} * \frac{364}{365}$ 로 나타낼 수 있다.
고로, k명의 생일이 다를 확률

• P(no match) = $\frac{365*364*363...*(365-k+1)}{365^k}$

로 나타낼 수 있다.
그리고 1에서 빼주면 k명중 생일이 같은 사람이 있을 확률이 나온다.

Non-naive definition

Axioms

(1) P($\emptyset$) = 0, P(S) = 1
(2) P($\cup^\infin_{n=1}A_n)=\sum^\infin_{n=1}P(A_n)$ if A_1, A_2 are disjoint events.

Properties

(1) $P(A^c)=1-P(A)$

proof. $1=P(S)=P(A\cup A^c)=P(A)+P(A^c)$ since $A\cap A^c = \emptyset$

(2) $If\space A\subseteq B,then\space P(A)\subseteq P(B)$

=> 한마디로, A가 발생하면, B가 발생한다는 말.
proof. $B=A\cup (B\cap A^c)$ => 여기서, $A$와 $B\cap A^c$은 disjoint한 관계.
고로, 두 번째 axiom을 활용하면, $P(B) = P(A)+P(B\cap A^c)\geq P(A)$ 가 됨.

(3) $P(A\cup B)=P(A)+P(B)-P(A\cap B)$

proof. $P(A\cup B)=P(A\cup (B\cap A^c))=P(A)+P(B\cap A^c)$
여기서 $P(B\cap A^c)$를 $P(B) - P(A\cap B)$로 바꿔주면서 위의 식이 나올 수 있게 된다. (equiv to $P(A\cap B) + P(B\cap A^c) = P(B)$, since $A\cap B, A^c\cap B$ are disjoint and the union is $B$.)
직관적으로 생각하면, 두 부분을 다 더하면 가운데 부분이 중복되어서 더해지므로 한번 빼줘야한다.

(4) $P(A\cup B\cup C) = P(A) + P(B) + P(C) - P(A\cap B)-P(A\cap C)-P(B\cap C)+P(A\cap B\cap C)$

이걸 활용해서 좀 더 일반적인 형태를 만들면

(5) $P(A_1\cup A_2\cup ... \cup A_n)=\sum^n_{j=1}P(A_j)-\sum_{i<j}P(A_i\cap A_j) + \sum_{i<j<k}P(A_i\cap A_j\cap A_k) - ... +(-1)^{n+1}P(A_1\cap ... \cap A_n)$ => Inclusion-exclusion principle(포함 배제의 원리)

Example of Inclusion-Exclusion principle

de Montmort's Problem(1713) => matching problem

1부터 n까지의 카드 뭉치가 있을 때, 잘 섞은 후, 카드를 넘겼을 때, 각 위치에 맞는 숫자가 나올 확률

• $A_j$: j번째 카드가 맞을 사건

우리는 여기서 $P(A_1\cup A_2\cup ... \cup A_n)$에 관심이 있는데 그 이유는, 이길 확률을 구하기 위해서이다.
한마디로, 위의 확률을 말로 풀어서 설명해보면, 첫번째 위치에 1번의 카드가 나오는 경우, 두번째 위치에 2번의 카드가 나오는 경우... n번째 위치에 n번의 카드가 나오는 경우, 이 n개의 사건에 대한 모든 경우를 생각하고 그에 대한 확률을 구하는 것이다.

$P(A_j)=\frac{(n-1)!}{n!} = \frac{1}{n}$

• $n!$: 전체 경우의 수
• $(n-1)!$: 한 카드의 위치를 고정하고 나머지 카드가 올 수 있는 경우의 수

$P(A_1\cap A_2) = \frac{(n-2)!}{n!} = \frac{1}{n(n-1)}$

• $(n-2)!$: 위와 같은 논리로 두 카드의 위치를 고정하고 나머지 카드가 올 수 있는 경우의 수

결국

$P(A_1\cap A_2\cap ... \cap A_k)=\frac{(n-k)!}{n!}$

가 된다.

그럼 이걸 이용해서 우리가 처음에 관심이 있었던 식을 구할 수 있게 되는데,

$P(A_1\cup A_2\cup ... \cup A_n)=\binom{n}{1}*\frac{1}{n}-\binom{n}{2}* \frac{1}{n(n-1)}+\binom{n}{3}\frac{1}{n(n-1)(n-2)}-...$

• 여기서 $\binom{n}{2}$은 $n(n-1)$의 식이 되기 때문에 각 항은 1로 약분(?)될 수 있다.
  
  그래서 식을 다시 써보면
  = $1-\frac{1}{2!}+\frac{1}{3!}-\frac{1}{4!}+...+(-1)^{n+1}\frac{1}{n!}$로 바꿀 수 있고 이건 결국
  $\approx 1-\frac{1}{e}$ 으로 정리된다.