Photography web hosting - 64 RANDOM NUMBERS 3.3.2 F. Permutation test. Divide
64 RANDOM NUMBERS 3.3.2 F. Permutation test. Divide the input sequence into n groups oft elements each, that is, (Ujt, Ujt+l, . . . , Ujt++r) for 0 5 j < n. The elements in each group can have t! possible relative orderings; the number of times each ordering appears is counted, and a chi-square test is applied with k = t! and with probability l/t! for each ordering. For example, if t = 3 we would have six possible categories, according to whether Usj < Usj+l < Us3+z or U3j < U3j+2 < U3j+l or *** or U3j+2 < U3j+l < U3je We assume in this test that equality between U s does not occur; such an assumption is justified, for the probability that two U s are equal is zero. A convenient way to perform the permutation test on a computer makes use of the following algorithm, which is of interest in itself: Algorithm P (Analyze a permutation). Given a sequence of distinct elements (ht..., Ut), we compute an integer f(Ul, . . . , Ut) such that 0 2 f(U1, . f * , Ut) < t!, and f(Ul,. . . , Ut) = f(Vl,. . . , Vt) if and only if (VI,. . . , Ut) and (VI,. . . ,Vt) have the same relative ordering. Pl. [Initialize.] Set r c t, f c 0. (During this algorithm we will have 0 5 f < t!/r!.) P2. [Find maximum.] Find the maximum of {VI,. . . , UT}, and suppose that U, is the maximum. Set f t T. f + s - 1. P3. [Exchange.] Exchange U, c* Us. P4. [Decrease r.] Decrease r by one. If r > 1, return to step P2. 1 Note that the sequence (VI,. . . , Ut) will have been sorted into ascending or- der when this algorithm stops. To prove that the result f uniquely characterizes the initial order of (VI,. . ., Ut), we note that Algorithm P can be run backwards: For r = 2, 3, . . . , t, set s c f modr, f t [f/r], and exchange U,. Us. It is easy to see that this will undo the effects of steps P2-P4; hence no two permutations can yield the same value of f, and Algorithm P performs as advertised. The essential idea that underlies Algorithm P is a mixed-radix representation called the factorial number system : Every integer in the range 0 2 f < t! can be uniquely written in the form f = (. * .(6-l x (t -1) + G-2) x (t -2) + * * * + cz) x 2 + Cl = (t - l)! Q-1 + (t - 2)! Q-2 + * * * + 2! cz + l! Cl (7) where the digits Cj are integers satisfying Cl 5 Cj L j, for 1 2 j < t. (8) In Algorithm P, cr.-1 = s - 1 when step P2 is performed for a given value of T.
Note: If you are looking for cheap and reliable webhost to host and run your web application check Vision coldfusion web hosting services