Basic Concepts of Probability Theory - (2)

Axiom of Probability

1. $ 0 \leq P[A]$
2. $ P[S] \leq 1$
3. $ A \cap B = \emptyset \longrightarrow P[A \cup B] = P[A] + P[B] $
   1. $ A_1, A_2, \: ... \: A_i \cap A_j = \emptyset \: \forall i \neq j \longrightarrow P[\cup_{i=1}^{\infty} A_i] = \sum_{i=1}^{\infty} P[A_i]$

Properties

1. $P[A^c] = 1 - P[A]$
2. $P[A] \leq 1$
3. $P[\emptyset] = 0$
4. $P[A\cup B] = P[A]+P[B] - P[A \cap B]$
5. $P[A \cup B \cup C] = P[A] + P[B] + P[C] - P[A\cap B] - P[B \cap C] - P[C \cap A] + P[A\cap B \cap C]$
6. If $A \subset B$ then $P[A] \leq P[B]$

위 Axiom을 만족하는 $P$를 어떻게 정해주어야 할까?

Finite Sample Space, $|S| = n$

set $A$가 Event Class $F$의 element이면 ($A \in F$)
$A = \{a_1, a_2, ... , a_m\}, m \leq n$이고 개별 outcome $a_i$는 mutually exclusive 하므로( Random expere 한번 시행에 하나의 outcome만 나오므로) $P[A] = \sum_{j=1}^{\infty} P[\{a_j\}]$
즉 sample space $S$의 개별 outcome에 해당하는 모든 elementary event {a_j}에 $P$를 먹여놓았으면 어떠한 event든 확률을 계산해낼 수 있다.

Infinite Countably Many Sample Space

Finite Sample Space와 동일하게 하면 된다.

Infinitie Uncountably Many Sample Space

Borel Field $F$를 잡으면, $F$의 임의의 원소(임의의 원소라 해도 그 임의의 원소는 sample space의 subset) $\sum_{k=1}^{\infty} A_k$형태로 쓸 수 있다. 
$A_k$는 $F$에 속하는 mutually exclusive interval 이므로 각각의 개별 interval에 대해서 $P$를 먹여놓으면 어떠한 interval에 대해서든 확률을 계산할 수 있다.

P : Counting해서 확률 정하기

Sample Space $S$는 Finite 하고 $S$의 모든 outcome들이 나올 확률이 동일하다고 하자(Equiprobable) 즉 주사위를 예로 들면 $S= \{1,2,3,4,5,6\}$ 이고 이때 각각의 숫자가 나올 확률은 모두 $1/6$으로 동일한 것이다. 만일 이 중 홀수개가 나올 확률을 계산하고자 하면 $A = \{1,3,5\}$이니 $P[A] = 3 \times {1 \over 6}$ 이 된다.

이렇게 $S$가 이렇게 Finite, Equiprobable하면 event $A$는 $S$의 subset이니 event $A$의 원소 개수들만 세주기만 하면 확률을 계산할 수 있게 된다. 
$$ P[A] = { |A| \over |S| } = {? \over n}$$

잘 세주기만 하면, 그러니까 Counting만 잘하면 된다는 건데, 그럼 어떻게 event $A$의 크기(element 개수)를 잘 셀 수 있을까? Counting 하는 방법은 크게 4가지 정도로 나눠서 볼 수 있다. 상황에 맞게 잘 가져다 쓰면 Counting도 쉽게 정형화된 방법으로 계산해낼 수 있게 된다.

Counting

일단 주머니에 1부터 n까지 숫자가 적혀있는 공이 있다고 생각하자. distinct object인 것이다.

1. Sampling k - balls with replacement(다시 넣기) with ordering ( 1,2,3 $\neq$ 1,3,2 )

$ n = 5, k = 3$ 이라할 때 결과 값은 (1,4,4) 같은 tuple 형태의 outome을 생각할 수 있다.
$$ n^k 개$$

2. Sampling k - balls without replacement with ordering

$$ n\cdot (n-1)\cdot (n-2) \cdot ... \cdot (n-k+1)$$

