Random-Number
Generation
Discrete-Event System Simulation
Purpose & Overview
Discuss the generation of random numbers.
Introduce the subsequent testing for
randomness:
Frequency
test
Autocorrelation test.
Properties of Random Numbers
Two important statistical properties:
Uniformity
Independence.
Random Number, Ri, must be independently drawn from a
uniform distribution with pdf:
1, 0 x 1
f ( x)
0, otherwise
2
x
E ( R ) xdx
0
2
1
2
Figure: pdf for
random numbers
3
Generation of Pseudo-Random Numbers
Pseudo, because generating numbers using a known
method removes the potential for true randomness.
Goal: To produce a sequence of numbers in [0,1] that
simulates, or imitates, the ideal properties of random numbers
(RN).
Important considerations in RN routines:
Fast
Portable to different computers
Have sufficiently long cycle
Closely approximate the ideal statistical properties of uniformity
and independence.
Techniques for Generating Random #s
Linear Congruential Method (LCM).
Combined Linear Congruential Generators (CLCG).
Random-Number Streams.
Linear Congruential Method
To produce a sequence of integers, X1, X2, between 0
and m-1 by following a recursive relationship:
X i 1 (aX i c) mod m, i 0,1,2,...
The
multiplier
The
increment
The
modulus
The selection of the values for a, c, m, and X0 drastically
affects the statistical properties and the cycle length.
The random integers are being generated [0,m-1], and to
convert the integers to random numbers:
Ri
Xi
, i 1,2,...
m
6
Example 7.1
Use X0 = 27, a = 17, c = 43, and m = 100.
The Xi and Ri values are:
X1 = (17*27+43) mod 100 = 502 mod 100 = 2,
R1 = 0.02;
X2 = (17*2+43) mod 100 = 77,
R2 = 0.77;
X3 = (17*77+43) mod 100 = 52,
R3 = 0.52;
Example 7.2
Look at the Excel worksheet
Characteristics of a Good Generator
Maximum Density
Such that the values assumed by Ri, i = 1,2,, leave no large
gaps on [0,1]
Solution: a very large integer for modulus m
Maximum Period
To achieve maximum density and avoid cycling.
Achieve by: proper choice of a, c, m, and X0.
Three rules are given in the text on page 255
Uniformity
Independence
Apply tests
Apply tests
9
Tests for Random Numbers
Two categories:
Testing for uniformity:
H0: Ri ~ U[0,1]
H1: Ri ~/ U[0,1]
Failure to reject the null hypothesis, H0, means that evidence of
non-uniformity has not been detected.
Testing for independence:
H0: Ri ~ independently
H1: Ri ~/ independently
Failure to reject the null hypothesis, H0, means that evidence of
dependence has not been detected.
Level of significance the probability of rejecting H0 when it
is true:
= P(reject H0|H0 is true)
10
Tests
Test of uniformity
Kolmogorov-Smirnov test
Chi-square test
Test of independence :
Autocorrelation test
Runs Tests
Runs up and runs down test
Runs above and below the mean
Lenght of runs test
Gap test
Poker test
11
Kolmogorov-Smirnov Test
Compares the continuous cdf, F(x), of the uniform
distribution with the empirical cdf, SN(x), of the N sample
observations.
F ( x ) x, 0 x 1
We know:
If the sample from the RN generator is R1, R2, , RN, then the
empirical cdf, SN(x) is:
number of R , R ,..., R which are x
S N ( x)
Based on the statistic:
D = max| F(x) - SN(x)|
Sampling distribution of D is known (a function of N, tabulated in
Table A.8.)
12
Kolmogorov-Smirnov Test
Example: Suppose 5 generated numbers are 0.44, 0.81, 0.14,
0.05, 0.93.
Step 1:
Step 2:
R(i)
0.05
0.14
0.44
0.81
0.93
i/N
0.20
0.40
0.60
0.80
1.00
i/N R(i)
0.15
0.26
0.16
0.07
R(i) (i-1)/N
0.05
0.04
0.21
0.13
Arrange R(i) from
smallest to largest
D+ = max {i/N R(i)}
D- = max {R(i) - (i-1)/N}
Step 3: D = max(D+, D-) = 0.26
Step 4: For = 0.05,
D = 0.565 > D
Hence, H0 is not rejected.
13
Chi-square test
Chi-square test uses the sample statistic:
n is the # of classes
(Oi Ei )
Ei
i 1
n
2
0
Ei is the expected
# in the ith class
Oi is the observed
# in the ith class
Approximately the chi-square distribution with n-1 degrees of
freedom (where the critical values are tabulated in Table A.6)
For the uniform distribution, Ei, the expected number in the each
class is:
N
Ei
, where N is the total # of observation
Valid only for large samples, e.g. N >= 50
14
Example 7.7
100 random numbers have been generated as given on page 264
Test the generator for uniformity
Oi
interval
(Oi - Ei )2 / Ei
Ei
10
10
10
10
10
10
10
10
10
10
10
100
15
Tests for Autocorrelation
Testing the autocorrelation between every m numbers (m
is a.k.a. the lag), starting with the ith number
The autocorrelation im between numbers: Ri, Ri+m, Ri+2m, Ri+(M+1)m
M is the largest integer such that
Hypothesis:
i (M 1 )m N
H 0 : im 0,
if numbers are independent
H1 : im 0,
if numbers are dependent
If the values are uncorrelated:
For large values of M, the distribution of the estimator of im,
denoted
is approximately normal.
im
16
Tests for Autocorrelation
Test statistics is:
im
Z0
im
Z0 is distributed normally with mean = 0 and variance = 1, and:
1
im
M 1
im
R
k 0
i km
Ri (k 1 )m 0.25
13M 7
12(M 1 )
If im > 0, the subsequence has positive autocorrelation
High random numbers tend to be followed by high ones, and vice versa.
If im < 0, the subsequence has negative autocorrelation
Low random numbers tend to be followed by high ones, and vice versa.
17
Example 7.8
Data from Page 265: test for autocorrelation
0.12 0.01 0.23 0.28 0.89 0.31 0.64 0.28 0.83 0.93
0.99 0.15 0.33 0.35 0.91 0.41 0.60 0.27 0.75 0.88
0.68 0.49 0.05 0.43 0.95 0.58 0.19 0.36 0.69 0.87
18
Example 7.8
Test whether the 3rd, 8th, 13th, and so on, for the following
output on Page 265.
Hence, = 0.05, i = 3, m = 5, N = 30, and M = 4
35
1 (0.23)(0.28) (0.28)(0.33) (0.33)(0.27)
0.25
4 1 (0.28)(0.05) (0.05)(0.36)
0.1945
13(4) 7
0.128
12( 4 1 )
0.1945
Z0
1.516
0.1280
35
From Table A.3, z0.025 = 1.96. Hence, the hypothesis is not
rejected.
19
Summary
In this chapter, we described:
Generation of random numbers
Testing of generators for uniformity
Testing of generators for independence
Caution:
Even with generators that have been used for years, some of
which still in used, are found to be inadequate.
Also, even if generated numbers pass all the tests, some
underlying pattern might have gone undetected.
20
