Restricted Permutations for Exchangeable Designs

Why the Permutation Scheme Must Match the Design

A permutation test does not become valid merely because it shuffles labels. Its validity depends on whether the null model makes the observed data interchangeable under the shuffles being used. In a stratified study, observations from different strata may have different outcome distributions. In a clustered study, measurements within the same cluster may be dependent. Shuffling across strata or individual measurements within clusters can therefore create rearrangements that the null model does not support.

The practical rule is to define the allowed permutations from the design and null hypothesis. A valid restricted scheme shuffles only within exchangeable sets, or moves whole units such as cluster vectors when those units are exchangeable. The target also matters: permuting within strata usually assesses association beyond the strata, not marginal independence in the pooled population.

Definition: Let \(Z\) denote the observed data and let \(G\) be a finite group of transformations that rearrange the data while preserving the design. The data are exchangeable under \(G\) under the null if, conditional on the design information being held fixed, \(Z\) and \(gZ\) have the same distribution for every \(g\in G\). A restricted permutation test uses only transformations in such a group.

For example, with paired observations \((X_i,Y_i)\), a transformation may keep all \(X_i\) fixed and permute the \(Y_i\) values. If the observations are divided into strata, the allowed group may consist of permutations that move \(Y_i\) only among observations in the same stratum. For clustered data, an allowed transformation may instead reassign entire outcome vectors \(Y_c\) among exchangeable clusters, leaving each vector’s internal dependence intact.

The Finite-Sample Validity Principle

Let \(T(Z)\) be a statistic for which large values count against the null. For a finite allowed group \(G\), define the nonrandomized permutation p-value by

