次へ: 8 f6(0) 上へ: 配列内のランダムな配置の選択の評価 前へ: 6 S(k,r) (PDF ファイル: rand3.pdf)


7 μ(N,m)

6 節で求めた $S(k,r)$ から $\mu (N,m)$ を計算してみる。 (16) を (4) に代入すると、
\begin{eqnarray*}\mu(N,m) &=& \frac{m!}{N^m}\left(\begin{array}{c} N \\ m \end... ...}\right)j^{m-1} \sum_{k=0}^\infty(m+k)\left(\frac{j}{N}\right)^k\end{eqnarray*}


となる。 $j/N\leq (m-1)/N<1$ であるから、最後の和は収束し、 (1), (2) より
\begin{eqnarray*}\sum_{k=0}^\infty(m+k)\left(\frac{j}{N}\right)^k &=& m\sum_{k... ...{j}{N}\,\frac{1}{(1-j/N)^2} = \frac{Nm}{N-j}+\frac{Nj}{(N-j)^2}\end{eqnarray*}


となるので、 $\mu(N,m)=\mu_\alpha+\mu_\beta$ と分け、
\begin{eqnarray*}\mu_\alpha &=& \frac{Nm^2}{N^m}\left(\begin{array}{c} N \\ m... ...begin{array}{c} m-1 \\ j \end{array}\right) \frac{j^m}{(N-j)^2} \end{eqnarray*}


と書けることになる。

まずは $\mu_\alpha$ の和の部分を考える。

\begin{displaymath} F_1(N,n) = \sum_{j=1}^n(-1)^{n-j}\left(\begin{array}{c} n \\... ...array}\right)(-1)^{n-j}\frac{j^n}{N-j} \hspace{1zw}(1\leq n<N) \end{displaymath}

とし $f_2(x,y)$ を、
\begin{displaymath} f_2(x,y)=\sum_{j=0}^n\left(\begin{array}{c} n \\ j \end{array}\right)(-1)^{n-j}e^{jx}e^{(N-j)y} \end{displaymath}

