Uniform random number generators: a review <s> LATTICES, EQUIDISTRIBUTION, AND DISCREPANCY <s> The Wolff algorithm is now accepted as the best cluster-flipping Monte Carlo algorithm for beating «critical slowing down.» We show how this method can yield incorrect answers due to subtle correlations in «high quality» random number generators <s> BIB001 </s> Uniform random number generators: a review <s> LATTICES, EQUIDISTRIBUTION, AND DISCREPANCY <s> Preface 1. Monte Carlo methods and Quasi-Monte Carlo methods 2. Quasi-Monte Carlo methods for numerical integration 3. Low-discrepancy point sets and sequences 4. Nets and (t,s)-sequences 5. Lattice rules for numerical integration 6. Quasi- Monte Carlo methods for optimization 7. Random numbers and pseudorandom numbers 8. Nonlinear congruential pseudorandom numbers 9. Shift-Register pseudorandom numbers 10. Pseudorandom vector generation Appendix A. Finite fields and linear recurring sequences Appendix B. Continued fractions Bibliography Index. <s> BIB002
The set Z = {fh = (u,, . . . , u,+t.-I) I n 2 0, (x0,..., Xk-l)EqrJ of all t-tuples of successive values produced by (l-2), from all possible initial states, is the intersection of a lattice Lt with the unit hypercube [0, l)t. This means that the points of 2-t lie in a limited number of equidistant parallel hyperplanes  . For the points to be evenly distributed over the entire period, the distance dt between those successive hyperplanes should be small. One can define the figure of merit t* MT=$nn -t for any positive integer T, where d: = ytmSklt is an absolute lower bound on the smallest possible dt, and -yt is the so-called Hermite constant. The constant 7t is known exactly only for t 5 8 but approximations of it are available for t > 8 (L'Ecuyer 1997d). An MT close to 1 means a superuniform distribution over the full period. L'Ecuyer (1997d) has computed tables of LCGs with good figures of merit MS, MIS, and M32, for m equal to the largest prime less than 2') for several values of e from 8 to 64. L'Ecuyer (1997b) provides combined MRGs which are good with respect to these figures of merit, together with computer implementations in C. Computing dt , called the spectral test, amounts to solving a quadratic optimization problem with integer variables. The programs of L'Ecuyer and  compute dt up to around 40 or more, and can handle large moduli m. Couture and L'Ecuyer (1996) explain how to analyze the (shifted) lattice associated with the set of recurrent states (only), for a given initial state, when that set generates a strict sublattice of Lt. One may want to consider vectors of nonsuccessive values produced by the generator: fix a set of non-negative integers I = { il, is, . . . , it}, put Z(I) = {(uil+n,. . ., ~i~+~) I n 2 0, so =(x0,..., Couture and L'Ecuyer (1996) and L'Ecuyer and Couture (1997) discuss how to compute &(I) in different contexts. The fact that for the AWC/SWB and additive or subtractive lagged-Fibonacci generators, the set '2$(I) (aside from the zero vector) is contained in only two planes, for a certain set I as mentioned previously, is a special case of their results. They also show, for example, that the two combined generators proposed in  and  can be approximated by linear congruential generators for which c&(I) 1 l/d % 0.408 for certain sets I. For simulations dealing with random points in space, those bad structures could have a dramatic effect BIB001  . A different way of looking at uniformity is to analyze the equidistribution of the point set Tt produced by the generator, as follows (Couture, L'Ecuyer, and Tezuka 1993;   Tezuka 1995) . This is typically applied to LFSR, GFSR, and other similar generators. Partition the hypercube [0, l)t into 2tL cubic cells of equal size. If each cell contains the same number of points of Tt, the sequence (or the set Tt) is called (t, .l)-equidistributed. Assuming that Tt has cardinality 2k, this is possible only for e 5 [k/t]. When '&, is (t, [k/tJ)-equidistributed fort=l,..., k, it is called maximally equidistributed (ME). Several ME combined LFSR generators are listed in L'Ecuyer (1996b), L'Ecuyer (1997e), together with fast computer implementations. Another measure of uniformity of a set of N points in t dimensions is through the notion of discrepancy (see BIB002 for details). When the aim is to imitate i.i.d. uniform random variables, the set of points that are used during a simulation should have a discrepancy comparable to what is normally expected from a set of random points, which is roughly O (N-'i2) . BIB002 gives general discrepancy bounds for several classes of generators, mostly for N = p. However, no efficient algorithm is available for computing the discrepancy exactly, except for certain special cases.