Linearity of Expectation (기댓값의 선형성)

정의

Linearity of Expectation (기댓값의 선형성) 은 두 확률 변수 X, Y 에 대해 E[X + Y] = E[X] + E[Y] 가 항상 성립한다는 정리. X 와 Y 가 독립일 필요가 없다. 스칼라 곱도 선형: E[aX + bY] = a·E[X] + b·E[Y].

조합론 / PS 에서 “복잡한 확률 변수를 단순한 indicator 의 합으로 분해” 하는 강력한 도구.

문제 상황과 동기

“랜덤한 순열에서 inversion 개수의 기댓값” 이나 “n 개의 공을 m 개의 상자에 랜덤하게 넣을 때 빈 상자 개수의 기댓값” 을 계산하려면, naive 하게는 모든 경우의 수를 직접 평균내야 한다.

• naive: 전체 경우 n! 또는 m^n 가지 전부 시뮬레이션 → 불가능.
• indicator + 선형성: 각 사건별 indicator 변수의 기댓값을 더하기만 하면 됨. 대부분 O(1) 계산.

핵심 통찰: X 의 분포를 몰라도 기댓값 자체는 더할 수 있다.

시각화

핵심 아이디어

공식

E[X + Y] = E[X] + E[Y]      (any X, Y, not necessarily independent)
E[aX + bY] = a·E[X] + b·E[Y]

증명 스케치 (이산 확률 변수):

E[X + Y] = Σ_x Σ_y (x + y) · P(X = x, Y = y)
         = Σ_x Σ_y x · P(X = x, Y = y) + Σ_x Σ_y y · P(X = x, Y = y)
         = Σ_x x · P(X = x) + Σ_y y · P(Y = y)
         = E[X] + E[Y]

주변 확률로의 축약이 key. 독립성 가정 없이 가능.

Indicator 변수 트릭

X_A = 1 if event A occurs, 0 otherwise
E[X_A] = P(A)

복잡한 확률 변수 Y 를 여러 indicator 의 합 으로 표현하면, 기댓값은 각 P(A) 의 합.

알고리즘

1. 관심 있는 값을 확률 변수 Y 로 정의.
2. Y 를 indicator 변수 X_1, ..., X_k 의 합으로 분해.
3. 각 E[X_i] = P(event i) 계산 (보통 O(1)).
4. E[Y] = Σ E[X_i] = Σ P(event i).

구현

// 예제: n 개의 공을 m 개의 상자에 랜덤하게 넣을 때
// 빈 상자 개수의 기댓값 = m * (1 - 1/m)^n
#include <bits/stdc++.h>
using namespace std;
​
int main() {
  int n, m; cin >> n >> m;
  // 각 상자가 빌 확률 = (1 - 1/m)^n
  double p_empty = pow(1.0 - 1.0 / m, n);
  double expected = m * p_empty;
  cout << fixed << setprecision(10) << expected << "\n";
​
  // 검증: indicator 변수 I_i = "i번 상자가 비었다"
  // E[I_i] = (1 - 1/m)^n
  // E[∑ I_i] = m * (1 - 1/m)^n
  return 0;
}

# 예제: n 개 공을 m 개 상자에 랜덤, 빈 상자 기댓값
def expected_empty(n: int, m: int) -> float:
  # E[빈 상자] = m * (1 - 1/m)^n
  from math import pow
  p_empty = pow(1.0 - 1.0 / m, n)
  return m * p_empty
​
# 예제2: 길이 n 순열의 inversion 기댓값 = n*(n-1)/4
def expected_inversions(n: int) -> float:
  # 각 쌍 (i,j) 가 inversion 일 확률 = 1/2
  # 쌍 개수 = C(n, 2) = n*(n-1)/2
  return n * (n - 1) / 4.0
​
n, m = map(int, input().split())
print(f"{expected_empty(n, m):.10f}")
print(f"inversion E: {expected_inversions(n):.10f}")

// 기댓값 선형성: 빈 상자 개수 기댓값
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
​
      // p_empty = (1 - 1/m)^n
      double p_empty = Math.pow(1.0 - 1.0 / m, n);
      double expected = m * p_empty;
      System.out.printf("%.10f%n", expected);
​
      // inversion 기댓값 = n*(n-1)/4
      double invE = (double) n * (n - 1) / 4.0;
      System.out.printf("%.10f%n", invE);
  }
}

3 4

1.2656250000
1.5000000000

10 5

1.0737418240
22.5000000000

복잡도

대표 예제: 순열의 Inversion

길이 n 의 랜덤 순열에서 inversion 쌍 (i, j) (i < j 이고 a[i] > a[j]) 의 기댓값:

• Indicator I_{i,j} = 1 if (i,j) 는 inversion
• P(I_{i,j} = 1) = 1/2 (두 원소 중 큰 쪽이 앞에 있을 확률)
• 총 쌍 = C(n, 2) = n(n-1)/2
• E[inversions] = Σ P(I_{i,j} = 1) = n(n-1)/4

선형성이 없으면 inversion 개수의 분포 (Gaussian) 를 알아야 하지만, 선형성 덕분에 분포와 무관하게 평균만 O(1).

대표 예제: Coupon Collector

n 종류의 쿠폰을 모두 모을 때까지의 기댓값 시행 횟수:

• T = 총 시행 횟수. T = T_1 + T_2 + … + T_n
• T_k = k-1 종류를 가진 상태에서 새 종류가 나올 때까지 시행 횟수
• T_k ~ Geometric(p = (n - k + 1) / n)
• E[T_k] = n / (n - k + 1)
• E[T] = n · (1 + 1/2 + 1/3 + … + 1/n) = n · H_n = n log n + O(n)

변형 / 활용

함정

1. 독립성 오해

“E[XY] = E[X]·E[Y]” 는 독립일 때만. 선형성은 E[X+Y] 에만 적용.

2. 분포 정보 손실

기댓값만 알 뿐, 분산이나 확률 분포는 모름. 분산은 Var(X+Y) = Var(X) + Var(Y) + 2·Cov(X,Y).

3. indicator 분해 실수

Indicator 가 전체를 정확히 커버하는지 확인. 누락이나 중복 주의.

4. 무한합 조건

무한 급수의 기댓값일 때 절대 수렴 조건 확인.

BOJ 연습 문제

참고

• 확률
• 조합론
• 기댓값