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

Probability of Unions of Events라고도 하며, disjoint하지 않은 합사건들의 확률을 계산하기 위한 공식이다.

만약 disjoint하다면 두 사건이 동시에 일어나지 않음이 보장되므로 단순히 확률을 더해도 성립하지만, disjoint하지 않다면 확률 계산에 두 사건이 동시에 일어남으로써 간섭되는 확률을 배제시켜야 한다.

P (A_{1} \cup A_{2} \cup \dots \cup A_{n}) = j = 1 \sum n P (A_{j}) - i < j \sum P (A_{i} \cap A_{j}) + i < j < k \sum P (A_{i} \cap A_{j} \cap A_{k}) - \dots + (- 1)^{n} P (A_{1} \cap A_{2} \cap \dots \cap A_{n})

3-sets Inclusion-Exclusion Principle

$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)$

Proof of 2-sets Inclusion-exclusion Principle

dependent(not disjoint)한 두 사건

A, B

에 대해서 다음과 같다.

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

⇒ Definition

$P (A \cup B) = P (A \cup (B \cap A^{C})) = P (A) + P (B \cap A^{C})$ 가 성립한다 ...(1)
$P (B) - P (A \cap B) = P (B \cap A^{C})$ ...(2) 가 성립해 Definition의 부분에 대입할 수 있으면 (1)의 수식과 동일해지므로, (2)가 성립함을 보이면 된다.
(2): $P (A \cap B) + P (A^{C} \cap B) = P (B)$ 가 Probability의 Axiom 2로부터 성립한다.

따라서, 2개 집합의 포함-배제 원리가 성립함이 증명된다.

무작위로 섞인 카드가 놓인 위치(첫번째, 두번째, …)와 카드에 쓰여있는 숫자가 일치할 확률은 얼마인가?

Assumption: 무작위로 섞여 있는 카드 $1, 2, \dots, n$ 중에서, 카드 $j$ 가 $j$ 번째 순서에 놓이는 사건을 $A_{j}$ 라고 하자.

$P (A_{j}) = \frac{1}{n}$ ⇒ $j$ 가 $j$ 번째 순서에 놓이는 사건이 n가지가 존재.
$P (A_{1} \cap A_{2}) = \frac{( n - 2 )!}{n !} = \frac{1}{n ( n - 1 )}$ ⇒ $(2 n) = \frac{n ( n - 1 )}{2}$ 가지 경우가 존재.
- 이 경우는 두 카드가 모두 각자의 위치에 놓이는 경우이다.
- 위 확률이 저러한 이유는, 만약 두 카드의 위치가 올바르게 정해지면 남은 $n - 2$ 개의 카드는 어떠한 순서로도 섞일 수 있다.
- 즉, $n$ 개의 카드를 놓는 방법(분모) 중, 두 카드의 위치가 올바르게 정해진 경우를 제외한 남은 카드를 섞는 놓는 방법(분모)는 $(n - 2)!$ 개이다.
$P (A_{1} \cap A_{2} \cap \dots \cap A_{n}) = \frac{( n - k )!}{n !}$ ⇒ $(k n)$ 가지 경우가 존재. 최소한 하나의 카드라도 그 위치와 일치할 확률은 $P (A_{1} \cup A_{2} \cup \dots \cup A_{n})$ 이고, 그 값은,

P (A_{1}) + P (A_{2}) + \dots + P (A_{n}) - P (A_{1} \cup A_{2}) - \dots + P (A_{1} \cup A_{2} \cup A_{3}) + \dots

이 때, 경우가 $n$ 가지, $\frac{n ( n - 1 )}{2}$ 가지.... 가 존재하므로

= 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 )} - \dots

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

\approx 1 - \frac{1}{e} ∵ Taylor Series

$n \to \infty$ 로 감에 따라, 그 확률은 $1 - \frac{1}{e}$ 에 근사하게 된다.