문제

포켓몬스터에는 안농이라는 포켓몬이 등장한다. 안농에는 총 28가지 형태가 있고, 동굴에서 각각의 형태의 안농이 같은 확률로 무작위하게 등장한다. 지우는 안농의 형태를 조사하고자 모든 형태의 안농을 만날때까지 총 91번의 안농을 만났다고 할때, 이때 지우는 운이 좋았던 편인걸까, 아니면 나빴던 것일까?

문제를 바꿔쓰자면, 지우가 모든 안농을 만나기까지 마주친 안농의 수를 확률 변수 X라고 할때, X의 평균과 표준편차를 구하는 문제이다.

직접 시도해보기

문제에 접근하는 가장 쉬운 방법은 직접 시도해보고, 그 결과를 바탕으로 판단하는 것일겁니다.

경우의 수를 통한 계산

서로 다른 형태의 안농이 n가지 있다고 할때, k번만에 모든 형태의 안농을 만나는 경우를 %%U_{k,n}%%라고 하자. 그러면 우리가 원하는 결과는 다음과 같이 계산할 수 있다.

	n번만에	n+1번만에	n+2번만에	...	i번만에 모두 만나는 경우
확률변수 X	%%n%%	%%n+1%%	%%n+2%%	...	%%i%%
해당 확률	%%\frac{U_{n,n}}{n^n}%%	%%\frac{U_{n+1,n}}{n^{n+1}}%%	%%\frac{U_{n+2,n}}{n^{n+2}}%%	...	%%\frac{U_{i,n}}{n^i}%%

$$E(X) = \sum_{i=n}^{\infty} {i\frac{U_{i,n}}{n^i}}$$

이제 %%U_{k,n}%%의 습성에 대해 분석해보자. k번째에 모든 다른 형태의 안농을 만나게 되는 경우의 수이므로, k번째 만난 안농은 앞의 k-1에서 만난 안농과 형태가 달라야 한다. 다시 말하면 앞에 만난 k-1회의 안농들은 n-1가지 형태가 고루 섞인 순열이 될 것이다. 이를 위해 수열 %%V_{k,n}%%를 다음과 같이 정의하자.

%%V_{k,n}=%%(n개의 서로 다른 형태가 전체 합쳐서 총 k번 등장하는 경우의 수) (단 %%k \ge n%%)

%%V_{k,1}%%은 1개의 형태가 총 k번 등장하는 경우인데, k가 몇이던 간에 1개의 형태가 k번 등장하는하는 경우는 단 1가지 밖에 없으므로, 그 값은 1이다.

%%V_{k,2}%%는 서로 다른 2개의 형태가 총 k번 등장하는 경우이므로 2가지 중 1개를 고르는 시행을 k번 반복하는 경우의 수 %%2^k%%개에서 k개가 모두 같은 경우 2가지를 뺀 %%2^k-2%%가 된다.

%%V_{k,n}%%의 습성을 탐구하기 위해 다음과 같은 항등식을 생각해보자. 서로 다른 n개의 형태 중 1개를 뽑는 것을 k번 반복하는 경우의 수는 %%n^k%%가지이다. 이 경우의 수 속에는 k개가 모두 다른 같은 경우, 2가지 형태인 경우, ... n가지인 경우가 모두 포함되어 있다. 따라서 다음이 성립한다.

$$n^k = V_{k,n} + \sideset{_n}{_{n-1}}C V_{k,n-1} + \sideset{_n}{_{n-2}}C V_{k,n-2} + \cdots + \sideset{_n}{_{1}}C V_{k,1}\\ \quad = \sum_{i=1}^{n} {\sideset{_n}{_i}C V_{k,i}}$$

여기서 %%\sideset{_n}{_r}C%%는 서로 다른 n개에서 r개를 중복없이 고르는 경우의 수, 즉 이항계수이다. %%k \ge n%%일때 반전을 통해 %%V_{k, n}%%을 계산하면 다음과 같다.

$$V_{k,n} = n^k - \sideset{_n}{_{n-1}}C (n-1)^k + \sideset{_n}{_{n-2}}C (n-2)^k - \cdots + (-1)^{n-1}\sideset{_n}{_1}C 1^k \\ \quad = \sum_{i=1}^{n} {(-1)^{n-i}\sideset{_n}{_i}C i^k}$$

%%V_{k,n}%%에서 k가 n보다 작은 경우에 대해서 생각해보자. 정의에 따르면 그 값은 0이 되는 것이 적절하다. %%0 < k < n%%에 대해 %%\sum_{i=1}^{n} {(-1)^{n-i}\sideset{_n}{_i}C i^k} = 0%%임을 증명해보자.

먼저 다음의 전개식을 고려해보자. $$G_0(x) = (1-x)^n = \sideset{_n}{_0}Cx^0 - \sideset{_n}{_1}Cx^1 + \cdots + \sideset{_n}{_n}C(-1)^n x^n \\ = \sum_{i=0}^{n} {(-1)^{n}\sideset{_n}{_i}C x^i}$$

