[Statistics] Probability 110 - Probability and Counting

Contents

 

 

본 글은 스탠포드 강의 중 확률론 110 강의에서 언급된 내용 및 용어를 정리하고 있다. 

 

확률과 셈의 원리 (Probability and Counting)

확률론은 유전학, 물리학, 계량 경제학, 인공지능 등 다양한 분야에서 사용되고 있으며, 확률은 불확실성(uncertainty)을 계량화하는 것을 가능하게 해준다. 

 

Multiplication Rule

발생 가능한 경우의 수가 $n_1, n_2, ... , n_r$가지인 1, 2, 3, ..., r 번의 시행에서 발생 가능한 모든 경우의 수는 $n_1 \times n_2 \times \\ \cdots \\ \times n_r$이다. 

 

Binomial Coefficient

$\begin{pmatrix} n \\ k \end{pmatrix} = \frac{n!}{(n-k)! k!} $ 크기가 n인 집합에서 만들 수 있는 크기 $k$인 부분 집합의 수를 의미한다. 예를 들어, 사람이 5명이 있을 때, 두 명을 선택하는 가짓수는 $\begin{pmatrix} 5 \\ 2 \end{pmatrix}$로 표현하거나 $_5C_2$가 되며, 이는 $\frac{5 \times 4}{2 \times 1}$으로 10이 된다. 사람을 A, B, C, D, E 로 가정 한다면, {A, B}, {A, C}, {A, D}, {A, E}, {B, C}, {B, D}, {B, E}, {C, D}, {C, E}, {D, E} 로 중복은 허용하지 않기 때문에 총 10개의 조합이 된다. 

 

순서가 상관 있는 경우에는 조합(Combination)이 아니라 순열(Permutation)을 사용하여야 하며, 순열은 P로 표현한다. 또한, 복원 추출과 비복원 추출이 존재할 수 있기 때문에 이를 표로 나타내면 아래와 같다. 

	순서 상관 O	순서 상관 X
복원	$n^k$	$_{n+k-1}C_k$
비복원	$n \times (n-1) \times \\ \cdots \\ \times (n-k+1) $	$_nC_k$

 

Example1

k개의 구슬을 n개의 상자에 넣는 경우의 수는 몇 가지 인가? 첫 번째 상자에는 3개의 구슬을 넣을 수 있고, 두 번째에는 0개, 세 번째에는 2개, 마지막 상자에는 1개의 구슬을 넣을 수 있다고 하자. 이때 k는 6이 되고, n은 4가 된다. 아래와 같은 예시로 조합을 생성하기에는 이해가 어려울 수 있다. 이를 아래의 예시로 바꿔서 생각해보자. 

n개의 원 사이에 k-1 개의 구분선을 넣는 경우의 수는 몇 가지 인가? 해당 문제는 n+k-1개의 위치에 원과 구분선을 배열하는 것과 동일하다. 원의 위치를 먼저 정하게 되면 구분선은 자동으로 위치가 지정된다. 그 반대도 성립하기 때문에 순서에 상관 없어진다. 

\[ \begin{pmatrix} n+k-1 \\ n-1 \end{pmatrix} = \begin{pmatrix} n+k - 1 \\ k \end{pmatrix} \]

 

Example2

확률을 대수적인 방법을 통해 접근하는 것보다 상황을 해석하는 것을 통해 증명하는 것이 때로는 쉬울 때도 있다. 아래의 수식을 대수적인 방법이 아닌 상황을 예로 들어 해석하는 형태로 이해해보자.

\[ n \times \begin{pmatrix} n-1 \\ k-1 \end{pmatrix} = k \times \begin{pmatrix} n \\ \end{pmatrix} k \]

이를 대수적인 방법으로 증명하기란 매우 까다롭다. 반면에 해석적으로 접근하면 매우 간단해진다. 예를 들어, n명 중에서 k명을 먼저 뽑고, k명 중에서 한 명을 회장으로 뽑는 문제로 해석할 수 있다. 이는 우변에 해당된다. 반대로, 한 명의 회장을 뽑고, 나머지 k명에 들어갈 사람을 뽑는 형태로 해석하면 이는 좌변이 되며, 좌변과 우변은 동일한 결과가 도출되는 것이다. 

 

Example3

이번에는 위 항등식 외에 주로 사용되는 항등식을 대수적인 방법이 아니라 해석적인 방법으로 통해 확인해보자. 

\[ \begin{pmatrix} m + n \\ k \end{pmatrix} = \sum^k_{j=0} \begin{pmatrix} m \\ j \end{pmatrix} \cdot \begin{pmatrix} n \\ k-j \end{pmatrix} \]

m개의 구슬이 들어간 상자가 있고, n개의 구슬이 들어간 상자가 있다고 가정하자. 그렇다면, m개의 구슬에서 먼저 j 개의 구슬을 뽑은 후,  나머지는 n개의 구슬이 들어간 상자에서 뽑는 경우의 수로 생각할 수 있다. m개의 구슬이 들어간 상자에서 0개부터 m개까지의 구슬을 뽑을 경우의 수를 모두 더하면 된다. 

 

Probability Space 

확률 공간은 S와 P로 구성되어 있으며, S는 표본 공간을 의미하고, P는 어떤 사건(event)을 입력으로 하는 함수를 의미한다. 확률 공간의 전체는 1로 표기하고 하나의 값도 들어있지 않다면 0이 된다. 이를 수식으로 표기하면 아래와 같다.

\[ P(\phi) = 0, \\ P(S) = 1 \]

\[ P( \cup^{\infty}_{n=1}A_n) = \sum^{\infty}_{n=1} P(A_n) \]

