문제 풀이 사이트 AtCoder에서 종종 출제되는 기댓값에 대한 이론적 정리.

Expected Value

기댓값은 영어로 Expected Value 이 번역된 말인데, 흔히들 EV로 줄여서 쓰는 듯 하다. 그래서 전기차(?) 랑 헷갈릴 때가 간혹 있다. 확률변수 $X$에 대한 기댓값은 보통 수학적으로 $E[X]$라고 나타낸다. 수식으로는,

• $E[X] = \displaystyle \sum_{i=1}^{n} x_iP_i$

이는 이산(Discrete) 확률 분포라고 하고, 연속으로는 적분으로 정의한다.

• $E[X] = \displaystyle \int xf(x)\,dx$

PS 분야에서는 DP 등과 엮여서 보통 Discrete한 경우를 많이 다루기 때문에, 이 부분을 집중적으로 살펴보자.

EV의 예시

아래와 같이 기초적인 경우들에 대해서 기댓값을 실제로 계산하는 과정을 살펴보자. Discrete의 경우를 살펴본다.

주사위 눈금의 기댓값 Case

가장 많은 예시로 나오는 Case이다. 모든 면이 나올 확률이 $\displaystyle \frac 1 6$로 같기 때문에, 아래와 같이 계산된다.

• $E[X] = \displaystyle \sum_{i=1}^{6} x_iP_i = \displaystyle \frac 1 6 \sum_{i=1}^6 x_i = \displaystyle \frac 1 6 (1+2+3+4+5+6) = 3.5$

동전 앞면의 수 Case

확률 변수 $X$를 동전 2개를 동시에 던졌을 때 나온 앞면의 수로 정의한다. 이 경우, $X = {0, 1, 2}$가 되고, 각 확률이 아래와 같다.

• $P[X = 0] = \frac 1 4$
• $P[X = 1] = \frac 1 2$
• $P[X = 2] = \frac 1 4$

따라서, 구하고자 하는 기댓값 $E[X] = 0 * 1/4 + 1 * 1/2 + 2 * 1/4 = 1$이다. 이렇게, 각 case의 확률이 달라지는 경우도 존재한다.

동전 던지는 횟수의 기댓값 Case

만약 어떤 사람이 앞면이 나올 때까지 동전을 반복해서 던진다면 동전을 던지게 되는 횟수의 기댓값은 어떻게 될까? 이는 수식보다도 아래처럼 case를 나누어 생각하는 것이 시작하기에 쉬울 것이다.

• 1번 만에 나올 확률: $\displaystyle \frac 1 2$
• 2번 만에 나올 확률: $\displaystyle \frac 1 2 \times \frac 1 2$
• 3번 만에 나올 확률: $\displaystyle (\frac 1 2)^3$

그리고 이는 무한히 반복된다. 각 case에서 동전을 던지는 횟수가 1씩 증가하게되므로, 기댓값은 아래와 같이 계산된다.

• $E[X] = \displaystyle \sum_{n=1}^\infty n (\frac 1 2)^n$

이는 멱급수로, 구하고자 하는 값을 $A$라고 했을 때, $\frac 1 2 A$를 계산해서 두 식을 빼주면 간단하게 값을 계산할 수 있다. 값은 $2$가 나온다.

주사위 던지는 횟수의 기댓값 Case

위 예시에서는 성공과 실패 확률이 같아서 계산하기가 너무 쉬웠다. 아주 약간 난이도를 높여보자. 만약 어떤 사람이 주사위 눈금이 1이 나올 때까지 주사위를 계속해서 던진다면 주사위를 던지는 횟수의 기댓값은 어떻게 될까? 역시 작은 경우부터 생각해보도록 하자.

• 1번 만에 나올 확률: $\displaystyle \frac 1 6$
• 2번 만에 나올 확률: $\displaystyle \frac 5 6 \times \frac 1 6$
• 3번 만에 나올 확률: $\displaystyle \frac 5 6 \times \frac 5 6 \times \frac 1 6$

