5 期待値の大きさの評価

この節では (3) を用いて、 期待値 $\mu (N,m)$ の大きさを考えてみる。

例えば $N=10$ の場合、各 $m$ に対する期待値 $\mu(10,m)$ の値は、 表 1 のようになる。

表 1: $N=10$ の場合の期待値

$m$	1	2	3	4	5	6	7	8	9	10
$\mu(10,m)$	1.00	2.11	3.36	4.79	6.46	8.46	10.96	14.29	19.29	29.29

この $N=10$ の場合は、$m=8$ でも回数の期待値は $m$ の 2 倍にもならず、 それほど大きいわけではない。$N$ が大きい場合でも、 $m$ があまり大きくなければ $m$ と $\mu (N,m)$ とはそれほど離れない。

実際、 $N\rightarrow\infty$ のときに $m$ も $N$ との比を固定して 大きくする、例えば $m=[rN]$ ($0<r<1$) のようにすると $m/N\rightarrow r$ であり、(3) より、

$$\begin{eqnarray*}\frac{\mu(N,m)}{N} &=& \sum_{k=1}^m\frac{1}{N-k+1} = \sum_{... ... \int_0^r\frac{dx}{1-x} = \log\frac{1}{1-r}\hspace{1zw}(0<r<1)\end{eqnarray*}$$

となることがわかる。つまり、大きい $N$ に対しては、$r=m/N$ に対して

$$\frac{\mu(N,m)}{N}\approx\log\frac{1}{1-r}$$

であるので、

$$\frac{\mu(N,m)}{m}\approx\frac{1}{r}\log\frac{1}{1-r}$$

となるが、この最後の関数 $f(r)=(1/r)\log\{1/(1-r)\}$ は $0\leq r<1$ で増加関数で、$f(+0)=1$, $f(0.8)=2.01$ 位なので、 $m<0.8N$ なら $\mu (N,m)$ は高々 $m$ の 2 倍程度にしかならない。

しかし、もちろん $f(1-0)=+\infty$ なので、$m$ が $N$ の近くならば 大きくなってしまうが、 元々の問題では、$m>N/2$ の場合は、逆に最初に全部を 1 にしてしまって、 $(N-m)$ 個をランダムに 0 にすればよいので、 実質的に $m\leq N/2$ の場合だけを考えればよく、 この場合の期待値 $\mu (N,m)$ と $m$ の比は最大で $f(0.5)=2\log 2=1.39$ 位であることがわかる。