Probability and counting
수학은 확실성에 대한 학문이다. 확률론은 불확실성(uncertainty)을 계량화 하는 것을 가능케 한다.
확률의 naive한 정의
표본공간(sample space):
어떤 실험(experiment)에서 발생 가능한 모든 경우의 집합. 무엇이든 실험을 하면 어떤 결과가 발생을 한다. 실험을 하기 전에는 무슨 일이 일어날지 알 수 없다. 표본 공간은 어떠한 상황도 표현할 수 있다.
사건(event):
표본공간의 부분집합. 집합에 관한 얘기는 나중에 naive하지 않은 정의에서 공리계로 다루어진다.
확률의 naive한 정의:
\(P(A)=\frac{A가 발생하는 경우의 수}{발생 가능한 모든 경우의 수}\)
여기서 내포하고 있는 가정은:
- 모든 사건이 발생할 확률은 같다.
- 유한한 표본공간에서 정의되었다.
셈 법칙(Counting Principle)
곱의 법칙(Multiplication Rule):
발생 가능한 경우의 수가 \(n_1, n_2, n_3,...,n_r\)가지인 \(1, 2, 3,...,r\)번의 시행에서 발생 가능한 모든 경우의 수는 \(n_1*n_2*n_3*...*n_r\)이다.
선택이 Symmetric해야 사용할 수 있다.
이항계수(Binomial Coefficient)
\[\binom{n}{k} = \frac{n!}{(n-k)!k!}\]Sampling Table
n개 중에서 k개 뽑는다고 하자.
복원, 순서 상관 있음
\[n^k\]비복원, 순서 상관 있음
\[n(n-1)...(n-k+1)\]복원, 순서 상관 없음
\[\binom{n+k-1}{k}\]비복원, 순서 상관 없음
\[\binom{n}{k}\]Story Proofs, Axioms of Probability
Tips for problem solving
가장 일반적인 경우와 가장 극단적인 경우를 생각하고, 계산하기 간단하지만 당연하지 않으며 유의미한 값을 계산해보아라.
문제를 작은 문제들로 쪼개서 생각해보아라.
Sampling Table
n개 중에서 k개 뽑는다고 하자.
복원, 순서 상관 없음
\[\binom{n+k-1}{k}\]먼저 일반적인 경우인 k=1을 대입해보자: \(\binom{n}{1}\)
다음으로 극단적인 경우인 k=0을 대입해보자: \(\binom{n-1}{0}\)
다음으로 간단하지만 당연하지는 않은 n=2: \(\binom{k+1}{k}=\binom{k+1}{1}=k+1\)
n=2, k=7이라고 하면, 한 종류의 구슬은 첫 번째 상자에 들어가고, 다른 종류의 구슬은 두 번째 상자에 들어간다고 생각할 수 있다. 첫 번째 상자에 들어갈 수 있는 경우의 수는 k+1가지이다.
n=4, k=6개를 순서 상관 없이 복원을 하며 뽑을 수 있는 경우의 수는?
일반화: n개의 상자에 k개의 구별 불가능한 object들을 넣을 수 있는 경우의 수는?
\(\binom{n+k-1}{n-1}\)
= n 개의 원 사이에 k-1개의 구분선을 넣는 경우는?
Story proof: 상황 해석을 통한 증명. 대수적 방법보다 쉬울 때가 있다.
- \[\binom{n}{k}=\binom{n}{n-k}\]
- \(n \times \binom{n-1}{k-1} = k \times \binom{n}{k}\)
n명 중에서 k명 뽑기, k명 중에서 한 명을 회장으로 뽑는 문제로 해석할 수 있다.
회장을 먼저 뽑고 나머지 k명에 들어갈 사람 뽑기 = k명을 뽑고 그 중에서 회장을 뽑기 - \(\binom{m+n}{k} = \sum_{j=0}^k \binom{m}{j} \binom{n}{k-j}\)
m+n개에서 k개 뽑기. 혹은 m개에서 j개뽑고, n개에서 k-j개 뽑는 경우를 전부 더한것. disjoint하기 때문에 다 더할 수 있다.
Non-naive definition of probability
확률공간은 S와 P로 구성되는데,
S는 표본공간이며, P는 함수이다.
공리
\(P(\emptyset)=0, P(S)=1\)
\(P(\cup_{n=1}^\inf A_n)=\sum_{n=1}^\inf P(A_n)\), \(A_i\), \(A_j\)는 서로소
두 가지 공리로부터 대부분의 식을 유도할 수 있다!
Birthday Problem and Properties of Probability
Birthday Problem
k명 중 2명 이상이 같은 생일을 가질 확률
k<365라고 할 때, (k>=365이면 비둘기집 원리에 의해 1)
P=\(\frac{365 \times 364 \times ... \times (365-k+1)}{365^k}\)
Non-naive definition of probability
공리
\(P(\emptyset)=0, P(S)=1\)
\(P(\cup_{n=1}^\inf A_n)=\sum_{n=1}^\inf P(A_n)\), \(A_i\), \(A_j\)는 서로소
확률의 특징
여집합: 1-p
subset: p(a) < p(b)
합집합: p(a)+p(b)-p(a^b)
공리로부터 유도할 수 있다.
포함배제의 원리(Inclusion-exclusion Principle)
A+B+C-A^B-B^C-C^A+A^B^C
몇개든 상관없이 + - + - 하는것.
deMontmort’s Problem
1,2,…,n 이라고 적힌 카드 n개가 있다.
카드가 놓인 위치와 카드에 쓰여있는 숫자가 하나라도 일치할 확률은?
1번 카드가 1번 위치에서 매칭될 확률.
\[P(A_1)=\frac{1}{n}\]1번 카드가 1번에서, 2번카드가 2번에서 매칭될 확률.
\[P(A_1 \cap A_2)=\frac{(n-2)!}{n!}=\frac{1}{n(n-1)}\]…
1번 카드가 1번에서, 2번카드가 2번에서,…,k번 카드가 k번에서 매칭될 확률.
\[\frac{(n-k)!}{n!}\]포함배제를 한다. 그런데 신기하게 테일러 시리즈로 근사됨을 볼 수 있다.
\[P(A_1 \cup A_2 \cup ... \cup An) \\\\ =P(A_1)+P(A_2)+...+P(A_n)-P(A_1 \cup A_2)-... \\\\ = n \times \frac{1}{n} - \frac{n(n-1)}{2!} \times \frac{1}{n(n-1)}+ ...\\\\ =1-\frac{1}{2!}+\frac{1}{3!}-...+(-1)^n \frac{1}{n!} \\\\ \approx 1-\frac{1}{e}\]