Generating Uniform Random Numbers
[Pages:38]Generating Uniform Random Numbers
Christos Alexopoulos and Dave Goldsman
Georgia Institute of Technology, Atlanta, GA, USA
June 7, 2009
Alexopoulos and Goldsman
June 7, 2009 1 / 38
Outline
1 Introduction 2 Some Generators We Won't Use 3 Linear Congruential Generators 4 Tausworthe Generator 5 Generalizations of LCGs 6 Choosing a Good Generator -- Some Theory 7 Choosing a Good Generator -- Statistical Tests
2 Goodness-of-Fit Test Runs Tests for Independence
Alexopoulos and Goldsman
June 7, 2009 2 / 38
Introduction
Introduction
Uniform(0,1) random numbers are the key to random variate generation in simulation.
Goal: Give an algorithm that produces a sequence of pseudo-random numbers (PRN's) R1, R2, . . . that "appear" to be iid Unif(0,1).
Desired properties of algorithm output appears to be iid Unif(0,1) very fast ability to reproduce any sequence it generates
References: Banks, Carson, Nelson, and Nicol (2005); Bratley, Fox, and Schrage (1987); Knuth (2) (1981); Law (2007).
Alexopoulos and Goldsman
June 7, 2009 3 / 38
Introduction
Classes of Unif(0,1) Generators
output of random device table of random numbers midsquare (not very useful) Fibonacci (not very useful) linear congruential (most commonly used in practice) Tausworthe (linear recursion mod 2) hybrid
Alexopoulos and Goldsman
June 7, 2009 4 / 38
Outline
Some Generators We Won't Use
1 Introduction 2 Some Generators We Won't Use
3 Linear Congruential Generators
4 Tausworthe Generator
5 Generalizations of LCGs
6 Choosing a Good Generator -- Some Theory
7 Choosing a Good Generator -- Statistical Tests 2 Goodness-of-Fit Test Runs Tests for Independence
Alexopoulos and Goldsman
June 7, 2009 5 / 38
Some Generators We Won't Use
Some Generators We Won't Use
a. Random Devices
Nice randomness properties. However, Unif(0,1) sequence storage difficult, so it's tough to repeat experiment.
Examples:
flip a coin particle count by Geiger counter least significant digits of atomic clock
b. Random Number Tables
List of digits supplied in tables. Cumbersome and slow -- not very useful. Once tabled no longer random.
Alexopoulos and Goldsman
June 7, 2009 6 / 38
Some Generators We Won't Use
c. Mid-Square Method (J. von Neumann)
Idea: Take the middle part of the square of the previous random number. John von Neumann was a brilliant and fun-loving guy, but method is lousy!
Example: Take Ri = Xi/10000, i, where the Xi's are positive integers < 10000.
Set seed X0 = 6632; then 66322 43983424; So X1 = 9834; then 98342 96707556; So X2 = 7075, etc,...
Unfortunately, positive serial correlation in Ri's.
Also, occasionally degenerates; e.g., consider Xi = 0003.
Alexopoulos and Goldsman
June 7, 2009 7 / 38
Some Generators We Won't Use
d. Fibonacci and Additive Congruential Generators
These methods are also no good!!
Take
Xi = (Xi-1 + Xi-2)mod m, i = 1, 2, . . . ,
where Ri = Xi/m, m is the modulus, X0, X1 are seeds, and a = b mod m iff a is the remainder of b/m, e.g., 6 = 13 mod 7.
Problem: Small numbers follow small numbers.
Also, it's not possible to get Xi-1 < Xi+1 < Xi or Xi < Xi+1 < Xi-1 (which should occur w.p. 1/3).
Alexopoulos and Goldsman
June 7, 2009 8 / 38
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- 1 5 equations find the solution set of each equation if
- free discord nitro codes 2021 get free discord nitro
- linear codes mathematical and statistical sciences
- owner s manual m750138b 1 item number serial number
- d c generators
- cyclic groups christian brothers university
- free discord nitro codes generator gp8 ¢ discordnitrofree
- aston academy gcse physics home
- generating uniform random numbers
- section i 6 cyclic groups
Related searches
- best monthly income generating investments
- income generating investments for retirees
- best income generating funds
- best income generating investments
- continuous uniform random variable calculator
- random number generator excel uniform distribution
- put random numbers in order
- excel random unique numbers within range
- how to generate random numbers in excel
- generate random unique numbers in excel
- 6 random numbers 1 25
- put these numbers in random order