Groupe d’études et de recherche en analyse des décisions

G-98-65

Sparse Serial Tests of Uniformity for Random Number Generators

, et

Different versions of the serial test for testing the uniformity and independence of vectors of successive values produced by a (pseudo)random number generator are studied. These tests partition the t-dimensional unit hypercube into k cubic cells of equal volume, generate n points (vectors) in this hypercube, count how many points fall in each cell, and compute a test statistic defined as the sum of values of some univariate function f applied to these k individual counters. Both the overlapping and the non-overlapping vectors are considered. For different families of generators, such as the linear congruential, Tausworthe, nonlinear inversive, etc., different ways of choosing these functions and of choosing k are compared, and formulas are obtained for the (estimated) sample size required to reject the null hypothesis of i.i.d. uniformity as a function of the period length of the generator. For the classes of alternatives that correspond to linear generators, the most efficient tests turn out to have (in contrast to what is usually done or recommended in simulation books) and use overlapping.

, 23 pages