Permutation Calibration for High-Dimensional Mean Tests

Why Permutation Calibration Needs an Invariance Assumption

A high-dimensional mean statistic may be easy to calculate but difficult to calibrate: its null distribution can depend on dimension, covariance structure, or dependence across coordinates. Permutation methods offer a way to generate a reference distribution by rearranging the observed data. The crucial question is not simply whether the mean is zero or whether two means are equal. It is whether the null model makes the data invariant under the rearrangements being used.

For a one-sample test, a common rearrangement changes the sign of each observation vector. For a two-sample test, it reallocates pooled observation vectors to the two groups while preserving group sizes. These operations have different assumptions. Under the appropriate invariance null, their calibration is valid in finite samples, regardless of the dimension or the choice of statistic. Under weaker null hypotheses, calibration generally needs a separate asymptotic justification.

One-Sample Sign-Flip Calibration

Let \(T(X_1,\ldots,X_n)\) be a real-valued statistic, with larger values taken as stronger evidence against the null. For a sign vector \(s=(s_1,\ldots,s_n)\in\{-1,1\}^n\), write \(sX=(s_1X_1,\ldots,s_nX_n)\). The sign-flip reference distribution consists of the \(2^n\) values \(T(sX)\). The upper-tail permutation p-value is

The statistic can target a dense or sparse departure. Examples include \(n\|\bar X\|^2\), where \(\bar X=n^{-1}\sum_i X_i\), and \(\sqrt{n}\max_{1\leq j\leq p}|\bar X_j|\). The validity argument does not require choosing one of these particular forms. It does require calculating the statistic in the same way for the observed data and every sign-flipped data set.

To prove the result, collect the observations into \(X=(X_1,\ldots,X_n)\), and let \(G=\{-1,1\}^n\) act on \(X\) by coordinatewise sign changes. Independence and central symmetry imply that \(gX\) has the same distribution as \(X\) for every \(g\in G\). For a fixed observed orbit \(\{gX:g\in G\}\), form the \(M=2^n\) statistic values \(a_g=T(gX)\), retaining repetitions. If an element \(h\) is selected uniformly from \(G\), its value \(a_h\) is one of these \(M\) values, and its upper-tail rank is

For any fixed list of \(M\) real numbers, at most \(\lfloor \alpha M\rfloor\) list positions can have upper-tail rank at most \(\alpha\): if the values are ordered from largest to smallest, positions tied at a value share a rank no smaller than the last position in that tie. Consequently, the fraction of \(h\)'s with \(r_h\leq\alpha\) is at most \(\alpha\). Since the distribution of \(X\) is invariant under every \(h\), averaging this orbit argument gives \(P(p_{\mathrm{sign}}\leq\alpha)\leq\alpha\). This proves the claim. \(\square\)

Two-Sample Label Permutations

For a statistic \(T\) measuring the difference between group means, pool the \(N\) vectors and calculate \(T\) for each of the \(\binom{N}{n_1}\) allocations to the first group. For a two-sided test, a typical choice is \(T=\|\bar X_1-\bar X_2\|\); for dense alternatives, a quadratic statistic may be used, and for sparse alternatives a maximum-coordinate statistic may be used. The p-value is the fraction of allocations whose statistic is at least as large as the observed one.

For a fixed pooled data set, list the statistic values for all \(M=\binom{N}{n_1}\) allocations, including repeated values. If the observed allocation is uniformly distributed among these allocations under the null, its upper-tail rank is the fraction of list entries at least as large as its value. As in the sign-flip proof, at most an \(\alpha\) fraction of entries can have upper-tail rank at most \(\alpha\). Conditional on the pooled data, the probability of rejection is therefore at most \(\alpha\); averaging over the pooled data gives the unconditional bound. \(\square\)

Asymptotic Calibration Beyond Exact Invariance

Sometimes the scientific null is weaker than the permutation invariance null. For example, two populations may have equal means but different covariance matrices. They are then not exchangeable, so ordinary label permutation is not a finite-sample test of equality of means. Studentizing a statistic can sometimes yield asymptotically valid permutation calibration under such a weak null, but studentization does not by itself prove validity.

For the proof, write the p-value as \(P_\pi(T_n^\pi\geq T_n\mid\text{data})\). The tie condition and uniform convergence of the conditional distribution imply that this differs from \(1-H(T_n)\) by a quantity converging to zero in probability. Since \(T_n\) converges in distribution to a variable with continuous cdf \(H\), the probability integral transform gives \(H(T_n)\xrightarrow{d}\text{Uniform}(0,1)\). Hence \(1-H(T_n)\) has the same limiting distribution, and adding a term that vanishes in probability does not change that limit. The permutation p-value is therefore asymptotically uniform. \(\square\)

This criterion states what an asymptotic argument must establish: the observed statistic and the conditional permutation distribution must converge to the same continuous limit. In high dimensions, those claims depend on the statistic and on conditions such as dimension growth, dependence across coordinates, group-size balance, and moment bounds. A result for one statistic or regime does not automatically apply to another. In particular, finite-sample invariance and asymptotic conditional convergence are distinct routes to validity.

Implementation and Common Pitfalls

When a statistic includes estimated scales, regularization parameters, or a data-driven choice among coordinates, the entire prescribed calculation must be repeated under each permutation if that choice is part of the test statistic. Holding a data-dependent choice fixed can produce a reference distribution for a different procedure than the one actually applied. Likewise, if exhaustive enumeration is impractical and permutations are sampled at random, the Monte Carlo p-value should account for the observed arrangement; a common conservative form is \((1+\#\{\text{sampled statistics at least as large as observed}\})/(B+1)\) for \(B\) sampled permutations.

Common mistake: “The two groups have equal means under the null, so their labels can be permuted freely.” This confuses a parameter restriction with distributional invariance. If their covariance structures or other distributional features differ, the labels need not be exchangeable. The correction is to use label permutations as an exact test only under exchangeability, or to establish a statistic-specific asymptotic conditional-limit result under the weaker null. For one-sample sign flips, the parallel error is to infer central symmetry from a zero mean.