乱数ライブラリー

スペクトル検定

スペクトル検定は、線形合同法のパラメータが適切かとうかを検定する手法であり、与えられた乱数列の性質を調べるものではない。

合同法による乱数列の生成は以下の式による。

$x_{n+1}=a x_n+c     (\text{mod} M)$

$x_0=b$


この乱数列の$k$個の要素を座標成分とする点列を考える。

$P_n\left(x_n,x_{n+1},\cdots ,x_{n+k}\right),    n=0,1,2,\cdots$


$k$次元の場合、$M^k$個の格子点のうちたかだか$M$点にしか点列$P_n$が配置されず、それらは$(k! M)^{1/k}$枚の等間隔に並んだ平行な$(k-1)$次元平面上に乗ってしまうことが知られている。この性質は、多次元疎結晶構造と呼ばれており、この構造が疎であり、高次元なるほど点列の密度が疎になることが問題である。

スペクトル検定では、以下の式で表される$\nu_k$を合同法乱数列の$k$次元頻度といい、合同法乱数列のランダムネスの尺度とする。

$\nu _k=\text{min} \left\{\sqrt{s_k^2+s_1^2+\cdots+s_k^2 }|s_1+a s_2+\cdots+a^{k-1}s_k=0 (\text{mod}  M)\right\}$


ただし、$s=(s_1,s_2,\cdots,s_k )$は非零整数ベクトルとする。クヌースは、判定基準として以下のような目安を示している。

$\log _2 \nu _k\geq \frac{30}{k},    (2\leq k\leq 6)$


参考文献:
  • 伏見正則,乱数,UP 応用数学選書,東京大学出版会,1989
  • D.E.Knuth, 渋谷正昭 訳, 準数値算法/乱数, サイエンス社, 1981



▲このページのトップに戻る