CS61B Lecture #30Why Random Sequences?What Is a ``Random Sequence''?Pseudo-Random SequencesGenerating Pseudo-Random SequencesWhat Can Go Wrong?Other GeneratorsAdjusting Range and DistributionArbitrary BoundsOther DistributionsComputing Arbitrary Discrete DistributionJava ClassesShufflingRandom SelectionAlternative Selection Algorithm (Floyd)CS61B Lecture #30[NOTE: The Lecture #28 slides covered Lectures #28–29].Administrative: On-line survey available.Today:• Pseudo-random Numbers (Chapter 11)• What use are random sequences?• Whatare“random sequences”?• Pseudo-random sequences.• How to get one.• Relevant Java library classes and methods.• Random permutations.Coming Up: Concurrency and synchronization (Data Structures, Chap-ter 10, andProgramming Into Java, Chapter 9).Last modified: Mon Nov 15 16:29:13 2004 CS61B: Lecture #30 1Why Random Sequences?• Choose statistical samples• Simulations• Random algorithms• Cryptography:– Choosing random keys– Generating streams of random bits (e.g., SSL xor’s your data w i tha regen eratable, pseudo-random bit stream that only you and therecipient can generate).• And, of course, gamesLast modified: Mon Nov 15 16:29:13 2004 CS61B: Lecture #30 2What Is a “Random Sequence”?• How about: “a sequence where all numbers occur with equal fr e-quency”?– Like 1 , 2, 3, 4, . . . ?• Well the n, how about: “an unpredictable se quence wher e all numbersoccur with equal frequency?”– Like 0, 0, 0, 1, 1, 2, 2, 2, 2, 2, 3, 4, 4, 0, 1, 1, 1,. . . ?• Besides, what i s wrong with 0, 0, 0, 0, . . . anyway? Can’t that occurby random selection?Last modified: Mon Nov 15 16:29:13 2004 CS61B: Lecture #30 3Pseudo-Random Sequences• Even if definable, a “truly” random sequence is difficult for a com-puter (or human) to produce.• For most purposes, need only a sequence that sati sfies certain sta-tistical properties, even if deterministic.• Sometimes (e.g., cryptography) need sequence that ishardorim-practicalto predict.•Pseudo-random sequence:deterministic sequence that passes somegiven set of s ta ti stical tests.• For example, look at lengths ofruns:increasing or decreasing con-tiguous subsequences.• Unfortunately, statistical crite ria to be used are quite involved. Fordetails, see Knuth.Last modified: Mon Nov 15 16:29:13 2004 CS61B: Lecture #30 4Generating Pseudo-Random Sequences• Not as easy as you might thi nk.• Seemingly compl ex jumbling methods can give rise to bad sequences.•Linear congruential methodis a simple method that has withstoodtest of time:X0=arbitrary seedXi= (aXi−1+ c) mod m, i > 0• Usually, m i s large power of 2.• For best results, want a ≡ 5 mod 8, and a, c, m with no commonfactors.• This gives generator with aperiod ofm (length of se que nce beforerepetition), and reasonablepotency(measures certain depe ndenciesamong adjacent Xi.)• Also want bits of a to “ha ve no obvious pattern” and pass certainother tests (see Knuth).• Java uses a = 25214903917, c = 11, m = 248, to comp ute 48-bitpseudo-random numbers but I haven’t checked to see how good thisis.Last modified: Mon Nov 15 16:29:13 2004 CS61B: Lecture #30 5What Can Go Wrong?• Short periods, many impossible values: E.g., a, c, m even.• Obvious patterns. E.g., just using lower 3 bits of Xiin Java’s 48-bitgenerator, to get integer s in range 0 to 7. By properties of modulararithmetic,Ximod 8 = (25214903917Xi−1+ 11 mod 248) mod 8= (5(Xi−1mod 8) + 3) mo d 8so we have a period of 8 on this gen erator; sequences like0, 1, 3, 7, 1, 2, 7, 1, 4, . . .are impossible. This is why Java doesn’t give you the raw 48 bits.• Bad potency leads to bad corr elations.– E.g . Take c = 0, a = 65539, m = 231, and make 3D points:(Xi/S, Xi+1/S, Xi+2/S), where S scale s to a unit cube.– Points will be arranged in p a rallel planes with voids between.– So, “random points” won’t ever get near ma ny points in the cube.Last modified: Mon Nov 15 16:29:13 2004 CS61B: Lecture #30 6Other Generators• Additive generator:Xn=arbitary value, n < 55(Xn−24+ Xn−55) mod 2e, n ≥ 55• Other choices than 24 an d 55 poss i ble.• This one has period of 2f(255− 1), for some f < e.• Simple implementation wi th circular buffer:i = (i+1) % 55;X[i] += X[(i+31) % 55]; // Why +31 (55-24) instead of -24?return X[i]; /* modulo 232*/• where X[0 .. 54] is initialized to some “random” initial seed val-ues.Last modified: Mon Nov 15 16:29:13 2004 CS61B: Lecture #30 7Adjusting Range and Distribution• Given raw sequence of numbers , Xi, from above methods in range(e.g.) 0 to 248, how to get uniform random integers in range 0 ton − 1?• If n = 2k, is easy: use top k bits of next Xi(bottom k bits not as“random”)• For other n, be ca reful of slight biases at the ends. For example, ifwe compute Xi/(248/n) using all integer division, and if (248/n) doesn’tcome out even, then you can get n as a result (wh i ch you don’t want).• Easy enough to fix with floating point, but can also do with integers;one method (used by Java for type int):/** Random integer in the range 0 .. n-1, n > 0 . */int nextInt (int n) {long X =next random long (0 ≤ X < 248);if (nis2kfor somek) returntopkbits ofX;int MAX =largest multiple of n that is< 248;while (Xi>= MAX) X =next random long (0 ≤ X < 248);return Xi/ (MAX/n);}Last modified: Mon Nov 15 16:29:13 2004 CS61B: Lecture #30 8Arbitrary Bounds• How to get arbitrary range of i ntegers (L to U )?• To get random float, x in range 0 ≤ x < d, computereturn d*nextInt (1<<24) / (1<<24);• Random double a bit more complicated: need two integers to getenough bits.long bigRand = ((long) nextInt(1<<26) << 27) + (long) nextInt(1<<27);return d * bigRand / (1L << 53);Last modified: Mon Nov 15 16:29:13 2004 CS61B: Lecture #30 9Other Distributions• Can also turn uniform random integ ers into arbitrary other distri-butions, like the Gaussian.0-2 -1 1 21yxP (x)• Curve is the desired probability distr i buti on (P (x) i s the probabilitythat a certain random var i able is ≤ x.)• Choose y uniformly between 0 and 1, and the corresponding x will bedistributed according to P .Last modified: Mon Nov 15 16:29:13 2004 CS61B: Lecture #30 10Computing Arbitrary Discrete Distribution• Example from book: wa nt integer values Xiwith Pr(Xi= 0) = 1/12,Pr(Xi= 1) = 1/2, Pr(Xi= 2) = 1/3, Pr(Xi= 3) = 1/12:0 1 2 3Legend:0:1:2:3:0 1 2 3 4• To get desired proba bi l ities,
View Full Document
Unlocking...