Expected Value: 기댓값, Linearity

정의

확률변수 X 의 기댓값:

기댓값은 “평균적으로 기대되는 값”. 랜덤 알고리즘 분석, 확률 DP 문제에서 핵심 도구.

문제 상황

복잡한 확률 공간에서 랜덤 변수의 기댓값을 구해야 할 때, 직접 계산하면 경우의 수가 폭발적으로 늘어난다.

예시: n 개 원소의 랜덤 순열에서 고정점 (자기 자리에 오는 원소, fixed point) 의 평균 개수?

순진한 접근: 고정점이 정확히 k 개인 경우를 모두 열거. 포함-배제 원리 필요. 복잡함.

핵심 아이디어: 지시 변수 (indicator variable) 로 분해 + Linearity of Expectation 적용.

시각화

flowchart LR
    R["랜덤 변수 X 계산"] -->|"직접 계산"| D["경우의 수 폭발"]
    R -->|"분해 접근"| L["지시 변수 Xi 합으로 표현"]
    L --> Ei["각 E_Xi 개별 계산"]
    Ei --> S["Linearity 적용해 합산"]
    style D fill:#f9a825,color:#000
    style S fill:#2e7d32,color:#fff

핵심 아이디어

Linearity of Expectation

독립 여부 무관. X, Y 가 상관관계가 있어도 성립한다.

이것이 핵심: 복잡한 합 확률 변수를 단순한 지시 변수들의 합으로 분해 가능.

지시 변수

지시 변수 $X_i$:

분해 패턴

1. 원하는 값 X 를 지시 변수 합으로 표현: $X={\sum }_{\{}i\}{X}_i$
2. Linearity 적용: $E[X]={\sum }_{\{}i\}E[X_i]$
3. 각 $E[X_i]=P({\text{이벤트}}_i)$ 를 개별 계산

각 $P({\text{이벤트}}_i)$ 는 원래 문제보다 훨씬 단순한 경우가 많다.

알고리즘

예시 1: Fixed Points in Random Permutation

n 개의 원소를 랜덤 순열 배치, 고정점 개수의 기댓값?

• $X_i$: i번째 원소가 고정점이면 1, 아니면 0
• $P(X_i=1)=\frac{1}{\{}n\}$ (n 자리 중 자기 자리에 올 확률)
• Linearity 적용:

랜덤 순열의 고정점 기댓값 = 1 (n 에 무관).

예시 2: Coupon Collector

n 종류 쿠폰, 매번 1개 랜덤 수집. 전 종류 모으려면 평균 몇 번?

• k-1 종류 보유 중, 새 쿠폰 확률 = $\frac{\{}{n}-k+1\}\{n\}$
• k 번째 새 쿠폰 수집에 필요한 시도 횟수 기댓값:

여기서 $H_n=1+\frac{1}{2}+\dots +\frac{1}{\{}n\}$ 는 조화급수.

예시 3: Quicksort 평균 비교 횟수

임의 pivot 선택 quicksort 의 평균 비교 횟수.

$X_{\{}ij\}$: 원소 i 와 j 가 비교되면 1, 아니면 0 ($i\text{<}j$).

$P(X_{\{}ij\}=1)=\frac{2}{\{}j-i+1\}$ (i..j 범위에서 i 또는 j 가 먼저 pivot 으로 선택될 확률).

구현

import random
​
def count_fixed_points(perm):
  return sum(1 for i, x in enumerate(perm) if i == x)
​
def coupon_steps(n, trials=50000):
  total = 0
  for _ in range(trials):
      collected = set()
      steps = 0
      while len(collected) < n:
          collected.add(random.randint(0, n - 1))
          steps += 1
      total += steps
  return total / trials
​
# 고정점 기댓값 = 1 검증
n = 8
trials = 50000
random.seed(42)
fp_total = 0
for _ in range(trials):
  perm = list(range(n))
  random.shuffle(perm)
  fp_total += count_fixed_points(perm)
print("Fixed points E =", round(fp_total / trials, 3))  # ~1.0
​
# Coupon Collector E[T] ~ n * H_n
n_c = 5
sim = coupon_steps(n_c)
theory = n_c * sum(1.0 / (n_c - k + 1) for k in range(1, n_c + 1))
print("Coupon n=5 sim=", round(sim, 2), "theory=", round(theory, 2))

#include <bits/stdc++.h>
using namespace std;
​
int main() {
  mt19937 rng(42);
  int n = 8, trials = 50000;
  double fp = 0;
  vector<int> perm(n);
  iota(perm.begin(), perm.end(), 0);
  for (int t = 0; t < trials; t++) {
      shuffle(perm.begin(), perm.end(), rng);
      for (int i = 0; i < n; i++) fp += (perm[i] == i);
  }
  printf("Fixed points E = %.3f\n", fp / trials);  // ~1.0
​
  // Coupon Collector
  int nc = 5;
  double theory = 0;
  for (int k = 1; k <= nc; k++) theory += (double)nc / (nc - k + 1);
  printf("Coupon n=%d theory=%.2f\n", nc, theory);
  return 0;
}

Fixed points E = 1.000
Coupon n=5 sim=11.41 theory=11.42

복잡도

기댓값 계산은 분석 도구이지, 알고리즘 자체가 아님. 실제 알고리즘 복잡도에 자주 등장하는 공식:

함정

흔한 실수

1. $E[XY]\ne E[X]\cdot E[Y]$ 를 독립 확인 없이 적용
2. 조건부 기댓값 $E[X\mid A]$ 와 $E[X]$ 혼동
3. 지시 변수로 분해 시 이벤트 겹침 (overlap) 고려 안 함
4. 연속 분포에서 합산을 적분으로 바꾸지 않음

BOJ 연습 문제

참고

• 확률론 기초
• Markov Chain
• 랜덤화 알고리즘
• 베이즈 정리
• Birthday Problem