Random Number Generation - Rice University

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

x n = f (x n"1, x n"2 ,...)

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

? !Example:

x n = (5x n"1 + 1) mod 16

¡ªFor x0= 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

cycle length

tail

period

5

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

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

Google Online Preview   Download