次へ: 8 最後に 上へ: プログラム中のある乱数の評価 その 2 前へ: 6 y4 の場合 (PDF ファイル: rand2.pdf)


7 さらなる改善

4, 5 節の議論により、 $y_2$, $y_3$, そして $y_5$ は同程度に確率を均等に配分していることが わかったが、 $R_M+1\equiv 0\pmod{L}$ の場合は完全に均等で、 そうでなければ少しずれがあり、そのずれは
\begin{displaymath} \frac{1}{R_M+1}\left\lceil\frac{R_M+1}{L}\right\rceil -\fr... ...eft\lceil\frac{R_M+1}{L}\right\rceil-1\right) =\frac{1}{R_M+1}\end{displaymath} (21)

である。通常この値は非常に小さいので、十分均等であると言える。

一方で、式 (18) で定義される $y_5$ には $0\leq \mu<1$ というパラメータが含まれ、 この値を変えると、

\begin{displaymath} \frac{1}{R_M+1}\left\lceil\frac{R_M+1}{L}\right\rceil,\hspac... ...1}{R_M+1}\left(\left\lceil\frac{R_M+1}{L}\right\rceil-1\right) \end{displaymath}

の現われ方が変わる。 よって、$\mu$ を定数とせず、 $y_5$ を使用する前に適当に取ってから $y_5$ を使用すると、 適当にならされることでさらなる均等配分になることが期待される。

つまり、$x$, $z$ を、ともに rand() から独立に計算される乱数値、 すなわち 0 から $R_M$ までの値を取る、独立で一様な確率変数とし、

\begin{displaymath} \mu=\frac{z}{R_M+1},\hspace{1zw}p_6=\frac{x+\mu}{R_M+1},\hspace{1zw} y_6=\lfloor p_6L+1\rfloor\end{displaymath} (22)

と定められる $y_6$ を考えてみる。 なお、この $y_6$ の計算には rand() を 2 回使用することになる。

$y_6$ は $x$, $z$ の 2 変数関数 $y_6=y_6(x,z)$ と考えることができ、 よって、$1\leq k\leq L$ に対し、

\begin{eqnarray*}\lefteqn{\mathrm{Prob}\{y_6=k\}} \ &=& \sum_{j=0}^{R_M}\math... ... &=& \sum_{j=0}^{R_M}\frac{1}{R_M+1}\mathrm{Prob}\{y_6(x,j)=k\} \end{eqnarray*}


となるが、6 節と同様の計算により、
\begin{eqnarray*}\lefteqn{\mathrm{Prob}\{y_6(x,j)=k\}} \ &=& \frac{1}{R_M+1}\... ...\lceil\frac{R_M}{L-1}(k-1)-\frac{j}{R_M+1}\right\rceil \right\} \end{eqnarray*}


