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 }⟺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

$$\begin{array}{}\text{(*)}& \mathsf{P}\{R=r\}=\frac{1}{n!},r\in \mathfrak{R},\end{array}$$

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 $\mathrm{\Psi }(x^{(.)},r)$ is a function defined on ${\mathfrak{X}}^{(.)}\times \mathfrak{R}$ in such a way that $0\le \mathrm{\Psi }\le 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}}\mathrm{\Psi }(x^{(.)},r)=\alpha$$

almost-everywhere, then the statistical test for testing $H_{\star }$ with critical function

$$\varphi (x)=\varphi (x_1\dots x_n)=\mathrm{\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[edit]