Random number properties; KS test algorithm

Properties of random numbers

Random numbers used in simulation are uniformly distributed on [0, 1) and statistically independent.

1. Uniformity. Each number is equally likely to fall in any sub-interval of [0, 1). If the interval is divided into n equal classes, each class should receive about N/n of the N numbers. The density is f(R) = 1 for 0 ≤ R ≤ 1, so E(R) = 1/2 and Var(R) = 1/12.
2. Independence. The value of one number must not depend on any earlier or later number. There should be no pattern, trend or correlation in the sequence, so knowing R1 tells nothing about R2.
3. Maximum density. Values should cover [0, 1) closely, so the generator should have a very large number of distinct values (small gaps between possible values).
4. Long (maximum) period. The sequence should not repeat for a very long time. Ideally the period is as large as the modulus m (full period).
5. Reproducibility. The same seed must give the same sequence. This is needed for debugging and for comparing alternative designs with the same random inputs.
6. Efficiency and portability. The generator should be fast, need little memory, and give the same results on different computers.

Kolmogorov-Smirnov (K-S) test

The K-S test compares the empirical (sample) cdf SN(x) of the generated numbers with the cdf of the uniform distribution, F(x) = x for 0 ≤ x ≤ 1. It works on the individual numbers, so it needs no grouping into classes and suits small samples.

Hypotheses: H0: the numbers are uniformly distributed on [0, 1]. H1: they are not.

Algorithm

1. Rank the N numbers from smallest to largest: R(1) ≤ R(2) ≤ ... ≤ R(N).
2. Compute D⁺ = max over i of [ i/N − R(i) ].
3. Compute D⁻ = max over i of [ R(i) − (i−1)/N ].
4. Compute D = max(D⁺, D⁻).
5. Find the critical value Dα from the K-S table for the chosen significance level α and sample size N.
6. If D > Dα, reject H0 (not uniform). If D ≤ Dα, no evidence to reject H0, so accept uniformity.

Example. Test the five numbers 0.44, 0.81, 0.14, 0.05, 0.93 with α = 0.05.

Ranked values and the differences:

D⁺ = 0.26, D⁻ = 0.21, so D = max(0.26, 0.21) = 0.26.

Critical value for N = 5, α = 0.05 is D0.05 = 0.565.

Since 0.26 < 0.565, H0 is not rejected. No difference between the sample and the uniform distribution has been detected, so the numbers can be used as uniform random numbers.