p(Z)=\frac{\#\{g\in G:T(gZ)\geq T(Z)\}}{|G|}.

The identity transformation is included in \(G\). Ties are counted in the tail, so this p-value is generally conservative rather than exactly uniform.

Theorem: If the null distribution of \(Z\), conditional on the fixed design information, is invariant under every \(g\in G\), then the permutation p-value above satisfies \(P(p(Z)\leq\alpha)\leq\alpha\) for every \(0\leq\alpha\leq1\). Thus rejecting when \(p\leq\alpha\) controls the Type I error at level \(\alpha\).

Proof. Fix an orbit \(\mathcal O=\{gZ:g\in G\}\). Under group invariance, conditional on this orbit, the observed point has the same distribution as a point obtained by applying a uniformly selected group element to it. Equivalently, the permutation statistic values \(T(gZ)\), counted with their multiplicities over \(g\in G\), determine the conditional p-value distribution.

Order those \(|G|\) values from largest to smallest, retaining ties. For any value in a tied group, its p-value is the number of values at least as large, divided by \(|G|\). If the cumulative number of values through a tied group is \(r\), every point in that group has p-value \(r/|G|\). Consequently, the number of points whose p-value is at most \(\alpha\) is either zero or the cumulative size \(r\) of a group satisfying \(r/|G|\leq\alpha\). In either case that number is at most \(\alpha|G|\). The conditional rejection probability is therefore at most \(\alpha\). Averaging over the orbits gives the stated bound. \(\square\)

A useful sufficient condition for stratified tests is the following. Conditional on fixed stratum labels and the \(X_i\), suppose the \(Y_i\) are independent within and across strata, and within each stratum they have a common distribution that does not depend on \(X_i\). Then the assignments of the observed \(Y\) values to the \(X\) values are exchangeable separately within each stratum. This condition gives a direct basis for within-stratum permutations; the group-invariance theorem gives the validity conclusion.

Worked Examples: Constructing the Allowed Group

Worked Example: A Stratified Association Statistic

There are two strata, each with two observations. In each stratum the fixed \(X\) values are \(0,1\). The observed \(Y\) values are \((1,3)\) in stratum A and \((2,4)\) in stratum B. Use the statistic \(T=\sum_b\sum_{i\in b}(X_i-\bar X_b)(Y_i-\bar Y_b)\), and use \(|T|\) for a two-sided test.

In stratum A, \(\bar X_A=0.5\), \(\bar Y_A=2\), so the contribution is \((-0.5)(-1)+(0.5)(1)=1\). In stratum B, \(\bar X_B=0.5\), \(\bar Y_B=3\), and the contribution is also \((-0.5)(-1)+(0.5)(1)=1\). Thus \(T=2\) and \(|T|=2\).

The allowed group independently swaps the two \(Y\) values within each stratum, giving \(2!\times2!=4\) transformations. In each stratum the contribution is \(1\) if the values are in increasing order and \(-1\) if they are reversed. Hence the four possible values of \(T\) are \(2,0,0,-2\). Exactly two have \(|T|\geq2\), so \(p=2/4=0.5\). Permuting across strata is not justified by this design-based scheme: the two strata have different observed outcome sets.

Worked Example: Permuting Whole Cluster Vectors

Suppose three exchangeable clusters each contribute a scalar \(X_c\) and a two-component outcome vector \(Y_c\). Let \(X=(1,2,3)\), and let the observed vectors be \(Y_1=(1,0)\), \(Y_2=(0,3)\), and \(Y_3=(2,0)\). Consider the statistic \(T=\sum_c(X_c-2)(s_c-2)\), where \(s_c\) is the sum of the two components of \(Y_c\).

The observed vector sums are \((1,3,2)\), so \(T=(-1)(1-2)+0(3-2)+1(2-2)=1\). Under the null that whole outcome vectors are exchangeable across these clusters, the allowed group has \(3!=6\) elements. The sums being reassigned are \(1,3,2\), or, after centering by 2, \(-1,1,0\).

For any reassignment, the statistic is the centered sum assigned to cluster 3 minus the centered sum assigned to cluster 1; cluster 2 has coefficient zero. Of the six ordered choices for those two clusters, the differences are \(1,2,-1,1,-2,-1\). Three are at least the observed value \(1\), so the one-sided permutation p-value is \(3/6=0.5\). The operation moved each two-component vector intact; it did not split its components across clusters.

In a clustered design, the word “block” must be used carefully. A cluster may be a unit that can be exchanged with other clusters, while its member-level observations remain dependent. Permuting individuals within that cluster is not justified by cluster-level exchangeability. If clusters differ in size or structure, a whole-cluster permutation may also be invalid unless the permitted transformation preserves those features and the null distribution is invariant under it.

How Unrestricted Permutations Can Miscalibrate a Test

The following finite example shows anti-conservative behavior under a conditional null. There are two strata, each of size two. The \(X\) values in stratum A are \((-1,1)\), and those in stratum B are \((0,0)\). In stratum A, the two \(Y\) values are \(+a\) and \(-a\), for a fixed \(a>0\), assigned to the two observations in either order with equal probability. In stratum B, both \(Y\) values are zero. Thus the assignment of \(Y\) within each stratum is exchangeable and unrelated to \(X\) under the null.

Worked Example: Pooled Shuffling Rejects Too Often

Use \(T=\sum_b\sum_{i\in b}(X_i-\bar X_b)(Y_i-\bar Y_b)\), and reject for large \(|T|\). In stratum B the \(X\) values are both zero, so its contribution is zero. In stratum A, whichever observation receives \(+a\), the contribution is \(2a\) or \(-2a\). Therefore the observed \(|T|\) is always \(2a\) under the null.

With the valid restricted group, only the two assignments of \(+a,-a\) within stratum A are allowed; stratum B is unchanged. Both assignments have \(|T|=2a\), so the two-sided p-value is \(2/2=1\). This particular statistic and design have no ability to distinguish the two assignments, but the test does not falsely reject.

Now incorrectly permute the four pooled \(Y\) values \((+a,-a,0,0)\) over the four \(X\) positions. There are \(4!/2!=12\) distinct assignments. The statistic has absolute value \(2a\) only when \(+a\) and \(-a\) occupy the two stratum-A positions, which happens in 2 of the 12 assignments. For the observed \(|T|=2a\), the unrestricted p-value is therefore \(2/12=1/6\). At nominal level \(0.2\), this procedure rejects for every possible assignment generated by the null, so its Type I error is \(1\), not at most \(0.2\). The pooled values are not exchangeable across strata: the unrestricted group has manufactured a reference distribution that does not match the null assignment mechanism.

This example concerns a conditional, within-stratum null. It does not say that pooled permutations are always wrong. If the scientific target is marginal independence and the observations really are exchangeable across the full sample under that null, unrestricted permutations may be appropriate. But if strata affect outcome distributions, a pooled shuffle generally does not test that conditional null. The null hypothesis and the permutation group must describe the same invariance.

Common Mistakes and a Practical Check

Permuting because the test is called a permutation test. The correction is to identify the null invariance first, then use only transformations that preserve it.
Permuting across strata while testing within-stratum association. If outcome distributions can vary by stratum, preserve each stratum’s membership during the shuffle.
Breaking a cluster into individual observations. If dependence is within the cluster, move the whole cluster vector when clusters themselves are exchangeable; do not treat its components as independent exchangeable units.
Confusing conditional and marginal independence. Within-stratum shuffling assesses association beyond the stratum structure. It does not by itself establish marginal independence in the pooled population.
Assuming a restricted scheme is automatically valid. The transformation must still be justified by the null model. Unequal cluster distributions, changing cluster sizes, or additional design constraints can require a different group.

Key takeaway: A permutation test is exact when the null makes the data invariant under its allowed transformations. For stratified data, preserve strata; for clustered data, preserve dependent clusters as intact units. The restriction is part of the statistical model, not a computational preference.

Check Your Understanding

For each question, identify the relevant invariance before deciding what can be shuffled.

In a stratified study, what condition on the outcome distributions supports permuting outcomes within each stratum?
Why does the group-invariance theorem imply a conservative p-value when ties are counted in the permutation tail?
Three clusters have two measurements each, and measurements within a cluster may be dependent. What should be moved if the clusters are exchangeable?
In the pooled-shuffling example, why is the pooled set of four \(Y\) values not exchangeable across all four \(X\) positions?
Does a within-stratum permutation test automatically test marginal independence? Explain the distinction.