Permutation test

A statistical test intended for testing the hypothesis $ H _ \star $ according to which the probability density (cf. Density of a probability distribution) of an observable random vector $ X = ( X _ {1} \dots X _ {n} ) $ belongs to the family of all $ n $- dimensional densities that are symmetric with respect to permutation of their arguments.

Assume that one has to test the hypothesis $ H _ \star $ that the probability density $ p( x) $ of the random vector $ X $ belongs to the family $ \mathbf H _ \star = \{ p( x) \} $ of all $ n $- dimensional densities $ p( x) = p( x _ {1} \dots x _ {n} ) $ that are symmetric with respect to permutation of the arguments $ x _ {1} \dots x _ {n} $, from a realization of the random vector $ X = ( X _ {1} \dots X _ {n)} $ that takes values $ x = ( x _ {1} \dots x _ {n} ) $ in $ n $- dimensional Euclidean space $ \mathbf R ^ {n} $. Then

$$ p( x) \in \mathbf H _ \star \iff p( x _ {1} \dots x _ {n} ) = p( x _ {r _ {1} } \dots x _ {r _ {n} } ), $$

where $ r = ( r _ {1} \dots r _ {n} ) $ is any vector from the space $ \mathfrak R $ of all permutations $ ( r _ {1} \dots r _ {n} ) $ of the vector $ ( 1 \dots n) $. The space $ \mathfrak R $ is the set of all realizations of the vector of ranks $ R = ( R _ {1} \dots R _ {n} ) $ naturally arising in constructing the order statistic vector $ X ^ {(.)} $ that takes values $ x ^ {(.)} $ in the set $ \mathfrak X ^ {(.)} \subset \mathbf R ^ {n} $. If $ H _ \star $ is true, then the statistics $ X ^ {(.)} $ and $ R $ are stochastically independent, and

$$ \tag{* } {\mathsf P} \{ R = r \} = \frac{1}{n!} ,\ r \in \mathfrak R , $$

and the probability density for $ X ^ {(.)} $ is $ n!p( x ^ {(.)} ) $, $ x ^ {(.)} \in \mathfrak X ^ {(.)} $.

Property (*) of the uniform distribution for $ R $ if $ H _ \star $ is true forms the basis of constructing the permutation test.

If $ \Psi ( x ^ {(.)} , r) $ is a function defined on $ \mathfrak X ^ {(.)} \times \mathfrak R $ in such a way that $ 0 \leq \Psi \leq 1 $ and such that for any $ r \in \mathfrak R $ it is measurable with respect to the Borel $ \sigma $- algebra of $ \mathfrak X ^ {(.)} $, and if also for some $ \alpha \in ( 0, 1) $,

$$ \frac{1}{n!} \sum _ {r \in \mathfrak R } \Psi ( x ^ {(.)} , r) = \alpha $$

almost-everywhere, then the statistical test for testing $ H _ \star $ with critical function

$$ \phi ( x) = \phi ( x _ {1} \dots x _ {n} ) = \Psi ( x ^ {(.)} , r) $$

is called the permutation test. If the permutation test is not randomized, $ \alpha $ should be taken a multiple of $ 1/n! $.

The most-powerful test for testing $ H _ \star $ against a simple alternative $ q( x) $ can be found in the family of permutation tests, where $ q( x) $ is any $ n $- dimensional density not belonging to $ \mathbf H _ \star $.

The family of permutation tests and the family of tests that are invariant under a change in the shift and scale parameters play significant roles in constructing rank tests (cf. Rank test). Finally, in the literature on mathematical statistics, one frequently finds the term permutation test replaced by "randomization test" .

See Order statistic; Invariant test; Critical function.

References

[1]	J. Hájek, Z. Sidák, "Theory of rank tests" , Acad. Press (1967)
[2]	E.L. Lehmann, "Testing statistical hypotheses" , Wiley (1986)