[Harvard: STAT 110] 2강: Story Proofs, Axioms of Probability

0. Introduction
 

강의를 시작하기 앞서 몇 가지 조언을 해주신다. 요약하면 다음과 같다. 
 
Don't lose common sense
 
강의가 진행될 수록 상식에서 벗어나고, 직관적이지 못한 결과를 자주 얻게 될 것이다. 직관적이지 않은 문제를 다룬다고 해서 상식을 아예 벗어나라는 것은 아니라는 것이다. 또, 답안을 쓸 때에 합리적인 이유가 있어야 한다. 예를 들어서 52개 중에서 5개를 선택하는 경우의 수를 구할 때, 이것을 (52, 5)로 둬도 괜찮다는 것이다. 교수님은 이를 '설명이 필요 없는 주석'이라고 부르신다. 이렇게 하면 말 그대로 답안에 대한 설명 없이도 설명이 된다는 것이다. 
 
Do check answers
 
자신이 푼 풀이를 반복하라는 것이 아니라, 다른 방법으로 답을 확인하라는 것이다. 이는 간단한 형태의 극단적인 경우를 모두 시도해보라는 것이다. 또, 간단한 다이어그램을 그려볼 수도 있다. 
 
Label peaple, objects, or something..
 
앞으로 나올 문제에는 n개, n마리, n명의 무언가가 있다. 이를 구분해서 풀어야 하기 때문에 n명의 사람이라면 이 사람들을 1부터 n까지의 숫자로 label하는 것이다.만약 상자 속에 빨간 공이 r개, 녹색 공이 g개 있다고 하면, 빨간 공은 1부터 r까지의 숫자로, 녹색 공은 r+1부터 r+g까지의 숫자로 label할 수 있을 것이다. 
 

