[Harvard: STAT 110] 3강: Birthday Problem, Properties of Probability

1. Birthday Problem

 

문제는 아주 간단하다. k명의 사람이 있을 때, 두 명의 생일이 같을 확률을 구하는 문제이다. 여기서는 최소한 두 명의 생일이 같을 확률을 구할 것이다. 몇 명의 사람이 있어야 최소한 50%의 확률로 두 명의 사람의 생일이 같을 수 있을지 알아보자. 

 

일반적으로 k명의 사람 중 두 명의 생일이 같을 확률을 구해야 한다. 2월 29일은 다른 날짜에 비해 확률이 낮다. 편의를 위해 1년은 365일로 가정하고 문제를 푼다. 그리고 365일이 모두 동일한 확률을 가진다고 가정한다. 

 

k > 365

 

먼저 k가 365보다 클 때를 가정해보자. 이때 확률은 1일 것이다. 왜냐하면 365명보다 많은 사람이 있지만 생일이 될 수 있는 날짜는 365개뿐이기 때문이다. 무조건 한 쌍 이상의 사람이 같은 생일을 가지고 있을 것이다. 이를 비둘기 집의 원리라고 부른다. 

 

50%의 확률로 두 명의 생일이 같으려면 몇 명이 있어야 하는지 알기 위해서는 여사건을 활용하면 간단히 풀 수 있다. 이는 다음과 같다. 

 

k명 중 두 명의 생일이 같을 확률 = 1 - 모두의 생일이 같지 않을 확률

 

그렇다면 k명 중 두 명의 생일이 같을 확률을 구해도 되지만, 모두의 생일이 같지 않을 확률을 구하는 것이 더 쉬울 것이다. 이 확률의 분모는 곱의 법칙에 의해 365^k가 될 것이다. 분자는 각각의 ID를 가지는 사람들을 생각해 보면 된다. 그리고 이 ID의 순서대로 한 명씩 파티에 들어온다고 해보자. 첫 번째 사람은 365일 중 아무 때나 생일이 될 수 있다. 두 번째 사람은 첫 번째 사람과는 다른 생일을 아무 때나 가질 수 있다. 마찬가지로 곱의 법칙을 사용하여 마지막 k 번째 사람은 365-k+1개의 날짜 중 하나여야된다. 이를 수식으로 표현하면 다음과 같다. 

 

모두의 생일이 같지 않을 확률:

 

$$\frac{365 \times 364 \times \dots \times (365-k+1)}{365^k}$$

 

따라서 생일이 같을 확률은 1에서 위 수식의 값을 뺀 것이다. 지금은 이것을 직접 계산하는 것은 쉽지 않다. 결과만 이야기하면 다음과 같다. 

 

$$x \begin{cases} 50.7\% (k = 23)  \\ 97\% (k = 50) \\ 99.99...\% (k = 100) \end{cases}$$

 

이 문제에서 k는 가장 의미 있는 값은 아니다. 가장 중요한 값은 k가 아니라 k에서 2개를 고르는 경우의 수이다. k명이 있을 때 k명 중에서 각 2명씩을 골라야 하기 때문이다. k명 중 2명을 고르는 경우는 아래의 수식과 같다.

 

$$\begin{pmatrix} k \\ 2\end{pmatrix} = \frac{k(k-1)}{2}$$

 

그리고 예를 들어 23명 중에서 2명을 고른다고 하면 23 x 22 / 2가 된다. 따라서 23명의 경우 253쌍을 만들 수 있는 것이다. 이제 이 결과가 타당한 결과로 보일 것이다. 23은 작은 수이지만, 253은 충분히 큰 수이다. 이제 여기서 어느 한 쌍이라도 충분히 생일이 같을 수 있다는 생각이 든다. 이 값은 거의 365에 근접한 값이다. 

 

만약 생일이 꼭 같은 것만 아니라 하루 차이가 나는 확률까지 포함한다면, 23은 14로 줄어든다. 14라는 것을 증명하는 것은 생일이 같을 확률 증명하는 것보다 훨씬 복잡하다. 

 

2. Non-naive definition

 

2. 1. Axioms

 

저번 강의에서 간단히 설명했지만 다시 한번 설명한다. 여기엔 두 가지의 정리만 있으면 된다. 두 가지 정리를 알기 전, 전체 집합인 표본 공간과 함수 P가 있었는데 P는 확률을 의미했다. 첫 번째 정리는 공집합의 확률은 0이고, 전체 표본 공간에 대한 확률은 1이라는 것이었다. 두 번째 정리는 합사건의 확률에 대한 정리이다. 

 

첫 번째 정리:

 

$$P( \emptyset) = 0, P(S) = 1$$

 

두 번째 정리:

 

