Exact Permutation Tests Under Exchangeability

Why Exchangeability Makes Permutation Calibration Possible

A permutation test replaces a reference distribution that may be difficult to derive with a finite distribution obtained by reallocating the observed pooled observations. Its validity is not automatic: the null hypothesis must make the pooled observations exchangeable, and the statistic must treat observation labels consistently. These conditions allow the observed allocation to be compared with all allocations on equal terms, even when the observations are multivariate and the statistic is based on ranks.

Consider two groups of fixed sizes \(n_1\) and \(n_2\), with \(N=n_1+n_2\) pooled observations \(Z_1,\ldots,Z_N\) in \(\mathbb{R}^d\). Write \(A_0\) for the indices assigned to group 1 in the observed data. The allocation set is \(\mathcal{A}=\{A\subseteq\{1,\ldots,N\}:|A|=n_1\}\), with \(M=\binom{N}{n_1}\) possible allocations.

Definition: The pooled observations are exchangeable under a null hypothesis if, for every permutation \(\pi\) of \(\{1,\ldots,N\}\), \((Z_1,\ldots,Z_N)\) and \((Z_{\pi^{-1}(1)},\ldots,Z_{\pi^{-1}(N)})\) have the same joint distribution. For a two-sample permutation test, this is the relevant null condition; equality of group means alone, for example, does not imply exchangeability.

For each allocation \(A\), let \(T(A;z)\) be a real-valued statistic calculated from the pooled data \(z=(z_1,\ldots,z_N)\) and the indices assigned to group 1. Large values will be taken as evidence against the null. The statistic may use multivariate ranks or rank scores calculated from the pooled observations.

Definition: A statistic is invariant under simultaneous relabeling if, for every permutation \(\pi\), allocation \(A\), and pooled sample \(z\), \[ T(\pi A;\pi z)=T(A;z), \] where \((\pi z)_i=z_{\pi^{-1}(i)}\) and \(\pi A=\{\pi(i):i\in A\}\). In words, changing the names of the pooled indices and changing the allocation in the same way leaves the statistic unchanged.

This condition is satisfied by statistics calculated by the same rule from the values assigned to each group. If a procedure estimates ranks or other quantities separately for each allocation, those quantities must be recalculated by the same rule for every allocation. Alternatively, a pooled rank construction can be held fixed while the group allocation changes. Either approach is permissible when the resulting statistic obeys the stated invariance condition.

The Permutation Reference Distribution

For fixed observed pooled values \(z\), the permutation reference distribution assigns equal probability \(1/M\) to each statistic \(T(A;z)\), \(A\in\mathcal{A}\). Its upper-tail inclusive p-value at observed allocation \(A_0\) is \[ p(z,A_0)=\frac{1}{M}\sum_{A\in\mathcal{A}} \mathbf{1}\{T(A;z)\geq T(A_0;z)\}. \] The weak inequality includes allocations tied with the observed statistic. For multivariate rank statistics, the statistic might be the squared norm of a group’s summed rank scores, a quadratic form in those scores, or another scalar summary. The permutation reference distribution is the finite distribution of that chosen scalar statistic, not a new distribution for the individual rank vectors.

Worked Example: Enumerating a Spatial-Rank Reference Distribution

Take four pooled observations in \(\mathbb{R}^2\): \(z_1=(1,0)\), \(z_2=(-1,0)\), \(z_3=(0,1)\), and \(z_4=(0,-1)\). Let group 1 have size two. Use the empirical spatial ranks \[ R_i=\frac{1}{3}\sum_{j\ne i}\frac{z_i-z_j}{\|z_i-z_j\|}, \] and define \(T(A;z)=\|\sum_{i\in A}R_i\|^2\).

For \(z_1=(1,0)\), the three unit differences are \((1,0)\), \((1,-1)/\sqrt{2}\), and \((1,1)/\sqrt{2}\). Thus \(R_1=c(1,0)\), where \(c=(1+\sqrt{2})/3\). By the same calculation for the other three points, \(R_2=-c(1,0)\), \(R_3=c(0,1)\), and \(R_4=-c(0,1)\).

