Why Exchangeability Is the Key Question
A permutation test does not become valid simply because labels can be rearranged on a computer. Its justification comes from a statistical claim: under the null hypothesis, the observed arrangement and the arrangements generated by the permitted permutations must be equally plausible, conditional on what is being held fixed. This requirement is exchangeability.
For marker-gene inference, a test statistic might be the difference in mean expression of a gene between cluster A and cluster B. A permutation procedure may keep expression values fixed and reassign the cluster labels, then compare the observed difference with the differences generated by the permitted reassigments. Which reassigments are permitted depends on the null and on the design. If cells differ systematically by a fixed covariate such as batch, donor, or treatment group, unrestricted shuffling can create label arrangements that would not be comparable under the null.
This tutorial concerns the validity of the permutation scheme, not whether a particular marker statistic is the best summary of expression. It also does not remove the need to account for data-adaptive cluster selection: rerunning a clustering pipeline addresses one part of that problem, but exchangeability of the permuted data under the null remains necessary.
State the Null and the Fixed Structure First
Suppose \(Y_i\) is expression of one gene in cell \(i\), \(L_i\) is its cluster label, and \(C_i\) is a fixed covariate such as batch. A useful conditional marker null is that, within each covariate stratum, the expression values have the same distribution across the labels being compared. In a two-label comparison, this can be expressed as equality of the conditional distributions of \(Y_i\) for A and B within each level of \(C_i\). For an exact label-randomization interpretation, the labels must also be exchangeable within each stratum under that null, conditional on the observed stratum membership and label counts.
This is a stronger requirement than saying that two overall means happen to be equal. If the distributions differ in spread or shape, a mean-based test can have a different null distribution from the one created by label shuffling. Likewise, if cells from one donor are correlated, treating them as independently exchangeable cells may overstate the amount of randomization. The unit that can be permuted must match the design and dependence structure.
A fixed covariate need not always be a reason to restrict permutations. The question is whether the null makes observations exchangeable across its levels. If batches have different expression distributions even under the marker null, cells cannot generally be shuffled across batches. A natural restricted scheme permutes labels separately within each batch, preserving the observed number of each label in every batch. If a batch contains only one label, it contributes no within-batch label reassignment; it cannot supply information for that conditional contrast.
A Short Justification for Restricted Permutations
The exactness argument is a symmetry argument. Let \(\mathcal{G}\) be the allowed set of permutations, and let \(T\) be the statistic. If, under \(H_0\), every arrangement in \(\mathcal{G}\) is equally likely conditional on the fixed information, then the rank of the observed statistic among the values \(\{T(g):g\in\mathcal{G}\}\) is uniform apart from discreteness and ties. Therefore, a tail proportion calculated over \(\mathcal{G}\) controls the probability of rejection at the stated level, with the usual conservative behavior from discrete p-values.
For covariate-stratified exchangeability, \(\mathcal{G}\) is the product of the permutation sets within the strata. If stratum \(b\) contains \(n_b\) cells with fixed counts \(n_{Ab}\) and \(n_{Bb}\), its label assignments number \(\binom{n_b}{n_{Ab}}\). Across independent exchangeable strata, the total number of allowed assignments is the product of these counts. The fixed counts matter: permuting labels while changing each stratum’s A/B composition does not condition on the same design information.
For a two-sided test based on a statistic \(T\) measuring A minus B, the exact permutation p-value is the fraction of allowed assignments for which the absolute permuted statistic is at least as large as the observed absolute statistic. Including equality handles ties and gives a valid, usually conservative, test for a discrete permutation distribution.
Worked Example: Exact Permutation Within Two Batches
Hypothetical data. Consider four cells in each of two batches, with two labels A and two labels B in each batch. The gene-expression values in batch 1 are \(0, 2, 6, 8\); those in batch 2 are \(1, 3, 5, 7\). Suppose the observed A cells have values \(0,2\) in batch 1 and \(1,3\) in batch 2. The observed B cells are the other two cells in each batch. We test the conditional null that labels are exchangeable within each batch, holding the expression values, batch memberships, and within-batch label counts fixed.
In batch 1, each allowed assignment chooses two of the four values for A. The A-minus-B mean difference is the sum of the A values minus half the batch total. Since the total is 16, the six possible differences are \(-6,-2,0,0,2,6\). The observed assignment \(A=\{0,2\}\) has difference \((0+2)/2-(6+8)/2=-6\).
In batch 2, the total is also 16, so the same calculation gives possible differences \(-4,-2,0,0,2,4\). In particular, the pair \(A=\{3,7\}\) gives \((3+7)/2-(1+5)/2=2\), and the pair \(A=\{3,5\}\) gives \((3+5)/2-(1+7)/2=0\). The observed assignment \(A=\{1,3\}\) has difference \((1+3)/2-(5+7)/2=-4\).
Give the two batches equal weight, as they have equal cell counts. The observed statistic is \(T=(-6+(-4))/2=-5\). There are \(\binom{4}{2}\binom{4}{2}=36\) allowed joint assignments. A permuted statistic has absolute value at least 5 only when the batch differences sum to at least 10 or at most \(-10\). Those cases are \((6,4)\) and \((-6,-4)\), two assignments in total. Thus the exact two-sided p-value is \(2/36=0.05556\). At \(\alpha=0.05\), this test does not reject the conditional null. This conclusion is not evidence that the null is true; it says only that this exact test does not find sufficient evidence against it at that threshold.
When Unrestricted Shuffling Fails
An unrestricted shuffle allows labels to move across covariate strata. If the covariate is related to expression, this can change the null distribution in a way that the observed design does not support. The problem is especially visible when label proportions differ by stratum: global shuffling can erase the relationship between label and stratum, even though that relationship is fixed in the data being analyzed.
The following example is deliberately small. It shows how a pooled difference can arise from a batch pattern even when the within-batch contrasts point in opposite directions. It is not a proof that every unrestricted test will be biased in the same direction; rather, it demonstrates why exchangeability must be checked rather than presumed.
Worked Example: Batch Imbalance Makes a Global Shuffle Inappropriate
Hypothetical data. In batch 1, the expression values are 10, 12, 14, and 16; labels A are assigned to 12, 14, and 16, while B is assigned to 10. In batch 2, values are 0, 2, 4, and 6; A is assigned to 0, while B is assigned to 2, 4, and 6. Batch 1 has a higher expression baseline than batch 2, and the label proportions differ by batch.
The pooled A mean is \((12+14+16+0)/4=10.5\). The pooled B mean is \((10+2+4+6)/4=5.5\). The pooled difference is \(10.5-5.5=5\). But the within-batch differences are \(14-10=4\) in batch 1 and \(0-4=-4\) in batch 2. The pooled comparison combines distinct batch compositions and does not represent a common within-batch contrast.
If the intended null is conditional on batch, a global label shuffle is invalid: it moves labels between batches and does not preserve the observed counts \(3\) A and \(1\) B in batch 1, and \(1\) A and \(3\) B in batch 2. A restricted shuffle keeps those counts fixed and compares labels only among cells in the same batch. The example has no basis for claiming a common direction of marker association across batches; the design and small sample make that limitation plain. A pooled statistic alone should not be interpreted as evidence of a batch-adjusted marker effect.
Choosing the Permutation Unit and Scheme
Fixed covariates can impose several kinds of restrictions. With batches, donors, or processing runs, the simplest option is often to permute within each stratum, provided there are enough observations and label variation within it. For a paired design, the exchangeable unit may be the pair, with label swaps performed within pairs. In a clustered or repeated-measures design, cells from one donor may share biological and technical effects; shuffling individual cell labels across donors can treat dependent observations as independent. In that setting, the permissible permutations may need to operate on donors or another independent experimental unit, or a model may be needed to represent the dependence.
The correct scheme also depends on how labels arose. If labels were randomly assigned within strata, the design itself can justify the corresponding randomization test under a sharp null of no effect. If labels are observational cluster assignments, exchangeability is a distributional assumption under a statistical null, not a consequence of random assignment. When clusters were formed using the same expression data, the labels can depend on the gene being tested. A simple shuffle of fixed labels does not automatically reproduce that selection. A pipeline-level permutation may address selection only if its permuted data are themselves generated under a defensible null and preserve the relevant covariates and dependencies.
| Scheme | What it preserves | When its justification may hold |
|---|---|---|
| Unrestricted label permutation | Overall A/B counts only | Labels are exchangeable across all cells under the stated null, with no unmodeled structure that changes their joint distribution |
| Within-stratum permutation | A/B counts within each fixed stratum | Labels are exchangeable among cells within strata under the conditional null |
| Block or unit-level permutation | Pairing, donor, or other dependence structure | The independent units or within-block arrangements are exchangeable under the null |
| Model-based conditional test | Covariate and dependence structure through a specified model | The model and its distributional assumptions adequately describe the null data-generating process |
Diagnostics, Alternatives, and Limits
Permutation diagnostics begin with the design, not a histogram of the resulting p-values. Tabulate label counts by batch, donor, and other fixed factors. Check whether both labels occur within the strata needed for a conditional comparison; inspect whether expression distributions visibly differ across those strata; and verify that the permutation code preserves exactly the intended counts and blocks. For small datasets, enumerate all allowed assignments when feasible and check the computed tail count directly.
A restricted scheme may have very few distinct assignments, producing a coarse p-value distribution and low power. If a stratum has no label variation, within-stratum permutations cannot identify a contrast there. If the observed label assignment is not exchangeable under the proposed null, narrowing the shuffle alone does not solve the issue: the null or design must be reconsidered. If dependence is present within donors, a cell-level permutation can still be invalid even when it is restricted by batch.
The main alternatives have different assumptions. A covariate-adjusted regression can estimate a conditional association, but its validity depends on the outcome model, link or distributional assumptions, and treatment of dependence. A stratified permutation makes fewer parametric assumptions about the statistic’s distribution, but requires within-stratum exchangeability and can be uninformative when strata are sparse. Sample splitting or an independent validation dataset can separate cluster discovery from marker testing, but it does not make an inappropriate permutation scheme valid. No method converts an association between cluster labels and expression into a causal effect without an appropriate causal design.
Common Mistakes
- Assuming that all label arrangements are equally plausible. Computation can generate a shuffle that the null does not justify. Specify the null and the fixed structure before choosing the permutation set.
- Permuting across batch while claiming a batch-conditional test. This changes the batch-specific label counts and ignores possible batch-related expression differences. Restrict permutations within batch when conditional exchangeability there is justified.
- Thinking that preserving batch alone guarantees validity. It does not address donor dependence, lack of label overlap, or labels selected from the gene expression under test. Check the whole design and the null mechanism.
- Calling a permutation p-value the probability that the null is true. It is a tail probability under the stated null and permitted permutation scheme, not a posterior probability of the null.
Check Your Understanding
For each question, state the reasoning as well as the answer. Solutions are included below.
- In a two-batch marker comparison, labels are exchangeable within batch but expression distributions differ between batches under the null. Which label permutations are justified?
- There are four cells in a stratum, two assigned label A and two label B. How many distinct assignments are included when the counts are fixed?
- Why can a permutation scheme that preserves batch still fail when cells from the same donor are dependent?
- A test reports a permutation p-value of 0.03. Give a correct interpretation, including the role of the null and the allowed shuffles.
Solutions. (1) Permute labels separately within each batch, retaining the batch-specific counts, assuming exchangeability within each batch is justified. (2) There are \(\binom{4}{2}=6\) assignments. (3) Batch restriction does not make dependent cells independently exchangeable; the permutation unit or scheme must preserve donor-level dependence, potentially by permuting independent donors or blocks. (4) Under the stated null and conditional on the fixed information, 3% of the permitted label arrangements yield a statistic at least as extreme as the observed one, using the test’s specified tail rule. It is not a 3% probability that the null is true.