1. Sampling table: case of (replace, order doesn't matter)
 

1강에서 sampling table에 대해 배웠다. 4개의 항목으로 나눌 수 있었고 이중 3개의 항목은 곱의 법칙을 잘 이해했다면 바로 채워 넣을 수 있었다. 그중 하나의 항목에 대해 이야기 하고자 한다. 
 
n개의 물체들 중에서 k번의 선택을 하는데, 이 경우 순서는 상관하지 않고 복원을 적용하는 경우이다. n개 중에서 한 개를 고르고 이것을 다시 돌려 놓는다. 그리고 하나를 고르고 다시 돌려 놓는 것을 k번 반복한다. 근데 다른 순서로 같은 것들을 뽑더라도 이를 하나로 간주한다는 것이다. 1강에서는 n+k-1개 중 k개를 고르는 경우의 수와 같다고 하였다. 이번 강의에서는 이를 증명한다. 
 
가설: replace, order doesn't matter = pick k times from set of n+k-1 objects
 
1. 1. Do check answers through extreme cases
 
먼저 서론에서 이야기 했던 extreme case로 문제를 풀어보자.
 
k = 0일 때: n-1개 중 0개를 고르는 경우가 된다. n-1개 중에서 0개를 고르는 것은 1가지 뿐이다. 
 
k = 1일 때: n개 중에서 1개를 고른 경우가 되고, n가지가 된다. 어차피 하나만 고르는 것이므로 복원을 하거나 하지 않거나 같은 결과이다. 그리고 순서 또한 상관 하는 것과 상관하지 않는 것이 같은 결과이다. 
 
n = 2일 때: 이 예시는 가장 간단한 형태의 특별한 예시이다. 이때는 k+1개 중에서 k개를 고르는 경우의 수가 된다. 이는 k+1개 중에서 1개를 고르는 것과 같고, k+1가지가 된다. 이제 이 가설이 맞는지 원래 조건(replace, order doesn't matter)에 맞추어 확인해보자. 
 
여기서 n = 2이고, k번 선택할 수 있다. 여기에 2개의 물체를 의미하는 상자를 그려보겠다. 그리고 k번 선택할 수 있는데, 간단하게 하기 위해 상자에 체크 표시를 하는 것으로 선택을 표시한다. Figure 1의 상자를 순서대로 1번 상자, 2번 상자라고 하자. 1번 상자를 선택할 때마다 상자에 점을 찍겠다. 또, 2번 상자를 선택하면 2번 상자에 점을 찍도록 한다. 
 

Figure 1

 
Figure 1의 경우, 1번을 3번 선택했고, 2번을 4번 선택했다. 복원을 하는 경우 선택의 횟수에는 제한이 없다. 전체 횟수가 가정했던 것과 동일하기만 하면 된다. 그리고 현재 조건은 순서가 상관 없기 때문에 점의 순서 또한 상관이 없다. 단지 상자의 점의 개수만 알면 되는 것이다. 
 
1번 상자에 점이 몇 개 있는지 알면, 나머지 2번 상자에 몇 개의 점이 있는지 알 수 있다. 1번 상자의 점의 개수는 0부터 k 사이의 값을 가진다. Figure 1의 예시에서는 k = 7이다. 따라서 총 k+1가지가 가능하다. 이를 통해 위 가설은 맞다는 게 증명이 된다. 
 
1. 2. Gerneral proof
 
위에서 사용한 방식은 n개의 구분 가능한 상자 안에 k개의 구분 불가능한 입자를 넣는 것이였고, 이 경우의 답은 n+k=1개 중 k개를 고르는 경우의 수가 되었다. 
 
이번에는 간단한 다이어그램을 그려 해결해보겠다. 이번에는 4개의 상자를 가지고 문제를 풀어보자. Figure 2에서 n = 4, k = 6이 된다. 
 

Figure 2

 
Figrue 2를 간단하게 변환시켜 설명해보겠다. Figure 3을 보면, 상자라고 생각하는 것이 아니라 세로로 선을 그어 구분하는 것임을 알 수 있다. 2번 상자는 비어있었기 때문에 두 개의 구분선 사이  아무런 점도 찍히지 않았다. 이처럼 간단하게 같은 상황을 다른 방법으로 표현할 수 있다.  
 

Figure 3

.
점은 k개지만, 구분선은 n-1이라는 것을 명심해야한다. Figure 3의 경우에는 n+k-1개의 자리가 있고, 점이 어디에 들어가야 하는지 구하면 되는 문제이다. 그리고 나머지 위치들은 분리선의 위치가 된다. 결국 n+k-1개 중에 k개를 고르는 문제가 된다. 또, n+k-1개 중에 n-1개를 고르는 문제라고 할 수도 있다. 
 

2. Story Proof
 

story proof는 해석에 의한 증명이라고 할 수 있다. 아래의 수식으로 간단한 예시를 들어보자. 일단 n개 중 k개를 고르는 것은, n-k개를 고르는 경우와 동일하다. 이 예시에서 벌써 해석에 의한 증명이 된 것이다. 팩토리얼과 같은 수학적 기호들로 생각하는 것이 아니라, "n개 중 k개를 고르는.."부터가 해석이고 이야기 이기 때문이다. 
 
$$\dbinom n{k} = \dbinom n{n-k}$$
 

아래의 수식으로 조금 더 어려운 예시를 들어보자. n-1개 중에 k-1개를 고르는 경우의 수에 n을 곱한 것은 n개 중 k를 고르는 경우의 수에 k를 곱한 것과 동일하다. 

 

$$n \dbinom {n-1}{k-1} = k \dbinom n{k}$$

 

위 수식을 이해하기 위해 예시를 들어보겠다. 일단 동아리 부원을 뽑는데, n명 중에서 k명을 선택하고, 그 중 한 명을 대표로 뽑는다고 해보자. 이는 두 가지 방법으로 계산할 수 있다. 첫 번째는 동아리에 들어갈 사람을 먼저 선택하는 것이다. 그렇다면 n명 중 k명을 고르는 경우의 수가 된다. 그리고 여기 k명 중 한 명은 반드시 동아리 대표가 되어야 한다. 따라서 곱의 법칙에 의해 k를 곱하게 되는 것이다. 첫 번째 방법으로 위 수식의 우변을 나타낼 수 있다. 두 번째 방법은 대표를 먼저 선택하는 것이다. 대표를 먼저 뽑은 후, n-1명 중에 k-1명의 동아리원을 더 뽑는 것이다. 그리고 다시 곱의 법칙을 적용하면 위 수식의 좌변을 나타낼 수 있다. 따라서 두 방법의 결과는 같은 것이 된다. 

 

따라서 story proof는 동일한 문제를 다른 방법으로 풀어서 증명하는 것을 의미한다. 

 

3. Axioms of Probability
 

이전까지는 모두 동일한 확률을 가지는 문제에 대해서만 이야기 했다. 이제 더 나아가, 모두 같은 확률을 가지지 않는 문제를 풀어보자. 그리고, 결과의 가짓수가 유한하지 않은 경우에 대해서도 알아보자. 이를 non-naive definition이라고 한다.

 

이를 알기 위해서는 먼저 확률 공간이라는 개념을 알아야한다. 확률 공간에는 두 개의 성분이 있다. 이를 각각 S와 P라고 하겠다. S는 표본 공간을 의미한다. 어떤 실험에서 가능한 모든 경우의 수의 집합이다. P는 어떤 사건을 입력으로 하는 함수이다. 따라서 P의 정의역은 S의 부분 집합이다. 여기서 어떤 사건을 A라고 해보자. 사건 A는 S의 부분 집합이고, 입력이 된다. 그리고 P(A)는 0부터 1 사이의 수이다. 즉, P의 입력은 사건이 되고, 출력은 0과 1 사이의 수가 된다. 

 
마지막으로 알아야 할 것은 P를 만족시키기 위한 정리이다. 다시 말해 P를 만족시키기 위해, 0과 1 사이의 숫자가 나오도록 하기 위해, 어떤 성질이 필요하냐는 것이다. 여기서 두 가지 정리만 알면 된다. 
 
첫 번째 정리는 공집합에 대한 확률은 0이고, 전체 집합에 대한 확률은 1이라는 것이다.
 
두 번째 정리는 합사건이다. 이때 이 합사건을 무한대로 계산하는 것을 가산 무한 합사건이라고 한다. 이 합사건의 확률은 모든 확률의 합과 같다. 이 정리에서는 중요한 조건이 있다. 사건 A1, A2, ...가 모두 서로소일 때만 가능하다는 것이다. 
 
이 두 가지 정리가 확률에 대한 정리이다. 또, 이 두 가지 정리로 확률에 대한 모든 정리들을 유도할 수 있다. 결국 모든 확률 정리가 이 두 가지 정리를 따른다는 것이다.