J2ee Web Hosting, Perl Scripting And Developing Blog

3.3.4 THE SPECTRAL TEST 89 3.3.4. The Spectral Test In this section we shall study an especially important way to check the quality of linear congruential random number generators; not only do all good generators pass this test, all generators now known to be bad actually fail it. Thus it is by far the most powerful test known, and it deserves particular attention. Our discussion will also bring out some fundamental limitations on the degree of ran- domness we can expect from linear congruential sequences and their generaliza- tions. The spectral test embodies aspects of both the empirical and theoretical tests studied in previous sections: it is like the theoretical tests because it deals with properties of the full period of the sequence, and it is like the empirical tests because it requires a computer program to determine the results. A. Ideas underlying the test. The most important randomness criteria seem to rely on properties of the joint distribution of t consecutive elements of the sequence, and the spectral test deals directly with this distribution. If we have a sequence (Un) of period m, the idea is to analyze the set of all m points {v&L, &x+1,. . . , Un+t-1) > (1) in t-dimensional space. For simplicity we shall assume that we have a linear congruential sequence (X~,a,c,m) of maximum period length m (so that c # 0), or that m is prime and c = 0 and the period length is m -1. In the latter case we shall add the point (0, 0, . . . ,O) to the set (l), so that there are always m points in all; this extra point has a negligible effect when m is large, and it makes the theory much simpler. Under these assumptions, (1) can be rewritten as -I~(z,s(x),s(s(z)),. . . , s - (x)) /0 5 z < m}, where s(x) = (ax + c) mod m (3) is the successor of 5. Note that we are considering only the set of all such points in t dimensions, not the order in which those points are actually generated. But the order of generation is reflected in the dependence between components of the vectors; and the spectral test studies such dependence for various dimensions t by dealing with the totality of all points (2). For example, Fig. 8 shows a typical small case in 2 and 3 dimensions, for the generator with s(z) = (1372 + 187) mod 256. (4 Of course a generator with period length 256 will hardly be random, but 256 is small enough that we can draw the diagram and gain some understanding before we turn to the larger m s that are of practical interest.
Note: In case you are looking for affordable and reliable webhost to host and run your business application check Vision php5 hosting services

88 RANDOM NUMBERS 3.3.3 EXERCISES-Second Set In many cases, exact computations with integers are quite difficult to carry out, but we can attempt to study the probabilities that arise when we take the average over all real values of 1: instead of restricting the calculation to integer values. Although these results are only approximate, they shed some light on the subject. It is convenient to deal with numbers U,, between zero and one; for linear con- gruential sequences, U, = Xn/m, and we have U,+l = {au,, + 0}, where 0 = c/m and {z} denotes x mod 1. For example, the formula for serial correlation now becomes 1 C= x(ax+8)dx-(~1xdx)1)/(~1~2dx-(~xdx)1) b 21. [HA&B] (R. R. Coveyou.) What is the value of C in the formula just given? b 22. [M22] Let a be an integer, and let 0 5 6 < 1. If x is a real number between 0 and 1, and if s(x) = {ax + 0}, what is the probability that s(x) < x? (This is the real number analog of Theorem P.) 23. [68] The previous exercise gives the probability that Un+l < U,. What is the probability that Un+z < Un+l < Un, assuming that Un is a random real number between zero and one? 24. [A4691 Under the assumptions of the preceding problem, except with 0 = 0, show that U, > Un+l > .. > Un++i occurs with probability What is the average length of a descending run starting at U,, assuming that U, is selected at random between zero and one? b 25. [A4951 Let QI, p, Q , /3 be real numbers with 0 5 o < p < 1, 0 2 cr < /I < 1. Under the assumptions of exercise 22, what is the probability that o 5 z < p and Q 2 s(x) < /I ? (This is the real number analog of exercise 19.) 26. [MZY] Consider a Fibonacci generator, where Un+l = {U,+U,-I}. Assuming that U1 and Uz are independently chosen at random between 0 and 1, find the prob- ability that VI < Uz < Us, Ul < U3 < UZ, UZ < Ui < UX, etc. [Hint: Divide the unit square, i.e., the points of the plane {(sly) ] 0 2 x,y < l}, into six parts, depending on the relative order of x, y, and {x $ y}, and determine the area of each part.] 27. [A&Z?] In the Fibonacci generator of the preceding exercise, let UO and UI be chosen independently in the unit square except that UO > VI. Determine the probabil- ity that Vi is the beginning of an upward run of length k, so that UO > VI < . . . < Uk > Uk+l. Compare this with the corresponding probabilities for a random sequence. 28. [M%] According to Eq. 3.2.1.3-5, a linear congruential generator with potency 2 satisfies the condition X,-l -2X,, + X n+i G (a -1)c (modulo m). Consider a generator that abstracts this situation: let U,+l = {a + 2U, -U,-I}. As in exercise 26, divide the unit square into parts that show the relative order of Vi, UZ, and Us for each pair (VI, Us). Are there any values of QI for which all six possible orders are achieved with probability &, assuming that UI and U2 are chosen at random in the unit square?
Note: In case you are looking for affordable webhost to host and run your servlet application check Vision mysql5 web hosting services

3.3.3 THEORETICAL TESTS 87 10. [M%] Show that when 0 < h < k it is possible to express a(k -h, Ic, c) and 0(h, k, -c) easily in terms of a(h, k, c). 11. [ARfO] The formulas given in the text show us how to evaluate c~(h, Ic, c) when h and Ic are relatively prime and c is an integer. For the general case, prove that a) ~(dh, dk, dc) = a(h, Ic, c), integer d > 0; b) a(h, k c + 0) = G, k c) + W cl~h integer c, real 0 < 0 < 1, when h and Ic are relatively prime and hh = 1 (modulo k). 12. [A&?,$] Show that if h is relatively prime to k and c is an integer, la(h, Ic, c)l 2 (k -l)(k -2)/k. 13. [M,z~] Generalize Eq. (26) so that it gives an expression for a(h, k, c). b 14. [MZO] The linear congruential generator that has m = 235, a = 2 + 1, c = 1, was given the serial correlation test on three batches of 1000 consecutive numbers, and the result was a very high correlation, between 0.2 and 0.3, in each case. What is the serial correlation of this generator, taken over all 235 numbers of the period? 15. [A&Z] Generalize Lemma B so that it applies to all real values of c, 0 5 c < k. 16. [MZd] Given the Euclidean tableau defined in (33), let po = 1, pl = al, and p, = a,p,-1 + p,-2 for 1 < j L t. Show that the complicated portion of the sum in Theorem D can be rewritten as follows, making it possible to avoid noninteger computations: c (-1)3+1& = & c (-q + b3(C3 + C,+1)P,-1. 3 3 ll?lt ll3lt [Hint: Prove that we have ~11j17(-1)3+1/m3m,+l = (-1)7f1p,-l/mlm,+tl for 1 5 r 2 t.1 17. [A&%?] Design an algorithm that evaluates cr(h, k, c) for integers h, k, c satisfying the hypotheses of Theorem D. Your algorithm should use only integer arithmetic (of unlimited precision), and it should produce the answer in the form A + B/k where A and B are integers. (Cf. exercise 16.) If possible, use only a finite number of variables for temporary storage, instead of maintaining arrays such as al, a2, . . . , at. b 18. [A&?31 (U. Dieter.) Given positive integers h, k, z, let Show that this sum can be evaluated in closed form, in terms of generalized Dedekind sums and the sawtooth function. [Hint: When z 5 k, the quantity lj/k] -L(j -z)/kJ equals 1 for 0 2 j < z, and it equals 0 for z 5 j < k, so we can introduce this factor and sum over 0 5 j < k.] b 19. [MZ3] Show that the serial test can be analyzed over the full period, in terms of generalized Dedekind sums, by finding a formula for the probability that a 2 X, < /3 and a 5 Xn+l < p when CY, p, CY , p are given integers with 0 5 cy < /3 2 m, 0 5 a < p 5 m. [Hint: Consider the quantity L(z -cu)/m] -L(z -P)/m].] 20. [MZ9] (U. Dieter.) Extend Theorem P by obtaining a formula for the probability that X, > Xntl > Xn+z, in terms of generalized Dedekind sums.
Note: If you are looking for best quality webspace to host and run your tomcat application check Vision tomcat hosting services

