数理解析研究所講究録1032 巻 1998 年 148-151

148

Cellular Automaton 擬似乱数に対するRandom Walk 検定
高嶋1

恵三

Jo‘三(大阪教育大学)

Cellular automaton による擬似乱数生成法

1 次元 cellular automaton による擬似乱数生成法は, [10] [9] などにによって研究されているが, –般に以下のように定式化される.
数列 $\{a_{n}, -\infty<n<\infty, 0\leq a_{n}<k\}$ をある法則 によって並列に, 同時に次世代の数に更新する :列$a_{n}’.=.\phi(ai-r’ i-r+1, \ldots, aai+r)$ .
$)$$\phi$$\{a_{n}’\}$

ここで, $k,$ $r(>0)$ は整数とする. 以下では, $k=2,$ $r=1$ の場合のみ考える. 実際の計算機は有限列でなければならないので,上に実現するには,うな周期条件を付加する :$\{a_{n}\}$$a_{1}’=\phi(a_{S_{)}}a1, a_{2})$$S$を正の整数として以下のよ,$a_{S}’=\emptyset(as_{-}1, aS, a_{1})$.

さらに, 興味ある場合として [10], [1] 等で良い生成法として研究, 紹介されている 2 つの生成法 :$a_{n}’=a_{n-1}+a_{n}+a_{n+1}+a_{n}a_{n+1}$
Type (I)或いは同等な,(mod 2),$a_{n}’=a_{n-1}\mathrm{X}\mathrm{O}\mathrm{R}(an\mathrm{O}\mathrm{R}an+1)$$a_{n}’=1+a_{n-1}+a_{n+1}+a_{n}a_{n+1}$
Type (II)或いは同等な,,(mod 2),$a_{n}’=a_{n-1}\mathrm{X}\mathrm{O}\mathrm{R}(a_{n}\mathrm{O}\mathrm{R}(\mathrm{N}\mathrm{O}\mathrm{T}an+1))$,について考察する. 但し, ここで OR, XOR, NOT はそれぞれ, 論理和, 排他論理和, 論理が充分大きい場合 (例えば $S\geq 100$ )否定, である. これらは非線型な生成法であり,充分長い周期をもつ (cf. [10]). なお, [10] では TyPe (II) は Type(I) に比較してやや望ましくない生成法とされているが, 本報告では比較のために取り上げることにする.
$S$

1492Random walk 検定

前節の擬似乱数生成法に対して, $[4]\sim[8]$ と同様に以下のような random walk の見本関数の汎関数に基づく統計的検定を試みる. 例えば, 見本関数の最大値による検定の方法は以下の通りである :を正の整数とし.
は検定の対象の $0,1$ の擬似乱数列とし,$L$$y_{n}$$x_{n}=2y_{n}-1$,とおく.

Step 1. (初期化) 対象となる, 擬似乱数列の配列を線型合同法を利用して初期化する.
Step 2.(見本関数の構成)$x_{n}$

より, 長さ $2L$ の random walk の見本関数 $\{s_{n}, 0\leq n\leq 2L\}$を以下のように構成する :$s_{n}= \sum i=1xi+2jL+2kNL,$$s_{0}=0$.

この見本関数の最大値$mx_{2L}^{j}= \max\{S_{n} :0\leq n\leq 2L\}$,を求める.

Step 3. ($\chi^{2}$検定) Step 2 を $j=0,$$\ldots,$$N-1$ , に対して繰り返し$mx_{2L}^{j}$の経験分布を求める :$f_{m}=\#\{j:mx_{2}^{j}=m\}L’ m=0,1,$ $\ldots,$ $2L$ .

この経験分布に対して$\chi^{2}$

検定を行いその値$\chi_{k}^{2}$を計算する :$x_{k}^{2}=m0 \sum_{=}^{K}\frac{(f_{m}’-N\mu 2L,m)2}{N\mu_{2L,m}}$,

但し, $K= \max\{k : \mathrm{P}\mathrm{r}(MX2L=k)>10.0\},$ $\mu_{2L,k}=\mathrm{P}\mathrm{r}(MX2L=k),$ $f_{k}’=f_{k}$ , forであり, $MX_{2L}$ は見本関
$k<K$ , and $\mu_{2L,K}=\Sigma^{2}kL=K\mathrm{P}\mathrm{r}(MX2L=k),$$K$である.
検定の自由度は数の最大値である. ここで,
$f_{K}’=\Sigma_{k=K}2Lf_{k}.\cdot$$\chi^{2}$

