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:
 |
Figure: pdf for
random numbers |
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
Replicable
Closely approximate the ideal statistical properties of uniformity
and independence.
Techniques for Generating Random
Numbers
Linear Congruential Method ( LCM ).
Combined Linear Congruential Generators (CLCG).
Linear Congruential Method
[Techniques]
To produce a sequence of integers, X1, X2, … between 0
and m-1 by fol lowing a recursive relationship:
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:
Example
[LCM]
Use X0 = 27, a = 17, c = 43, and m = 100.
The Xi and Ri values are:
Characteristics of a Good Generator
[LCM]
Maximum Density
Such that he values as sumed by R i, i = 1,2,…, leave no large
gaps on [0,1]
Problem: Instead of continuous, each Ri is discrete
Solution : a very large integer for modulus m
Approximation appears to be of little consequence
Maximum Period
To achieve maximum density and avoid cycling.
Achieve by: proper choice of a, c, m, and X0.
Most digital computers use a binary re presentation of
numbers
Speed and efficiency are aided by a modulus, m, to be (or close
to) a power of 2.
Combined Linear Congruential Generators
[Techniques]
Reason: Longer period generator is needed because of the
increasing complexity of stimulated systems .
Approach: Combine two or more multiplicative congruential
generators.
Let 
, be the ith output from k different
multiplicative congruential generators.
The jth generator:
Has prime modulus
and multiplier
and period is
Produces integers
is approx ~ Uniform on integers in [1,
m-1]
is approx ~ Uniform on integers in
Combined Linear Congruential Generators
Theorem: If
are any independent discretevalued
random variable , and
is uniformly
distributed on
then
is uniformly distributed on
Combined Linear Congruential Generators
[Techniques]
Suggested form:
The maximum possible period is:
Example: For 32-bit computers, L’Ecuyer [1988] suggests
combining
k = 2 generators with
2,147,483,399 and
. The algorithm becomes:
Step 1: Select seeds
X1,0 in the range [1, 2,147,483,562] for the 1st generator
X2,0 in the range [1, 2,147,483,398] for the 2nd generator.
Step 2: For each individual generator,
mod 2,147,483,563
mod 2,147,483,399.
Step 3:
mod 2,147,483,562.
Step 4: Return
Step 5: Set j = j+1, go back to step 2.
Combined generator has period:
