Permutation Calibration and Exchangeability Limits

Why Permutation Calibration Needs More Than a Location Null

Permutation calibration replaces a model-based reference distribution with the distribution of a statistic under relabellings of the observed data. This can be attractive for robust multivariate tests: the statistic may be based on robust location estimates or other procedures whose finite-sample distribution is difficult to calculate. But shuffling labels is not automatically distribution-free. Its exactness depends on whether the null makes the permitted relabellings equally plausible.

The key distinction is between a null hypothesis about a feature of a distribution and a null hypothesis that makes the full observations exchangeable. Equality of robust locations, by itself, is generally weaker than equality of distributions. If groups have different scatter or other distributional features, unrestricted label permutations need not provide a valid finite-sample reference distribution for a location test.

Definition: A collection of random vectors $X_1,\ldots,X_N$ is exchangeable under a set of permutations $\mathcal{G}$ if, for every $\pi\in\mathcal{G}$, the joint distribution of $(X_1,\ldots,X_N)$ is the same as that of $(X_{\pi(1)},\ldots,X_{\pi(N)})$. For unrestricted permutations, $\mathcal{G}$ contains every permutation of the $N$ observation indices. Independent observations with a common multivariate distribution are exchangeable.

For a two-group comparison, suppose there are $n_1$ observations in group 1 and $n_2$ in group 2, with $N=n_1+n_2$. A common sufficient condition for unrestricted label permutation is the null $F_1=F_2$, where $F_g$ is the distribution of a group-$g$ observation, together with independence across observations. Conditional on the pooled observations, each assignment of $n_1$ of them to group 1 is then equally likely. This is a statement about the full distributions, not merely their centers.

Constructing a Robust Permutation Test

Choose a statistic $T$ that measures departure from the null and is large for departures of interest. For example, $T$ might be a norm of a difference between robust multivariate location estimates, possibly scaled using a robust scatter estimate. The choice of robust estimator and statistic determines what departures the test is sensitive to; the permutation argument concerns how the statistic is calibrated.

For every permitted assignment, calculate the statistic from the observations with that assignment’s group labels. This means recomputing every label-dependent part of the procedure, including robust location estimates and any scale or scatter estimates. Holding the observed estimates fixed while shuffling only a final contrast generally does not produce the permutation distribution of the stated statistic.

