次へ: 7 μ(N,m) 上へ: 配列内のランダムな配置の選択の評価 前へ: 5 期待値の大きさの評価 (PDF ファイル: rand3.pdf)


6 S(k,r)

この節以降で、3 節で述べた方法での計算を行い、 それが 4 節での結果 (3) と一致することを確認する。 ただし、ここから先の話は元の問題からすれば本質的な話ではなく、 純粋に数学的な議論のみである。 また、この方針での計算はかなり大変であるので、 この後いくつかの節に分けて考察する。

3 節で考えたように、$k$ 回余計にかって $(m+k)$ 回で終わる確率は

\begin{eqnarray*}p_{m+k} &=& \frac{N-1}{N}\,\frac{N-2}{N}\cdots\frac{N-m+1}{N}... ... \end{array}\right)m!\frac{1}{N^k}S(k,m-1)\hspace{1zw}(1<m\leq N)\end{eqnarray*}


であるので、期待値 $\mu (N,m)$ は、
\begin{displaymath} \mu(N,m) =\sum_{k=0}^\infty (m+k)p_{m+k} =\frac{m!}{N^m}\... ...\\ m \end{array}\right)\sum_{k=0}^\infty\frac{m+k}{N^k}S(k,m-1)\end{displaymath} (4)

となる。まずは、この $S(k,r)$ を $k$ と $r$ の式で表すところから始める。 なお、$m=1$ のときは明らかに $\mu(N,m)=1$ であるから、 以後 $1<m\leq N$ として考える。

3 節で見たように、$S(k,r)$ には、

$\displaystyle S(k,r)$ $\textstyle =$ $\displaystyle \sum_{i=1}^r iS(k-1,i)$ (5)
$\displaystyle S(k,1)$ $\textstyle =$ $\displaystyle 1$ (6)

が成り立つ。 $S(1,r)=r(r+1)/2$ も言えていたが、これはむしろ (5) で
\begin{displaymath} S(0,r)=1\end{displaymath} (7)

であるとすれば得られるので、(7) が成り立つとすればよい。 なお、(5) を この式の $r$ を $(r-1)$ とした式と比較してみればわかるが、
\begin{displaymath} S(k,r)=S(k,r-1)+rS(k-1,r)\hspace{1zw}(k\geq 1,\ r\geq 2) \end{displaymath} (8)

が成り立つことに注意する。以後、この (6), (7), (8) から $S(k,r)$ を求めていくことにするが、 逆にこれを満たす $S(k,r)$ が一意に決定されることも容易にわかる。

さて、今 (8) で $r=2$ としてみると、 (6) より

\begin{displaymath} S(k,2) =S(k,1)+2S(k-1,2) =2S(k-1,2)+1 \end{displaymath}

となるから、この両辺を $2^k$ で割れば、
\begin{displaymath} \frac{S(k,2)}{2^k}=\frac{S(k-1,2)}{2^{k-1}}+\frac{1}{2^k} \end{displaymath}

となるので、こ の式にこの式の $k$ を $(k-1)$ にしたものを代入する、 といったことを繰り返すことによって、
\begin{eqnarray*}\frac{S(k,2)}{2^k} &=& \frac{S(k-1,2)}{2^{k-1}}+\frac{1}{2^k}... ...+\frac{1}{2^k} \\ &=& \frac{1-1/2^{k+1}}{1-1/2}=2-\frac{1}{2^k}\end{eqnarray*}


となり、よって
\begin{displaymath} S(k,2)=2\cdot 2^k-1\end{displaymath} (9)

が得られる。同様に、(8) で $r=3$ とすると
\begin{displaymath} S(k,3) =S(k,2)+3S(k-1,3) =3S(k-1,3)+2\cdot 2^k-1 \end{displaymath}

