References
- 확률과 통계 강의 1, 2강 (KOWC - 한양대학교 이상화 교수님)
- Fundamentals of Applied Probability and Random Processs (Oliver Ibe)
Contents
- Independent Events
- Combined Experiments
- Permutation, Combination, Binomial Theorem
- Stirling's Formula
Independent Events
'두 개의 사건 A와 B가 서로 독립(mutually indepedent)이다'라는 것은 조건부 확률을 사용하여 정의할 수 있습니다.
\[P(B|A) = P(B)\]
즉, A라는 조건이 B의 확률에 영향을 미치지 않는다는 것을 의미합니다.
마찬가지로 A와 B가 서로 독립이기 때문에, 아래도 성립합니다.
\[P(A|B) = P(A)\]
조건부 확률인 \(P(B|A) = \frac{P(A \cap B)}{P(A)}\)이기 때문에, 이 식을 위의 식에 대입하게 되면 다음의 식을 얻을 수 있습니다.
\[P(B|A) = \frac{P(A \cap B)}{P(A)} = P(B)\]
따라서, 두 사건 A와 B가 서로 독립인지를 보여주기 위해서는 아래의 식을 만족하는지 보여주면 됩니다.
\[P(A \cap B) = P(A)P(B)\]
두 사건이 서로 독립이라는 것은 각각의 사건이 서로에게 영향을 주지 않는다는 것을 의미합니다.
이런 독립 사건은 주로 random output이 나오는 실험을 repeated (restored) trials에서 발생합니다(ex, 주사위 던지기).
주의해야 할 점은 Independent와 Exclusive는 다른 의미를 가지고 있다는 것입니다. 독립은 서로의 사건이 영향을 미치지 않는다는 의미이고, 상호 배타적(mutually exclusive)이라는 것은 서로 공통된 요소가 없다는 의미(교집합이 없다)입니다.
또 한 가지 특징으로는 두 사건 A와 B가 서로 독립이라면, 두 사건 A와 B의 Compliment Events들 끼리도 모두 독립이라는 것입니다. 즉, \(\overline{A}\)와 B, \(\overline{B}\)와 A, \(\overline{A}\)와 \(\overline{B}\)가 모두 서로 독립입니다.
간단히 아래의 식을 통해서 A와 \(\overline{B}\)가 독립 사건이 맞는지 확인할 수 있습니다.
\[\begin{align*} P(A \cap \overline{B}) &= P(A) - P(A \cap B) = P(A) - P(A)P(B) \\ &= P(A)(1-P(B)) \\ &= P(A)P(\overline{B}) \end{align*}\]
Combined Experiments
Combined Experiments는 두 가지 이상의 실험을 수행한다는 것을 의미합니다. 예를 들어, 동전을 두 번 던진다라는 것이 이에 해당합니다. 이는 각각 \(S_1, S_2\)의 Sample Space를 가지고 있는 두 실험을 수행하는 것입니다.
이때, combined experiments에 의해서 생성되는 Sample Space \(S\)는 \(S_1 \times S_2\)로 나타납니다. 이때, 곱하기(\(\times\))를 Cartesian Product(곱집합)라고 합니다.
간단히 Cartesian Product는 각각 Sample Space를 사용해 순서쌍을 만드는 것이라고 볼 수 있습니다.
예를 들어, 동전을 3번 던지는 combined experiement를 예시로 살펴보겠습니다. 이는 동전 한 번 던지는 것을 3개의 실험으로 수행한다고 볼 수 있습니다. 여기서 각 Sample Space \(S_1, S_2, S_3\)는 다음과 같습니다(H: 앞면, T: 뒷면).
\[\begin{matrix} S_1 = \{H, T\} \\ S_2 = \{H, T\} \\ S_3 = \{H, T\} \end{matrix}\]
이들을 Cartesian Product를 통해 하나로 합치면, \(S = S_1 \times S_2 \times S_3\)이 됩니다.
이를 구하면, \(S\)는 \(\{HHH, HHT, \cdots, TTT\}\)가 됩니다(총 8가지).
Combinatorial Analysis
Permutation (순열)
순열(permutation)은 서로 다른 n개의 요소를 (1열로) 나열하는 것을 의미합니다(line arrangement of n different objects). 이때, 순서(order)가 고려됩니다.
첫 번째 위치에 올 수 있는 요소는 n개가 있고, 두 번째 위치는 (n-1)개, 세 번째 위치는 (n-2)개가 올 수 있습니다. 따라서, 전체 나열할 수 있는 경우의 수는 \(n(n-1)(n-2)\cdots(2)(1)\)이 되며, 이를 n 팩토리얼(factorial), \(n!\)로 정의합니다.
참고로 \(0!\)은 아무것도 나열하지 않는 방법을 의미하는데, 아무것도 나열하지 않는 방법 한 가지를 의미하여 1이 됩니다.
\[0! = 1\]
n개의 요소에서 r개를 뽑아 나열하는 경우의 수는 어떻게 될까요?
이를 위의 방법으로 계산하지만, 전체 개수를 나열하는 것이 아닌 r개만을 나열하기 때문에 다음의 식처럼 나타나고,
\[n(n-1)\cdots(n-r+1) = {}_nP_r\]
\({}_nP_r\)로 표현합니다. 이를 팩토리얼 연산으로 표현하면 \(\frac{n!}{(n-r)!}\)로 표현할 수 있습니다.
- Group Permutation (중복 순열)
Group Permutation은 중복이 있는 요소들 중에서 뽑아 나열하는 것을 의미합니다. 동일한 요소들이 여러 개 존재하고, 총 개수 \(n\)이 \(n = n_1 + n_2 + \cdots + n_k\)로 표현할 수 있습니다.
예를 들어, 10개의 공이 있을 때, 빨간공은 5개, 하얀공은 3개, 까만공은 2개 있는 경우가 있을 수 있습니다. 10개의 공을 1열로 나열하려면, 다음과 같이 계산할 수 있습니다.
\[\frac{n!}{5!3!2!}\]
이를 일반화하면, 중복되는 갯수만큼 나누어주는 것과 같습니다.
\[\frac{n!}{n_1!n_2!\cdots n_k!}\]
Circular Permutation (원순열)
Circular Permutation은 1열로 나열하는 것이 아니라, 원으로 나열하는 원순열입니다.
원순열에서 나열했을 때, 순서를 그대로 유지하면서 위치를 shift하는 것은 동일하다고 볼 수 있습니다. 따라서 shift한 결과(빨간색 순서)는 동일한 것이고, 이렇게 동일한 경우가 n가지가 존재합니다. 따라서, 원순열에서 나열할 수 있는 경우의 수는 다음과 같습니다.
\[\frac{n!}{n}\]
조금 더 문제를 복잡하게 만들면, 원이 아닌 직사각형에서의 순열을 구하는 문제가 있습니다.
1,2,3,4,5 순서로 나열해보면, 1의 위치가 2, 3, 4, 5에 위치할 때는 shift를 하더라도 다른 경우라고 볼 수 있습니다. 하지만 6만큼 shift를 한 경우에는 직사각형을 180도 회전한 것과 동일하게 됩니다. 따라서 5번 shift될 때마다 반복하기 때문에 위의 직사각형에서 10개의 요소를 나열하는 경우의 수는 다음과 같이 계산됩니다.
\[\frac{10!}{10} \times 5\]
이러한 경우의 문제는 얼마나 위치가 대칭적이냐에 따라서 원순열의 공식의 값에 곱해지는 값이 달라지게 됩니다.
Combinations (조합)
Combination(조합)은 서로 다른 n개의 objects에서 r개의 object(s)를 뽑는 것입니다. \({}_nC_r\)로 표현하며, 여기서 순서(order)는 고려되지 않습니다.
\[{}_nC_r = \frac{{}_nP_r}{r!} = \begin{pmatrix}n \\ r \end{pmatrix} = \frac{n!}{(n-r)!r!}\]
Combination과 관련하여 아래의 공식은 유용하게 사용됩니다.
\[\begin{pmatrix} n+m \\ r \end{pmatrix} = \sum_{k=0}^{r}\begin{pmatrix}n \\ k\end{pmatrix} \begin{pmatrix} m \\ r-k \end{pmatrix}\]
여기서 일반적으로 r은 n과 m보다 작은 값입니다.
예를 들어, n명의 남학생과 m명의 여학생이 있는 Sample Space를 고려해보겠습니다. 이 중에서 남학생, 여학생을 고려하지 않고 r명의 학생을 뽑는 경우를 생각해봅시다. 이때, 남학생을 뽑는 경우와 여학생을 뽑는 경우를 서로 배반 사건으로 생각하여 뽑을 수 있습니다. 즉, 남학생을 0명 뽑으면 여학생을 r명 뽑고, 남학생을 1명 뽑으면 여학생을 r-1명 뽑고, 이런식으로 남학생을 r명 뽑고 여학생을 0명 뽑는 경우까지 나열할 수 있습니다.
남학생 0명, 여학생 r명 뽑는 경우의 수는 \(\begin{pmatrix} n \\ 0 \end{pmatrix} \begin{pmatrix} m \\ r \end{pmatrix}\)로 계산할 수 있고, 남학생 1명, 여학생 r-1명 뽑는 경우의 수는 \(\begin{pmatrix} n \\ 1 \end{pmatrix} \begin{pmatrix} m \\ r-1 \end{pmatrix}\)로 계산할 수 있습니다. 마지막인 남학생 r명을 뽑고, 여학생을 0명 뽑는 경우의 수는 \(\begin{pmatrix} n \\ r \end{pmatrix} \begin{pmatrix} m \\ 0 \end{pmatrix}\)로 계산됩니다. 각각의 사건은 배반 사건이기 때문에 총 경우의 수는 배반 사건들의 모든 경우를 다 더한 결과가 됩니다.
위의 공식은 나중에 이항 분포에 대해서 살펴볼 때 또 나오기 때문에 간단하게 살펴봤습니다.
Binomial Theorem (이항 정리)
이항 정리는 거듭 제곱으로 표현되는 식의 계수들을 간단히 정리하는 공식입니다.
\[\begin{align*} (a+b)^n &= A_0a^n + A_1a^{n-1}b^1 + A_2 a^{n-2}b^2 + \cdots + A_n b^n \\ &= \sum_{k=0}^{n} \begin{pmatrix} n \\ k \end{pmatrix} a^k b^{n-k} \\ &= \sum_{k=0}^{n} \begin{pmatrix} n \\ k \end{pmatrix} a^{n-k} b^{k} \end{align*}\]
위의 a와 b를 하나를 1이고 하나는 \(x\)로 설정한 함수 \(f(x) = (1+x)^n\)를 살펴봅시다.
이항 정리에 의해서 \(f(x)\)는 다음과 같이 표현할 수 있습니다.
\[f(x) = (1+x)^n = \sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix} x^k\]
위 식에, \(x = 1\)을 대입하면,
\[2^n = \sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix} = {}_nC_0 + {}_nC_1 + \cdots + {}_nC_n\]
을 유도할 수 있습니다.
또는, \(x = -1\)을 대입하면,
\[0 = \sum_{k=0}^n \begin{pmatrix} n \\ k \end{pmatrix}(-1)^k = {}_nC_0 - {}_nC_1 + \cdots\]
위의 두 식을 더하거나 빼면, 아래의 식이 유도됩니다.
\[\begin{align*} {}_nC_2 + {}_nC_4 + {}_nC_6 + \cdots = 2^{n-1} \\ {}_nC_1 + {}_nC_3 + {}_nC_5 + \cdots = 2^{n-1} \end{align*}\]
이번에는 \(f(x)\)를 미분해보도록 하겠습니다.
\[f'(x) = n(1+x)^{n-1} = \sum_{k=0}^n k \begin{pmatrix} n \\ k \end{pmatrix} x^{k-1}\]
위 식에, \(x = 1\)을 대입하면 아래의 식을 얻을 수 있습니다.
\[n2^{n-1} = \sum_{k=0}^n k \begin{pmatrix} n \\ k \end{pmatrix} = {}_nC_1 + 2_nC_2 + 3_nC_3 + \cdots\]
한 번 더 미분하면,
\[f''(x) = n(n-1)(1+x)^{n-2} = \sum_{k=0}^n k(k-1) \begin{pmatrix} n \\ k \end{pmatrix} x^{k-2}\]
가 됩니다. 위 식을 풀어보면 \(k^2\)과 \(\begin{pmatrix} n \\ k \end{pmatrix}\)에 대한 식으로 표현되고, 이를 이용하면 \(\sum_{k=0}^n k^2 \begin{pmatrix} n \\ k \end{pmatrix}\)도 계산할 수 있습니다.
그렇다면 이것들이 왜 필요하냐 ?
이들은 이항 분포 \(B(n, p)\)에 확률들이 이항 정리를 통해서 구해집니다.
\[\begin{pmatrix} n \\ k \end{pmatrix} p^k (1-p)^{n-k}\]
특히, 이항 분포의 평균 \(np\)와 분산 \(np(1-p)\)를 유도할 때, 위에서 살펴본 이항 정리 공식들이 사용됩니다.
이번에는 \(f(x)\)를 멱급수로 표현해보도록 하겠습니다(\(|x| < 1\)).
\[f(x) = 1 + 2x + 3x^2 + 4x^3 + \cdots\]
이는 f(x)에 x를 곱한 뒤, 위의 식에서 빼주면 조금 간단하게 식을 변형할 수 있습니다.
\[\begin{align*} f(x) &= 1 &&+ 2x + 3x^2 + 4x^3 + \cdots \\ xf(x) &= &&+ 1x + 2x^2 + 3x^3 + \cdots \end{align*}\]
위의 두 식을 빼주면,
\[(1-x)f(x) = 1 + x + x^2 + x^3 + \cdots = \frac{1}{1-x}\]
가 계산됩니다.
이번에는 \(g(x)\)를 다음과 같이 정의해보겠습니다.
\[g(x) = \sum_{k=0}^{\infty} x^k = \frac{1}{1-x}\]
그런데 \(g(x)\)를 미분하면,
\[g'(x) = \sum_{k=0}^{\infty} k x^{k-1} = f(x)\]
가 됩니다.
즉,
\[g'(x) = \left ( \frac{1}{1-x} \right )'\]
로 계산할 수 있습니다. 따라서, 멱급수와 다른 방식으로 \(f(x)\)를 계산할 수 있습니다.
Stirling's Formula
스털링 근사라고 부르며, \(n!\)를 근사하는 공식입니다. \(n!\)에서 n이 커지면, 그 수가 엄청나게 커지고 그 값을 연산하는 것이 힘들게 됩니다.
스털링 근사는 n이 충분히 클 때, 다음과 같이 \(n!\)를 근사합니다.
\[n! \approx \sqrt{2\pi n} \left (\frac{n}{e} \right )^n\]
위 그래프를 보면 알 수 있듯이, n(x)가 충분히 클 때 두 값의 비가 1에 수렴하는 것을 확인할 수 있습니다.
'ML & DL > 확률과 통계' 카테고리의 다른 글
| 확률 분포 (Probability Distribution) (0) | 2022.05.30 |
|---|---|
| 확률 변수의 평균과 분산 (0) | 2022.05.28 |
| 확률 변수 (Random Variables) (0) | 2022.05.26 |
| 조건부 확률과 베이즈 정리 (0) | 2022.05.22 |
| 기본 확률 개념 (0) | 2022.05.20 |
댓글