84 RANDOM (Web hosting script) NUMBERS 3.3.3 This is a very
84 RANDOM NUMBERS 3.3.3 This is a very respectable value of C indeed. But the generator has a potency of only 3, so it is not really a very good source of random numbers in spite of the fact that it has low serial correlation. It is necessary to have a low serial correlation, but not sufficient. Example 3. Estimate the serial correlation for general a, m, and c. Solution. If we consider just one application of (30), we have da, m, c> 25:+6&-6:–o(m,u,c). Now la(m, a, c)l < a by exercise 12, and therefore 4a, m, 4 =:I 1-6C+6 : 2 (39) cz m U ( m ( m )> * The error in this approximation is less than (a + 6)/m in absolute value. The estimate in (39) was the first theoretical result known about the ran- domness of congruential generators. R. R. Coveyou [JACK 7 (1960), 72-741 obtained it by averaging over all real numbers x between 0 and m instead of con- sidering only the integer values (cf. exercise 21); then Martin Greenberger [Math. Comp. 15 (1961), 383-3891 gave a rigorous derivation including an estimate of the error term. So began one of the saddest chapters in the history of computer science! Although the above approximation is quite correct, it has been grievously misap- plied in practice; people abandoned the perfectly good generators they had been using and replaced them by terrible generators that looked good from the standpoint of (39). For more than a decade, the most common random number generators in daily use were seriously deficient, solely because of a theoretical advance. A little knowledge is a dangerous thing. If we are to learn by past mistakes, we had better look carefully at how (39) has been misused. In the first place people assumed uncritically that a small serial correlation over the whole period would be a pretty good guarantee of randomness; but in fact it doesn t even ensure a small serial correlation for 1000 consecutive elements of the sequence (see exercise 14). Secondly, (39) and its error term will ensure a relatively small value of C only when a z fi; therefore people suggested choosing multipliers near Jm. In fact, we shall see that nearly all multipliers give a value of C that is substantially less than l/fi, hence (39) is not a very good approximation to the true behavior. Minimizing a crude upper bound for C does not minimize C. In the third place, people observed that (39) yields its best estimate when c/m M 4 f ifi, since these values are the roots of 1 -6x + 6s2 = 0. In the absence of any other criterion for choosing c, we might as well use this one. The latter statement is not incorrect, but it is misleading at best, since experience has shown that the value of c has hardly any influence on the true value of the serial