%%G_{k+1}(x) = x G_{k}'(x)%% 라고 하면 임의의 자연수 k에 대해 $$G_k(x) = \sum_{i=1}^{n} {(-1)^{n}\sideset{_n}{_i}C i^k x^i}$$ 가 성립한다.

%%G_k(x)%%가 %%(1-x)^{n-k}%% 인수를 가짐을 수학적 귀납법을 통해 증명해보자.

%%G_i(x)%%를 %%f_i(x) (1-x)^{n-i}%% (단 %%f_i(x)%%는 %%(1-x)%%와 서로소인 다항식)의 형태로 나타낼 수 있다고 가정하자.

먼저 k=0일때, %%G_0(x) = (1-x)^n%%이므로 %%f_0(x)=1%%으로 성립한다.

n보다 작은 자연수 k에 대해 성립한다고 가정하면, $$G_{k+1}(x) = x G_{k}'(x)\\ \quad = f_k'(x) (1-x)^{n-k} + (n-k)f_k(x)(1-x)^{n-k-1} \\ \quad = \left(f_k'(x)(1-x) + (n-k)f_k(x)\right)(1-x)^{n-k-1}$$인데, 가정에 따라 %%f_k(x)%%는 %%(1-x)%%와 서로소이므로, %%\left(f_k'(x)(1-x) + (n-k)f_k(x)\right)%% 역시 %%(1-x)%%와 서로소이므로 %%f_{k+1}(x)%%라고 할 수 있으므로 $$G_{k+1}(x) = f_{k+1}(x)(1-x)^{n-(k+1)}$$

따라서 n보다 작은 자연수 k에 대해 %%G_k(x) = f_k(x) (1-x)^{n-j}%% (단 %%f_k(x)%%는 %%(1-x)%%와 서로소인 다항식)이다.

그러므로 %%0 < k < n%%인 k에 대해 %%G_k(1) = 0%%이므로, %%\sum_{i=1}^{n} {(-1)^{n}\sideset{_n}{_i}C i^k} = 0%%이다.

기존의 %%V_{k,n}%%는 다음과 같이 정의되었다. $$V_{k,n} = \sum_{i=1}^{n} {(-1)^{n-i}\sideset{_n}{_i}C i^k} (k \ge n)$$ $$V_{k,n} = 0 (0 < k < n)$$ %%\sum_{i=1}^{n} {(-1)^{n-i}\sideset{_n}{_i}C i^k} = 0 (0 < k < n)%%임으로 위 정의를 더 간략하게 바꿀 수 있다. $$V_{k,n} = \sum_{i=1}^{n} {(-1)^{n-i}\sideset{_n}{_i}C i^k} (k > 0)$$

%%U_{k,n}%%는 n-1개 형태의 안농을 총 k-1회 만난 뒤에 k번째에 마지막 형태의 안농을 만나는 경우의 수이므로 %%n V_{k-1,n-1}%%과 같다.

$$U_{k,n} = n V_{k-1,n-1} = n \sum_{i=1}^{n-1} {(-1)^{n-1-i}\sideset{_{n-1}}{_i}C i^{k-1}}$$

이제 다시 E(X)를 구하는 일로 돌아가보자.

$$E(X) = \sum_{k=n}^{\infty} {k\frac{U_{k,n}}{n^k}}\\ \quad = \sum_{k=n}^{\infty} {k\frac{n V_{k-1,n-1}}{n^k}}\\ \quad = \sum_{k=1}^{\infty} {k\frac{n V_{k-1,n-1}}{n^k}} - V_{0, n-1}\\ \quad = \sum_{k=1}^{\infty} {k\frac{\sum_{i=1}^{n-1} {(-1)^{n-1-i}\sideset{_{n-1}}{_i}C i^{k-1}}}{n^{k-1}}} - (-1)^n\\ \quad = \sideset{_{n-1}}{_{1}}C\sum_{k=1}^{\infty} {k\left(\frac{1}{n}\right)^{k-1}} - \sideset{_{n-1}}{_{2}}C\sum_{k=n}^{\infty} {k\left(\frac{2}{n}\right)^{k-1}} +\\ \quad \cdots + (-1)^{n-1}\sideset{_{n-1}}{_{n-1}}C\sum_{k=1}^{\infty} {k\left(\frac{n-1}{n}\right)^{k-1}} - (-1)^n\\ \quad = \sum_{i=1}^{n-1} {(-1)^{n-1-i} \sideset{_{n-1}}{_i}C \sum_{k=1}^{\infty}{k\left(\frac{i}{n}\right)^{k-1}}} - (-1)^n$$

이를 계산하기 위해서는 다음 수열의 합을 계산할 수 있어야 한다. %%\sum_{k=n}^{\infty} {kr^{k-1}}%% (단 %%|r| < 1%%)

