독립 사건과 순열 및 조합

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

출처 : https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%84%B8%EB%A7%81_%EA%B7%BC%EC%82%AC

위 그래프를 보면 알 수 있듯이, n(x)가 충분히 클 때 두 값의 비가 1에 수렴하는 것을 확인할 수 있습니다.