Class 12. Random Numbers• NRi C §7.• Frequently needed to generate initial conditions.• Often used to solve problems statistically.• How can a computer generate a random number?– It can’t! Generators are pseudo-random.– Generators are deterministic: it’s always possible t o produce the same sequenceover and over.– Sometimes this is a good thing!Random Number Generators• User specifies an initial value, or seed.• Initializing generator with same seed gives same sequence of “random” numbers.• For a different sequence, use a different seed.• One strategy is to use the current time, or the processor ID, to seed the generator.– Problem: this may have p oor dynamic range, or may be correlated with when thecode is run.– Solution: combine sources, e.g., int seed = (int) time(NULL) % getpid() +getppid(), to get a more robust seed.Choosing a Generator• Since generators do not produce truly random sequences, it’s possible that your resultsmay be affected by the generator used!• Often the supplied generators on a g iven machine have poor statistical properties.• But even a statistically sound generator can still be inadequate for a particular appli-cation.• Be wary if you ever need more than ∼ 106random numbers, and certainly if you needmore than the largest representable integer!• Solution: always compare results using two generators.1Guidelines• Follow these steps to minimize problems:1. Always remember to seed the g enerator before using it (discarding any returnedvalue).2. Use seeds that are “somewhat random,” i.e., have a good mixture of bits, e.g.,2731771 or 102 93085 instead o f 1 or 4096 or some other power of 2.3. Avoid sequential seeds: they may cause correlations.4. Compare results using at least two generators.5. When publishing, indicate g enerator used.6. Often it’s a good idea to make a note of the seed used for a given r un, in case youneed to regenerate the sequence again la ter.Uniform Deviates• Random numbers that lie within a specified range (typically 0 to 1), with any onenumber in the range as likely as any other, a r e uniform de viates, i.e.,p(x) dx =(dx if 0 ≤ x ≤ 1,0 otherwise.• Useful in themselves, often used to generate differently distributed deviates.• Distinguish between linear generators (discussed next) and nonlinear generators (do aweb search).Linear Congruential Generators• Typical of most system-supplied generators.• Produces series of integers I1, I2, I3, ..., each between 0 and m − 1, using:Ij+1= aIj+ c (mod m),where m is the modulus, and a and c are positive integers called the multiplier and theincrement, respectively.• If m, a, a nd c are properly chosen, all possible integers between 0 a nd m − 1 occur atsome point.– The choice of a = 75= 16807, c = 0, m = 231− 1 = 2147483647 is known as theminimal standard generator.– Often a and c chosen so as to have integer overflow on nearly every step, givingless predictable sequence and avoiding the mod operation.2• The LCG method is very fast but it suffers from sequential correlations.• If k random numbers at a time are used to plot points in k- dimensional space, pointstend to lie on (k − 1)-dimensional hyperplanes. There will be at most m1/kplanes,e.g., ∼ 1600 if k = 3 and m = 232!• The quality of a LCG is measured by the maximum distance between successive hy-perplanes: t he smaller the distance, the better.• Also, low-order bits may be less random than high-order bits, e.g., last bit alternatingbetween 0 and 1.– To generate random number between 1 a nd 10 with rand(), usej = 1 + (int) (10.0*rand()/(RAND MAX + 1.0));and notj = 1 + (rand() % 10);(which uses lower-order bits).NRiC RNGs• NRi C gives several uniform deviate generators:Generator Speed Notesran0 1.0 Small multiple, serial correlations.ran1 1.3 General purpose, maximum 108values.ran2 2.0 Like ran1, but lo nger period.ran3 0.6 Subtractive method, not well studied.ranqd1 0.1 Fast, machine-dependent.ranqd2 0.3 Ditto.ran4 4.0 Good properties, slow.• On the department machines, see rand(), random(), and drand48().• There is much discussion on the web of relative merits of RNGs. Recommended gen-erators include TT800 and the Mersenne Twister.• Bottom line: test it yourself, or use web-published testing routines, e.g., spectral meth-ods.Transformation Method• Suppose we want to g enerate a deviate from a distribution p(y) dy, where p(y) = f (y)for some positive and normalized function f, with y ranging from yminto ymax.• Let F (y) be the cumulative distribution of f (y), from yminto y, i.e., F (y) =Ryyminf(y0) dy0.3• Set a uniform deviate x = F (y)/ F (ymax) and solve for y: this is the new generationfunction.• Only useful if F−1(x) is easy to compute.Example: Exponential deviates• Suppose we want p(y) dy = e−ydy, y ∈ [0, ∞).• Apply the transformation method:– Have f (y) = e−y, F (y) = e−0− e−y= 1 − e−y.– Set x = F (y)/F (∞) and solve x(1 − e−∞) = 1 − e−yfor y.– Get y(x) = − ln(1 − x) = − ln(x) (since 1 − x is distributed the same as x).• So if x is a uniform deviate between 0 and 1, y(x) (x > 0) will be an expo nentialdeviate.• See NRiC §7.2 for Gaussian deviates.Another example: A simple IMF• Suppose we want to g enerate particle masses according to M dM = MαdM, M ∈[Mmin, Mmax].• From the transformation method we g et:M = Mmin(1 + x"MmaxMminα+1− 1#)1α+1,orM =h(1 − x)Mα+1min+ xMα+1maxi1α+1.• Notice that for a flat distribution (α = 0), get expected result.• What happens if α = −1? EFTS...Initial Conditions• Often want to generate random initial conditions for a simulation, e.g., initial positionand velocity.• Must take care when using transformations, since may not get distribution yo u expect.• For example, to fill a flat disk of radius R with random points is it better to:1. Choose random θ and r then set x = r cos θ, y = r sin θ?2. Fill a square and reject points with x2+ y2> R2?Answer: 2, but 1 will work if r2(instead of r) has a uniform random distribution.4Application: Cryptography• A simple encryption/decryption algorithm can be constructed using random numbergenerators.• If both part ies know the initial seed, they can both reproduce the same sequence o fvalues.• However, communicating the seed between parties carries risk.• One popular technique is to combine public and private keys for secure communication(the example below is