Lecture 02. Story Proofs, Axioms of Probability (Statistics 110, Harvard)

이 포스팅은 Harvard에서 진행된 Joe Blitzstein의 Statics 110 강좌를 기반으로 작성되었습니다.

• 강의 및 자료 링크

문제를 풀기 위한 Tips

1. 상식으로 접근하지 않기, reason을 생각해보기
2. 몇 가지 간단한 케이스 대입해보기 ex. $n=0, k=1$ 등 간단한 숫자들
3. label 붙이기 ex. 10명 중 4명과 6명의 팀을 구성할 때와 5명씩 두 팀을 구성할 때
   $\binom{10}{4} = \binom{10}{6} \neq \binom{10}{5} \div 2!$

[continue] Sampling Table: choose $k$ objects out of $n$

	order matter	order doesn’t
replace	$n^k$	$\binom{n+k-1}{k}$
don’t replace	$n(n-1)…(n-k+1)$	$\binom{n}{k}$

order doesn't & replace 증명
Pick $k$ times from set of $n$ objects, where order doesn’t matter with replacement.

1. Extreme Case (Tip 2 적용)
   $k=0 \Rightarrow \binom{n-1}{0} = 1$
   $k=1 \Rightarrow \binom{n}{1} = n$

2. Simplest Nontrivial Example: $n=2$
   \(\binom{k+1}{k} = \binom{k+1}{1} = k+1\)

object가 2개임을 가정했을 때, $o_1$을 선택한 경우의 수: {0, 1, …, k} 중 한 개를 선택할 경우의 수
($o_2$를 선택한 경우의 수는 $k$개에서 $|o_1|$을 빼면 됨)

1. 동치 생각하기
   Equiv. How many ways are there to put $k$ indistinguishable particles into $n$ indistinguisable boxes.

$n$개의 boxes → $n-1$개의 lines, $k$개의 dots → $k$개의 dots
즉, 총 $n+k-1$개의 자리가 있고, 그 중 점의 위치만 고르면 나머지 위치는 선들의 위치가 됨
$\therefore \binom{n+k-1}{1}$

Story Proofs: Proof by Interpretation

[Ex. 1]

\[\binom{n}{k} = \binom{n}{n-k}\]

$n$명 중 $k$명을 선택하는 것은, 나머지 $n-k$명을 선택하는 것과 같다.

[Ex. 2]

\[n\binom{n-1}{k-1} = k\binom{n}{k}\]

Pick $k$ ppl out of $n$, with 1 designated as president.
LHS: president 1명을 선택, 나머지 중에서 $k-1$명 선택
RHS: $n$명 중 $k$명을 먼저 선택, $k$명 중에서 president 1명 선택

[Ex. 3] Vandermonde

\[\binom{m+n}{k} = \sum^k_{j=0}\binom{m}{j}\binom{n}{k-j}\]

$m+n$명 중 $k$명 선택
LHS: 말 그대로
RHS:

$m$명의 그룹	$n$명의 그룹
$0$	$k$
$1$	$k-1$
…	…
$k$	$0$

Axioms of Probability (non-naive)

A probability space (확률 공간) consists of $S$ and $P$,
where $S$ is a sample space, and $P$ is a function which takes an event $A \subseteq S$ as input, and returns $P(A) \in [0, 1]$ as output, such that
(1) $P(\varnothing) = 0, P(S) = 1$
(2) $P(\displaystyle \bigcup^{\infin}{n=1} A_n) = \sum^\infin{n=1}P(A_n)$ if $A_1, A_2, …$ are disjoint(서로소).