Group: TESTING

Testing Random Numbers

Department of Computer Science
Florida State University

  A reliable random number generator is obviously a key requirement for any serious stochastic simulation. However what is a "good" RNG? Since there does not exist a test (or test suite), which if a RNG passes it, identifies a RNG as good, we seek to design various tests to detect a RNG's defects so that we can tell which RNGs might be sufficiently random -- or at least avoid using an unsuitable RNG.
  What is a test? Any function of elements of an i.i.d. random sequence may serve as a test, if its distribution is known, or even if its distribution is merely compared with that of other RNGs. Anyone with a knowledge of probability theory should be able to create his own tests to test RNGs.
  The game of designing and testing RNG is somewhat like detecting drug use in sports. On the one hand, new tests are developed to catch a different generator's defects and, on the other hand, new generators are built which would pass all the current statistical tests, and so on.
  Here we are trying to build a state-of-art test suite so that it is easy for anyone who wants to test their RNGs. We have two parts of this test suite: Knuth's Empirical tests and Marsaglia's Stringent tests.
  1. Knuth's Empirical tests ( Mild tests)
    1. Collisions test.
    2. Gap Test
    3. Parallel Statistical tests
    4. Blocking test
    5. Fourier Transform test
  2. Marsaglia's Stringent tests.
    1. Overlapping M-tuple tests
    2. Overlapping-Permutation tests
    3. The OPSO test (Overlapping-pairs-sparse-occupancy)
    4. Parking lot, lattice and related tests.
    5. The Birthday-spacings test
    6. Ranks of random binary matrices
GROUP
MEETINGS
Time: Wednesdays 8:00 AM
Place: 486 Dirac Science Library
MEMBERS
Hongmei Chi
Yaohang Li
  Yaohang's home page
Wenchang Yan
  Wenchang's home page
NAVIGATION
Home
PRNG Group
Testing Group
QRNG Group
Discrete Group
MCPDE Group
QMC Group
Finance Group
PRINCIPLE INVESTIGATOR
Prof. Michael Mascagni
WEBMASTER
Ethan Kromhout
Project 9
Improving the SPRNG test suite

 The SPRNG test suite includes ten valuable tests for pseudo-random number sequences, most based on Knuth's descriptions. This project will seek to improve the quality and efficiency of the current tests, and add new tests to help judge new families of generators.

Project 1
Development of a Fast Discrepancy Code

 The uniformity of a sequence of points is measured in terms of its discrepancy.
The L∞ discrepancy is defined by:

The L2 discrepancy is defined by

Where RN(J) is the Monte Carlo quadrature error in measuring the volume of subset J of Id.
Similarly, the star discrepancy is defined over rectangular sets with one vertex at 0.
Usually the computation of the L2 discrepancy of N d-dimensional points is O(N2). The computation of the L∞ discrepancy of N d-dimesional points is O(Nd). The project is to try to find an efficient way to reduce the computional cost of discrepancy to measure the uniformity of multi-dimensional random sequence.

Project 2
Development of A Fast Spectral Code

 SPECTRAL TEST CODE:
  Spectral test is one of the theoretical tests that provides a way to check the quality of RNGs with a lattice structure such as linear congruent RNGs. Compared with theoretical test, empirical testing consumes more time and resources, also we will have to carry out these tests with samples of similar size and in similar dimensions as in our original simulation. For this reason, theoretical figures of merit have been designed that allow to assess RNGs.
  In Knuth's famous book, he wrote of the spectral test: "Not only do all good generators pass this test, all generators now known to be bad actually fail it".
  The spectral test embodies aspects of the both the empirical and theoretical tests because it deals with properties of the full period of the sequence also requires a computer program to determine the results.
  The spectral test quantity has a nice geometric interpretation which computes the maximal distance between successive parallel hyper planes covering all possible points Xn that the RNG produces. This interpretation leads to very efficient algorithms to compute the value of the spectral test.