그리고 이는 무한히 반복된다. 각 case에서 주사위를 던지는 횟수가 1씩 증가하게되므로, 기댓값은 아래와 같이 계산된다.

• $E[X] = \displaystyle \sum_{n=1}^\infty n (\frac 5 6)^{n-1} \frac 1 6$

이를 간단한 C++ 프로그램으로 작성해서 계산해보면 아래와 같다.

void solve() {
    double ret = 0.0;
    double cur = 1.0;
    for(int n = 1; n < 100; ++n) {
        ret += cur * n / 6.0;
        cur *= 5.0 / 6.0;
    }
    printf("%.15lf\n", ret);
}

이를 계산해보면 해당 값은 $6$로 수렴한다는 것을 알 수 있다. (100회 반복 시 약 $5.999998$이 나온다) 즉, 주사위를 1이 나올 때까지 던지게 되는 횟수의 기댓값은 $6$이라는 것이다.

이전 기댓값과의 관계로 정의하기

이전 기댓값과의 관계를 통해 일종의 DP 처럼 전이(transition) 개념을 사용할 수 있다. 만약 $E[X]$가 $E[Y]$와 $E[Z]$ 로부터 전이되어 구성될 수 있다고 하면, 아래처럼 수식으로 나타내서 구할 수 있다.

• $E[X] = P_Y E[Y] + P_Z E[Z]$

여기서, $P_Y$와 $P_Z$는 각각 $Y$, $Z$에서 $X$로 전이될 확률을 나타내며, 전체 확률(여기서는 $P_Y + P_Z$)은 1이 된다.

동전 앞면 나올 때까지 던지는 Case

위 수식을 가지고, 우선 비교적 간단한 동전의 앞면이 처음 나올 때까지 던지는 경우를 살펴보자. 여기서 $E[Y]$를 $Y$번 던졌을 때 1이 단 한번도 안나올 경우의 기댓값이라고 정의해보자. 그러면, $E[X]$는 2가지 case에서부터 전이가 됨을 알 수 있다.

1. $E[Y]$ 에서 $\frac 1 2$ 확률로 $E[X]$로 전이
   • 이 경우에는 던지는 횟수가 1 증가한다.
2. $E[X]$ 에서 $\frac 1 2$ 확률로 $E[X]$로 전이
   • 이 경우는 던지는 횟수가 증가하지 않는다. 자기 자신으로의 전이이다.

이를 수식으로 정리해서 한번 구해보도록 하자.

• $E[X] = \displaystyle \frac 1 2 (E[Y] + 1) + \frac 1 2 E[X]$
  • $\displaystyle \frac 1 2 E[X] = \frac 1 2 (E[Y] + 1)$
  • $E[X] = E[Y] + 1$

$E[Y]$는 어떻게 구할까? 이는 간단하게 아래 수식으로 구해진다.

• $E[Y] = \displaystyle \sum_{i=1}^\infty (\frac 1 2) ^ n = 1$

즉, $E[X] = 2$가 된다.

1 나올 때까지 주사위를 던지는 Case

위와 거의 유사하다. 확률 계산이 조금 달라진다.

1. $E[Y]$ 에서 $\frac 1 6$ 확률로 $E[X]$로 전이
   • 이 경우에는 던지는 횟수가 1 증가한다.
2. $E[X]$ 에서 $\frac 5 6$ 확률로 $E[X]$로 전이
   • 이 경우는 던지는 횟수가 증가하지 않는다. 자기 자신으로의 전이이다.

이를 수식으로 정리해서 한번 구해보도록 하자.

• $E[X] = \displaystyle \frac 1 6 (E[Y] + 1) + \frac 5 6 E[X]$
  • $\displaystyle \frac 1 6 E[X] = \frac 1 6 (E[Y] + 1)$
  • $E[X] = E[Y] + 1$

또 이 경우의 $E[Y]$는 아래와 같다.

• $E[Y] = \displaystyle \sum_{i=1}^\infty (\frac 5 6) ^ n = 5$

즉, $E[X] = 6$가 된다.