CSE 411

Simulation & Modeling

Chapter 7: Random-Number Generators

 “Random” Definitions
 Random Variable
 A random variable or stochastic variable is a variable whose value is subject to variations
due to chance
 In probability theory, a random variable is a measurable function from a probability
space to a measurable space of values that the variable can take on.
 Random Variate
 A random variate is a particular outcome of a random variable: the random variates
which are other outcomes of the same random variable would have different values.
 Random Numbers
 Random variates generated from the U(0,1) distribution is called random numbers

Dept of CSE, BUET 2

 Random Number Generators
 Lots of Physical and Machine oriented generator
 First Arithmetic Approach – Midsquare Method

 The generators are not truly random in nature (in the sense of being
unpredictable)
 That’s why they are called pseudorandom
Dept of CSE, BUET 3
 Properties of a Good Arithmetic Random Number
Generator
 Uniform and not correlated
 Fast and memory-efficient
 Reproducibility
 Separate stream producing capability
 Portable

Dept of CSE, BUET 4

 Linear Congruential Generators
• Use a recursive formula to generate ith random integer number

is the initial value called seed or starting value.

 are non-negative and should follow the following property

Dept of CSE, BUET 5

 Objections
• Not purely random (pseudo-random)
• can be obtained directly from by using the following formula

 Only a fraction of rational values can be determined

Dept of CSE, BUET 6

 LCG - Looping Behavior
 Consider the example

 The length of the cycle is called the period of a generator

 If the period is m, then it is called full period

Dept of CSE, BUET 7

 LCG - Conditions for full period
• Having full period is a desirable property
 The LCG has full period if and only if the following three conditions hold:
 The only positive integer that (exactly) divides both and is 1
 If is a prime number that divides , the divides
 If 4 divides , then 4 divides

Dept of CSE, BUET 8

 Different LCGs
• Mixed Generators
 If
 Multiplicative Generators
 If

Classification is based on

Dept of CSE, BUET 9

 LCG –Mixed Generators
• Possible to have a full period
 Large m is expected to generate a large period and high density of ’s
 Computers of early days were slow in division, so can be useful
 If b=31, then what can be inferred about the values of and
 should be odd
 should be divisible by 4.

The only positive integer that (exactly) divides both and is 1

If is a prime number that divides , the divides
If 4 divides , then 4 divides

Dept of CSE, BUET 10

 LCG –Multiplicative Generators
•
 For multiplicative generator c=0

 Which can be the highest possible value for multiplicative generator?

 Consider the computers of the early days and so

 Highest possible period:
 Very small in quantity
 May induce large gap
 RANDU uses , ,
 Not good at all! Provides poor statistical properties

Dept of CSE, BUET 11

 LCG –Multiplicative Generators
• is not good in multiplicative generators
 Searching for alternative
 Searching … Searching … Searching…
 Found an alternative ! Thanks to Hutchinson 

 Period of can be found if

 m is prime (select the largest prime number that is less than )
 is a primitive element modulo
 The smallest integer for which is divisible by is

 These are called Prime Modulus Multiplicative LCGs (PMMLCGs)

Dept of CSE, BUET 12

 PMMLCGs
 Bottlenecks
 How to find out the primitive element modulo m?
 Benefit of using integer overflow for division purpose diminishes!

Dept of CSE, BUET 13

 Other Kinds of Generators
• More General Congruences
 General equation considered for Congruences

 Different kinds of generators obtained using this equation

 Quadratic Congruential Generator
 Multiple Recursive Generators (MRGs)

Dept of CSE, BUET 14

 Quadratic Congruential Generator
• Using in

 Length of period?

Dept of CSE, BUET 15

 Multiple Recursive Generators (MRGs)
• Using in

 Length of period?

Dept of CSE, BUET 16

 Dynamically changing � and �
• Proposed by Haas (1987)
 Change the value of and before generating each
 Provides a huge period!

Dept of CSE, BUET 17

 Composite Generators
 Combining two or more separate generators
 Advantages
 Longer Period
 Better Statistical Behavior
 Disadvantage
 High Cost

Dept of CSE, BUET 18

Composite Generators : Shuffling method
• Two LCGs are required
 First one is used to generate a value between 0 and 1
 Second one is used to generate an integer between 1 and k
 A vector of size k ’s is maintained (Study the reference book for details)

