[Discrete Mathematics] 간단한 이산 확률론(discrete probability theory)

---

기본 개념

 

실험(experimant)은 결과 도출 과정, 사건(event)은 실험 결과, 표본 공간(sample space)은 가능한 모든 실험 결과 집합이다.

유한한 표본공간 $ S $ 에서 모든 결과가 동등하게(equally likely) 일어난다 가정할 때 사건 $ E $ 의 발생 확률 $ P(E) $ 은 $ P(E) = | E | / | S | $ 이다. 만약 가능한 결과가 $ n $ 개 라면 각 결과가 나올 확률은 $ 1/n $ 이다. 그러나 일반적으로 결과는 동등하게 일어나지 않는다.

함수 $ P $ 를 확률 함수라 하면 표본공간 $ S $ 의 원소로서 각 결과 $ x \in S $ 에 대해 $ [0, 1] $ 의 수를 할당한다. 이때 할당된 수가 확률이며 $ \sum_{x \in S} P(x) = 1 $ 을 만족해야 한다. 두 가지 중 하나라도 만족하지 않는다면 확률 함수라 할 수 없다.

사건 $ E $ 는 실험 결과인데 특정 결과들의 집합으로 생각할 수도 있다. 이때 $ P(E) $ 는 사건에 해당하는 결과들의 확률의 합으로 $ P(E) = \sum_{x \in E} P(x) $ 이다. 사건 $ E $ 가 일어나지 않는 집합 $ \bar{E} $ 의 확률은 $ P( \bar{E} ) = 1 - P(E) $ 이다.

 

---

상호배타 및 독립

 

만약 어떤 두 사건 $ E_1 $ 과 $ E_2 $ 가 존재할 때 $ E_1 \cap E_2 = \emptyset $ 이라면 이를 상호배타적(mutually exclusive)이라 한다. 만약 두 사건 $ E_1 $ 과 $ E_2 $ 가 상호배타적이라면 $ P(E_1 \cup E_2) = P(E_1) + P(E_2) $ 이고, 상호배타적이지 않다면 $ P(E_1 \cup E_2) = P(E_1) + P(E_2) - P(E_1 \cap E_2) $ 이다.

특정 사건 $ F $ 가 일어났을 때 다른 특정 사건 $ E $ 가 일어날 확률을 $ P ( E \mid F) $ 라 나타낼 수 있고, 이를 조건부확률이라 한다. 단 $ P(F) > 0 $ 이어야 한다. 조건부확률 $ P(E \mid F) = P(E \cap F) / P(F) $ 를 만족한다.

사건 $ E $ 의 확률이 $ P(E) = P(E \mid F) $ 라면, 즉 사건 $ F $ 가 일어나던 일어나지 않던 사건 $ E $ 가 발생할 확률이 변하지 않는다면 $ E $ 와 $ F $ 를 독립사건(independent event)이라 한다. 또한 독립사건이라면 $ P(E) = P(E \mid F) = P(E \cap F) / P(F) $ 이고, $ P(E \cap F) = P(E) \times P(F) $ 이다. 반대로 $ P(E \cap F) = P(E) P(F) $ 라면 두 사건 $ E $ 와 $ F $ 는 독립이다. 즉 독립이라는 말고 $ P(E \cap F) = P(E) P(F) $ 는 동치이다.

 

---

패턴 인식과 베이즈 정리

 

패턴 인식(pattern recongition)은 아이템들의 특징을 기반으로 여러 클래스로 분류하는 것이다. 예를 들어 가격과 여러 요소들을 기준으로 비행기 티켓은 이코노미, 비즈니스, 퍼스트로 나뉜다. 특징 집합 $ F $ 가 주어지면 각 클래스에 대해 $ P (C_i \mid F ) $ 를 계산하고 가장 그럴듯한, 즉 가장 확률이 큰 클래스로 분류하면 된다.

$ P(C_i \mid F) $ 를 계산하기 위해 베이즈 정리(참고 링크)가 활용된다.

가능한 클래스가 $ C_1, C_2, \cdots, C_n $ 이고, 클래스의 각 쌍이 상호배타적이어야 하며, 아이템들은 각 클래스 중 하나로 반드시 분류된다고 가정하자. 그렇다면 특징 집합 $ F $ 에 대해 다음이 성립한다.

$$ P(C_j \mid F) = \dfrac{P(F \mid C_j) P(C_j)}{\sum_{i=1}^n P(F \mid C_i)P(C_i)} $$

 

---

이항계수와 조합 항등식

 

이항정리는 $ (a + b)^n $ 의 전개에서 나타나는 계수들에 대한 공식을 제공한다. $ a^{n-k} b^k $ 형태의 항은 $ k $ 개의 인수에서 $ b $ 를 선택하고 $ n-k $ 개의 인수에서 $ a $ 를 선택함으로 얻어지는데, 이는 $ C(n, k) $ 가지 방법으로 선택할 수 있다. 이는 $ C(n, k) $ 가 $ n $ 개의 항목에서 $ k $ 개를 선택하는 방법의 수이기 때문이다. 따라서 $ a^{n-k} b^k $ 형태의 항은 $ C(n, k) $ 번 나타난다.

$ a $ 와 $ b $ 가 실수이고 $ n $ 이 양의 정수일 때 $ (a+b)^n = \sum_{k=0}^n C(n, k) a^{n-k} b^k $ 가 성립한다.

$ C(n, r) $ 은 이항식 $ a+b $ 의 어떤 제곱을 전개했을 때 계수를 나타내므로 이항계수(binomial coefficient)라 한다.

이항계수를 삼각형 형태로 나타낼 수 있는데, 이렇게 나타내면 경계는 1이고 내부 모든 값은 자신의 위에 있는 두 값의 합이다. 즉 $ C(n+1, k) = C(n, k-1) + C(n, k) $ 이다. 이렇게 그린 삼각형을 파스칼 삼각형이라 한다.

$ C(n+1, k) = C(n, k-1) + C(n, k) \qquad (1 \leq k \leq n ) $ 를 조합 항등식이라 하고, 카운팅 방법을 위주로 사용하는 증명 방법을 조합적 증명이라 한다.