$$P(\bigcup_{n=1}^\infty A_n) = \sum_{n=1}^\infty P(A_n)$$

 

두 번째 정리에서 n이 1부터 m, 또는 무한대가 되더라도 유한사건이 된다. 이 값은 n이 1부터 무한대일 때 P(A_n) 값의 합이 된다. 근데 두 번째 정리에는 중요한 조건이 있다. A_1, A_2,... 가 모두 겹치지 않는 서로소여야 한다는 것이다. 

Figure 1

 

벤 다이어그램을 그려보자. Figure 1에서 표본 공간 S가 있다. 무한대의 사건을 모두 그리지 못하기 때문에 세 가지만 그려보겠다. 직관적으로 확률을 면적으로 생각해 보자. 확률을 면적으로 생각한다면 직사각형의 면적은 1이 된다. 그 안에 그려진 원들도 확률을 면적으로 생각한다면, 이 세 가지 사건을 더한 것의 확률은 세 원들의 면적의 합이 된다. 이를 무한대까지 확장해도 변함없는 사실이다. 

 

위의 두 정리는 P가 만족해야 할 것들이었다. 

 

2. 2. Properties of Probability

 

위 두 가지 간단한 규칙을 가지고 확률에 관련된 모든 정리들을 유도할 수 있다. 위 정리를 이용한 간단한 결과를 만들어 보자. 첫 번째는 여집합이다. 

 

1st properties

 

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

 

사실 위 속성은 birthday problem을 풀 때도 사용했었다. 또, 단순한 정의를 사용할 때에도 이는 항상 참이었다. 모든 사건은 그런 것과 그렇지 않은 것으로 나눌 수 있기 때문이다. 이를 수학적으로 증명해 보자. 

 

Proof of 1st properties

 

$$1 = P(S) = P(A\cup A^C)$$

 

첫 번째 정리를 통해 1은 전체 공간의 확률임을 알고 있다. 그리고 S를 A와 A^C의 합사건이라고 할 수 있다. P(A)는 A의 안쪽, P(A^C)는 A의 바깥쪽이기 때문에 이 둘을 합치면 전체가 된다. 그리고 둘은 서로소이기 때문에 아래와 같이 쓸 수 있다. 

 

$$P(A \cup A^C) = P(A) + P(A^C)$$

 

이는 두 번째 정리를 사용한 것이다. 

 

2nd properties

 

$$P(B) \geq P(A) $$

 

두 번째 property도 유용하다. 만약 사건 A가 사건 B에 포함된다고 하면, P(A)는 P(B) 보다 작거나 같다. 이것도 벤 다이어그램으로 보면 확실히 직관적이다. B는 더 큰 원이고 안에 작은 원인 A를 포함할 것이다. 따라서 B 원의 면적이 당연히 더 큼을 알 수 있다. 이를 수학적으로 증명해 보자. 

 

Proof of 2nd properties

 

$$B = A \cup (B \cap A^C )$$

$$P(B) = P(A) + P(B \cap A^C) \geq P(A)$$

 

먼저 B를 A와 A가 아닌 고리 부분, 이렇게 두 부분으로 나누어 생각해 보자. 따라서 B를 A와 고리 부분의 합사건으로 생각할 수 있다. 그리고 이 두 집합은 서로소이다. 따라서 단순한 덧셈으로 나타낼 수 있다. 그리고 확률의 정의에 의해 확률은 음수가 될 수 없기 때문에, 음수가 아닌 어떤 값을 더했으므로, P(B)는 P(A) 보다 큰 값이 된다. 

 

3rd properties

 

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

 

세 번째 property는 약간 복잡하다. 합사건의 확률에 대한 것이다. 만약 A와 B가 서로소일 때는 그냥 P(A) + P(B)를 계산하면 된다. Figure 2를 보면 A와 B가 겹치는 교집합이 있다. 직관적으로 A와 B의 면적을 더하게 되면 교집합 부분이 중복되게 된다. 따라서 이 값을 한 번 빼줘야 한다. 

Figure 2

 

Proof of 3rd properties

 

이를 수학적으로 증명해 보자. 먼저 어떻게 axiom을 사용할지 생각해야 한다. 두 번째 정리는 중요하지만 이 정리는 서로소일 때만 적용할 수 있다. 따라서 이것들을 서로소인 상태로 만들어야 한다. 먼저 세 번째 property를 증명하기 위해 A와 B의 합사건을 다시 정의해 보자. 

 

$$P(A \cup B) = P(A \cup (B \cap A^C)) = P(A) + P(B \cap A^C)$$

 

A와 B의 합을 서로소 집합으로 나누기 위해서 합사건을 다시 정의해 보았다. 이제 위의 수식이 세 번째 property 수식과 동일하다면 증명할 수 있다. 즉, 아래의 수식이 같음을 증명해야 한다. 

 

