数学アルゴリズム研究ノート『非線形合同法による擬似乱数周期の延長』

数学アルゴリズム研究ノート（２）

２．非線形合同法による擬似乱数周期の延長

2003年７月　田沼英樹

２－１．非線形合同法の拡張

　前回考察した二次合同法（あるいはさらに高次の合同法）は，線形合同法と同じく

$x_{r+1}=f(x_{r})$

という形の一変数の漸化式を用いたものですが，この方式では基本的に周期が一変数のビット表現の組み合わせを超えることができず，また $f$ として多項式を用いているために，下位ビットの周期が短いという弱点も同様に受け継いでいます．

　そこでまず，より長周期で優良な擬似乱数を得るために，多倍長演算でビット長を仮想的に増やす方法が考えられますが，多倍長の乗算は計算負荷が大きいため，これはあまり実用的であるとは言えません．

　次に，二変数の漸化式

$\left\{\begin{array}{l} x_{r+1}=f(x_{r}, y_{r})\\ y_{r+1}=g(x_{r}, y_{r})\end{array}\right.$

により周期を二変数の組み合わせに拡張することが考えられますが，まず単純に $x_{r}$ と $y_{r}$ のビット長を $n$ として， $f$ と $g$ に多項式を用いて周期 $2^{2n}$ の擬似乱数を得ようとしても，これがどうにもうまくいきません．定理１－３の証明と同様の手法で延長した最上位ビットの挙動を調べようとしても， $x_{r}$ と $y_{r}$ の組み合わせの周期が高次の $2$ べきであるために，最上位ビットが反転しなくなってしまうのです．（確かめてみてください）

　そこで，少し発想を変えて

$\left\{\begin{array}{l} {x_{r}} \text{は} \mathrm{[}1,2^{m}-1\mathrm{]} \text{の}曾mathrm{S}\text{ての}箪mathrm{l}\text{をとる}周期 2^{m}-1 \text{の}欺mathrm{[}似乱数\\ y_{r+1}=f(x_{r}, y_{r})\end{array}\right.$

という形の擬似乱数を考えます．つまり， ${y_{r}}$ は種となる擬似乱数 ${x_{r}}$ の周期を延長したものとなり， $y_{r}$ のビット長を $n$ とすると，最大 $2^{n}(2^{m}-1)$ の周期をとり得ることになります．ここで，擬似乱数 ${x_{r}}$ は条件として特殊な形の周期を持ちますが，多くのシフトレジスタ（あるいは有限体上の多項式環）をもとにした擬似乱数は，このような周期を持ちます．

２－２．擬似乱数周期の延長

　先に述べたように，まず ${x_{r}}$ を $\mathrm{[}1, 2^{m}-1\mathrm{]}$ の全ての値をとるビット長 $m$ で周期 $2^{m}-1$ の擬似乱数列とし， ${y_{r}}$ を合同式

$y_{r+1}\equiv f(x_{r}, y_{r}) {\rm mod}2^{n}$

で生成されて $\mathrm{[}0, 2^{n}-1\mathrm{]}$ の値をとるビット長 $n$ の数列とします．

　そして，関数 $f$ として二次式

$f(x, y) = a_{20}x^{2}+a_{11}xy+a_{02}y^{2}+a_{10}x+a_{01}y+a_{00}$

をとったときの値の組の列 ${(x_{r}, y_{r})}$ の周期について，定理１－３の証明と類似の手法で考察を行うことにします．

　まず $n=1$ のとき， $f$ について

$f(x, y) \equiv a_{20}x+a_{11}xy+a_{02}y+a_{10}x+a_{01}y+a_{00} {\rm mod}2$

$\equiv a_{11}xy+(a_{20}+a_{10})x+(a_{02}+a_{01})y+a_{00} {\rm mod}2$

という合同式が成り立ちますが，簡単のために $a_{11}\equiv 0{\rm mod}2, a_{02}+a_{01}\equiv 1{\rm mod}2$ という制約条件を付け加えると

$y_{r+1}-y_{r} \equiv (a_{20}+a_{10})x_{r}+a_{00} {\rm mod}2$

となり， $r\in\mathrm{[}0, 2^{m}-2\mathrm{]}$ について両辺の総和をとると

$\displaystyle y_{2^{m}-1}-y_{0} \equiv (a_{20}+a_{10})\sum_{x=1}^{2^{m}-1}x+a_{00}(2^{m}-1) \equiv 2^{m-1}(2^{m}-1)(a_{20}+a_{10})+(2^{m}-1)a_{00} {\rm mod}2$

となることから， $m\geq 2, a_{00}\equiv 1{\rm mod}2$ のとき $y_{2^{m}-1}-y_{0}\equiv 1{\rm mod}2$ より ${(x_{r}, y_{r})}$ は周期 $2^{1}(2^{m}-1)$ を持ちます．

　条件を一旦まとめると， $f$ が $a_{11}\equiv 0{\rm mod}2, a_{02}+a_{01}\equiv a_{00}\equiv 1{\rm mod}2$ を満たすとき， $m\geq 2, n=1$ について ${(x_{r}, y_{r})}$ は周期 $2^{n}(2^{m}-1)$ を持ちます．

　次に，ある $n\geq 1$ について ${(x_{r}, y_{r})}$ が周期 $2^{n}(2^{m}-1)$ を持つと仮定し， $y_{r}$ の上位に $1$ ビット拡張して $2^{n}z_{r}+y_{r}, z_{r}\in{0, 1}$ とおいて

$2^{n}z_{r+1}+y_{r+1} \equiv f(x_{r}, 2^{n}z_{r}+y_{r}) {\rm mod}2^{n+1}$

とした場合の ${(x_{r}, 2^{n}z_{r}+y_{r})}$ の周期を考えます．

　 $f$ についての合同式

$f(x_{r}, 2^{n}z_{r}+y_{r}) = a_{20}x_{r}^{2}+a_{11}x_{r}(2^{n}z_{r}+y_{r})+a_{02}(2^{n}z_{r}+y_{r})^{2}+a_{10}x_{r}+a_{01}(2^{n}z_{r}+y_{r})+a_{00}$

$\equiv f(x_{r}, 2^{n}z_{r}+y_{r})+(a_{11}x_{r}+a_{01})2^{n}z_{r} {\rm mod}2^{n+1}$

より， $a_{11}\equiv 0{\rm mod}2, a_{01}\equiv 1{\rm mod}2$ という制約条件を付け加えると

$2^{n}z_{r+1}+y_{r+1} \equiv f(x_{r}, 2^{n}z_{r}+y_{r}) \equiv f(x_{r}, y_{r})+2^{n}z_{r} {\rm mod}2^{n+1}$

$2^{n}(z_{r+1}-z_{r}) \equiv f(x_{r}, y_{r})-y_{r+1} {\rm mod}2^{n+1}$

が成り立ちます．そこで $r\in\mathrm{[}0, 2^{n}(2^{m}-1)-1\mathrm{]}$ について両辺の総和をとると

$\displaystyle 2^{n}(z_{2^{n}(2^{m}-1)}-z_{0}) \equiv \sum_{r=0}^{2^{n}(2^{m}-1)}\left\{f(x_{r},y_{r})-y_{r+1}\right\} {\rm mod}2^{n+1}$

$\displaystyle\equiv a_{20}\sum_{x=1}^{2^{m}-1}x^{2}\sum_{y=0}^{2^{n}-1}1+a_{11}\sum_{x=1}^{2^{m}-1}x\sum_{y=0}^{2^{n}-1}y+a_{02}\sum_{x=1}^{2^{m}-1}1\sum_{y=0}^{2^{n}-1}y^{2}+a_{10}\sum_{x=1}^{2^{m}-1}x\sum_{y=0}^{2^{n}-1}1+(a_{01}-1)\sum_{x=1}^{2^{m}-1}1\sum_{y=0}^{2^{n}-1}y+a_{00}\sum_{x=1}^{2^{m}-1}1\sum_{y=0}^{2^{n}-1}1 {\rm mod}2^{n+1}$

$\displaystyle\equiv a_{20}\frac{(2^{m}-1)(2^{m+1}-1)}{3}2^{m-1}2^{n}+a_{11}(2^{m}-1)2^{m-1}(2^{n}-1)2^{n-1}+a_{02}(2^{m}-1)\frac{(2^{n}-1)(2^{n+1}-1)}{3}2^{n-1}+a_{10}(2^{m}-1)2^{m-1}2^{n}+(a_{01}-1)(2^{m}-1)(2^{n}-1)2^{n-1}+a_{00}(2^{m}-1)2^{n} {\rm mod}2^{n+1}$

$\displaystyle\equiv 2^{m-3}2^{n+1}\left\{a_{20}\frac{2(2^{m}-1)(2^{m+1}-1)}{3}+a_{11}(2^{m}-1)(2^{n}-1)+a_{10}2(2^{m}-1)\right\}+a_{02}(2^{m}-1)\frac{(2^{n}-1)(2^{n+1}-1)}{3}2^{n-1}+(a_{01}-1)(2^{m}-1)(2^{n}-1)2^{n-1}+a_{00}(2^{m}-1)2^{n} {\rm mod}2^{n+1}$

となることから， $m\geq 3, a_{02}\equiv 0{\rm mod}2$ という制約条件を付け加えると $a_{01}\equiv 1{\rm mod}2$ より

$\displaystyle 2^{n}(z_{2^{n}(2^{m}-1)}-z_{0}) \equiv a_{02}(2^{m}-1)\frac{(2^{n}-1)(2^{n+1}-1)}{3}2^{n-1}+(a_{01}-1)(2^{m}-1)(2^{n}-1)2^{n-1}+a_{00}(2^{m}-1)2^{n} {\rm mod}2^{n+1}$

$\equiv a_{02}2^{n-1}+(a_{01}-1)2^{n-1}+a_{00}2^{n} {\rm mod}2^{n+1}$

$\equiv 2^{n-1}(a_{02}+a_{01}-1+2a_{00}) {\rm mod}2^{n+1}$ ．

　したがって， ${(x_{r}, 2^{n}z_{r}+y_{r})}$ の周期が $2^{n+1}(2^{m}-1)$ となるための条件は

$2^{n}(z_{2^{n}(2^{m}-1)}-z_{0}) \equiv 2^{n-1}(a_{02}+a_{01}-1+2a_{00}) \equiv 2^{n} {\rm mod}2^{n+1}$

$\Leftrightarrow a_{02}+a_{01}+2a_{00}\equiv 3{\rm mod}4$

となり，前出の $n=1$ についての条件 $a_{11}\equiv 0{\rm mod}2, a_{02}+a_{01}\equiv a_{00}\equiv 1{\rm mod}2, m\geq 2$ と合わせて

$a_{11}\equiv 0{\rm mod}2, a_{02}+a_{01}\equiv 1{\rm mod}4, a_{01}\equiv a_{00}\equiv 1{\rm mod}2, m\geq 3$

とすると，数学的帰納法により次の定理が成り立ちます．

【定理２－２－１】

　 ${\bm{x}_{\bm{r}}}$ を $\mathrm{[}\bm{1}, \bm{2}^{\bm{m}}-\bm{1}\mathrm{]}$ の全ての値をとる周期 $\bm{2}^{\bm{m}}-\bm{1}$ の整数列とし， ${\bm{y}_{\bm{r}}}$ を $\mathrm{[}\bm{0}, \bm{2}^{\bm{n}}-\bm{1}\mathrm{]}$ の値をとる整数列で，整数係数の二次式 $\bm{f}(\bm{x}, \bm{y})=\bm{a}_{\bm{2}\bm{0}}\bm{x}^{\bm{2}}+\bm{a}_{\bm{1}\bm{1}}\bm{x}\bm{y}+\bm{a}_{\bm{0}\bm{2}}\bm{y}^{\bm{2}}+\bm{a}_{\bm{1}\bm{0}}\bm{x}+\bm{a}_{\bm{0}\bm{1}}\bm{y}+\bm{a}_{\bm{0}\bm{0}}$ により合同式 $\bm{y}_{\bm{r}+\bm{1}}\equiv\bm{f}(\bm{x}_{\bm{r}}, \bm{y}_{\bm{r}}) {\rm mod}\bm{2}^{\bm{n}}$ から生成されるものとする．このとき $\bm{a}_{\bm{1}\bm{1}}\equiv\bm{0}{\rm mod}\bm{2}, \bm{a}_{\bm{0}\bm{2}}+\bm{a}_{\bm{0}\bm{1}}\equiv\bm{1}{\rm mod}\bm{4}, \bm{a}_{\bm{0}\bm{1}}\equiv\bm{a}_{\bm{0}\bm{0}}\equiv\bm{1}{\rm mod}\bm{2}, \bm{m}\geq\bm{3}$ であるならば，任意の $\bm{n}\in\bm{N}$ に対し値の組の列 ${(\bm{x}_{\bm{r}}, \bm{y}_{\bm{r}})}$ は周期 $\bm{2}^{\bm{n}}(\bm{2}^{\bm{m}}-\bm{1})$ を持つ．

　ここで一つ注意が必要なのは，値の組の列 ${(x_{r}, y_{r})}$ が最大周期を持ったとしても，数列 ${y_{r}}$ が必ずしも同じ周期を持つとは限らないということです．しかし，制約条件を少し増やすだけで， ${y_{r}}$ も同じ周期を持つことを示すことができます．

【系２－２－２】

　定理２－２－１の条件に加え，さらに $\bm{a}_{\bm{2}\bm{0}}\equiv\bm{0}{\rm mod}\bm{2}, \bm{a}_{\bm{1}\bm{0}}\equiv\bm{1}{\rm mod}\bm{2}, \bm{n}\geq\bm{m}$ であるならば， ${\bm{y}_{\bm{r}}}$ は周期 $\bm{2}^{\bm{n}}(\bm{2}^{\bm{m}}-\bm{1})$ を持つ．

［証明］

　 $f(x, y)$ を $x$ の多項式とみなすと定理１－２の条件を満たすことから， $f(x, y)$ は変数 $x$ について単射である．

　 ${y_{r}}$ の周期を $p$ とおくと $y_{1}=f(x_{p}, y_{0})=f(x_{0}, y_{0})$ となるが， $f$ の単射性から $x_{p}=x_{0}$ となり， ${y_{r}}$ は ${(x_{r}, y_{r})}$ と同じ周期を持つ．■

　このように， $f$ の単射性を仮定することによって容易に ${y_{r}}$ の最大周期が保証されるわけですが，このままでは $n\geq m$ という条件があるために， $n$ がワード長で制限されているときには周期が高々 $2^{n}(2^{n}-1)$ で頭打ちになってしまいます．

　そこで，もう少し詳細な解析を行うことにより，次の様に条件を緩めることができます．

【系２－２－３】

　定理２－２－１の条件に加え，さらに $\bm{a}_{\bm{2}\bm{0}}+\bm{a}_{\bm{1}\bm{0}}\equiv\bm{1}{\rm mod}\bm{2}$ であるならば， ${\bm{y}_{\bm{r}}}$ は周期 $\bm{2}^{\bm{n}}(\bm{2}^{\bm{m}}-\bm{1})$ を持つ．

［証明］

　 $r$ が $\mathrm{[}0, 2^{m}-2\mathrm{]}$ にわたって動くとしたとき， ${x_{r}}$ の最下位ビットが $0$ となる回数は $2^{m-1}-1$ ， $1$ となる回数は $2^{m-1}$ である． ${x_{r}}$ の最下位ビットの周期を $p$ とし，周期内で最下位ビットが $0$ となる回数を $p_{0}$ ， $1$ となる回数を $p_{1}$ とすると

$\displaystyle\frac{(2^{m}-1)p_{0}}{p}=2^{m-1}-1, \frac{(2^{m}-1)p_{1}}{p}=2^{m-1} \Rightarrow \frac{(2^{m}-1)(p_{1}-p_{0})}{p}=1 \Rightarrow \frac{2^{m}-1}{p}=\frac{1}{p_{1}-p_{0}}$

となるが，両辺は整数であることから $p_{1}-p_{0}=1, p=2^{m}-1$ となり， ${x_{r}}$ の最下位ビットの列は周期 $2^{m}-1$ を持つ．

　次に ${y_{r}}$ の周期を $q$ とおくと，任意の $r$ について

$y_{r+1}\equiv f(x_{r+q}, y_{r})\equiv f(x_{r}, y_{r}) {\rm mod}2^{n} \Rightarrow (a_{11}y_{r}+a_{20}+a_{10})(x_{r+q}-x_{r})\equiv 0 {\rm mod}2$

となることから， $a_{11}\equiv 0{\rm mod}2, a_{20}+a_{10}\equiv 1{\rm mod}2$ のとき $x_{r+q}\equiv x_{r} {\rm mod}2$ となり， $q$ は ${x_{r}}$ の最下位ビット列の周期 $2^{m}-1$ の倍数となる．

　ここで， ${(x_{r}, y_{r})}$ の周期 $2^{n}(2^{m}-1)$ は ${x_{r}}$ の周期 $2^{m}-1$ と ${y_{r}}$ の周期 $q$ の最小公倍数であるが， $q$ が $2^{m}-1$ の倍数であることから $q=2^{n}(2^{m}-1)$ となり， ${y_{r}}$ は周期 $2^{n}(2^{m}-1)$ を持つ．■

　このように， $f(x, y)$ が $x$ の最下位ビットについて単射であるという条件だけで ${y_{r}}$ の周期が最大になることが保証されますが，実際に擬似乱数として利用する場合にはなるべく ${x_{r}}$ について多くの情報が反映されることが望ましく，下位 $n$ ビットについて単射であるための条件 $a_{20}\equiv 0{\rm mod}2, a_{10}\equiv 1{\rm mod}2$ を満たしている方が良いものと思われます．

　そこで，このような擬似乱数列の延長を以下のように定義します．

【定義２－２－４】

　 ${\bm{x}_{\bm{r}}}$ を周期 $\bm{M}$ の整数列とし， ${\bm{y}_{\bm{r}}}$ を $\mathrm{[}\bm{0}, \bm{2}^{\bm{n}}-\bm{1}\mathrm{]}$ の値をとる整数列で，関数 $\bm{f}(\bm{x}, \bm{y})$ により合同式 $\bm{y}_{\bm{r}+\bm{1}}\equiv\bm{f}(\bm{x}_{\bm{r}}, \bm{y}_{\bm{r}}) {\rm mod}\bm{2}^{\bm{n}}$ から生成されるものとする．このとき ${\bm{y}_{\bm{r}}}$ は $\bm{f}$ による ${\bm{x}_{\bm{r}}}$ の延長であるという．ここで ${\bm{y}_{\bm{r}}}$ の周期が $\bm{2}^{\bm{n}}\bm{M}$ であるとき，この延長は全周期的であるという．また $\bm{f}(\bm{x}, \bm{y})$ が $\bm{x}$ の下位 $\bm{n}$ ビットについて単射であるならば，この延長は単射的であるという．

　上記の定理および系は， $f$ が二次式のときに擬似乱数列の延長が全周期的であるための十分条件を示していることになります．つまり，これらの結果をまとめて言い換えると，次の定理になります．

【定理２－２－５】

　 ${\bm{x}_{\bm{r}}}$ を $\mathrm{[}\bm{1}, \bm{2}^{\bm{m}}-\bm{1}\mathrm{]}$ の全ての値をとる周期 $\bm{2}^{\bm{m}}-\bm{1}$ の整数列（ただし $\bm{m}\geq\bm{3}$ とする）とし， ${\bm{y}_{\bm{r}}}$ を整数係数の二次式 $\bm{f}(\bm{x}, \bm{y})=\bm{a}_{\bm{2}\bm{0}}\bm{x}^{\bm{2}}+\bm{a}_{\bm{1}\bm{1}}\bm{x}\bm{y}+\bm{a}_{\bm{0}\bm{2}}\bm{y}^{\bm{2}}+\bm{a}_{\bm{1}\bm{0}}\bm{x}+\bm{a}_{\bm{0}\bm{1}}\bm{y}+\bm{a}_{\bm{0}\bm{0}}$ による ${\bm{x}_{\bm{r}}}$ の延長とする．このとき $\bm{a}_{\bm{1}\bm{1}}\equiv\bm{0}{\rm mod}\bm{2}, \bm{a}_{\bm{0}\bm{2}}+\bm{a}_{\bm{0}\bm{1}}\equiv\bm{1}{\rm mod}\bm{4}, \bm{a}_{\bm{0}\bm{1}}\equiv\bm{a}_{\bm{0}\bm{0}}\equiv\bm{1}{\rm mod}\bm{2}, \bm{a}_{\bm{2}\bm{0}}+\bm{a}_{\bm{1}\bm{0}}\equiv\bm{1}{\rm mod}\bm{2}$ であるならば，この延長は全周期的である．また $\bm{a}_{\bm{2}\bm{0}}\equiv\bm{0}{\rm mod}\bm{2}, \bm{a}_{\bm{1}\bm{0}}\equiv\bm{1}{\rm mod}\bm{2}$ であるならば，この延長は単射的である．

　ここで，実用的には乗算を一度で済ませるために， $f$ を一次式の積として表現した方が便利になります．

【系２－２－６】

　定理２－２－５の条件のもとで $\bm{f}(\bm{x}, \bm{y})=(\bm{a}_{\bm{0}}\bm{y}+\bm{b}_{\bm{0}}\bm{x}+\bm{c}_{\bm{0}})(\bm{a}_{\bm{1}}\bm{y}+\bm{b}_{\bm{1}}\bm{x}+\bm{c}_{\bm{1}})$ とおく．このとき $\bm{a}_{\bm{0}}\equiv\bm{b}_{\bm{0}}\equiv\bm{0}{\rm mod}\bm{2}, \bm{c}_{\bm{0}}\bm{a}_{\bm{1}}\equiv\bm{1}{\rm mod}\bm{4}, \bm{b}_{\bm{1}}\equiv\bm{c}_{\bm{1}}\equiv\bm{1}{\rm mod}\bm{2}$ ならば $\bm{f}$ による延長は全周期的かつ単射的である．

２－３．延長擬似乱数の性質

　この擬似乱数の延長は，かき混ぜ法（前回の参考文献を参照）と同様に乱数の性質の改良を図るとともに，さらに乱数周期の延長までできるということから，かなり強力な乱数発生の手段となり得ます．そして非常に興味深いのは，全く性質の異なる二種類の擬似乱数を，ただ単に加えたりするのではなく，本質的に融合できるということです．

　例えば，Ｃ言語表記で次のような変換から得られる数列を考えます．

　　　x = (g &−(x&1)) ^ (x>>1)

　ここで， g のところには何か適当な定数を置くことになりますが，例えば x を32ビットの符号なし整数とした場合， g に 0x80000057 を指定して 0 以外の値を x の初期値とすると，周期 $2^{32}-1$ の数列が得られます．これは，原始多項式 $x^{32}+x^{7}+x^{5}+x^{3}+x^{2}+x^{1}+x^{0}$ によって生成されるシフトレジスタによる乱数列に相当します．一般に，有限体上の多項式の演算を利用した数列は，整数の合同式とくらべて比較的容易に長い周期を得ることができます．

　ところが，この数列は特定の１ビットのみを取り出して利用する分にはある程度乱数として有効なのですが，シフトレジスタ全体を整数値として取り出した場合，例えば偶数値の次は必ず半分の値になるといったように値の相関がかなり強く，そのままでは擬似乱数としてほとんど使い物になりません．そこで，この数列を元にして非線形合同法で延長することにより，相関を消した上でさらに長周期の擬似乱数を得ることが可能になります．（次回，詳しく検討します）

　このように，有限体上の多項式環と整数の合同式という全く異質のものが融合して互いに補い合うというのは，それ自体数学的にも興味深いものであるといえます．

　延長された擬似乱数列の性質については，その多くを種になる数列 ${x_{r}}$ と変換関数 $f(x, y)$ に依るために一般的にあまり細かなことは言えませんが，ほぼ自明な範囲で以下の定理が成り立ちます．

【定理２－３－１】

　 ${\bm{x}_{\bm{r}}}$ を $\mathrm{[}\bm{1}, \bm{2}^{\bm{m}}-\bm{1}\mathrm{]}$ の全ての値をとる周期 $\bm{2}^{\bm{m}}-\bm{1}$ の整数列とし， ${\bm{y}_{\bm{r}}}$ を $\mathrm{[}\bm{0}, \bm{2}^{\bm{n}}-\bm{1}\mathrm{]}$ の値をとる整数列で， ${\bm{x}_{\bm{r}}}$ の全周期的かつ単射的な延長であるとする．もし $\bm{m}>\bm{n}$ であるならば，隣接する２つの値の組 $(\bm{y}_{\bm{r}}, \bm{y}_{\bm{r}+\bm{1}})$ は $\bm{2}^{\bm{2}\bm{n}}$ 通りの全ての値の組み合わせをとる．また $\bm{m}=\bm{n}$ であるときは， $\left(\bm{y}, \bm{f}(\bm{0}, \bm{y})\right)$ という形の組を除外した $\bm{2}^{\bm{2}\bm{n}}-\bm{2}^{\bm{n}}$ 通りの値の組み合わせを周期内に一回ずつとる．

　このように，種になる数列と変換関数についてあまり仮定することなく，２次元についての均等分布が保証されることになります．

　さらに，種になる数列が多次元について均等に分布することがわかっている場合，次のことがいえます．

【定理２－３－２】

　 ${\bm{x}_{\bm{r}}}$ の隣接する $\bm{k}$ 個の組 $(\bm{x}_{\bm{r}}, \bm{x}_{\bm{r}+\bm{1}}, \cdots, \bm{x}_{\bm{r}+\bm{k}-\bm{1}})$ の下位 $\bm{n}$ ビットの値が $\bm{2}^{\bm{k}\bm{n}}$ 通りの全ての組み合わせをとり得るとき，その全周期的かつ単射的な延長である $\bm{n}$ ビットの数列 ${\bm{y}_{\bm{r}}}$ の $\bm{k}+\bm{1}$ 個の組 $(\bm{y}_{\bm{r}}, \bm{y}_{\bm{r}+\bm{1}}, \cdots, \bm{y}_{\bm{r}+\bm{k}})$ は $\bm{2}^{(\bm{k}+\bm{1})\bm{n}}$ 通りの全ての値の組み合わせをとる．

　つまり，種になる数列が $k$ 次元について均等に分布するとき，その全周期的かつ単射的な延長は $k+1$ 次元について均等に分布することがわかります．ただし，この多次元均等分布は $n$ ビット全体についてのものであって，さらに上位ビットのみについてより多次元に均等分布するといった詳細な結果を得るためには，おそらく個々の変換関数 $f(x, y)$ について詳しく解析を行う必要があります．

　ここで，多次元均等分布が保証されている擬似乱数列で，先に述べた方法で延長可能なものの具体例として， Mersenne Twister [1] というものがあります．この擬似乱数生成法はシフトレジスタによる擬似乱数を究極にまで発展させた手法で， $2^{19937}-1$ という非常に長い周期と， $623$ 次元にわたって均等分布するという著しい性質を持ち，また高速に実行できるという特徴を持っています．この擬似乱数の出力は $32$ ビットの整数列となりますが，実際には $19937$ ビットの内部状態を持ち，その一部を変換して出力していることから，仮想的には $19937$ ビットの整数列の下位 $32$ ビットのみを取り出して使っているとみなすことができます．したがって，定理２－２－５で非線形合同法により $m=19937, n=32$ として周期を $2^{19969}-2^{32}$ に延長することが可能となり，またそれが単射的であれば，定理２－３－２により $624$ 次元にわたって均等に分布することがわかります．ただし， Mersenne Twister には出力の上位ビットのみについても優れた多次元分布を持つといった性質がありますが，これについては延長によってかえって失われてしまう可能性があります．

　もっとも，実用的には Mersenne Twister をさらに延長する必要性などあまりないのかもしれませんが，理論的にはこういった別の方向からもさらに新しい発展の可能性があることを示しておきたいと思います．

参考リンク

[1] Mersenne Twister: A random number generator

次に進む

戻る