Step 4. (Kolmogorov-Smirnov 検定) Step 3 を $k=0,1,$の経験分布$F_{30}$を求める.

自由度 $K$ の, に対して繰り返しに対して分布関数 $F(x)$ に基づき,$\ldots,$$29$$F_{30}$$\chi^{2}$

Kolmogorov-Smirnov 検定を行い, その Kolmogorov-Smirnov 統計量
める :$K_{30}^{+}$$=$$\sqrt{30}$$\max$$-\infty<x<\infty$$K_{30}^{-}$$=$$\sqrt{30}$$\max$$-\infty<x<\infty$

Step 5. Steps 2-4 を 100 回繰り返し,99 % 以上となる個数を求める.

$K_{30}^{+},$$K_{30}^{-}$$K_{30}^{+},$$K_{30}^{-}$

を求$(F_{30}(x)-F(x))$ ,$(F(x)-F_{30}(X))$ .の値が 95 %\sim 99 %, に入る個数, 及び150

3Maximum 検定の結果について結果の–部を表 (1) に示す. これらの結果からすぐに分かることは, random walk の見
本関数の長さ $2L$ が cellular automaton のセルの数より短い場合は比較的良い検定結果が得られるが, $2L\geq 1.2S$ の場合には極端に悪い結果が得られることである.
M 系列擬似乱数や加算生成法などの場合も, random walk の見本関数の長さが特性多項式の次数より長い場合, 統計的に偏りが見られるが (cf. $[4]\sim[8]$ ), 表 (1) の結果はそれらよりさらに偏っており, cellular automaton 擬似乱数は random walk などの離散確率過程のシミレーションには不適当であることが見て取れる.
最後に, cellular automaton 擬似乱数の研究者の–人 S. Wolfram はすでによく知られているとおり, 著名な数式処理ソフト Mathematica の制作者である. また, Mathematica の発売元である Wolfram Research Inc は Mathematica に組み込まれている擬似乱数生成関数のアルゴリズムを公表していないが cellular automaton のアルゴリズムに基づく擬似乱数であるようだ. そこで実際に Mathematica の擬似乱数生成関数を用いて maximum 検定を行ってみたが, 表 (1) のような検定結果は得られなかった ( $2L$ は 20000 程度まで行ってみた). そこで Mathematica の擬似乱数は前節で述べた Type(I), Type(II) とは別のアルゴリズムによるものと想像されるが, 正確なところは不明である.
$S$$\supset-$

参考文献[1] Engel : Exploring Mathematics with your Computer, Mathematical Association ofAmerica, 1993.
[2] W. Feller : An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd.
ed. Wiley, (1968).

[3]$\mathrm{D}.\mathrm{E}$. Knuth: The Art of Computer Programming, Vol. 2, $Semi- nume\dot{n}ca\iota A\iota go\dot{\mathcal{H}}thmS$,2nd ed. Addison-Wesley, (1981).

[4] K. Takashima : Sojourn time test for maximum-length linearly recurring sequenceswith characteristic primitive trinomials, J. Japanese Soc. Comp. Stat. 7, (1994) 77-87.
[5] K. Takashima : Sojourn time test of $m$-sequences with characteristic pentanomials,
J. Japanese Soc. Comp. Stat. 8, (1995) 37-46.
[6] K. Takashima: Last visit time tests for pseudorandom numbers, Journal of JapaneseSociety of Computational Statistics, 9, 1996, 1- 14.
[7] K. Takashima : Random walk tests of additive number generators, “Proceedings ofthe Workshop on Turbulent Diffusion and Related Problems in Stochastic Numerics”( . S. Ogawa and K. Sabelfeld), Inst. Stat. Math., 1997, 55-65.
$\mathrm{e}\mathrm{d}\mathrm{s}$151[8] K. Takashima: Random walk tests of reciprocal $m$-sequences, Monte Carlo Methods
and Simulations, 3, 1997, 155- 166.
[9] S. Tezuka and M. Fushimi : A Method of Designing Cellular Automata as Pseudorandom Number Generators for Built-in Self-test for VLSI, Contemporary Math., 168,363-367.
[10] S. Wolfram: Random Sequence Generation by Cellular Automata, $Adv$ . Appl. Math.,
7, 123- 169, 1986.