There are \(\binom{4}{2}=6\) allocations. The two opposite pairs, \(\{1,2\}\) and \(\{3,4\}\), have rank-score sum zero and statistic zero. Each of the other four pairs consists of perpendicular rank vectors, so its statistic is \(c^2+c^2=2c^2=(6+4\sqrt{2})/9\), approximately \(1.295\).

If the observed allocation is \(A_0=\{1,3\}\), its statistic is the larger value. Four of the six allocations have statistics at least that large, so the inclusive p-value is \(4/6=2/3\). This calculation uses the same pooled rank vectors for all allocations and compares the observed statistic with the complete finite reference distribution.

Conditional Exactness: The Main Result

The term “exact” refers to finite-sample validity without an asymptotic approximation. With an inclusive p-value, validity generally means that the rejection probability is at most the nominal level; ties and the discreteness of the reference distribution can make the test conservative.

Theorem: Suppose \(Z_1,\ldots,Z_N\) take values in \(\mathbb{R}^d\) and are exchangeable under the null. Fix the group sizes and observed allocation \(A_0\). Let \(T\) be measurable and invariant under simultaneous relabeling. Then the inclusive upper-tail permutation p-value satisfies \[ P\{p(Z,A_0)\leq\alpha\mid\mathcal{O}\}\leq\alpha \] for \(0\leq\alpha\leq1\), almost surely, where \(\mathcal{O}\) denotes the pooled sample’s permutation orbit. Consequently \(P\{p(Z,A_0)\leq\alpha\}\leq\alpha\).

The permutation orbit \(\mathcal{O}\) is the finite set of pooled data configurations obtainable by permuting the indices of the observed tuple. Conditional on this orbit, exchangeability gives equal probability to its distinct configurations. Repeated observations do not invalidate this statement: a uniformly chosen permutation of the indices generates each distinct configuration with the same multiplicity.

