Windows 2003 server web - 76 RANDOM NUMBERS 3.3.3 Let us begin with
76 RANDOM NUMBERS 3.3.3 Let us begin with a proof of a simple a priori law, for the least complicated case of the permutation test. The gist of our first theorem is that we have X,+1 < X, about half the time, provided that the sequence has high potency. Theorem P. Let a, c, and m generate a linear congruential sequence with maximum period; let b = a - 1 and let d be the greatest common divisor of m and b. The probability that X,+1 < X, is equal to 3 + r, where r = (2(c mod d) -d)/2m; (1) hence Irl < d/2m. Proof. The proof of this theorem involves some techniques that are of interest in themselves. First we define s(x) = (aa: + c) mod m. (2) Thus, &+I = s(Xn), and the theorem reduces to counting the number of integers 2 such that 0 < z < m and s(z) < z (since each such integer occurs somewhere in the period). We want to show that this number is $(m + 2(cmodd) -d). (3) The function [(z -s(z))/ml is equal to 1 when z > s(z), and it is 0 otherwise; hence the count we wish to obtain can be written simply as (4) (Recall that r—y] = -[yJ and b = a -1.) Such sums can be evaluated by the method of exercise 1.2.4-37, where we have proved that g = w@, k), (5) whenever h and k are integers and k > 0. Since a is relatively prime to m, this formula yields o<~m[EgJ = @-l)p–) +(+ - o<~~~~~J=(b-l)~-l)+~+C-(emodd) , - and (3) follows immediately. 1