Random Number Generation

Random Number Generation

Dr. John Mellor-Crummey

Department of Computer Science Rice University

johnmc@cs.rice.edu

COMP 528 Lecture 21 5 April 2005

Topics for Today

Understand

? Motivation ? Desired properties of a good generator ? Linear congruential generators

--multiplicative and mixed

? Tausworthe generators ? Combined generators ? Seed selection ? Myths about random number generation ? What's used today: MATLAB, R, Linux

2

Why Random Number Generation?

? Simulation must generate random values for variables in a

specified random distribution

--examples: normal, exponential, ...

? How? Two steps

--random number generation: generate a sequence of uniform FP random numbers in [0,1]

--random variate generation: transform a uniform random sequence to produce a sequence with the desired distribution

3

How Random Number Generators Work

? Most commonly use recurrence relation

xn = f (xn"1, xn"2,...)

recurrence is a function of last 1 (or a few numbers), e.g.

?

xn = (5xn"1 + 1) mod 16 !E--xaFmorpxl0e=: 5, first 32 numbers are 10, 3, 0,

1,

6, 15,

12, 13,

2, 11,

8,

9,

14, 7, 4, 5, 10, 3, 0, 1, 6, 15, 12, 13, 2, 11, 8, 9, 14, 7, 4, 5

!--x's are integers in [0,16]

--dividing by 16, get random numbers in interval [0,1]

? Properties of pseudo-random number sequences

--from seed value, can determine entire sequence

--they pass statistical tests for randomness

--reproducibility (often desirable)

4

Random Number Sequences

? Some generators do not repeat the initial part of a sequence

tail

cycle length

period

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download