이를 위해 다음 식을 생각해보자. $$S(r) = \sum_{k=1}^{\infty} {k(r)^{k-1}}$$ $$S(r) - rS(r) = \sum_{k=1}^{\infty} {kr^{k-1}} - \sum_{k=1}^{\infty} {kr^{k}}\\ = \sum_{k=1}^{\infty} {r^{k-1}} = \frac{1}{1-r}$$ 따라서 %%S(r) = \sum_{k=1}^{\infty} {k(r)^{k-1}} = \frac{1}{(1-r)^2}%%을 얻는다.

E(X) 계산을 계속 진행해보면 $$\sum_{i=1}^{n-1} {(-1)^{n-1-i} \sideset{_{n-1}}{_i}C \sum_{k=1}^{\infty}{k\left(\frac{i}{n}\right)^{k-1}}} - (-1)^n\\ \quad = \sum_{i=1}^{n-1} {(-1)^{n-1-i} \sideset{_{n-1}}{_i}C S\left(\frac{i}{n}\right)} - (-1)^n\\ \quad = \sum_{i=1}^{n-1} {(-1)^{n-1-i} \sideset{_{n-1}}{_i}C \left(\frac{n}{n-i}\right)^2} - (-1)^n\\ \quad = \sideset{_{n-1}}{_{n-1}}C \left(\frac{n}{1}\right)^2 - \sideset{_{n-1}}{_{n-2}}C \left(\frac{n}{2}\right)^2 + \sideset{_{n-1}}{_{n-3}}C \left(\frac{n}{3}\right)^2 \cdots \\ + (-1)^{n-2} \sideset{_{n-1}}{_{1}}C \left(\frac{n}{n-1}\right)^2 + (-1)^{n-1} \\ \quad = n^2 \sum_{i=0}^{n-1} {(-1)^i \sideset{_{n-1}}{_i}C \frac{1}{(i+1)^2}}$$

따라서 E(X)는 다음과 같다.$$E(X) = n^2 \sum_{i=0}^{n-1} {(-1)^i \sideset{_{n-1}}{_i}C \frac{1}{(i+1)^2}}$$

표준편차를 계산하기 위해 %%E(X^2)%%을 계산해보자.

$$Q(r) = \sum_{k=1}^{\infty} {k^2(r)^{k-1}}$$ $$(1-r)Q(r) = \sum_{k=1}^{\infty} {(2k-1)(r)^{k-1}}$$ $$(1-r)^2Q(r) = 1 + \sum_{k=2}^{\infty} {2(r)^{k-1}}\\ = \frac{2}{1-r} - 1$$ $$Q(r) = \frac{2}{(1-r)^3} - \frac{1}{(1-r)^2}$$ $$E(X^2) = \sum_{k=n}^{\infty} {k^2\frac{U_{k,n}}{n^k}}\\ \quad = \sum_{k=n}^{\infty} {k^2\frac{n V_{k-1,n-1}}{n^k}}\\ \quad = \sum_{k=1}^{\infty} {k^2\frac{n V_{k-1,n-1}}{n^k}} - V_{0, n-1}\\ \quad = \sum_{k=1}^{\infty} {k^2 \frac{\sum_{i=1}^{n-1} {(-1)^{n-1-i}\sideset{_{n-1}}{_i}C i^{k-1}}}{n^{k-1}}} - (-1)^n\\ \quad = \sum_{i=1}^{n-1} {(-1)^{n-1-i} \sideset{_{n-1}}{_i}C \sum_{k=1}^{\infty}{k^2\left(\frac{i}{n}\right)^{k-1}}} - (-1)^n\\ \quad = \sum_{i=1}^{n-1} {(-1)^{n-1-i} \sideset{_{n-1}}{_i}C Q\left(\frac{i}{n}\right)} - (-1)^n\\ \quad = 2n^3 \sum_{i=0}^{n-1} {(-1)^i \sideset{_{n-1}}{_i}C \frac{1}{(i+1)^3}} - n^2 \sum_{i=0}^{n-1} {(-1)^i \sideset{_{n-1}}{_i}C \frac{1}{(i+1)^2}} $$

자 그러면 n=28을 대입해서 실제 X의 분포에 대해서 살펴보자.

$$E(X) = 28^2 \sum_{i=0}^{27} {(-1)^i \sideset{_{27}}{_i}C \frac{1}{(i+1)^2}} \approx 109.96 $$ $$E(X^2) = 2 \times 28^3 \sum_{i=0}^{27} {(-1)^i \sideset{_{27}}{_i}C \frac{1}{(i+1)^3}} - 28^2 \sum_{i=0}^{27} {(-1)^i \sideset{_{27}}{_i}C \frac{1}{(i+1)^2}} \approx 13243.54 $$ $$V(X) = E(X^2) - E^2(X) = 1152.16$$ $$\sigma(X) = \sqrt{V(X)} = 33.94$$

따라서 28 종류의 안농을 모두 만날때까지 마주쳐야할 안농의 수 X는 평균은 109.96, 표준편차는 33.94인 분포를 이룬다. 정규분포표에 따르면 이러한 분포에서 %%X \ge 91%%일 확률은 28.82%이다. 따라서 지우는 상위 28.82% 안에 들 만큼 운이 좋았다고 할 수 있다.

단계별로 기대값을 계산해 합치기