Expected Value: 기댓값, Linearity

Expected Value, 기댓값, expectation

정의

확률변수 X 의 기댓값:

$$E[X]=\sum _{x}x\cdot P(X=x)\text{{}(discrete)\}$$ $$E[X]=\int x\cdot f(x)dx\text{{}(continuous)\}$$

Linearity of Expectation

독립 여부 무관: E[X + Y] = E[X] + E[Y].

이것이 경쟁 프로그래밍에서 강력한 이유: 복잡한 이벤트를 지시 변수 합으로 분해.

예시: n 개 편지가 다른 봉투에 무작위 배정

각 편지 i 가 자기 봉투에 갈 확률 = 1/n. 지시변수 X_i (i-th 편지가 자기 봉투) → E[X_i] = 1/n. E[total] = Σ 1/n = 1.

“랜덤 순열의 fixed points 기댓값 = 1” 결과 도출.

응용

• 뽑기, coupon collector: E[전부 뽑기] = n · H_n ≈ n ln n
• 무작위 알고리즘 분석 (quicksort, randomized primality)
• 마르코프 체인 흡수 시간

참고

• Markov Chain
• Linearity of Expectation