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

본 게시글은 [하버드] 확률론 기초: Statistics 110, 3강 - Birthday Problem과 확률의 특성을 보고 정리한 글입니다.

학습 목표

확률의 non-naive한 정의의 공리(규칙)을 이용하여 확률의 특성을 증명할 수 있으며, 포함배제의 원리를 이해한다.

 

핵심 키워드

• Birthday Problem
• 확률의 non-naive한 정의의 공리
• 확률의 특성
• 포함배제의 원리

 

학습 내용

생일 문제 (Birthday Problem)

생일 문제는 k명 중에 2명 이상이 같은 생일을 가질 확률을 뜻한다.

일별 출생 확률은 동일하고 각각의 사건은 독립적으로 발생한다고 가정한다.

 

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

k > 365 일 때  확률은 1이다

k <= 365 라 할 때, 여사건을 이용하여 확률을 계산해보자

P(no match : 두 명의 생일이 같지 않은 경우)를 구하고 1에서 해당 확률을 빼면 최소한 한 쌍의 생일이 일치하는 확률을 구할 수 있습니다.

 

이런 방법은 자주 사용되는 방법으로, 사건의 확률을 직접 찾는 것이 쉬울지 여사건을 계산하는 것이 쉬운지 생각해봐야 합니다.

이 경우에는 여사건을 게산하는것이 더 쉽습니다.

 

확률의 naive한 정의를 사용해서 모두 동일한 확률이라고 가정하면 분모는 ${365}^k$가 됩니다.

 

분자의 경우 각각의 ID를 가지는 사람들을 생각해봅시다. ID의 순서대로 한 명씩 파티에 들어온다고 해봅시다.

첫 번째 사람은 365일 중 아무 때나 생일이 될 수 있습니다 : 365. 

두 번째 사람은 첫 번째 사람과는 다른 생일을 아무 때나 가질 수 있습니다 : $365\times 364$. 

다음 사람은 이 두 사람을 제외하고 아무 때나 생일을 가질 수 있습니다 : $365\times 364\times 363$

 

이렇게 계속 곱해집니다. 따라서 다음과 같은 식으로 표현할 수 있죠.

$$\frac{365\times 364\times 363\times ...\times (365-k+1)}{{365}^k}$$

 

참고로 P(match: 두 명의 생일이 같은 경우)의 확률을 보면 k가 23일 때 50.7%, k가 50일 때 97%, k가 100일 때 99.999%의 확률을 가집니다.

 

직관적으로 생각해보면 가장 중요한 값은 k가 아닌 k에서 2개를 고르는 경우의 수입니다. k명이 있을 때 k명 중에서 각 2명씩을 골라야 하기 때문입니다.

$$(\genfrac{}{}{0ex}{}{k}{2})=\frac{k\times (k-1)}{2},(\genfrac{}{}{0ex}{}{23}{2})=\frac{23\times 22}{2}=253$$

따라서 23명의 경우 253쌍을 만들 수 있고 큰 확률을 가질 것 같습니다.

 

확률의 non naive 한 정의

공리(자명한 이치)

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

아무것도 일어나지 않는 경우는 없다

확실한 사건에 대해서는 항상 1의 확률을 가진다

 

2. $P({\cup }_{n=1}^{\mathrm{\infty }}{A}_n)=\sum _{n=1}^{\mathrm{\infty }}P(A_n)(A_1,A_2,...,A_{n}disjoint)$

[합사건의 확률에 대한 정리]

n이 1부터 m또는 무한대가 되더라도 유한사건이 된다

$P({\cup }_{n=1}^{\mathrm{\infty }}{A}_n)$ 값은 n이 1부터 무한대일 때 P(An) 값의 합이 됩니다.

A1, A2, ...가 모두 겹치지 않는 서로소여야 한다.  

 

 

확률의 특징

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

 Proof

$$1=P(S)=P(A\cup A^c)=P(A)+P(A^c),sinceA\cap A^c=\varnothing$$

$P(A\cup A^c)$에서 $A$와 $A^c$는 서로소 이기 때문에 $P(A)+P(A^c)$이다 (공리 1)

 

2.$ifA\subseteq B,thenP(A)\le P(B)$

Proof

$$B=A\cup (B\cap A^c)$$

$$P(B)=P(A)+P(B\cap A^c)\ge P(A)$$

확률은 항상 0~1 사이의 값을 가지기 때문에 음수를 가질 수 없다.

따라서 $P(A)+P(B\cap A^c)$는 $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)-P(A\cap B)=P(B\cap A^c)$인 경우 등식 성립

$P(A\cap B)+P(A^c\cap B)=P(B)$ 이므로 성립한다 (공리2)

$A$와 $A^c$는 서로소 이기 때문에 위 두 집합은 서로소 이다.

 

 

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

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

 

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

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

$P(A_1\cup A_2\cup ...\cup A_n)$ 이것이 최소 한 장의 카드가 매칭되는 확률의 수학적 표현이다.

 

$P(A_j)$는 j번째 카드가 숫자 j가 써져있을 확률입니다.

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

모든 위치에 대한 확률이 같은 확률이라고 할 때 $\frac{1}{n}$이 됩니다.

 

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

$$...$$

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

카드 뭉치의 순서는 $n!$가지가 가능합니다. $A_1\cap A_2$는 첫번째 카드가 1이고, 2번째 카드가 2인경우로 나머지 n-2장의 카드는 어떠한 순서도 가능합니다. 따라서 $P(A_1\cap A_2)=\frac{(n-2)!}{n!}$이 됩니다.

 

이것을 계속하면 $P(A_1\cap A_2\cap ...\cap A_k)=\frac{(n-k)!}{n!}$이것은 맨 위부터 k장의 카드가 정확히 1부터 k까지인 상황이죠. 나머지 n-k장의 카드는 어떤 순서가 되든지 상관없습니다. 따라서 $P(A_1\cap A_2\cap ...\cap A_k)=\frac{(n-k)!}{n!}$이 됩니다.

 

이제 포함배제의 원리를 적용시켜보겠습니다. 포함배제의 원리에 따라 위에서 구한 값들을 대입해보면 $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)}-...$와 같은 형태를 발견 할 수 있고 정리해보면 $1-\frac{1}{2!}+\frac{1}{3!}-...+(-1{)}^{n+1}\frac{1}{n!}$이렇게나옵니다.

 

$1-\frac{1}{2!}+\frac{1}{3!}-...+(-1{)}^{n+1}\frac{1}{n!}$ 이 식이 $e^x$의 테일러 급수라는 것을 기억해내야 합니다. 따라서 근사적으로 $\approx 1-\frac{1}{e}$의 값을 가집니다

 

그러므로 구하고자 하는 확률인 $P(A_1\cup A_2\cup ...\cup A_n)$는

$$=P(A_1)+P(A_2)+...+(P_n)-P(A_1\cup A_2)-...+P(A_1\cup A_2\cup A_3)+...$$

$$=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)}-...$$

$$=1-\frac{1}{2!}+\frac{1}{3!}-...+(-1{)}^{n+1}\frac{1}{n!}-->테일러시리즈$$

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