Discrete Probability

Discrete Mathematics and its Applications · Kenneth H. Rosen · Ch. 6

Intuition

확률은 단순히 '운'을 계산하는 것이 아니라, 발생 가능한 전체 경우의 수에 대해 특정 사건이 차지하는 비중을 정교하게 모델링하고 그 기댓값을 추적하는 수학적 도구이다.

One-liner

유한하거나 가산 무한한 표본 공간에서 사건의 가능성을 수치화하고, 조건부 정보에 따른 확률의 변화(Bayes)와 결과값의 평균적 거동(Expectation)을 분석한다.

Prerequisites

• Set Theory (집합론): 표본 공간과 사건을 집합으로 표현하기 위한 기초 (Ch. 2).
• Combinatorics (조합론): 순열($P(n, r)$)과 조합($C(n, r)$)을 이용한 경우의 수 계산 (Ch. 5).
• Summation Formulas (합 공식): 기댓값 계산을 위한 등비수열 및 급수의 합 (Ch. 2).

Goals

• 라플라스의 고전적 확률 정의와 현대적 확률 분포의 차이를 이해한다.
• 조건부 확률을 계산하고 두 사건의 독립성을 판별할 수 있다.
• 베이즈 정리를 활용하여 추가 정보가 주어졌을 때의 사후 확률을 갱신한다.
• 무작위 변수의 기댓값과 분산을 계산하여 데이터의 중심 경향과 산포도를 파악한다.
• 체비쇼프 부등식을 통해 확률 변수가 평균에서 벗어날 확률의 상한을 구한다.

Core Concepts

6.1 An Introduction to Discrete Probability (이산 확률의 도입)

Laplace's Definition of Probability (라플라스의 확률 정의)

모든 가능한 결과가 일어날 가능성이 같을 때(Equally likely), 사건 $E$의 확률 $p(E)$는 다음과 같이 정의된다.

Definition

유한 표본 공간 $S$의 모든 원소가 일어날 확률이 같을 때, 사건 $E \subseteq S$의 확률은 다음과 같다.

$$p(E) = \frac{|E|}{|S|}$$

(p.394)

• Sample Space (표본 공간): 실험에서 발생 가능한 모든 결과의 집합 $S$.
• Event (사건): 표본 공간의 부분집합 $E$.

The Probability of Combinations of Events (사건 조합의 확률)

• Complementary Event (여사건): $p(\bar{E}) = 1 - p(E)$. 직접 구하기 어려운 확률은 여사건을 통해 계산하는 것이 유리하다 (p.396).
• Union of Events (사건의 합집합): $p(E_1 \cup E_2) = p(E_1) + p(E_2) - p(E_1 \cap E_2)$. (p.397)

6.2 Probability Theory (확률론)

Probability Distribution (확률 분포)

결과가 반드시 '동일한 확률'을 가질 필요는 없다. 각 결과 $s \in S$에 대해 다음 조건을 만족하는 $p(s)$를 할당한다.

Definition

1. $0 \le p(s) \le 1$
2. $\sum_{s \in S} p(s) = 1$ (p.401)

Conditional Probability (조건부 확률)

사건 $F$가 일어났다는 전제 하에 사건 $E$가 일어날 확률이다.

Definition

$p(F) > 0$일 때, $F$가 주어졌을 때 $E$의 조건부 확률 $p(E|F)$는 다음과 같다.

$$p(E|F) = \frac{p(E \cap F)}{p(F)}$$

(p.404)

Independence (독립성)

두 사건이 서로에게 아무런 정보를 주지 않을 때 독립이라고 한다.

• 정의: $p(E \cap F) = p(E)p(F)$ (p.405).

Bernoulli Trials and Binomial Distribution (베르누이 시행과 이항 분포)

결과가 '성공' 혹은 '실패' 두 가지만 존재하는 독립적인 시행을 반복할 때의 확률이다.

Theorem

