To Lecture Notes

Tests for Uniform Random Number Generators

Classic Reference: Knuth, The Art of Computer Programming: Vol. 2, Seminumerical Algorithms, Second Edition, 1981, pp. 38-113.

Mean and Variance Tests

• The expected value and theoretical variance of a standard uniform random variable are 1/2 and 1/12, respectively. To see this,
  if x is standard uniform (U(0,1)), E(x) = ∫₀¹ x dx = (x²/2)|₀¹ = 1²/2 = 0²/2 = 1/2 and
  Var(x) = E(x²) - E(x)² = ∫₀¹ x² dx - 0.5² = (x³/3)|₀¹ - 1/4 = (1³/3 - 0³) - 1/4 = 1/3 - 1/4 = 1/12.
   
• Therefore the sample mean and standard deviation of 10,000 U(0,1) random numbers should be about 0.5 and √1/12 = 0.289. Try it.
   
• Now generate a matrix of 1,000 rows of length 100 U(0,1) random vectors. Think of each row as being a batch of 100 uniform random vectors. The standard error of the sample means for the rows should be about σ / √n. Try it.

Frequency Test

• Divide the interval [0,1] into equal length bins with breaks 0, 1/a, 2/a, ... , (n-1)/n, 1. U(0,1) random numbers should fall within into each of these intervals with equal probability. However, the fit should not be too good, because that would imply nonrandomness.
   
• Run this script to perform a χ²-test to check if the random numbers fall into the bins defined by 0, 1/10, 2/10, ... , 9/10, 1 with equal probability.
  

  x <- runif(1000)
  histinfo <- hist(x, breaks=seq(0, 1, 0.1))
  print(chisq.test(histinfo$counts))

• Let p be the p-value from the χ²-test. Here are Knuth's recommended conclusions about the generated U(0,1) pseudo-random numbers (Knuth, Page 44):
   
  

  P-value	Conclusion
  p < 0.01 or 0.99 < p	Generated numbers are not sufficiently random
  0.01 ≤ p < 0.05 or 0.95 < p ≤ 0.99	Generated numbers are suspect
  0.05 ≤ p < 0.10 or 0.90 < p ≤ 0.95	Generated numbers are almost suspect.

Serial Test

• To perform the serial test on generated U(0,1) random numbers, organize the the generated random numbers into pairs:
   
  
  (x₁, x₂), (x₃, x₄), ... , (x_n-1, x_n),
  
  Then plot these points in the unit square, partitioned into k² smaller squares.
   
• This plot of 1,000 U(0,1) random numbers is plotted in the unit square divided into 5² = 25 squares using this script:
  

  x <- runif(1000)
  M <- matrix(x, 500, 2, byrow=TRUE)
  plot(M, main='500 Pairs of U(0,1) Random Numbers',
     xlab='First Random Number in Pair',
     ylab='Second Random Number in Pair')
  for(i in (0:5)/5) {
     abline(h=i, col="red")
     abline(v=i, col="red")
  }
  

• It is easiest in R to organize the 1,000 points as rows of a 500 × 2 matrix before plotting.
   
• Now perform a χ²-test on the counts of points in each of the 25 smaller squares to see if they are randomly distributed with equal probability in each square. Use this script:
  

  u <- M[,1]
  v <- M[,2]
  x <- floor(5*v) + u
  y <- v - floor(5*v)/5
  cnt <- hist(x, breaks=(0:25)/5)$counts
  chisq.test(cnt)
  

• By replacing each (u,v) with the corresponding (x,y), a 5 × 5 classification grid is transformed to a 1 × 25 grid. This allows the hist function to obtain the number random number pairs in each cell.

Other Tests

• Knuth discusses several more tests, some with colorful names:
   
  
  Kolmogorov-Smirnov   Gap   Poker   Coupon Collector
   
  Permutation   Serial Correlation   Multidimensional Spectral
  
  
• The most powerful of the tests listed above is the Multidimensional Spectral Test.
   
• This script illustrates the concept of the Poker Test:
  

  x <- runif(500)
  ints <- floor(10 * x)
  M <- matrix(ints, 100, 5)
  print(M)
  

  Now
   
  
  1. Classify each row like a poker hand with only one suit: no pairs, one pair, two pairs, three of a kind, full house, four of a kind, five of a kind.
      
  2. Calculate the expected probability of each of these results:
      
     

     Result	Probability
     No pairs	0.3024
     One pair	0.4680
     Two pairs	0.1440
     Three of a Kind	0.0720
     Full House	0.0090
     Four of a Kind	0.0045
     Five of a Kind	0.0001

     
      
  3. Perform a χ²-test to test how close the actual results are to the expected results.
  
  
• A good uniform random generator passes more of these tests than a poor random generator would pass.