3. Sampling k- balls without repelacement without ordering

Without Ordering이므로 일단 ordering 해서 뽑은 다음 ordering 있게 뽑은 것에서 순서를 없앤다고 생각하면 편하다

1. $ n\cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-k+1)$ : without replacement, with ordering으로 k개 뽑기
2. k개의 공을 뽑았을 때 나올 수 있는 순서의 경우의 수는 $k!$ 개수이므로 $k!$로 나눠주기

$$
{ n\cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-k+1) \over k!} \\
= {n \cdot (n-1) \cdot (n-2) \cdot ... \cdot 2 \cdot 1 \over k!(n-k)!} \\
= {n! \over k!(n-k)!} \\
= C_{k}^{n}
$$
 \begin{pmatrix} n \\ k \end{pmatrix} 

한편으로는 집합으로 나누는 경우의 수와 동일하다고도 볼 수 있는데, $C_{k}^{n}$은 n개의 distinct object를 $k$개 $(n-k)$개 로 나누는 경우의 수와 동일한 것이다. 가령 1,2,3 숫자가 적힌 3개의 공이 있을 때 1개 / 2개 집합으로 나누는 경우의 수는 ${3! \over 2!1!} = 3$ 이 된
$$ 3 | 1,2  \\ 2 | 1,3 \\ 1 | 2, 3 $$

이렇게 3가지 경우의 수가 나온다
집합으로 나눈 경우의 수이므로 (1,2)와 (2,1)은 같은 것이다. 

좀 더 확장해보면 집합1: $n_1$개,  집합2: $n_2$개, 집합3: $n_3$개 ... 집합k: $n_k$개 원소를 지닌 부분집합으로 n개의 집합을 쪼갤 때에는 아래와 같이 된다는 걸 생각해볼 수 있다. (물론 $ n = \sum_{j=1}^{k} n_j$)
$$ {n! \over n_1!n_2!n_3! ... n_k!}$$

multinomial coefficient

4. Sampling K - balls with replacement without ordering

예를 들어 $n=5, k=3$이라 해보자. (1,1,1) 같은 outcome도 나올 것이고 (1,3,3) 같은 결과도 나올 것인데, 이때 (1,3,3)(with replacement로 같은 숫자 가능) 은 (3,1,3), (3,3,1) 도 모두 같은 경우로 치겠다는 것이고, (1,3,5) 같은 결과가 나오면 (1,5,3), (3,1,5), (3,5,1), (5,3,1), (5,1,3)도 모두 같은 경우로 치겠다는 것이다. (without ordering으로 순서 제거)

어렵게 생각할 것 없이 아래와 같은 그림을 생각해보면 쉽게 counting할 수 있다. 가로축 1,2,3,4,5는 보자기에 있는 공의 숫자를 말하는 것이고, 세로축 1,2,3은 tuple의 index를 의미한다. 즉 X로 표시된 (4,1), (5,2), (5,3)은 $outcome \: (4,5,5)$를 의미한다. 파란색 동그라미는 $outcome \: (5,4,5)$를 의미한다.

가장 아랫줄은 각각의 숫자들(1,2,3,4,5) 열에 몇 개의 Mark 가 표시되었는지 센 것이다. $outcome \: (4,5,5)$를 기준으로 4는 1개, 5는 2개가 mark되었다는 걸 알 수 있다. 그리고 각각의 숫자들(1,2,3,4,5) 사이를 막대기로 표시하고, Mark 개수만큼 X 기호를 해당 열에 적어주면, 이제 우리가 원하는 경우의 수는 저 막대기 (|): 4개와 X: 3개를 배열하는 경우의 수와 동일하게 된다.
$n=5, k=3$인 Sampling with replacement without ordering 은 ${ 7! \over 4!3!}$이 된다
$$
(n-1+k)! \over k!(n-1)!
$$

math.stackexchange의 Unordered Sampling with replacment 글

---

참고자료
Alberto Leon - Probability, Statistics, and Random Processes For Electrical Engineering, 3rd edtion