$$P(A) + P(B \cap A^C) = P(A) + P(B) - P(A \cap B))$$

 

먼저 위 식에서 양변에 P(A)가 있기 때문에 P(A)를 제외한 나머지 부분이 같은지 증명하면 된다. 

 

$$P(B \cap A^C) = P(B) - P(A \cap B)$$

 

위 수식에서 P(A ∩ B)를 이항 해보자. 

 

$$P(A \cap B) + P(B \cap A^C) = P(B)$$

 

위 수식이 참이라는 것은 두 번째 정리에 의해 알 수 있다. 일단 A ∩ B와 A^C ∩ B는 서로소이다. 왜냐하면 A와 A^C 두 집합에 동일한 원소가 포함되는 것은 불가능하기 때문이다. 따라서 이 둘은 서로소이고, 합사건은 B가 된다. A ∩ B와 A^C ∩ B는 B를 둘로 쪼갠 것이나 다름없기 때문이다. 이를 포함베제의 원리라고 한다. 

 

3. Inclusion-exclusion Principle

 

포함베제의 원리는 간단하다. 위에서 증명한 세 번째 properties를 두 가지 사건 이상인 경우로 확장시켜 생각해 보자. 먼저 세 가지 사건의 경우이다. P(A∪B∪C)를 다이어그램을 통해 나타내면 Figure 3와 같다. 위에서 증명했던 것처럼 각각의 확률을 더하고 중복된 부분을 빼보자. 이는 아래의 수식과 같다. 

 

$$P(A) + P(B) +P(C) - P(A\cap B) - P(A\cap C) -P(B\cap C) $$

 

그런데 이제 너무 많이 빼 버린 것이 돼 버렸다. Figure 3을 보며 다시 생각해 보면 세 부분이 교차하는 부분은 어떻게 될까? 세 집합의 교집합은 세 번 더해졌다가, 세 번 빼졌다. 따라서 아직 세어지지 않았기 때문에 다시 더해주어야 된다. 이는 아래의 수식과 같다. 

 

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

 

이것이 포함배제의 원리이다. 일반적인 경우는 n개 사건에 대한 합사건의 경우이다. 먼저 각 사건을 더하고 각 사건들의 교집합을 뺀다. 그리고 세 집합의 교집합을 더한다. 이렇게 덧셈과 뺄셈이 교대로 반복된다. 이렇게 계속 반복되어서 마지막은 모든 사건의 교집합이 된다. 이는 덧셈 아니면 뺄셈이 될 것이다. 일반식은 아래의 수식과 같다. 

 

$$P(A_1 \cup A_2 \cup \dots \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) - \dots + (-1)^{n+1}P(A_1 \cap A_2 \cap \dots \cap A_n)$$

 

4. Matching Problem

 

이는 몽마르트 문제라고도 불린다. 이 문제는 다음과 같다. 카드 뭉치가 있다고 해보자. 각 카드가 스페이스 A나 클로버 7 같은 것들 보다는 카드가 1부터 n까지의 숫자로 표시되어 있다고 해보자. 어차피 기존 카드도 중복되는 것이 없어서 고유의 숫자를 부여해도 된다. 먼저 카드를 섞고 1부터 차례로 숫자를 세며 카드를 한 장씩 뒤집는다. 카드 번호와 센 숫자가 같으면 이기고 다르면 진다. 

 

포함배제의 원리를 사용해서 문제를 풀어보자. 사건 A_j가 있다고 하자, 이 사건을 j번째 카드가 매칭되는 상황이라고 하자. 따라서 구해야 되는 것은 합사건의 확률이다. 아래의 수식을 구해야 한다. 

 

$$P(A_1 \cup A_2 \cup \dots \cup A_j)$$ 

 

이를 계산하기 위해서는 P(A_j)를 알아야 한다. 모든 위치에 대한 확률이 같은 확률이라고 하면, 1/n의 확률이 된다. 그렇다면 P(A_1 ∩ A_2)를 구해보자. 

 

$$P(A_1 \cap A_2) = (n-2)! / n! = 1/n(n-1)$$

$$P(A_1 \cap \dots \cap A_k) = (n-k)! / n!$$

 

위의 수식을 따라서 matching 문제의 확률을 구하면 아래와 같다. 

 

$$ P(A_1 \cup A_2 \cup \dots \cup A_j) = n\frac{1}{n} - \frac{n(n-1)}{2!}\frac{1}{n(n-1)} + \frac{n(n-1)(n-2)}{3!}\frac{1}{n(n-1)(n-2)} = 1 - \frac{1}{2!} + \frac{1}{3!} - \frac{1}{4!}+\dots +(-1)^(n+1)\frac{1}{n!} = 1 - \frac{1}{e}$$