Paper detail

Some Patterns of Duplications in the outputs of Mersenne Twister Pseudorandom Number Generator MT19937

The Mersenne Twister MT19937 pseudorandom number generator, introduced by the last two authors in 1998, is still widely used. It passes all existing statistical tests, except for the linear complexity test, which measures the ratio of the even-odd of the number of 1's among specific bits (and hence should not be important for most applications). Harase reported that MT19937 is rejected by some birthday-spacing tests, which are rather artificially designed. In this paper, we report that MT19937 fails in a natural test based on the distribution of run-lengths on which we found an identical value in the output 32-bit integers. The number of observations of the run-length 623 is some 40 times larger than the expectation (and than the numbers of the observations of 622 and 624, etc.), which implies that the corresponding p-value is almost 0. We mathematically analyze the phenomena, and obtain a theorem which explains these failures. It seems not to be a serious defect of MT19937, because finding the defect requires astronomical efforts. Still, the phenomena should be reported to the academic society relating to pseudorandom number generation.