Proof. First fix any list of \(M\) real numbers \(t_A\), one for each allocation \(A\in\mathcal{A}\). If an allocation \(B\) is chosen uniformly from \(\mathcal{A}\), define \[ q_B=\frac{1}{M}\#\{A:t_A\geq t_B\}. \] Then \(P(q_B\leq\alpha)\leq\alpha\). To see this, order the distinct statistic values from largest to smallest. For each distinct value, \(q_B\) is the cumulative number of allocations at that value or above, divided by \(M\). The allocations for which \(q_B\leq\alpha\), if any, therefore form an initial collection in this ordering containing at most \(\lfloor \alpha M\rfloor\) allocations. Its probability under uniform choice of \(B\) is at most \(\lfloor\alpha M\rfloor/M\leq\alpha\).

Now condition on an orbit and represent its uniformly distributed configuration as \(\pi z\), where \(z\) is any fixed representative and \(\pi\) is a uniformly chosen permutation. For every allocation \(A\), relabeling invariance implies \(T(A;\pi z)=T(\pi^{-1}A;z)\). Therefore the permutation p-value computed from \((\pi z,A_0)\) equals the upper-tail rank of \(T(\pi^{-1}A_0;z)\) among the fixed list \(\{T(A;z):A\in\mathcal{A}\}\). The allocation \(\pi^{-1}A_0\) is uniform on \(\mathcal{A}\), because every allocation of size \(n_1\) is the inverse image of \(A_0\) under the same number of permutations. The finite-list argument gives the claimed conditional bound. Taking expectations over \(\mathcal{O}\) gives the unconditional bound. \(\square\)

Worked Example: Ties and a Randomized p-Value

Use the four spatial-rank scores from the preceding example. The six allocation statistics consist of four copies of \(h=2c^2\) and two copies of zero. For an observed allocation with statistic \(h\), the inclusive p-value is \(4/6\). For an observed allocation with statistic zero, it is \(6/6=1\).

One may remove conservatism caused by ties by adding independent randomization. Let \(G\) be the number of allocations with statistic strictly greater than the observed value, \(E\) the number tied with it, and \(U\sim\operatorname{Uniform}(0,1)\), independent of the data. Define \(p_{\mathrm{rand}}=(G+UE)/M\). For an observed high-statistic allocation here, \(G=0\), \(E=4\), so \(p_{\mathrm{rand}}=2U/3\). For an observed zero-statistic allocation, \(G=4\), \(E=2\), so \(p_{\mathrm{rand}}=(4+2U)/6\).

Under uniform choice of an allocation, the four high-statistic allocations each contribute a uniform value on \([0,2/3]\), and the two low-statistic allocations each contribute a uniform value on \([2/3,1]\). The first region has total probability \(4/6\) and the second \(2/6\); their densities are respectively \((4/6)/(2/3)=1\) and \((2/6)/(1/3)=1\). Thus the randomized p-value is uniform on \([0,1]\) under the conditional permutation distribution. The inclusive p-value avoids extra randomization and remains valid, but can be conservative.

What the Conditions Do—and Do Not—Guarantee

Exchangeability is a statement about the joint distribution of the pooled observations, not merely about a selected feature such as their means. If group distributions differ in shape or spread, equal means need not make the pooled observations exchangeable. Conversely, under the exchangeable null, the finite-sample argument does not require normality, a covariance estimate, or an asymptotic approximation. It applies to a chosen multivariate rank statistic as long as the statistic is measurable and respects simultaneous relabeling.

The result establishes null calibration, not power or scientific relevance. A test still needs a statistic suited to the alternative of interest, and all choices that affect the statistic must be specified consistently across allocations. For example, if a rank transformation depends on the pooled observations, it must not secretly use the original group labels to treat otherwise identical allocations differently.

Worked Example: How Label Dependence Breaks Calibration

Let \(N=2\), \(n_1=1\), and suppose \(Z_1,Z_2\) are iid, hence exchangeable. Consider the rule \(T(A;z)=1\) if index 1 belongs to \(A\), and \(T(A;z)=0\) otherwise. With observed allocation \(A_0=\{1\}\), the two reference statistics are \(1\) for \(\{1\}\) and \(0\) for \(\{2\}\). The inclusive p-value is therefore \(1/2\) for every observed data set.

At nominal level \(\alpha=1/2\), the rule that rejects when \(p\leq\alpha\) rejects with probability one, exceeding its nominal level. The statistic has the same written rule for every allocation, but it depends on the index label rather than on the values assigned to the group. It fails the required condition: relabeling indices and the allocation together can change its value. The correction is not to rely on exchangeability alone; use a statistic invariant under simultaneous relabeling, as in a group statistic calculated from the assigned observations.

Common Mistakes

Assuming exchangeability makes every statistic valid. It does not. The statistic must also be invariant under simultaneous relabeling of the pooled values and allocation.
Using a strict tail without stating the tie rule. The usual inclusive p-value counts statistics equal to the observed one. Omitting ties can make the p-value anti-conservative.
Calling equal means an exchangeability condition. Exchangeability concerns the joint distribution under permutations, not one moment alone.
Keeping label-dependent preprocessing fixed. Recompute allocation-dependent steps consistently, or use a pooled construction that does not privilege the observed labels.

Key takeaway: Under exchangeability, a relabeling-invariant statistic has a valid finite-sample permutation test: conditional on the pooled permutation orbit, the observed allocation is equivalent to a uniformly selected allocation. Inclusive p-values are super-uniform; randomization within ties can produce exact uniform p-values.

Check Your Understanding

Check that you can identify both the null condition and the role of the allocation reference distribution.

State the simultaneous relabeling condition for \(T(A;z)\) using a permutation \(\pi\).
Why does exchangeability make the observed allocation comparable to a uniformly selected allocation after conditioning on the permutation orbit?
For \(M=10\) allocations, an observed statistic is tied with the two largest values and no value is strictly larger. What is its inclusive p-value?
Explain why equal group means alone do not establish the validity of an exact permutation test.
What property fails in the index-based statistic from the counterexample?