乱数ライブラリー

Random walk test

In k-dimensional random walk test, $\left\lceil \log _2 k\right\rceil$ bit random numbers are generated, and n step random walk is performed on the k-dimensional cubic lattices starting from the origin.$\lceil x\rceil$ is the smallest integer greater than or equal to $x$ for real $x$. This step is repeated $N$ times. Each $2^k$ quadrant, the end of the random walk will be counted ${N_i },i=1,2,…,2^k$. As each quadrant become equal probability when random number is in the uniform, $\chi^2$ statistics expressed by the following equation can be tested by following the $\chi^2$ distribution with degrees of freedom 2.

$\chi ^2=\sum _{i=1}^{2^k} \frac{\left(N_i-N2^{-k}\right){}^2}{N2^{-k}}$


It is noted that the result varies depending on the method of converting the motion of the random walk from the random number.

Examples on the method of converting are introduced. In order to convert the movement of the random walk from the random number, it may be as follows. As a one-dimensional random walk test $[0,1)$ uniform random numbers $\{x_i \},i=1,2,…,n$ are generated. The random numbers are converted as follows: the position on $x$-axis is moved to -1 or +1 direction by $x$ value.

$-1 (x_i<0.5)$

$+1 (x_i\ge 0.5)$


As a 2-dimensional random walk test $[0,1)$ uniform random numbers $\{x_i,y_i\},i=1,2,…,n$ are generated. The random numbers are converted as same as above: the position on $y$-axis is moved to -1 or +1 direction by $y$ value.



Reference:
  • JIS Z 9031:2012, Procedure for random number generation and randomization



Back to this TOP