성공 확률이 $p$, 실패 확률이 $q = 1-p$인 $n$번의 독립적인 베르누이 시행에서 정확히 $k$번 성공할 확률은 다음과 같다.

$$b(k; n, p) = C(n, k) p^k q^{n-k}$$

(p.407)

Random Variables (무작위 변수)

표본 공간의 각 결과에 실수 값을 할당하는 함수이다 (p.408).

• 예: 동전을 3번 던질 때 '앞면이 나온 횟수'.

6.3 Bayes' Theorem (베이즈 정리)

부분적인 증거를 바탕으로 사건의 확률을 갱신하는 강력한 도구이다.

Theorem (Bayes' Theorem)

$p(E) \neq 0, p(F) \neq 0$일 때:

$$p(F|E) = \frac{p(E|F)p(F)}{p(E|F)p(F) + p(E|\bar{F})p(\bar{F})}$$

(p.418)

• Application: 스팸 메일 필터링 (특정 단어 $w$가 포함되었을 때 스팸일 확률 계산).

6.4 Expected Value and Variance (기댓값과 분산)

Expected Value (기댓값)

무작위 변수가 평균적으로 가질 것으로 예상되는 값이다.

Definition

표본 공간 $S$ 위에서의 무작위 변수 $X$의 기댓값 $E(X)$는 다음과 같다.

$$E(X) = \sum_{s \in S} p(s)X(s)$$

또는 값 $r$을 기준으로 $E(X) = \sum_{r \in X(S)} p(X=r)r$. (p.426, 427)

• Linearity of Expectations (기댓값의 선형성): $E(X_1 + \dots + X_n) = E(X_1) + \dots + E(X_n)$. 독립 여부와 상관없이 성립하며 매우 강력한 분석 도구이다 (p.429).

Variance and Standard Deviation (분산과 표준 편차)

값이 기댓값(평균)으로부터 얼마나 퍼져 있는지를 나타낸다.

Definition

• Variance (분산): $V(X) = E((X - E(X))^2) = E(X^2) - (E(X))^2$.
• Standard Deviation (표준 편차): $\sigma(X) = \sqrt{V(X)}$. (p.436)

Chebyshev's Inequality (체비쇼프 부등식)

무작위 변수가 평균에서 특정 거리 이상 떨어져 있을 확률의 상한을 제공한다.

Theorem

양의 실수 $r$에 대하여:

$$p(|X(s) - E(X)| \ge r) \le \frac{V(X)}{r^2}$$

(p.439)

Key Theorems & Formulas

• Geometric Distribution (기하 분포): 첫 성공이 나올 때까지의 시행 횟수 $X$의 기댓값 $E(X) = 1/p$ (p.433).
• Product of Independent Variables: $X, Y$가 독립이면 $E(XY) = E(X)E(Y)$ (p.435).
• Sum of Independent Variances: $X, Y$가 독립이면 $V(X+Y) = V(X) + V(Y)$ (p.437).

Intuitions

• Monty Hall 직관: 처음 선택한 문이 정답일 확률은 $1/3$이지만, 나머지 두 문 중 하나가 오답임이 밝혀지면 '바꾸지 않았을 때 정답일 확률'은 여전히 $1/3$인 반면, '바꿨을 때 정답일 확률'은 남은 확률 전체인 $2/3$가 된다 (p.398).
• Bayes' Theorem 직관: 희귀 질병($0.001\%$) 검사에서 양성이 나왔을 때, 검사 정확도가 $99\%$라 하더라도 실제 질병에 걸렸을 확률은 매우 낮을 수 있다. 이는 '진짜 양성'보다 '가짜 양성'의 절대적 숫자가 더 많을 수 있기 때문이다 (p.419).
• Linearity of Expectation 직관: 여러 사건이 서로 얽혀 있어도(종속적이어도), 전체의 평균은 각각의 평균을 더한 것과 같다. 이는 복잡한 시스템의 평균치를 구할 때 시스템을 잘게 쪼개서 분석할 수 있게 해준다.

Worked Examples

Example 1: Poker Hand (Four of a Kind)

문제: 52장의 카드 중 5장을 뽑을 때, 같은 종류의 카드 4장이 포함될 확률은?

핵심 단계:

1. 전체 경우의 수: $C(52, 5) = 2,598,960$.
2. 포카드를 만드는 경우:
   • 종류 선택: $C(13, 1)$
   • 해당 종류 4장 모두 선택: $C(4, 4) = 1$
   • 나머지 1장 선택 (남은 48장 중): $C(48, 1)$
3. 확률: $\frac{13 \times 1 \times 48}{2,598,960} \approx 0.00024$. (p.396)

Example 2: Birthday Problem

문제: 최소 몇 명이 모여야 생일이 같은 사람이 있을 확률이 $1/2$보다 커지는가?

핵심 단계:

1. 모든 사람의 생일이 다를 확률 $p_n$을 계산한다.
2. $p_n = \frac{365}{366} \cdot \frac{364}{366} \cdots \frac{367-n}{366}$ (366일 기준).
3. $1 - p_n > 0.5$가 되는 최소 $n$을 찾는다. 요점: 결과는 $n=23$으로, 직관보다 훨씬 적은 인원만으로도 충분하다 (p.410).

Common Pitfalls

Pitfall

Independence vs. Mutually Exclusive: 독립 사건(Independence)과 배반 사건(Mutually Exclusive)을 혼동하지 말 것. 독립은 한 사건의 발생이 다른 사건의 확률에 영향을 주지 않는 것이고, 배반은 두 사건이 동시에 일어날 수 없는($E \cap F = \emptyset$) 것이다.

Pitfall

Expected Value isn't "Random": 무작위 변수(Random Variable)는 이름과 달리 '변수'가 아닌 '함수'이며, 기댓값은 확률적으로 결정되는 값이 아니라 확정된 상수값(평균)이다 (p.408).

Connections

• 선행 개념: Ch. 5 조합론 (확률 계산의 기본 도구).
• 후속 개념: Ch. 7 고급 계수 기법 (점화식을 이용한 확률 계산).
• 응용 분야:
  • Monte Carlo Algorithm: 결정론적 해법이 어려운 문제를 무작위 추출을 통해 근사적으로 해결 (p.411).
  • Probabilistic Method: 특정 성질을 가진 객체가 존재함을 증명하기 위해, 무작위로 뽑은 객체가 해당 성질을 가질 확률이 0보다 큼을 보여주는 비구성적 증명법 (Ch. 1 비구성적 존재 증명의 확률적 확장, p.413).

Critical Notes

교재가 강조하는 것

• 도박(Gambling)에서 기원한 확률론이 컴퓨터 과학(알고리즘 복잡도)과 유전학 등 다양한 분야로 확장되는 과정.
• 라플라스의 고전적 정의에서 일반적인 확률 분포 정의로의 전이.

실제로 중요한 것 (요약자 관점)

• Linearity of Expectations: 실무적으로 복잡한 알고리즘의 평균 실행 시간을 계산할 때 가장 많이 쓰이는 기법이다.
• Bayesian Spam Filtering: 단순한 수학 공식이 실제 스프트웨어 서비스(스팸 필터)에 어떻게 구현되는지 보여주는 훌륭한 사례이다.

교재가 생략하거나 얼버무리는 것

• 연속 확률 분포(Continuous Probability Distribution)는 이산 수학의 범위를 벗어나므로 다루지 않으며, 이를 위해서는 미적분학(Integral Calculus)이 필요함을 짧게 언급만 하고 넘어간다 (p.401).

Open Questions

이해하지 못한 것

• 확률적 방법(Probabilistic Method)에서 램지 수 $R(k, k)$의 하한선을 증명하는 과정의 조합론적 부등식 처리.

더 알고 싶은 것

• 기하 분포 외에 컴퓨터 과학에서 자주 쓰이는 푸아송 분포(Poisson Distribution)나 지수 분포(Exponential Distribution)와의 연결 고리.