となるので、
$\displaystyle {\mathrm{Prob}\{y_6=k\}}$
  $\textstyle =$ $\displaystyle \frac{1}{(R_M+1)^2}\sum_{j=0}^{R_M} \left\{ \left\lceil\frac{R_M+... ...ght\rceil -\left\lceil\frac{R_M+1}{L}(k-1)-\frac{j}{R_M+1}\right\rceil \right\}$ (24)

となる。


補題 3

整数 A、および $R_M+1>L$ に対して、

\begin{displaymath} \sum_{j=0}^{R_M}\left\lceil\frac{A}{L}-\frac{j}{R_M+1}\right\rceil =\left\lceil\frac{R_M+1}{L}A\right\rceil \end{displaymath} (25)


証明

まず、$0\leq A<L$ に対して (25) を示す。 このとき、$0\leq A/L<1$ なので、 $0\leq j\leq R_M$ に対し、

\begin{displaymath} -1<\frac{A}{L}-\frac{j}{R_M+1}<1 \end{displaymath}

となる。よって、
\begin{displaymath} \left\lceil\frac{A}{L}-\frac{j}{R_M+1}\right\rceil \end{displaymath}

は、この場合 0 か 1 である。 よって、これが 1 となる $j$ の個数を数えればよい。 これが 1 となるのは、
\begin{displaymath} \frac{A}{L}-\frac{j}{R_M+1}>0 \end{displaymath}

のとき、すなわち、
\begin{displaymath} 0\leq j<\frac{R_M+1}{L}A \end{displaymath}

となる $j$ の個数となるので、 それは丁度 $\lceil (R_M+1)A/L\rceil$ 個となる。 よって、$0\leq A<L$ のときは (25) が成り立つ。

一般の整数 $A$ に対しては、 $A$ を $L$ で割った商を $Q$, 余りを $R$ とすれば、 $A=QL+R$, $0\leq R<L$ で、

\begin{displaymath} \left\lceil\frac{A}{L}-\frac{j}{R_M+1}\right\rceil = \lef... ...eil = Q+\left\lceil\frac{R}{L}-\frac{j}{R_M+1}\right\rceil \end{displaymath}

となり、$R$ に対しては、 (25) の $A$ を $R$ に変えたものが成り立つので、
\begin{eqnarray*}\lefteqn{ \sum_{j=0}^{R_M}\left\lceil\frac{A}{L}-\frac{j}{R_M+... ...\right\rceil \ &=& \left\lceil\frac{R_M+1}{L}A\right\rceil \end{eqnarray*}


となり、一般の $A$ に対しても (25) が成り立つ。


この補題 3 により、(24) は、

\begin{eqnarray*}\lefteqn{\mathrm{Prob}\{y_6=k\}} \ &=& \frac{1}{(R_M+1)^2}\l... ...L}k\right\rceil -\left\lceil\frac{(R_M+1)^2}{L}(k-1)\right\rceil\end{eqnarray*}


となる。この $\delta_k$ は、補題 2 により、
\begin{displaymath} \delta_k =\left\lceil\frac{(R_M+1)^2}{L}\right\rceil-1,\ \left\lceil\frac{(R_M+1)^2}{L}\right\rceil \end{displaymath}

のいずれかであることもわかる。 よって、 $(R_M+1)^2\equiv 0\pmod{L}$ であれば、$y_6$ は均等で、 そうでない場合のずれは、
\begin{displaymath} \frac{1}{(R_M+1)^2}\left\lceil\frac{(R_M+1)^2}{L}\right\rcei... ...\frac{(R_M+1)^2}{L}\right\rceil-1\right\} =\frac{1}{(R_M+1)^2} \end{displaymath}

となり、(21) と比較すれば、 こちらの方がはるかに小さいことがわかる。

ついでに、$y_2$, $y_6$ それぞれの分散も計算してみよう。 いずれも平均は $1/L$ であるから、$y_2$ の分散 $V_2$ は、

\begin{displaymath} V_2 = \frac{1}{L}\sum_{k=1}^L \left(\frac{\alpha_k}{R_M+1}-\frac{1}{L}\right)^2\end{displaymath} (26)

と定義されるが、今、
\begin{displaymath} \left\lceil\frac{R_M+1}{L}\right\rceil=q, \hspace{1zw}r=qL-(R_M+1) = L\left\langle\frac{R_M+1}{L}\right\rangle \end{displaymath}

とすると、明らかに $r$ は $0\leq r<L$ となる整数で、
\begin{displaymath} R_M+1=qL-r,\hspace{1zw}q=\left\lceil\frac{R_M+1}{L}\right\rceil\end{displaymath} (27)

となるので、この場合、$\alpha_k$ は、$(q-1)$ が $r$ 個、 $q$ が $(L-r)$ 個あり、
\begin{displaymath} (q-1)r+q(L-r)=qL-r=R_M+1 \end{displaymath}

となっていることがわかる。よって、$V_2$ は、
\begin{eqnarray*}V_2 &=& \frac{1}{L}\left\{ \left(\frac{q-1}{R_M+1}-\frac{1}{... ...(L-r)^2+(L-r)r^2}{L^3(R_M+1)^2} = \frac{r(L-r)}{L^2(R_M+1)^2} \end{eqnarray*}


となる。

一方、$y_6$ の分散 $V_6$ は、

\begin{displaymath} V_6 = \frac{1}{L}\sum_{k=1}^L \left(\frac{\delta_k}{(R_M+1)^2}-\frac{1}{L}\right)^2 \end{displaymath}

であり、この場合は、(27) の代わりに
\begin{displaymath} (R_M+1)^2=\bar{q}L-\bar{r},\hspace{1zw} \bar{q}=\left\lceil\frac{(R_M+1)^2}{L}\right\rceil,\hspace{1zw} 0\leq\bar{r}<L\end{displaymath} (28)

と取れば、$\delta_k$ は、$(\bar{q}-1)$ が $\bar{r}$ 個、 $\bar{q}$ が $(L-\bar{r})$ 個あり、よって、
\begin{eqnarray*}V_6 &=& \frac{1}{L}\left\{ \left(\frac{\bar{q}-1}{(R_M+1)^2}... ...{r}^2}{L^3(R_M+1)^4} = \frac{\bar{r}(L-\bar{r})}{L^2(R_M+1)^4}\end{eqnarray*}


となる。
\begin{displaymath} 0\leq \frac{r(L-r)}{L^2},\hspace{0.5zw} \frac{\bar{r}(L-\bar{r})}{L^2}\leq\frac{1}{4} \end{displaymath}

であり、もちろん $r$, $\bar{r}$ によって多少変わるが、 一般的には $V_2$ よりも $V_6$ の方がかなり小さくなる。

次へ: 8 最後に 上へ: プログラム中のある乱数の評価 その 2 前へ: 6 y4 の場合
竹野茂治＠新潟工科大学
2007年6月22日