Uniform random number generators: a review <s> COMBINED GENERATORS <s> The meaning of randomness is studied for the simple case of binary sequences. Ensemble theory is used, together with correlation coefficients of any order. Conservation laws for the total amount of correlation are obtained. They imply that true randomness is an ensemble property and can never be achieved in a single sequence. The relation with entropy is discussed for different ensembles. Well-tempered pseudorandom sequences turn out to be suitable sources of random numbers, and practical recipes to generate them for use in large-scale Monte Carlo simulations are found. <s> BIB001 </s> Uniform random number generators: a review <s> COMBINED GENERATORS <s> The twisted GFSR generators proposed in a previous article have a defect in k -distribution for k larger than the order of recurrence. In this follow up article, we introduce and analyze a new TGFSR variant having better k -distribution property. We provide an efficient algorithm to obtain the order of equidistribution, together with a tight upper bound on the order. We discuss a method to search for generators attaining this bound, and we list some of these such generators. The upper bound turns out to be (sometimes far) less than the maximum order of equidistribution for a generator of that period length, but far more than that for a GFSR with a working are of the same size. <s> BIB002 </s> Uniform random number generators: a review <s> COMBINED GENERATORS <s> The fixed vector of any m -sequence based on a trinomial is explicitly obtained. Local nonrandomness around the fixed vector is analyzed through model-construction and experiments. We conclude that the initial vector near the fixed vector should be avoided. <s> BIB003
Combination is a way of increasing the period length and improving the statistical properties of generators  L'Ecuyer and Cot& 1991;  L'Ecuyer 1996b;   Tezuka 1995; Wang and Compagner 1993) . However, blind combinations or mixtures give no guarantee of improvement. It is important to understand the structure of the resulting generator. Among the classes of combined generators that have been successfully analyzed theoretically, one finds the combined MRGs and the combined Tausworthe/GFSR generators. Take J MRGs of order Ic, the form Xj,n = (aj,lXj,n-l+e * .+ aj,kxj,n-k) 130 L 'Ecuyer with distinct prime moduli and maximal period pj = mjk-1. Let&,..., SJ be arbitrary integers such that gcd(&j, mj) = 1 for each j and define the combinations mod ml; G,, = z,,/ml (9) and (10) mj , nj be the inverse of m/mj modulo ai = mod m for i = l,..., k. Then, the periodic sequence {w,,} is exactly the same as the sequence {u,,} given by the MRG (l-2), and the sequence {$,} is almost the same in the sense that [u, -fi,,l is uniformly very close to zero when the mj's are close to each other. See L'Ecuyer and Tezuka (1991), L'Ecuyer (1996b) for details and proofs. Therefore, these combinations can be seen as convenient ways of implementing an MRG with a large composite modulus. The maximal period for the combination is p = lcm(pl, . . . , P1) = 21-J ni=, pj. The main advantages of these combinations are (a) an increased period length, while all computations are performed modulo relatively small integers mj; (b) the fact that (1) can have many nonzero coefficients even if the recurrence (8) of each component has few of them. LFSR and GFSR generators whose recurrence is based on a trinomial, like in (3)) are fast but have important statistical defects BIB002 BIB003 BIB001 . Again, this may be resolved by combination. Tezuka and L'Ecuyer (1991) and Wang and Compagner (1993) propose to combine J "easy-toimplement" LFSR generators, the jth producing a sequence { Uj,n, n 2 0}, by a bitwise exclusive-or of the Uj,,'s: u,, = UI,,, @ . . . $ UJ,n. The resulting generator is equivalent to a LFSR generator whose recurrence has a reducible characteristic polynomial equal to the product of the characteristic polynomials of the individual components. The period could reach nj"=, (2kj -1)) where kj is the the degree of the characteristic polynomial of component j, provided that the kj are pairwise coprime. GFSR and twisted GFSR generators can also be combined in a similar way. Such combinations can be viewed as practical ways of implementing recurrences with "good" characteristic polynomials, with many nonzero coefficients.