4 次の要素が得られるまでの回数の期待値

この節では、2 節、3 節とは異なる方法で、 期待値 $\mu (N,m)$ を計算してみることにする。

この問題では、一つ目はどれを選んでもいいので一つ目は必ず 1 回で決まる。 この先、次の二つ目 (2 種類目) の数字が出るまでに 平均何回かかるかを考えてみる。

この場合は、一つ目の同じものが出続けている間は選択し続けるが、 そうでないものが出ればそこで終わりである。 つまり、

1 回で済む確率 $=\displaystyle \frac{N-1}{N}$,
2 回で済む確率 $=\displaystyle \frac{1}{N}\times\frac{N-1}{N}$,
3 回で済む確率 $=\displaystyle \left(\frac{1}{N}\right)^2\times\frac{N-1}{N}$

のようになる。よって、二つ目の数字が出るまでの回数の期待値は、

$$\mu_\beta = \sum_{k=1}^\infty k\left(\frac{1}{N}\right)^{k-... ...rac{N-1}{N} = \frac{N-1}{N}\frac{1}{(1-1/N)^2} = \frac{N}{N-1}$$

となる。

$(j-1)$ 個の異なる数字が取れたところから始めると、 次の $j$ 個目の異なる数字が取れるまでには、

1 回で済む確率 $=\displaystyle \frac{N-j+1}{N}$,
2 回で済む確率 $=\displaystyle \frac{j-1}{N}\times\frac{N-j+1}{N}$,
3 回で済む確率 $=\displaystyle \left(\frac{j-1}{N}\right)^2\times\frac{N-j+1}{N}$

のようになるので、期待値は

$$\begin{eqnarray*}\mu_j &=& \sum_{k=1}^\infty k\left(\frac{j-1}{N}\right)^{k-1... ...\frac{N-j+1}{N}\frac{1}{\{1-(j-1)/N\}^2} \\ &=& \frac{N}{N-j+1}\end{eqnarray*}$$

となる。$\mu (N,m)$ は、この $\mu_j$ を $j=1$ から $j=m$ まで 累積したものになるので、

$$\mu(N,m)=\sum_{j=1}^m \frac{N}{N-j+1}$$ (3)

となる。例えば、$N=10$, $m=3$ の場合は、

$$\mu(10,3) = \frac{10}{10}+\frac{10}{9}+\frac{10}{8} = 3+\frac{1}{9}+\frac{1}{4} = 3+\frac{13}{36}$$

となって、2 節の結果と確かに一致する。