이때, $A_i, A_j$는 서로소이다. 서로소는 두 사건 사이에 겹치는 부분이 없어야 한다는 것을 의미한다. 만약 겹치는 부분이 있는 경우에는 1을 넘어갈 수도 있다. 위 두 가지의 공리를 통해 대부분의 식을 유도할 수 있다. $P(A)$는 0과 1사이의 값을 가져야 한다.

 

 

Birthday Problem

Birthday Problem은 확률을 다룰 때 자주 등장하는 예시 중 하나이다. 이는 k 명 중에 2명 이상이 같은 생일일 확률을 구하는 문제를 의미한다. 이때 일별 출생 확률은 모두 동일하며, 각각의 사건은 독립적으로 발생한다는 것을 가정한다. 이때 k가 몇 명 이상이어야 같은 생일을 가진 사람들이 있을 확률이 50%가 넘을까?

 

$k > 365$라고 한다면 확률은 1이 될 것이다. $k \le 365$라고 하면 모두 다를 확률은 $\frac{365 \times 364 \times \cdots \times (365 - k + 1)}{365^k}$가 된다. k=23일 때 50.7%, 50명인 경우에는 97%, k=100인 경우에는 99.9%가 된다. 대수적으로 계산하기에는 매우 복잡해보인다. 이를 직관적으로 한 번 바꾸어서 풀어보자. 일단 같은 생일일 확률을 구하기 위해서는 두 명의 사람을 선택하여야 한다. 그렇다면 k 명 중에서 2명을 뽑는 가짓수는 $\frac{k \cdot (k-1)}{2}$가 될 것이다. 23명이 있는 경우 253 쌍의 조합을 만들 수 있다. 이때 253 쌍 중에서 생일이 같을 확률은 50% 이상으로 보일 수 있다. (직관적으로 접근하기 때문에 정확한 값을 도출할 수 는 없다.)

 

Properties of Probability

확률에는 위에서 다룬 것 처럼 두 가지의 공리가 존재할 뿐만 아니라, 다양한 특징이 존재한다. 어떤 특징들이 존재하는지 확인하고 이를 유도해보자.

 

$ (1) \quad P(A^C)  = 1 - P(A) $

\[ \begin{equation} \begin{split} \text{proof)  } 1 = P(S) & = P(A \cup A^C) \\ \\ & = P(A) + P(A^C) \end{split} \end{equation} \]

 

$ (2) \quad \text{if  } A \subset B, P(A) \le P(B) $

\[ \begin{equation} \begin{split}  \text{proof)  } B & = A \cup (B \cap A^C) \\ \\ P(B) & = P(A) + P(B \cup A^C) \ge P(A) \end{split} \end{equation} \]

 

$ (3) \quad P(A \cup B) = P(A) + P(B) - P(A \cap B) $

\[ \begin{equation} \begin{split} \text{proof)  } P(A \cup B) & = P(A \cup (B \cap A^C)) \\ \\ & = P(A) + P(B \cap A^C) \end{split} \end{equation} \]

 

우리가 공리를 사용하기 위해서는 서로소인 상태로 만들어 주어야 한다. 따라서, (3) 수식을 우변과 같은 형태로 변경한다. (3) 경우에는 $P(B) - P(A \cap B) = P(B \cap A^C)$인 경우에 등식이 성립한다. 이는 공리 2에 의해서 $P(A \cap B) + P(A^C \cap B) = P(B)$이기 때문에 등식이 성립된다. 

 

Inclusion - exclusion Principle

조합론에서의 포함배제 원리(Inclusion-exclusion Principle)는 유한 집합의 합집합의 원소 개수를 세는 기법이다. 여러 개의 합집합에 대한 크기를 구할 때 사용하며, 이산수학 및 확률론에서 중요하고 유용한 원리 중 하나이다.

\[ \begin{equation} \begin{split} P(A_1 \cup A_2 \cup \cdots \cup A_n) & = \sum^n_{j=1} 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 P(A_1 \cap A_2 \cap \cdots \cap A_n) \\ \\ P \left( \bigcup^{n}_{i=1} A_i \right) & = \sum_{\emptyset \neq I \subset [n] } (-1)^{|I| - 1} P \left( \bigcap_{i \in I} A_i \right)   \end{split} \end{equation} \]

 

Example

deMontmort's Problem: 카드가 놓인 위치와 카드에 쓰여있는 숫자가 일치할 확률은 얼마인가? 무작위로 섞여 있는 카드 1, 2, ..., n 중에서, 카드 j가 j 번째 순서에 놓이는 사건을 $A_j$라고 할 때, $P(A_j) = \frac{1}{n}$이 되며, 총 $n$가지가 존재한다. $P(A_1 \cap A_2)$는 $\frac{ (n-2)! }{n!}$가 되고, 확률은 $\frac{1}{n(n-1)}$이 된다. 구하고자 하는 확률인 $P(A_1 \cup \cdots A_n)$은 테일러 급수로 전개해 구할 수 있으며, 수식은 아래와 같다. 

 

$ P(A_1 \cup A_2 \cup \cdots \cup A_n) $

\[ \begin{equation} \begin{split} & = P(A_1) + P(A_2) + \cdots + P(A_n) - P(A_1 \cup A_2) - \cdots + P(A_1 \cup A_2 \cup A_3) + \cdots \\ \\ & = 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)} - \cdots \\ \\ & = 1 - \frac{1}{2!} + \frac{1}{3!} - \cdots + (-1)^n \frac{1}{n!} \\ \\ & \approx 1 - \frac{1}{e} \end{split} \end{equation} \]