C. Counting and Probability

집계와 확률에 대해 알아보자.

C.1. Counting

집계는 몇 개나 있는지 세는 것이다.

Rules of sum and product

합의 법칙은 서로소인 집합에서는 |A∪B| = |A| + |B|임을 말한다. 곱의 법칙은 A, B가 유한집합일 때 |A × B| = |A|·|B|임을 말한다.

Strings

유한집합 S에서의 문자열은 S의 원소의 나열이다. 길이 k의 문자열을 k-문자열이라 한다. 부분 문자열은 부분 집합인 문자열이다. k-부분문자열은 길이 k의 부분문자열이다.

Permutations

유한집합 S의 순열은 S의 각 원소가 한 번만 등장하는 순서열이다. k-순열은 S 내 원소 k개인 집합의 순열이다. n-집합의 k-순열의 수는 \frac{n!}{(n-k)!}이다.

Combinations

유한집합 S의 k-조합은 k-부분집합이다. n-집합의 k-조합의 수는 \frac{n!}{k!(n-k)!} 이다.

Binomial coefficients

n-집합의 k-조합의 수를 \binom{n}{k}로 표기하며 이항 계수라고도 한다. 이는 이항 표현식(x+y)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{k} y^{n-k}과 연관이 있다.

Binomial bounds

이항 계수는 (\frac{n}{k})^{k} \leq \binom{n}{k} \leq (\frac{en}{k})^{k}의 상한/하한을 갖는다.

0 \leq \lambda \leq 1에 대해 \binom{n}{\lambda k} \leq 2^{n H(\lambda)}이 성립한다. 여기서 H(\lambda) = -\lambda \lg \lambda - (1 - \lambda) \lg (1 - \lambda)이진 엔트로피 함수이다.

C.2. Probability

확률은 근원사건의 집합인 표본공간 S에 의해 정해진다. 사건은 표본공간의 부분집합이다. S는 확실 사건, \emptyset영사건이라 한다. A \cap B = \emptyset이면 두 사건은 상호 배타적이라 한다.

Axioms of probability

표본공간 S에서의 확률분포 Pr은 다음의 확률공리들을 만족하는 함수이다:

  • Pr(A) ≥ 0.
  • Pr(S) = 1.
  • 두 사건 A, B가 상호 배타적이면 Pr(A ∪ B) = Pr(A) + Pr(B).

Pr(A)를 A의 확률이라 한다. \bar{A} = S - A를 A의 여사건이라 하며 P(\bar{A}) = 1 - P(A)이다.

Discrete probability distribution

유한/가산 표본공간에서 정의된 확률분포를 이산 확률분포라 한다. S가 유한이고 모든 근원사건의 확률이 같으면 균등확률분포라 한다. 예로는 공평한 동전이 있다.

Continuous uniform probability distribution

구간 [c, d]에 대해, a ≤ c ≤ d ≤ b에서 연속균등확률분포P([c, d]) = \frac{d-c}{b-a}로 정의된다.

Conditional probability and independence

조건부확률P(A | B) = \frac{P(A \cap B)}{P(B)}로 정의된다. P(A ∩ B) = P(A)P(B)이면 A, B는 독립이다. 사건들 내의 모든 쌍이 독립이면 쌍별 독립이다. 사건들의 모든 확률의 곱이 사건들의 교집합의 확률과 같으면 이 사건들은 상호 독립이다. 상호 독립이면 쌍별 독립이지만 반대는 아니다.

Bayes’ theorem

P(A|B) = \frac{P(A) P(B|A)}{P(B)}베이즈 정리라 한다.

C.3. Discrete random variables

이산확률변수는 유한/가산 확률공간에서 실수로의 함수이다. 확률변수 X와 실수 x에 대해, f(x) = P(X = x)을 X로부터 정의되는 확률밀도함수라 한다. f(x, y) = P(X = x and Y = y)를 X와 Y로부터 정의되는 결합확률밀도함수라 한다. 결합확률밀도함수가 각 확률변수의 확률밀도함수의 곱이면 두 확률변수는 독립이라 한다.

Expected value of a random variable

이산확률변수의 기대값(기대, 평균)은 E[X] = \sum_{x} x P(X = x)이다. E[X + Y] = E[X] + E[Y] 가 성립하며 이를 기대값의 선형성이라 한다. f(x)가 볼록 함수일 때 젠센 부등식인 E[f(X)] ≥ f(E[X])가 성립한다.

Variance and standard deviation

확률변수의 분산\mathrm{Var}[X] = E[(X - E[X])^{2}]로 정의된다. 이의 제곱근은 표준편차라 한다.

C.4. The geometric and binomial distribution

동전 던지기는 성공실패 두 가지 경우가 있는 베르누이 시행으로 볼 수 있다. 베르누이 시행에 대해서는 성공 확률 p를 부여한다.

The geometric distribution

P(X = k) = q^{k-1}p의 분포를 기하 분포라 한다. E[X] = \frac{1}{p}, \mathrm{Var}[X] = \frac{q}{p^{2}}이다.

The binomial distribution

P(X = k) = \binom{n}{k} p^{k} q^{n-k}의 분포를 이항 분포라 한다. E[X] = np, \mathrm{Var}[X] = npq이다.

Lemma. n ≥ 0, 0 < p < 1, q = 1 – p, 0 ≤ k ≤ n이면 b(k; n; p) \leq (\frac{np}{k})^{k} (\frac{nq}{n-k})^{n-k}이다.

C.5. The tails of the binomial distribution

이항 분포의 꼬리를 알아보자.

Theorem. 확률 p의 베르누이 시행 n번에 대해 0 ≤ k ≤ n이면 P(X \geq k) \leq \binom{n}{k}p^{k}이다.

Corollary. 확률 p의 베르누이 시행 n번에 대해 0 ≤ k ≤ n이면 P(X \geq k) \leq \binom{n}{k}(1-p)^{n-k}이다.

Theorem. 확률 p의 베르누이 시행 n번에 대해 0 ≤ k ≤ np이면 P(X < k) < \frac{kq}{np - k} b(k; n; p)이다.

Corollary. 확률 p의 베르누이 시행 n번에 대해 0 ≤ k ≤ np/2이면 P(X < k)는 P(X < k + 1)의 절반보다 작다.

Corollary. 확률 p의 베르누이 시행 n번에 대해 np < k < n이면 P(X > k) < \frac{(n-k)p}{k - np}b(k; n; p)이다.

Corollary. 확률 p의 베르누이 시행 n번에 대해 (np + n)/2 < k < n이면 P(X > k)는 P(X > k – 1)의 절반보다 작다.

Theorem. i번째 시행의 확률이 p_{i}인 베르누이 시행 n번에 대해 전체 성공 횟수를 나타내는 확률변수가 X고 E[X] = μ이면 r > μ에 대해 P(X - \mu > r) \leq (\frac{\mu e}{r})^{r}이다.

Corollary. 확률 p의 베르누이 시행 n번에 대해 r > np이면 P(X - np \geq r) \leq (\frac{npe}{r})^{r}이다.