3강- Birthday Problem과 확률의 특성 (Birthday Problem, Properties of Probability)

Birthday Problem:

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

 

$k \geq 365$일때,

1년이 365일이고, 있는 사람이 365명보다 많으므로 무조건 1명은 생일이 겹친다

$$P(A) = 1$$

 

$k\leq 365$일때,

k 명의 생일이 모두 다를 경우 = $\frac{365*364* \cdots * (365 - k +1)}{365^k}$

k명 중에 2명 이상이 같은 생일을 가질 확률 = 1 - k 명의 생일이 모두 다를경우

=> k=23일때 50.7%, k=50일때, 97%, k=100일때 99.9%이다

 

직관적으로 생각하면, k = 23명일때 2명을 뽑는 경우의 수는

$$\binom{23}{2} = 253$$

이므로, 생각보다 가능성이 낮지 않다.

 

확률의 공리:

1. $P(\phi ) = 0,  P(S) = 1$

2. $P(\bigcup_{n=1}^{\infty}) = \sum_{n=1}^{\infty}P(A_n)$ ($A_i, A_j$는 서로소이다)

 

확률의 공리로부터 나온 확률의 기본 정리

 

• $P(A^c) = 1-P(A)$
• $A \subset B$인 경우, $P(A) \leq  P(B)$
• $P(A\cup B) = P(A) + P(B) - P(A \cap B)$

 

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

$$P(A_1 \cup A_2 \cup \cdots \cup A_n) = \sum_{j=1}^{n} 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) - \cdots + (-1)^{n+1}P(A_1 \cap A_2 \cap \cdots \cap A_n)$$

 

 

deMontmort's Problem

카드가 놓은 위치와 카드에 쓰여있는 숫자가 일치할 확률은 얼마인가?

무작위로 섞여 있는 카드 n개 중에서, 카드 j가 j번째 순서에 놓이는 사건을 $A_j$라고 할때,

$P(A_j) = $ j번째 카드만 j번째에 놓고 나머지는 상관없이 배열 $= \frac{1*(n-1)!}{n!} = \frac{1}{n}$ => n개

$P(A_i \cap A_j) = $ j와 i 번째 카드가 i,j번째에 있고 나머지는 상관 x $= \frac{(n-2)!}{n!} = \frac{1}{n(n-1)}$ => $\binom{n}{2}$개

...$P(A_1 \cap A_2 \cap \cdots \cap A_n) = \frac{n!}{n!} = 1$ => $\binom{n}{n}$개

 

포함 배제의 원리를 사용하면,$$P(A_1 \cup A_2 \cup \cdots \cup A_n) = P(A_1) + P(A_2) + \cdots + P(A_n) - P(A_1 \cap A_2) - \cdots+ P(A_1\cap A_2\cap A_3) - \cdots$$$$= n  \frac{1}{n} - \binom{n}{2}\frac{1}{n(n-1)}  + \binom{n}{3}\frac{1}{n(n-1)(n-2)} - \cdots$$

$$= 1 - \frac{1}{2!} + \frac{1}{3!} - \cdots + (-1)^{n+1}\frac{1}{n!}$$

테일러 급수에 의해서

$$\approx 1-\frac{1}{e}$$