Permutation test: Let $\mathcal{A}$ be the set of permitted assignments, with $M=|\mathcal{A}|$, and let $T(a)$ be the statistic computed under assignment $a$. For an observed assignment $a_0$, the nonrandomized upper-tail permutation $p$-value is $$ p_{\mathrm{perm}}=\frac{\#\{a\in\mathcal{A}:T(a)\geq T(a_0)\}}{M}. $$ The observed assignment is included. If the null makes the permitted assignments equally likely, this $p$-value is finite-sample valid: its probability of being at most $\alpha$ is no greater than $\alpha$.

The inequality rather than equality allows for ties in the statistic. A randomized version can break ties to attain an exact uniform $p$-value under the same invariance conditions, but the nonrandomized version is usually simpler and is conservative when ties occur. For Monte Carlo sampling of assignments, the sampled fraction is an approximation to the full permutation calculation; it is not the exact enumeration described by the formula.

Worked Example: Enumerating a Robust Location Statistic

There are two observations in each of two groups. The observed group 1 vectors are $(0,0)$ and $(0,2)$, and the observed group 2 vectors are $(4,0)$ and $(4,2)$. Use the squared Euclidean distance between the groups’ coordinatewise medians as $T$. For a group of size two, define each coordinate’s median as the average of the two values.

Under the observed assignment, the group medians are $(0,1)$ and $(4,1)$. Thus $T(a_0)=(0-4)^2+(1-1)^2=16$. There are $\binom{4}{2}=6$ assignments of two pooled vectors to group 1; for each, the remaining two form group 2.

If group 1 receives $\{(0,0),(0,2)\}$, its median is $(0,1)$, the other group’s median is $(4,1)$, and $T=16$. If it receives $\{(4,0),(4,2)\}$, the groups reverse and $T=16$.

If group 1 receives $\{(0,0),(4,0)\}$, the two medians are $(2,0)$ and $(2,2)$, giving $T=4$. The assignment $\{(0,2),(4,2)\}$ also gives $T=4$. Each of the two remaining assignments has median $(2,1)$ in both groups, so $T=0$.

Exactly two of the six assignments have a statistic at least as large as 16. Therefore $p_{\mathrm{perm}}=2/6=1/3$. This enumeration illustrates the mechanics of calibrating a robust location statistic; its small sample size is not a recommendation for using this particular statistic in practice.

Why Exchangeability Gives Validity

The validity argument is a finite-sample symmetry argument. Under the null, the observed assignment has no special status among the permitted assignments. Consequently, its statistic has a rank in the permutation distribution that cannot systematically be among the most extreme ranks. Ties can only make the nonrandomized upper-tail test more conservative.

Theorem: Suppose the null distribution is invariant under a finite set $\mathcal{A}$ of permitted assignments, and the observed assignment is uniform over $\mathcal{A}$ conditional on the orbit of the data under those assignments. For any real-valued statistic $T$, the upper-tail permutation $p$-value defined above satisfies $$ P(p_{\mathrm{perm}}\leq\alpha)\leq\alpha $$ for every $0\leq\alpha\leq1$.

Proof. Fix an orbit and list the $M$ statistic values from its permitted assignments in decreasing order, including repetitions: $t_{(1)}\geq t_{(2)}\geq\cdots\geq t_{(M)}$. If the observed assignment has value $t_{(r)}$, its upper-tail $p$-value counts every assignment whose statistic is at least $t_{(r)}$. That count is at least $r$, so $p_{\mathrm{perm}}\geq r/M$. Thus $p_{\mathrm{perm}}\leq\alpha$ can occur only for assignments with rank $r\leq\alpha M$. There are at most $\lfloor\alpha M\rfloor$ such ranks among the $M$ equally likely assignments. The conditional probability is therefore at most $\lfloor\alpha M\rfloor/M\leq\alpha$. Averaging over the orbits gives the stated unconditional inequality. $\square$

For independent groups with a common distribution under the null, the group labels are exchangeable conditional on the pooled observations when group sizes are fixed. The theorem then applies to any statistic computed consistently for each assignment, including a robust multivariate statistic. The theorem does not establish that a proposed robust location null creates exchangeability; that must be justified separately from the model and design.

When Unrestricted Label Permutations Fail

A null hypothesis of equal robust location does not generally imply equality of distributions. Groups may have the same center but different scatter, tail behavior, or other features. In that situation, an observation’s distribution can depend on its original group even when the location contrast is zero. The labels are then not exchangeable, so the symmetry proof above does not apply. A particular permutation test may still have acceptable behavior in a particular setting, but exact finite-sample calibration cannot be claimed from equal location alone.

Worked Example: Equal Centers but Unequal Scatter

Consider two independent groups of bivariate observations. For group 1 let $X=(\varepsilon,\eta)$, and for group 2 let $X=(10\varepsilon,\eta)$, where each of $\varepsilon$ and $\eta$ independently equals $-1$ or $1$ with probability $1/2$. Both groups have center $(0,0)$, including coordinatewise median zero. Their covariance matrices are $$ \operatorname{Var}(X\mid g=1)= \begin{pmatrix}1&0\\0&1\end{pmatrix}, \qquad \operatorname{Var}(X\mid g=2)= \begin{pmatrix}100&0\\0&1\end{pmatrix}. $$

The groups do not have the same distribution: the absolute value of the first coordinate is always 1 in group 1 and always 10 in group 2. With one observation from each group, the event that the group 1 label is attached to an observation whose first coordinate has absolute value 10 has probability zero under the actual sampling scheme. If labels were exchangeable conditional on the pooled observations, that event would have probability $1/2$, since either of the two observations could receive the group 1 label.

Thus equal centers do not make the unrestricted labels exchangeable in this example. The calculation demonstrates why the exactness argument fails; it does not imply that every statistic under every unequal-scatter model must have an inflated rejection rate. It does mean that unrestricted permutations cannot be justified as an exact test of equal robust location solely by citing that location null.

Nuisance structure creates a related limitation. For instance, if observations come from matched sets or blocks with different baseline distributions, shuffling labels across the entire data set mixes observations that are not exchangeable. If the design and null support label swaps only within each block, the valid permutation set should contain those within-block assignments, not all pooled assignments. Permuting fitted residuals in a regression setting is also not automatically exact: fitting can make residuals dependent and their distributions need not be invariant under arbitrary shuffling.

Restricted Permutations and a Blocked Example

The same symmetry principle works with a restricted set of permutations. The restriction must follow from the design or a model-based invariance condition, not from a preference for a smaller reference set. Under a blocked design, for example, one may permute labels within each block while preserving the observed number of labels of each type in that block. This is valid when the assignments are randomized within blocks under the null, or when the observations are exchangeable within each block under the null.

Worked Example: Permuting Within Blocks

There are two blocks, each containing one observation from each group. The observed group 1 vectors are $(0,0)$ and $(10,2)$; group 2 has $(2,0)$ and $(12,2)$. Use the distance between the groups’ coordinatewise medians as $T$, with the median of two values defined as their average. The observed medians are $(5,1)$ and $(7,1)$, so $T(a_0)=2$.

There are $2^2=4$ allowed assignments, because the labels can be swapped independently within either block. The observed assignment gives $T=2$. Swapping only the labels in block 2 gives medians $(6,1)$ for both groups and $T=0$. Swapping only the labels in block 1 also gives both medians $(6,1)$ and $T=0$. Swapping labels in both blocks gives medians $(7,1)$ and $(5,1)$, so $T=2$.

The restricted upper-tail $p$-value is therefore $2/4=1/2$. An unrestricted permutation would allow assignments that break the block structure and would answer a different calibration question. The validity of this restricted calculation still depends on within-block exchangeability or the relevant randomization mechanism.

Key takeaway: Robustness of a statistic does not make its permutation reference distribution valid. Exact permutation calibration comes from invariance of the observations or assignment mechanism under the permitted relabellings. Match the permutation set to that invariance.

Common Mistakes

Assuming equal location means exchangeability. Equal robust centers do not rule out different scatter or distributional shapes. Establish the needed invariance, or do not claim exact permutation validity.
Permuting across nuisance strata. If exchangeability holds only within blocks, unrestricted shuffling ignores the structure that supports the null distribution. Restrict the allowed permutations accordingly.
Keeping estimates fixed across permutations. If the statistic includes robust estimates that depend on group labels, recompute them for every assignment.
Interpreting a valid calibration as a robust statistic. Permutation addresses the reference distribution; it does not make a nonrobust statistic resistant to outliers or ensure power against every alternative.

Check Your Understanding

Use the exchangeability condition, rather than the word “permutation” alone, to assess each situation.

What distributional null and sampling condition commonly justify unrestricted two-sample label permutations?
Why does equal robust location with unequal scatter fail to establish finite-sample exactness?
In a permutation test using group-specific robust location and scatter estimates, which quantities must be recalculated for each assignment?
When is it appropriate to restrict permutations to within-block label swaps?
What does a conservative upper-tail permutation $p$-value guarantee under the stated invariance conditions, and how can ties affect it?