とすると、二項定理より
\begin{eqnarray*}f_2(x,y) &=& \sum_{j=0}^n\left(\begin{array}{c} n \\ j \end{a... ...^je^{Ny} = (e^{x-y}-1)^n e^{Ny} \\ &=& (e^x-e^y)^n e^{(N-n)y}\end{eqnarray*}


となる。一方、$N-j\geq N-n>0$ なので、
\begin{displaymath} \int_{-\infty}^0 e^{(N-j)y} dy =\left[\frac{1}{N-j}e^{(N-j)y}\right]_{y=-\infty}^{y=0} =\frac{1}{N-j} \end{displaymath}

が成り立つから、
\begin{displaymath} f_3(x)=\int_{-\infty}^0 f_2(x,y)dy \end{displaymath}

とすれば、 $F_1(N,n)=f_3^{(n)}(0)$ となることになる。

$f_3(x)$ の積分を $e^y=t$ と置換して計算すると、

\begin{displaymath} f_3(x) = \int_{-\infty}^0 (e^x-e^y)^n e^{(N-n)y}dy = \int_0^1(e^x-t)^n t^{N-n-1} dt \end{displaymath}

となるが、これをさらに $t=e^x s$ と置換すると、
\begin{displaymath} f_3(x)=e^{Nx}\int_0^{e^{-x}}(1-s)^n s^{N-n-1} ds \end{displaymath}

となる。この積分の部分を $f_4(x)$ とすると、$f_4'(x)$ のテイラー展開は
\begin{eqnarray*}f_4'(x) &=& \left(\int_0^{e^{-x}}(1-s)^n s^{N-n-1} ds\right)'... ...{-Nx}(e^x-1)^n = -(1+O(1))(x+O(x^2))^n \\ &=& -x^n+O(x^{n+1})\end{eqnarray*}


となるので、これを積分すれば
\begin{displaymath} f_4(x)=f_4(0)-\frac{x^{n+1}}{n+1}+O(x^{n+2})\end{displaymath} (17)

であることがわかる。よって $f_3(x)$ は
\begin{displaymath} f_3(x)=f_4(0)e^{Nx}+O(x^{n+1}) \end{displaymath}

となり、よって $F_1(N,n)$ は
\begin{displaymath} F_1(N,n)=f_3^{(n)}(0)=N^nf_4(0) \end{displaymath}

と表される。 ここで $f_4(0)$ はベータ関数で書け、
\begin{eqnarray*}f_4(0) &=& \int_0^1(1-s)^n s^{N-n-1} ds = B(n+1,N-n) = \f... ...\frac{1}{(n+1)\left(\begin{array}{c} N \\ n+1 \end{array}\right)}\end{eqnarray*}


となり、結局 $F_1(N,n)$ は
\begin{displaymath} F_1(N,n)=\frac{N^n}{(n+1)\left(\begin{array}{c} N \\ n+1 \end{array}\right)} \end{displaymath}

と書けることになる。これにより $\mu_\alpha$ は
\begin{displaymath} \mu_\alpha = \frac{m^2}{N^{m-1}}\left(\begin{array}{c} N ... ...N^{m-1}}{m\left(\begin{array}{c} N \\ m \end{array}\right)} =m\end{displaymath} (18)

となる。 次に $\mu_\beta$ の和の部分
\begin{displaymath} F_2(N,n) = \sum_{j=1}^n(-1)^{n-j}\left(\begin{array}{c} n \\... ...{c} n \\ j \end{array}\right)(-1)^{n-j}\frac{j^{n+1}}{(N-j)^2} \end{displaymath}

を考える ($1\leq n<N$)。 この場合、
\begin{eqnarray*}\int_{-\infty}^0\int_{-\infty}^t e^{(N-j)y}dydt &=& \int_{-\i... ...}{N-j}\int_{-\infty}^0e^{(N-j)t}dt %= \\ &=& \frac{1}{(N-j)^2}\end{eqnarray*}


を利用して、
\begin{displaymath} f_5(x) =\int_{-\infty}^0\int_{-\infty}^tf_2(x,y)dydt =\sum_{... ...}{c} n \\ j \end{array}\right)(-1)^{n-j}\frac{e^{jx}}{(N-j)^2} \end{displaymath}

とすれば、 $F_2(N,n)=f_5^{(n+1)}(0)$ となることがわかる。 一方 $f_3(x)$ と同様の計算により $f_5(x)$ は
\begin{eqnarray*}f_5(x) &=& \int_{-\infty}^0\int_y^0f_2(x,y)dtdy = -\int_{-... ...1-s)^n s^{N-n-1}(\log s+x) ds %= \\ &=& -e^{Nx}f_6(x)-xf_3(x)\end{eqnarray*}


と変形できる。ここで $f_6(x)$ は
\begin{displaymath} f_6(x) = \int_0^{e^{-x}} (1-s)^n s^{N-n-1}\log sds \end{displaymath}

とする。$f_6'(x)$ のテイラー展開は、
\begin{displaymath} f_6'(x) = -e^{-x}(1-e^{-x})^n e^{(-N+n+1)x}(-x) = e^{-Nx}(e^x-1)^n x = x^{n+1}+O(x^{n+2}) \end{displaymath}

となるので、これを積分すれば
\begin{displaymath} f_6(x) = f_6(0) +\frac{x^{n+2}}{n+2}+O(x^{n+3})\end{displaymath} (19)

となるから、$f_5(x)$ は (17), (19) より
\begin{eqnarray*}f_5(x) &=& -e^{Nx}\{f_6(0)+O(x^{n+2})\}-f_4(0)xe^{Nx}+O(x^{n+2}) \\ &=& -f_6(0)e^{Nx}-f_4(0)xe^{Nx}+O(x^{n+2})\end{eqnarray*}


となるので、よって $F_2(N,n)$ は
\begin{eqnarray*}F_2(N,n) &=& f_5^{(n+1)}(0) = -N^{n+1}f_6(0)-(n+1)N^nf_4(0)... ...0)-\frac{N^n}{\left(\begin{array}{c} N \\ n+1 \end{array}\right)}\end{eqnarray*}


と表されることになる。よって $\mu_\beta$ は、
\begin{eqnarray*}\mu_\beta &=& \frac{m}{N^{m-1}}\left(\begin{array}{c} N \\ m ... ... &=& -Nm\left(\begin{array}{c} N \\ m \end{array}\right)f_6(0)-m\end{eqnarray*}


となり、(18) より、
\begin{displaymath} \mu(N,m)=\mu_\alpha+\mu_\beta= -Nm\left(\begin{array}{c} N \\ m \end{array}\right)f_6(0)\end{displaymath} (20)

となるので、結局この
\begin{displaymath} f_6(0)=\int_0^{1} (1-s)^n s^{N-n-1}\log sds \hspace{1zw}(n=m-1) \end{displaymath}

を求めればいいことになる。

次へ: 8 f6(0) 上へ: 配列内のランダムな配置の選択の評価 前へ: 6 S(k,r)
竹野茂治＠新潟工科大学
2008年5月24日