Modified Randomization Tests for Nonparametric Hypotheses

Suppose X₁, , Xₘ, Y₁, , Yₙ are m + n = N independent random variables, the X's identically distributed and the Y's identically distributed, each with a continuous cdf. Let z = (z₁, , zₘ, z₌ + ₁, , zN) = (x₁, , xₘ, y₁, , yₙ) represent an observation on the N random variables and let u (z) = (1/m) ᵐ₈ = ₁ zᵢ - (1/n) N₈ = ₌ + ₁ zᵢ = x - y. Consider the r = N! N-tuples obtained from (z₁, , zN) by making all permutations of the indices (1, , N). Since we assume continuous cdf's, then with probability one, these r N-tuples will be distinct. Denote them by z^ (1), , z^ (r), and suppose that they have been ordered so that u (z^ (1) u (z^ (r) ). Notice that since x - y = (1/m) N₈ = ₁ zᵢ - (N/m) y = (N/n) x - (1/n) N₈ = ₁ zᵢ, the same ordering can be induced by choosing u (z) = c x or u (z) = - c y for any c > 0. Assuming that the cdf's of X₁, Y₁ are of the form F (x), F (x -) respectively, Pitman 2 suggested essentially the following test of the hypothesis H' that = 0. Select a set of k (k > 0) integers i₁, , iₖ, (1 i₁ 0. A practical shortcoming of this procedure is the great difficulty in enumerating the points z^ (i) and the evaluation of u (z^ (i) ) for each of them. For instance, even after eliminating those permutations which always give the same value of u, then for sample sizes m = n = 5, there are 105 = 252 permutations to examine, and for sample sizes m = n = 10, there are 2010 = 184, 765 permutations to examine. In the following section, we propose the almost obvious procedure of examining a "random sample" of permutations and making the decision to accept or reject H on the basis of those permutations only. Bounds are determined for the ratio of the power of the original procedure to the modified one. Some numerical values of these bounds are given in Table 1. The bounds there listed correspond to tests which in both original and modified form have size, and for which the modified test is based on a random sample of s permutations drawn with replacement. These have been computed for a certain class of alternatives which is described below. For simplicity, we have restricted the main exposition to the two-sample problem. In Section 5, we point out extensions to the more general hypotheses of invariance studied in 1.