[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명씩을 골라야 하기 때문입니다.

$$\binom{k}{2} = \frac{k\times(k-1)}{2}, \binom{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}^{\infty}A_n)=\sum_{n=1}^{\infty}P(A_n)\quad (A_1, A_2, ..., A_n disjoint)\)

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

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

\(P(\cup_{n=1}^{\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), since A \cap A^c = \varnothing$$

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

 

2.\(if\: A\subseteq B, then \: P(A) \leq P(B)\)

Proof

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

$$P(B) = P(A) + P(B\cap A^c) \geq 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)} --> \binom{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!} \quad --> 테일러 시리즈$$

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