86 RANDOM NUMBERS 3.3.3 not on c) have small partial quotients. In particular, the result of exercise 19 implies that the serial test on pairs will be satisfactorily passed if and only if a/m has no large partial quotients. The book Dedekind Sums by Hans Rademacher and Emil Grosswald (Math. Assoc. of America, Carus Monograph No. 16, 1972) discusses the history and properties of Dedekind sums and their generalizations. Further theoretical tests, including the serial test in higher dimensions, are discussed in Section 3.3.4. EXERCISES-First Set 1. [A4101 Express Z mod y in terms of the sawtooth and 6 functions. 2. [M20] Prove the replicative law, Eq. (10). 3. [HM%%?] What is the Fourier series expansion (in terms of sines and cosines) of the function f(s) = ((x))? b 4. [Ml91 If m = lOlo, what is the highest possible value of d (in the notation of Theorem P), given that the potency of the generator is lo? 5. [A4211 Carry out the derivation of Eq. (17). 6. [A4271 Let hh + kk = 1. (a) Show, without using Lemma B, that a@, k, c) = a(h, k, 0) + 12 for all integers c 2 0. (b) Show that if 0 < j < k, (c) Under the assumptions of Lemma B, prove Eq. (21). b 7. [A424] Give a proof of the reciprocity law (19), when c = 0, by using the general reciprocity law of exercise 1.2.4-45. b 8. [M.!?4] (L. Carlitz.) Let By generalizing the method of proof used in Lemma B, prove the following beautiful identity due to H. Rademacher: If each of p, Q, r is relatively prime to the other two, (The reciprocity law for Dedekind sums, with c = 0, is the special case r = 1.) 9. [A4401 Is there a simple proof of Rademacher s identity (exercise 8) along the lines of the proof in exercise 7 of a special case?
Note: In case you are looking for affordable and reliable webhost to host and run your j2ee application check Vision best web hosting services

3.3.3 THEORETICAL TESTS 85 correlation when a is a good multiplier; the choice c/m = 3 f $,a reduces C substantially only in cases like Example 2 above. And we are fooling ourselves in such cases, since the bad multiplier will reveal its deficiencies in other ways. Clearly we need a better estimate than (39); and such an estimate is now available thanks to Theorem D, which stems principally from the work of U. Dieter [Math. Comp. 25 (1971), 855-8831. Theorem D implies that o(a,m,c) will be small if the partial quotients of a/m are small. Indeed, by analyzing generalized Dedekind sums still more closely, it is possible to obtain quite a sharp estimate: Theorem K. Under the assumptions of Theorem D, we always have 1 aj-c uj+; 5 cr(h,k,c) 2 c uj+; c uj-;. (40) –2 c l 0, approaches large ClNote: In case you are looking for affordable webhost to host and run your web application check Vision http web server services

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
Note: In case you are looking for affordable and reliable webhost to host and run your j2ee application check Vision web design programs services

3.3.3 THEORETICAL TESTS 83 Theorem D. Let h, k, c be integers with 0 < h 5 k, 0 2 c < k, and h relatively prime to k. Form the Euclidean tableau as defined in (33) above, and assume that the process stops after t steps with mt+l = 1. Let s be the smallest subscript such that c, = 0, and let h be defined by (36). Then a(h, k, c) = T + c (-l) + (a, -6b, + 6mjzJ+I) 1Note: If you are looking for high quality webhost to host and run your jsp application check Vision florida web design services

82 RANDOM NUMBERS 3.3.3 Here ai = lmjlm,+~l, bj = lcjlmi+d (33) m,+2 = rnj modmj+r, ci+l = cy modmj+l, and it follows that 0 I m3+l < mj, 0 2 Cj < mj. (34) We have assumed for convenience that Euclid s algorithm terminates in (32) after four iterations; this assumption will reveal the pattern that holds in the general case. Since h and k were relatively prime to start with, we must have m5 = 1 and cg = 0 in (32). Let us further assume that cs # 0 but c4 = 0, in order to get a feeling for the effect this has on the recurrence. Equations (30) and (31) yield c(h, k, c) = o(m2, ml, cl) = f(m2, ml, cl) -4m3, m2, c2) = . . = f(m2, ml, cd -f(m3, m2, c2) + f(m4, m3, c3) -f(m5, m4, c4). The first part h/k + k/h of the formula for f(h, k, c) in (19) contributes ?$+Tp?$-$+~+~-~-~ to the total, and this simplifies to !!+(al+~)-~-(a~+~)+~+(a3+~)-~-a4 = h/k + al -a2 + a3 -a4. _ The next part l/hk of (19) also leads to a simple contribution; according to Eq. 4.5.3-9 and other formulas in Section 4.5.3, we have l/mlmz -l/m2m3 + l/m3m4 -l/m4m5 = h /k -1, (35) where h is the unique integer satisfying h h c 1 (modulo k), 0 < h < k. (36) Adding up all the contributions, and remembering our assumption that c4 = 0 (so that e(m4,cs) = 0, cf. (20)), we find that o(h, k, c) = y + (al -a2 + a3 -4 -6(bl -b2 + b3 - b4) 4 4 -++-- m2m3 m3m4 in terms of the assumed tableau (32). Similar results hold in general:
Note: If you are looking for reliable webhost to maintain and run your java application check Vision java hosting services

3.3.3 THEORETICAL TESTS 81 which follows from the usual method of expanding the right-hand side into partial fractions. Moreover, if o(z) = (X -yl)(z -yz). . . (CC -y,), we have d(Yj) = (Yj -Yl). . . (Y.j -Yj-l)(Yj -Yj+1). . . (Yj -Ym); (28) this identity may often be used to simplify expressions like those in the left-hand side of (27). When h and Ic are relatively prime, the numbers w, w2, . . . , tik–l, ghP1 are all distinct; we can therefore consider formula (27) in the &&a; c ase of the polynomial (z -w). . . (zr - w~- )(x -5). . . (z -ch-l) = (x -l)(zh -1)/(x -1)2, obt aining the following identity in x: This identity has many interesting consequences, and it leads to numerous reci: procity formulas for sums of the type given in Eq. (26). For example, if we differentiate (29) twice with respect to x and let x + 1, we find that Replace j by h -j and by Ic - j in these sums and use (26) to get ~(kh,O)+ 3(h h -1) which is equivalent to the desired result. I Lemma B gives us an explicit function f(h, k, c) such that 4h, k, c) = f(h k c) -o(k h, c) (30) whenever 0 < h 5 k, 0 2 c < k, and h is relatively prime to k. From the definition (16) it is clear that a(k, h, c) = c(k mod h, h, c mod h). (31) Therefore we can use (30) iteratively to evaluate o(h, Ic, c), using a process that reduces the parameters as in Euclid s algorithm. Further simplifications occur when we examine this iterative procedure more closely. Let us set ml = k, m2 = h, cl = c, and form the following tableau: ml = alm2 + m3 cl =hmz+cz m2 = a2m3 + m4 Q = bzm3 + ~3 (32) m3 = a3m4 + m5 ~3 = km4 + ~4 m4 = a4m5 ~4 = km5 + ~5
Note: In case you are looking for affordable webhost to host and run your servlet application check Vision ecommerce web hosting services

80 RANDOM NUMBERS 3.3.3 If w is the complex kth root of unity elnilk, we have by Eq. 1.2.9-13 1 w-j?g(wjx) = ?-x7, if0 < r < k. i c Ojj ..,(X~-Xj-~)(XIXj)(Xj-Xj+l)~~~(xj-xn) = (x-x&r.(x-xn) ) (27)
Note: In case you are looking for affordable and reliable webhost to host and run your j2ee application check Vision web design programs services