Dept of CSE, BUET 19

 Composite Generators : Using Generators of Different
Moduli
• Generate integers and through generators using different moduli
 Generate using the following formula

 Very long period and good statistical properties

 Very fast

 k number of generators can be used instead to two

Dept of CSE, BUET 20

 Feedback Shift Register Generators
• Also known as Tausworthe Generators
 Operate on bits to form random numbers

Where but other constants may or may not be

 Generally two of the constants are taken as non-zero

 This is equation is equivalent to ?

 Exclusive OR operation

 What is the maximum possible period of the generalized equation?

Dept of CSE, BUET 21
 Feedback Shift Register Generators
• To get integers, we take l consecutive ’s

And

Dept of CSE, BUET 22

 Feedback Shift Register Generators
 These generators can easily be implemented on a binary computer using a
switching circuit called a linear feedback shift register (LFSR)

 LFSR has some statistical dificiencies

 L’Ecuyer considered combined LFSR generators
 Lewis and Payne introduced Generalized Feedback Shift Register (GFSR)
 Matsumoto and Kurita introduced the idea of twisted GFSR (TGTSR)
Dept of CSE, BUET 23
 Testing Random-Number Generators
 Empirical Tests
 Theoretical Tests

Dept of CSE, BUET 24

 Empirical Tests
 Four empirical tests
 Chi-square test (with all parameters known)
 Serial test
 Runs (or runs-up) test
 Direct assessment

Dept of CSE, BUET 25

 Chi-square test
• Divide [0,1] into k subintervals of equal length and generate
 Let be the number of ’s that are in the jth interval and let

 Then for large n, will have an approximate chi-square distribution with k-1 df
under the null hypothesis that’s are IID(0,1) random variables
 For a significance level reject the hypothesis if where is the upper critical point
of the chi-square distribution with k-1 df
 For large values of k, the following approximation can be used

 where is the upper critical point of the N(0,1) distribution

Dept of CSE, BUET 26

 Serial test
• Generalization of chi-square test to higher dimensions
 If ’s are really IID(0,1) random variates, then the non-overlapping d-tuples should
also be random vectors distributed uniformly on the d-dimensional unit
hypercube,
,
 Divide [0,1] into k subintervals of equal length and generate
 Let be the number of ’s having first component in subinterval , second component
in subinterval , etc.
 If we let,

 Then for large n, will have an approximate chi-square distribution with -1 df .

Dept of CSE, BUET 27
 Serial test
• Why may serial test be important?
 If the individual ’s are correlated, the distribution of the d-vectors will deviate
from d-dimensional uniformity

Dept of CSE, BUET 28

 Runs test
• Also known as Runs-up test
 It is a test of independence only, not for uniformity checking
 Check the ’s and determine lengths of monotonically increasing subsequences
 For example, 0.86, 0.11, 0.23, 0.03, 0.13, 0.06, 0.55, 0.64, 0.87, 0.10

 For large n, R will have an approximate chi-square distribution with 6df.

Dept of CSE, BUET 29
Runs test

Dept of CSE, BUET 30

 Direct Assessment
• Determining correlation among the data points

 Our expectation is
 For ideal case,
and

 Now the estimate of is

Dept of CSE, BUET 31

 Direct Assessment
• Determining the estimated correlations

 Determining estimated variance

 Calculating test statistic

 If , then reject the hypothesis that

Dept of CSE, BUET 32
 Theoretical Tests
 Theoretical tests are global whereas empirical tests are local
 First and simple approach: If possible compute the sample mean, variance and
correlations over an entire cycle from the constants defining the generator
 Not possible always
 Sometimes can be misleading
 Second approach is well-known which is based on the observation of Marsaglia
 “Random number fall mainly in the planes”

Dept of CSE, BUET 33

Theoretical Tests

Dept of CSE, BUET 34

Theoretical Tests

Dept of CSE, BUET 35

 Spectral Test
• Let = Distance of the farthest adjacent hyperplanes of a generator using m and a
 =Theoretical lower bound on [applicable for LCGs]
for all a
Where is a constant whose exact value is known only for
 Figures of merit for a LCG:

And

 The less the value of , the better the generator is

Dept of CSE, BUET 36

 Reference
Simulation Modeling and Analysis by Averill M Law (Fourth Edition)

Chapter 7 (7.1 - 7.4)

Dept of CSE, BUET 37