Tests of randomness by the gambler’s ruin algorithm

摘要

In the gambler’s ruin algorithm on the cyclic group Zn={0,1,…,n-1} we consider arrival time at 0 starting from a fixed point x ≠ 0 and use several versions of arrival time algorithm to test pseudorandom number generators. This kind of test based on the exact probability density for a random walk on a finite group is done for the first time. The test results show hidden defects in some generators such as combined multiple recursive generators and Mersenne Twister generators.