Testing Random Number Generators

So-called Random number generators on computers are deterministic functions producing a sequence of numbers which should mimic a sample of i.i.d. U(0; 1) random variables. Two classes of tests are commonly applied to such generators. Firstly, the theoretical tests, which look at the intrinsic structure of the generator to derive behavioral properties of the sequence of points, usually over the whole period. These theoretical tests are specific to each class of generators and include the lattice and spectral tests, discrepancy bounds calculations, period length calculations, etc.. Secondly, the empirical goodness-of-fit tests, which try finding statistical evidence against the null hypothesis: "the sequence is a sample from i.i.d. U(0; 1) random variables". In this paper, we survey the main techniques from both classes, discuss their philosophy, and look at some of the most recent developments in that area. 1. INTRODUCTION Testing randomness, when speaking about (pseudo)- random numbe..