Restricted Permutations for Paired and Clustered Designs

Why the Permutation Set Must Reflect the Design

A permutation test is only as defensible as the transformations it allows. In paired data, the two measurements on a subject are linked; in clustered data, observations from the same cluster may be linked; and in a restricted experiment, treatment labels may have been assigned subject to fixed counts or other constraints. Permuting individual rows without regard to these features can create arrangements that the design could never produce.

The central task is to specify a set of admissible transformations and explain why the null hypothesis makes those transformations valid. There are two common justifications. In a randomized experiment, the set comes from the assignment mechanism, and a sharp null fixes the outcomes that would be observed under every assignment. In an exchangeability argument, the null distribution of the data must be invariant under the transformations. These justifications are related, but they are not interchangeable.

Paired Differences and Sign Flips

For pair \(i\), let \(X_i\in\mathbb{R}^q\) be the first measurement vector and \(Y_i\in\mathbb{R}^q\) the second. Define the paired difference \(D_i=Y_i-X_i\). Pairing is retained by analyzing the difference vector, rather than treating the \(X_i\)'s and \(Y_i\)'s as two unrelated samples. A sign flip of pair \(i\) replaces \(D_i\) by \(-D_i\), which corresponds to swapping the two measurements in that pair.

For \(m\) pairs, write \(D=(D_1,\ldots,D_m)\). A sign vector \(s=(s_1,\ldots,s_m)\in\{-1,1\}^m\) acts by \(sD=(s_1D_1,\ldots,s_mD_m)\). Independent sign flips are justified by the distributional condition that \(D\) and \(sD\) have the same distribution for every \(s\). Mutual independence of the \(D_i\)'s and central symmetry of each \(D_i\) are sufficient for this condition, but joint sign invariance can hold without independence.

A zero mean alone is not enough. For example, let a scalar difference \(D_i\) equal \(-1\) with probability \(0.9\) and \(9\) with probability \(0.1\). Then \(E[D_i]=-0.9+0.9=0\), but the distribution is not invariant under sign reversal: it assigns positive probability to \(-1\) and \(9\), not to their sign-reversed counterparts with matching probabilities. A sign-flip reference distribution is not justified by the mean-zero condition in this example.

Restricted Labels Within Strata

Suppose units are divided into prespecified strata and treatment assignment is restricted within each stratum. For example, an experiment may assign exactly one of two units in every stratum to treatment. Under a sharp null hypothesis—each unit's outcome is unchanged by treatment—the observed outcomes can be held fixed while treatment labels are reassigned only in ways allowed by the design. Permuting labels across strata would generally violate the assignment mechanism.

The same principle applies when a distributional exchangeability argument is used rather than a randomized assignment. Units may be permuted within a stratum only when the null makes their labels or observations exchangeable there. The strata must be defined independently of the outcomes being tested, and the permitted rearrangements must preserve any fixed counts or other design restrictions.

Clusters: Move the Randomization Unit as a Whole

When treatment is assigned to clusters, the cluster—not each person or measurement within it—is the assignment unit. Under a sharp null, one may reassign treatment labels among clusters according to the actual cluster-level assignment scheme, while keeping each cluster's full outcome vector together. If treatment is instead randomized among individuals separately within each cluster, labels may be reassigned within each cluster subject to its own assignment restrictions. Which scheme is appropriate depends on how treatment was assigned.

For a distributional permutation argument, the corresponding requirement is exchangeability at the unit being permuted. If whole cluster vectors are exchangeable under the null, permute whole vectors. Shuffling individual observations across clusters would additionally assume that those observations can be exchanged across cluster membership, which need not be true. In particular, a cluster-level treatment assignment does not justify row-level permutations simply because the data table has one row per individual.

When an Orbit-Based Test Is Valid

The finite-group result below formalizes the distributional justification for restricted transformations. It also clarifies what the conditional permutation calculation means. Let \(G\) be a finite group acting measurably on a data object \(D\), and suppose the null distribution is invariant: \(gD\) has the same distribution as \(D\) for every \(g\in G\). Let \(T\) be a real-valued statistic. Define the inclusive upper-tail orbit proportion \(p(D)=|G|^{-1}\sum_{g\in G} I\{T(gD)\geq T(D)\}\).

Proof. Let \(U\) be independent and uniform on \(G\). By invariance, \(UD\) has the same distribution as \(D\). For every fixed \(d\), \(Ud\) is uniform over the distinct points of its finite orbit, since each point has the same number of preimages in \(G\); also, \(p(x)\) is constant across that orbit.

For fixed \(d\), list the \(N\) distinct orbit points in decreasing order of their statistic, grouping ties together. Each point in a tied block has \(p\)-value equal to the cumulative size of that block and all preceding blocks, divided by \(N\); thus the points with \(p\)-values at most \(\alpha\) comprise complete initial blocks, of total size \(k\) with \(k/N\leq\alpha\). Therefore \(P\{p(UD)\leq\alpha\mid D=d\}\leq\alpha\). Since \(UD\) and \(D\) have the same distribution, \(P\{p(D)\leq\alpha\}\leq\alpha\). \(\square\)

For a uniformly randomized finite assignment set under a sharp null, the same counting argument gives the randomization reference distribution conditional on the fixed potential outcomes. For a distributional invariance argument, the unconditional distribution of \(T(UD)\) equals that of \(T(D)\), where \(U\) is independently and uniformly selected from \(G\). Conditional on the observed \(D\), however, the sign-flip or permutation distribution is an orbit-based reference distribution; it can justify a valid randomization test under the stated invariance, but it need not equal the unconditional null distribution.

Choosing and Reporting the Transformations

A useful way to construct a scheme is to name the unit that may move, the restrictions it must obey, and the null argument that makes the movement valid. The transformation set should be fixed before inspecting which arrangement gives the most favorable result. For Monte Carlo approximations to a large set, the sampled transformations must still come from the correct restricted set; computational sampling cannot repair a wrongly specified set.

Common Pitfalls and Why the Distinction Matters

The most common error is to treat any rearrangement as harmless under a vague null such as “no effect.” A zero average paired difference does not imply sign symmetry. Equal marginal distributions do not, by themselves, justify arbitrary permutations of dependent observations. And a cluster-randomized design does not permit individual-level treatment-label shuffling. Each of these mistakes changes the reference set and therefore changes the test.

A second error is to say that the conditional permutation distribution “is the null distribution.” Under a valid invariance condition, the orbit-based test can control rejection probability, as the theorem shows. But for a particular observed data set, its orbit may contain fewer values or a different range than the marginal null distribution. Validity of the test does not require those two distributions to be identical.