2 問題設定と簡単な場合の考察

問題を以下のように設定する:

$1$ から $N$ までの $N$ 個の数字から、 ランダムに一つを選ぶことを繰り返す。 一回の選択でそのいずれが出る確率も等しく $1/N$ であるとする。 選んだ数の集合の異なる要素の数が $m$ ($1\leq m\leq N$) になるまで それを繰り返すこととする。 それが終わるまでに繰り返し選択した回数の 期待値 (平均値) $\mu (N,m)$ を求めよ。

まず、簡単のために、$N=10$, $m=3$ として考えてみることにする。 この場合は、最低 3 回の選択が必要になるが、3 回で終わるのは、 最初の一つ目の数はどれでもよく、二つ目は一つ目と違う数であればよく、 三つ目の数は前の 2 つと違うものであればよいので、 3 回で終わる確率 $p_3$ は、

$$p_3 = 1\times\frac{9}{10}\times\frac{8}{10} = \frac{72}{100}$$

である。

4 回で終わるのは、2 回目に一つ目の数と同じものが出てしまうか、 または 3 回目に一つ目か二つ目の数と同じものが出る場合なので、 その確率 $p_4$ は

$$p_4 = 1\times\frac{1}{10}\times\frac{9}{10}\times\frac{8}{10... ...ac{2}{10}\times\frac{8}{10} = \frac{72}{100}\times\frac{3}{10}$$

となる。

同様に、5 回の場合は、(2 回目、3 回目) が前と同じものか、 (2 回目、4 回目) が、または (3 回目、4 回目) が前にでたものと同じものか、 のいずれかの場合であり、よって、

$$p_5 = \frac{72}{100}\times\left( \frac{1}{10}\times\frac{1}... ...10}\times\frac{2}{10} +\frac{2}{10}\times\frac{2}{10} \right)$$

のようになる。これを繰り返すと、$(k+3)$ 回 ($k\geq 0$) となる確率 $p_{k+3}$ は、

$$\begin{eqnarray*}p_{k+3} &=& \frac{72}{100}\left\{ \left(\frac{1}{10}\right)... ...0}^k \left(\frac{1}{10}\right)^{k-j} \left(\frac{2}{10}\right)^j\end{eqnarray*}$$

となることがわかる。これは公比 2 の等比級数なので、

$$p_{k+3} =\frac{72}{100}\times\left(\frac{1}{10}\right)^k\frac{2^{k+1}-1}{2-1} =\frac{72}{100}\times\frac{2^{k+1}-1}{10^k}$$

となる。よって、回数の期待値 $\mu(10,3)$ は、

$$\begin{eqnarray*}\mu(10,3) %\\ &=& &=& \sum_{k=0}^\infty (k+3)p_{k+3} = \fr... ...eft(\frac{2}{10}\right)^k +3k\left(\frac{1}{10}\right)^k\right\}\end{eqnarray*}$$

となる。ここで、$\vert x\vert<1$ に対して、

$$\sum_{k=0}^\infty x^k = 1+x+x^2+x^3+\cdots = \frac{1}{1-x}$$ (1)

であるから (無限等比級数)、この両辺を微分すれば

$$\sum_{k=1}^\infty kx^{k-1} = 1+2x+3x^2+4x^3+\cdots = \frac{1}{(1-x)^2}$$ (2)

が成り立つことに注意する。

よって、この (1), (2) より

$$\begin{eqnarray*}\sum_{k=0}^\infty k\left(\frac{2}{10}\right)^{k-1} &=& \sum_... ...t(\frac{1}{10}\right)^k %&=& = \frac{1}{9/10} = \frac{10}{9}\end{eqnarray*}$$

なので、

$$\begin{eqnarray*}\mu(10,3) &=& \frac{72}{100}\left( \frac{4}{10}\times\frac{1... ...frac{24}{10} = \frac{81-16}{180}+3 %\\ &=& = 3+\frac{13}{36}\end{eqnarray*}$$

となる。