3.5 WHAT IS A RANDOM SEQUENCE? (Web server on xp) 147 Proof.
3.5 WHAT IS A RANDOM SEQUENCE? 147 Proof. The definition of a k-distributed sequence states that this result is true in the special case that 1, if u1 5 z1 < wl,.. .,uk 2 xk < vk; f(x1, . . . , xk) = (9) 0, otherwise. Therefore Eq. (8) is true whenever f = al fl +asf~ +. . . +a,fm and when each fj is a function of type (9); in other words, Eq. (8) holds whenever f is a step- function obtained by (i) partitioning the unit k-dimensional cube into subcells whose faces are parallel to the coordinate axes, and (ii) assigning a constant value to f on each subcell. Now let f be any Riemann-integrable function. If E is any positive number, we know (by the definition of Riemann-integrability) that there exist step func- tions f and 7 such that f(zl,. . . , zk) 2 f(xl, . . . , zk) 5 7(x1,. . . , xk), and such that the difference of the integrals of f and 7 is less than 6. Since Eq. (8) holds for f and 7, and since - we conclude that Eq. (8) is true also for f. 1 Theorem B can be applied, for example, to the permutation test of Section 3.3.2. Let (pl,pz,. .., pk) be any permutation of the numbers {1,2,. . . , k}; we want to show that pr(un+p~–l < &1+~~-1 < . . . < un+pk-l) = l/k!. (10) To prove this, assume that the sequence (Un) is k-distributed, and let 1, if xpl < xpz < . < xpr; f(x1,. . . , xk) = 0, otherwise. We have pr(un-tpl-1 < Un+pz–l < *. . < un+pk-l) -I J f(xl, . . . . . . , xk) dXl dXk ~;:;~p~~zpk…lx’” dq,,f2 dxpl = ;. Corollary P. If a [ 0,l) sequence is k-distributed, it satisfies the permutation test of order k, in the sense of Eq. (10). 1