6. 기댓값 (Expected Value, E[X]) — 확률 가중 평균

핵심 인사이트

기댓값 (Expected Value) E[X] 은 "무한히 반복하면 평균적으로 얻을 값"이 아니라, 확률로 가중된 가중 평균 (Probability-Weighted Average) 이다. 기댓값의 선형성 (Linearity of Expectation) 은 독립성 여부와 무관하게 항상 성립하는 강력한 도구로, 복잡한 알고리즘 분석을 극적으로 단순화한다. 전체 기댓값 법칙 (Law of Total Expectation) 은 조건부 기댓값을 재귀적으로 활용해 복잡한 기댓값을 단계별로 계산하는 핵심 기법이다.

Ⅰ. 기댓값의 정의

이산 확률 변수

E[X] = Σₓ x · P(X=x) = x₁·p₁ + x₂·p₂ + ... + xₙ·pₙ

예시 — 주사위:

E[X] = 1·(1/6) + 2·(1/6) + 3·(1/6) + 4·(1/6) + 5·(1/6) + 6·(1/6)
     = (1+2+3+4+5+6)/6 = 21/6 = 3.5

주사위를 던져 3.5가 나오는 경우는 없지만, 기댓값은 3.5다 — 이것이 "기댓값은 실제 가능한 값이 아닐 수 있다"는 의미다.

연속 확률 변수

E[X] = ∫₋∞^{+∞} x · f(x) dx

예시 — 균등 분포 U(0,1):

E[X] = ∫₀¹ x · 1 dx = [x²/2]₀¹ = 0.5

함수의 기댓값 — LOTUS 법칙

(Law of the Unconscious Statistician)

이산: E[g(X)] = Σₓ g(x) · P(X=x)
연속: E[g(X)] = ∫ g(x) · f(x) dx

g(X)의 분포를 직접 구하지 않아도 됨!

📢 섹션 요약 비유: 기댓값은 "복권을 수백만 번 사면 1번 당 평균 얼마를 돌려받을까"다 — 1번으로 그 금액을 받을 수는 없지만, 장기적 평균을 나타낸다.

Ⅱ. 기댓값의 성질 — 선형성이 핵심

선형성 (Linearity of Expectation)

E[aX + b] = a·E[X] + b         (상수 이동과 스케일)
E[X + Y] = E[X] + E[Y]         (독립 여부 무관! 항상 성립)
E[aX + bY + c] = a·E[X] + b·E[Y] + c

왜 독립 없이도 성립하는가?

E[X+Y] = Σₓ Σᵧ (x+y) · P(X=x, Y=y)
       = Σₓ Σᵧ x · P(X=x, Y=y) + Σₓ Σᵧ y · P(X=x, Y=y)
       = Σₓ x · P(X=x) + Σᵧ y · P(Y=y)
       = E[X] + E[Y]    ← 결합 분포의 주변화 (Marginalization) 이용

곱의 기댓값 (독립인 경우만)

X⊥Y이면: E[XY] = E[X] · E[Y]
종속이면: E[XY] = E[X]·E[Y] + Cov[X,Y]

기댓값 성질 정리표

📢 섹션 요약 비유: "합의 기댓값" 선형성은 "각 직원 급여 평균의 합 = 전체 급여 합의 평균"처럼, 개별 계산을 따로 하고 더해도 된다는 강력한 단순화 규칙이다.

Ⅲ. 기댓값 분석 — 퀵정렬 평균 시간 복잡도

기댓값의 선형성이 알고리즘 분석에 어떻게 활용되는지 보여주는 대표 예시다.

랜덤 퀵정렬 (Randomized QuickSort) 분석

n개 원소를 정렬할 때, 비교 횟수의 기댓값:

X_{ij} = {1 if 원소 i와 j가 직접 비교됨, 0 otherwise}

총 비교 횟수 X = Σ_{i<j} X_{ij}

E[X] = Σ_{i<j} E[X_{ij}]    ← 선형성 적용!
      = Σ_{i<j} P(i와 j가 비교됨)
      = Σ_{i<j} 2/(j-i+1)
      ≈ n·H(n) ≈ n·ln(n) = O(n log n)

선형성 덕분에 각 쌍의 비교 확률만 계산하면 전체 기댓값이 나온다.

