Lehmer Random Number Generators: IntroductionDiscrete-Event Simulation:A First CourseSection 2.1: Lehmer Random Number Generators: IntroductionSection 2.1: Lehmer Random Number Generators: Introduction Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Lehmer Random Number Generators: IntroductionSection 2.1: Lehmer Random Number Generators:Introductionssq1 and sis1 require input data from an outside sourceThe usefulness of these programs is limited by amount ofavailable dataWhat if more data needed?What if the model changed?What if the input data set is small or unavailable?A random number generator address all problemsIt produces real values between 0.0 and 1.0The output can be converted to random variate viamathematical transformationsSection 2.1: Lehmer Random Number Generators: Introduction Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Lehmer Random Number Generators: IntroductionRandom Number GeneratorsHistorically there are three types of generatorstable look-up generatorshardware generatorsalgorithmic (software) generatorsAlgorithmic generators are widely accepted because they meetall of the following criteria:randomness - output passes all reasonable statistical tests ofrandomnesscontrollability - able to reproduce output, if desiredportability - able to produce the same output on a wide varietyof computer systemsefficiency - fast, minimal computer resource requirementsdocumentation - theoretically analyzed and extensively testedSection 2.1: Lehmer Random Number Generators: Introduction Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Lehmer Random Number Generators: IntroductionAlgorithmic GeneratorsAn ideal random number generator produces output such thateach value in the interval 0.0 < u < 1.0 is equally likely tooccurA good random number generator produces output that is(almost) statistically indistinguishable from and idealgeneratorWe will construct a good random number generator satisfyingall our criteriaSection 2.1: Lehmer Random Number Generators: Introduction Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Lehmer Random Number Generators: IntroductionConceptual ModelConceptual Model:Choose a large positive integer m. This defines the setXm= {1, 2, . . . , m − 1}Fill a (conceptual) urn with the elements of XmEach time a random number u is needed, draw an integer x“at random” from the urn and let u = x/mEach draw simulates a sample of an independent identicallydistributed sequence of Uniform(0, 1)The possible values are 1/m, 2/m, . . . (m − 1)/m.It is important that m be large so that the possible values aredensely distributed between 0.0 and 1.0Section 2.1: Lehmer Random Number Generators: Introduction Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Lehmer Random Number Generators: IntroductionConceptual Model0.0 and 1.0 are impossibleThis is important for some random variatesWe would like to draw from the urn with replacementFor practical reasons, we will draw without replacementIf m is large and the number of draws is small relative to m,then the distinction is largely irrelevantSection 2.1: Lehmer Random Number Generators: Introduction Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Lehmer Random Number Generators: IntroductionLehmer’s AlgorithmLehmer’s algorithm for random number generation is definedin terms of two fixed parameters:modulus m, a fixed large prime integermultiplier a, a fixed integer in XmThe integer sequence x0, x1, . . . is defined by the iterativeequationxi+1= g (xi)withg(x) = ax mod mx0∈ Xmis called the initial seedSection 2.1: Lehmer Random Number Generators: Introduction Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Lehmer Random Number Generators: IntroductionLehmer GeneratorsBecause of the mod operator, 0 ≤ g(x) < mHowever, 0 must not occur since g(0) = 0Since m is prime, g(x) 6= 0 if x ∈ Xm.If x0∈ Xm, then xi∈ Xmfor all i ≥ 0.If the multiplier and prime modulus are chosen properly, aLehmer generator is statistically indistinguishable fromdrawing from Xmwith replacement.Note, there is nothing random about a Lehmer generatorFor this reason, it is called a pseudo-random generatorSection 2.1: Lehmer Random Number Generators: Introduction Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Lehmer Random Number Generators: IntroductionIntuitive Explanation0 m 2m 3m 4m 5mx a ax• • •←− −→| |g(x)←−−−−−−−−−−−−−−−−−−−− −−−−−−−−−−−−−−−−−−−−→|⌊ax/m⌋ m←−−−−−−−−−−−−−−−−−−−−−−−ax−−−−−−−−−−−−−−−−−−−−−−−→| |When ax is divided by m, the remainder is “likely” to be anyvalue between 0 and m − 1Similar to buying numerous identical items at a grocery storewith only dollar bills.a is the price of an item, x is the number of items, andm = 100.The change is likely to be any value between 0 and 99 centsSection 2.1: Lehmer Random Number Generators: Introduction Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Lehmer Random Number Generators: IntroductionParameter ConsiderationsThe choic e of m is dictated, in part, by system considerationsOn a system with 32-bit 2’s complement integer arithmetic,231− 1 is a natural choiceWith 16-bit or 64-bit integer representation, the choice is notobviousIn general, we want to choose m to be the largestrepresentable prime integerGiven m, the choice of a must be made with great careSection 2.1: Lehmer Random Number Generators: Introduction Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Lehmer Random Number Generators: IntroductionExample 2.1.1If m = 13 and a = 6 with x0= 1 then the sequence is1, 6, 10, 8, 9, 2, 12, 7, 3, 5, 4, 11, 1, . . .The ellipses indicate the sequence is periodicIf m = 13 and a = 7 with x0= 1 then the sequence is1, 7, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2, 1 . . .Because of the 12, 6, 3 and 8, 4, 2, 1 patterns, this sequenceappears “less random”If m = 13 and a = 5 then1, 5, 12, 8, 1, . . . or 2, 10, 11, 3, 2, . . . or 4, 7, 9, 6, 4, . . .This less-than-full-period behavior is obviously undesirableSection 2.1: Lehmer Random Number Generators: Introduction Discrete-Event Simulationc2006 Pearson Ed., Inc. 0-13-142917-5Lehmer Random Number Generators: IntroductionCentral IssuesFor a chosen (a, m) pair, does the