となるので、$3^k$ で割れば
\begin{eqnarray*}\frac{S(k,3)}{3^k} &=& \frac{S(k-1,3)}{3^{k-1}} +2\left(\fra... ...\left(\frac{2}{3}\right)^k-\frac{1}{2}+\frac{1}{2}\,\frac{1}{3^k}\end{eqnarray*}


より、
\begin{displaymath} S(k,3)=\frac{9}{2}\cdot 3^k-4\cdot 2^k+\frac{1}{2}\end{displaymath} (10)

のようになる。この、(9), (10) より、
\begin{displaymath} S(k,r)=\sum_{j=1}^r a_{r,j} j^k =a_{r,1}\cdot 1^k+a_{r,2}\cdot 2^k+\cdots+a_{r,r}\cdot r^k\end{displaymath} (11)

の形であることが想像される。

もし、この (11) を (8) に代入して、 (6), (7), (8) を満たすように矛盾なく $a_{r,j}$ を決定できれば、 前に述べたようにそれを満たす $S(k,r)$ は一意であるから、 それで $S(k,r)$ が得られることになる。

(11) を (8) に代入すると、

\begin{displaymath} \sum_{j=1}^r a_{r,j}j^k = \sum_{j=1}^{r-1} a_{r-1,j}j^k +r\... ...{r-1}\left(a_{r-1,j}+\frac{r}{j}a_{r,j}\right)j^k +a_{r,r}r^k \end{displaymath}

となる。よって、 $1\leq j\leq r-1$ に対して、
\begin{displaymath} a_{r,j}=a_{r-1,j}+\frac{r}{j}\,a_{r,j} \end{displaymath}

であればよく、これは、
\begin{displaymath} a_{r,j}=\frac{-j}{r-j}\,a_{r-1,j} \end{displaymath}

を意味するので、
\begin{eqnarray*}a_{r,j} &=& \frac{-j}{r-j}\,a_{r-1,j} = \frac{-j}{r-j}\,\f... ... &=& \frac{-j}{r-j}\,\frac{-j}{r-1-j}\cdots\frac{-j}{1}\,a_{j,j}\end{eqnarray*}


となり、
\begin{displaymath} a_{r,j} = \frac{(-j)^{r-j}}{(r-j)!}\,a_{j,j}\end{displaymath} (12)

となることになる。この $a_{j,j}$ は次のように決定できる。 (11) に $k=0$ を代入すると (7) より
\begin{displaymath} S(0,r)=\sum_{j=1}^r a_{r,j}=1 \end{displaymath}

となるが、ここに (12) を代入して
\begin{displaymath} \sum_{j=1}^r \frac{(-j)^{r-j}}{(r-j)!}a_{j,j}=1\hspace{1zw}(r\geq j)\end{displaymath} (13)

が得られるが、 この (13) から次々 $a_{j,j}$ を求めることができる。 例えば、(13) に $r=1$ を代入すれば
\begin{displaymath} \frac{(-1)^0}{0!}a_{1,1}=1 \end{displaymath}

より $a_{1,1}=1$ となり、$r=2$ を代入すると、
\begin{displaymath} \frac{(-1)^1}{1!}a_{1,1}+\frac{(-2)^0}{0!}a_{2,2}=1 \end{displaymath}

となるので、 $a_{2,2}=a_{1,1}+1=2$ と求まる。以下、計算すると、
\begin{displaymath} a_{3,3}=\frac{9}{2}=\frac{3^2}{2}, \ a_{4,4}=\frac{32}{3}=\frac{4^3}{6}, \ a_{5,5}=\frac{625}{24}=\frac{5^4}{24} \end{displaymath}

のようになるので、
\begin{displaymath} a_{j,j}=\frac{j^{j-1}}{(j-1)!}=\frac{j^j}{j!}\end{displaymath} (14)

となることが予想される。 これは実際に、(13) と帰納法を用いれば証明できる。 $j<r$ まで (14) が成り立つとすれば、 (13) により $a_{r,r}$ は、
\begin{displaymath} a_{r,r} = 1-\sum_{j=1}^{r-1} \frac{(-j)^{r-j}}{(r-j)!}\,\fra... ...\left(\begin{array}{c} r \\ j \end{array}\right)\frac{j^r}{r!} \end{displaymath}

となる。ここで、
\begin{displaymath} \sum_{j=0}^r\left(\begin{array}{c} r \\ j \end{array}\right)(-1)^{r-j}j^r=r!\end{displaymath} (15)

であることを用いれば、
\begin{eqnarray*}a_{r,r} &=& 1-\frac{1}{r!}\left\{\sum_{j=0}^r (-1)^{r-j}\left... ...ight)r^r-0\right\} \\ &=& 1-\frac{1}{r!}(r!-r^r)=\frac{r^r}{r!}\end{eqnarray*}


となるので、帰納法により (14) が成り立つことになる。

(15) は、母関数の方法を用いて以下のように証明できる。 二項定理により、

\begin{displaymath} f_1(x) =\sum_{j=0}^r\left(\begin{array}{c} r \\ j \end{array}\right)(-1)^{r-j}e^{jx} =(e^x-1)^r \end{displaymath}

であるが、 $(e^{jx})^{(r)}=j^r e^{jx}$ なので (15) は $f_1^{(r)}(0)$ に等しいことになる。

一方、テイラー展開を考えると、

\begin{eqnarray*}f_1(x) &=& (e^x-1)^r = \left(x+\frac{x^2}{2!}+\frac{x^3}... ...lefteqn{(O(x^{r+1})\mbox{ は $(r+1)$\ 次以上の項の和を意味する})}\end{eqnarray*}


となるので $f_1^{(r)}(0)=r!$ となり、 これで (15) が示されたことになる。

結局、(11), (12), (14) により、

\begin{displaymath} S(k,r) =\sum_{j=1}^r\frac{(-j)^{r-j}}{(r-j)!}\,\frac{j^j}{... ...ft(\begin{array}{c} r \\ j \end{array}\right)\frac{j^{r+k}}{r!}\end{displaymath} (16)

となる。 これは、$r=1$ とすると
\begin{displaymath} S(k,1)=(-1)^0\left(\begin{array}{c} 1 \\ 1 \end{array}\right)\frac{1^{1+k}}{1!}=1 \end{displaymath}

となり (6) も満たすので、 (6), (7), (8) を矛盾なく満たすことになり、 確かに (16) が成り立つことがわかる。

次へ: 7 μ(N,m) 上へ: 配列内のランダムな配置の選択の評価 前へ: 5 期待値の大きさの評価
竹野茂治＠新潟工科大学
2008年5月24日