┌────────────────────────────────────────────────────────┐
│  기댓값 분석 — E[X] 확률 가중 시각화                   │
│                                                        │
│  X값    확률     기여값                                │
│  ┌────┬────────┬────────────────────────────────────┐ │
│  │ 1  │ P=0.2  │ ████  (1×0.2 = 0.2)               │ │
│  │ 2  │ P=0.3  │ ██████████ (2×0.3 = 0.6)          │ │
│  │ 3  │ P=0.3  │ ████████████████ (3×0.3 = 0.9)    │ │
│  │ 4  │ P=0.2  │ █████████████████ (4×0.2 = 0.8)   │ │
│  └────┴────────┴────────────────────────────────────┘ │
│                                                        │
│  E[X] = 0.2+0.6+0.9+0.8 = 2.5   ← 가중 평균          │
│  확률 기중(막대 높이 × 위치)의 균형점                  │
└────────────────────────────────────────────────────────┘

📢 섹션 요약 비유: 퀵정렬 분석에서 선형성은 "수천 쌍의 비교를 한꺼번에 계산하는 대신, 각 쌍을 독립적으로 계산해서 더하는" 마법 같은 분해 기법이다.

Ⅳ. 의사결정 이론 — 기댓값 기반 선택

기댓값 최대화 (Expected Utility Maximization)

각 행동 aᵢ의 기대 보상:
  EU(aᵢ) = Σⱼ P(결과 j) · U(결과 j | 행동 aᵢ)

최적 행동: a* = argmax_i EU(aᵢ)

위험 관리 예시:

기댓값만으로는 "공격적 투자 > 보수적 > 예금"이지만, 위험 회피 (Risk Aversion) 를 고려하면 효용 함수 (Utility Function) 로 재계산 필요.

📢 섹션 요약 비유: 기댓값 기반 의사결정은 "복권 여러 장 살지 vs 한 번 산다"를 수익 기댓값으로 비교하는 것이다 — 하지만 실제 선택에는 위험 허용도도 함께 고려해야 한다.

Ⅴ. 전체 기댓값 법칙 (Tower Property)

공식

E[X] = E[E[X|Y]]
     = Σᵧ E[X|Y=y] · P(Y=y)   (이산)
     = ∫ E[X|Y=y] · f_Y(y) dy   (연속)

응용 — 재귀 알고리즘 분석

랜덤 퀵정렬 T(n):
  피벗이 k번째 원소로 선택될 확률 = 1/n

  E[T(n)] = E[E[T(n)|피벗 위치]]
           = (1/n) Σₖ₌₁ⁿ (T(k-1)+T(n-k)+cn)
           → T(n) = O(n log n) 도출

응용 — 이중 확률 계산

보험 청구 총액 S = X₁+X₂+...+X_N (N: 랜덤 청구 건수)

E[S] = E[E[S|N]]
     = E[N · E[X₁]]     (동일 분포 가정)
     = E[N] · E[X₁]

→ 청구 건수와 금액을 분리해서 계산 가능!

📢 섹션 요약 비유: 전체 기댓값 법칙은 "학교 평균 성적"을 직접 계산하는 대신 "각 반 평균의 가중 평균"으로 계산하는 것과 같다 — 복잡한 문제를 계층별로 쪼개서 푼다.

📌 관련 개념 맵

📈 관련 키워드 및 발전 흐름도

[확률 분포 (Probability Distribution)]
    │
    ▼
[기댓값 (Expected Value)]
    │
    ▼
[분산 (Variance)]
    │
    ▼
[중심극한정리 (CLT, Central Limit Theorem)]

이 흐름도는 확률 분포에서 기댓값과 분산을 거쳐 중심극한정리로 확장되는 흐름을 보여준다.

👶 어린이를 위한 3줄 비유 설명

• 기댓값은 "주사위를 아주 많이 던지면 평균적으로 몇이 나올까"를 미리 계산하는 것이야 — 실제로 3.5가 나올 수는 없지만, 평균은 3.5야.
• 선형성 덕분에 복잡한 게임 점수의 기댓값도 각 파트별로 쪼개서 더하면 돼 — 독립이든 아니든 상관없이!
• 알고리즘 설계자들은 기댓값으로 "평균적으로 얼마나 빠른가"를 계산해서 좋은 알고리즘을 고른다.