乱数ライブラリー

Spectrum test

Spectrum test does not examine the nature of the given random number sequence, but it is a technique to test whether the parameters of a congruential method are appropriate.

A congruential method generates random number sequence by the following equation.

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

$x_0=b$


The sequence of points with $k$ element coordinate components uses this random number sequence.

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


In the case of $k$-dimensional, point sequence $P_n$ is only placed at most $M $points out of $M ^ k$ grid points. It is known that these points are placed on the $(k! M)^{1/k}$ equally spaced parallel $(k-1)$-dimensional plane. This property, called multi-dimensional sparse crystal structure, has the problem that this structure is coarse and that the density of the point sequence becomes more sparse in higher dimensional.

In the spectrum test the $\nu_k$ represented by the following formula is the $k$-dimensional frequency of congruential random number sequence. it is a measure of the randomness of congruential random number sequence.

$\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\}$


Where, $s=(s_1,s_2,\cdots,s_k )$ is a non-zero integer vector. Knuth shows the following approximate criteria.

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


References :
  • M.Fushimi , Random number , UP Sensho Applied Mathematics , University of Tokyo Press , 1989
  • D.E.Knuth, The Art of Computer Programming Vol.II, Addison-Wesley,1981.



Back to this TOP