IntroductionSome Generators We Won't UseLinear Congruential GeneratorsTausworthe GeneratorGeneralizations of LCGsChoosing a Good Generator --- Some TheoryChoosing a Good Generator --- Statistical Tests2 Goodness-of-Fit TestRuns Tests for IndependenceGenerating Uniform Random NumbersChristos Alexopoulos and Dave GoldsmanGeorgia Institute of Technology, Atlanta, GA, USAJune 7, 2009Alexopoulos and Goldsman June 7, 2009 1 / 38Outline1Introduction2Some Generators We Won’t Use3Linear Congruential Generators4Tausworthe Generator5Generalizations of LCGs6Choosing a Good Generator — Some Theory7Choosing a Good Generator — Statistical Testsχ2Goodness-of-Fit TestRuns Tests for IndependenceAlexopoulos and Goldsman June 7, 2009 2 / 38IntroductionIntroductionUniform(0,1) random numbers are the key to random variategeneration in simulation.Goal: Give an algorithm that produces a sequence of pseudo-randomnumbers (PRN’s) R1, R2, . . . that “appear” to be iid Unif(0,1).Desired properties of algorithmoutput appears to be iid Unif(0,1)very fastability to reproduce any sequence it generatesReferences: Banks, Carson, Nelson, and Nicol (2005); Bratley, Fox,and Schrage (1987); Knuth (2) (1981); Law (2007).Alexopoulos and Goldsman June 7, 2009 3 / 38IntroductionClasses of Unif(0,1) Generatorsoutput of random devicetable of random numbersmidsquare (not very useful)Fibonacci (not very useful)linear congruential (most commonly used in practice)Tausworthe (linear recursion mod 2)hybridAlexopoulos and Goldsman June 7, 2009 4 / 38Some Generators We Won’t UseOutline1Introduction2Some Generators We Won’t Use3Linear Congruential Generators4Tausworthe Generator5Generalizations of LCGs6Choosing a Good Generator — Some Theory7Choosing a Good Generator — Statistical Testsχ2Goodness-of-Fit TestRuns Tests for IndependenceAlexopoulos and Goldsman June 7, 2009 5 / 38Some Generators We Won’t UseSome Generators We Won’t Usea. Random DevicesNice randomness properties. However, Unif(0,1) sequence storagedifficult, so it’s tough to repeat experiment.Examples:flip a coinparticle count by Geiger counterleast significant digits of atomic clockb. Random Number TablesList of digits supplied in tables.Cumbersome and slow — not very useful.Once tabled no longer random.Alexopoulos and Goldsman June 7, 2009 6 / 38Some Generators We Won’t Usec. Mid-Square Method (J. von Neumann)Idea: Take the middle part of the square of the previous randomnumber. John von Neumann was a brilliant and fun-loving guy, butmethod 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 / 38Some Generators We Won’t Used. Fibonacci and Additive Congruential GeneratorsThese methods are also no good!!TakeXi= (Xi−1+ Xi−2)mod m, i = 1, 2, . . . ,where Ri= Xi/m, m is the modulus, X0, X1are seeds, anda = 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< Xior Xi< Xi+1< Xi−1(which should occur w.p. 1/3).Alexopoulos and Goldsman June 7, 2009 8 / 38Linear Congruential GeneratorsOutline1Introduction2Some Generators We Won’t Use3Linear Congruential Generators4Tausworthe Generator5Generalizations of LCGs6Choosing a Good Generator — Some Theory7Choosing a Good Generator — Statistical Testsχ2Goodness-of-Fit TestRuns Tests for IndependenceAlexopoulos and Goldsman June 7, 2009 9 / 38Linear Congruential GeneratorsLinear Congruential GeneratorsLCG’s are the most widely used generators. These are pretty goodwhen implemented properly.Xi= (aXi−1+ c) mod m, where X0is the seed.Ri= Xi/m, i = 1, 2, . . .Choose a, c, m carefully to get good statistical quality and long periodor cycle length, i.e., time until LCG starts to repeat itself.If c = 0, LCG is called a multiplicative generator.Alexopoulos and Goldsman June 7, 2009 10 / 38Linear Congruential GeneratorsTrivial Example: For purposes of illustration, consider the LCGXi= (5Xi−1+ 3) mod 8If X0= 0, we have X1= (5X0+ 3) mod 8 = 3; continuing,i 0 1 2 3 4 5 6 7 8 9Xi0 3 2 5 4 7 6 1 0 3Ri038285848786818038so that the sequence starts repeating with X8= 0.This is a full-period generator, since it has cycle length m = 8.Generally speaking, full-period is a good thing. 2Alexopoulos and Goldsman June 7, 2009 11 / 38Linear Congruential GeneratorsBetter Example: Here’s a portable FORTRAN implementation(Bratley, Fox, and Schrage 1987) that we’ve seen before. It works fine,is fast, and is full-period with cycle length > 2 billion,Xi= 16807 Xi−1mod (231− 1).Input: IX is an integer seed between 1 and 231− 1.FUNCTION UNIF(IX)K1 = IX/127773 (integer division leaves no remainder)IX = 16807*(IX - K1*127773) - K1*2836IF (IX.LT.0) IX = IX + 2147483647UNIF = IX*4.656612875E-10RETURNENDOutput: UNIF is real-valued in (0,1). 2Stay tuned for various ways to assess the quality of PRN generators.Alexopoulos and Goldsman June 7, 2009 12 / 38Linear Congruential GeneratorsSo what can go wrong with LCG’s?a. Something like Xi= (4Xi−1+ 2) mod 8 is not full-period, since itonly produces even integers.b. Something like Xi= (Xi−1+ 1) mod 8 is full-period, but itproduces very non-random output: X1= 1, X2= 2, X3= 3, etc.c. In any case, if m is small, you’ll get quick cycling whether or notthe generator is full period. “Small” could mean anything less than2 billion or so!d. And just because m is big, you still have to be careful. In additionto a. and b. above, some subtle problems can arise. Take a look atRANDU. . . .Alexopoulos and Goldsman June 7, 2009 13 / 38Linear Congruential GeneratorsExample: The infamous RANDU generator,Xi= 65539 Xi−1mod 231,was popular during the 1960’s.Here’s what (Ri−2, Ri−1, Ri) look like if you plot them in 3-D (stolenfrom Wikipedia). If they were truly iid Unif(0,1), you’d see dotsrandomly dispersed in the unit cube. But instead, the random numbersfall entirely on 15 hyperplanes (not good).Alexopoulos and Goldsman June 7, 2009 14 / 38Tausworthe GeneratorOutline1Introduction2Some Generators We Won’t Use3Linear Congruential Generators4Tausworthe Generator5Generalizations of LCGs6Choosing a Good Generator — Some Theory7Choosing a Good Generator — Statistical