Why Exchangeability Determines Permutation Validity
A permutation test compares an observed association statistic with statistics obtained after rearranging the data under a null hypothesis. The arithmetic of the rearrangement is usually straightforward; the harder question is whether those rearrangements represent outcomes that could have occurred under the null. If subjects differ systematically in ancestry, recruitment site, or family membership, an unrestricted shuffle can create combinations that the study design or the null model does not permit.
In genetic association data, let \(G_i\) denote a genotype or genotype vector, \(Y_i\) a phenotype, and \(C_i\) measured covariates for subject \(i\). A permutation scheme rearranges one or more of these quantities across subjects. Its validity depends on which quantities are held fixed, which are rearranged, and whether the null distribution is invariant to those rearrangements.
For example, under a simple null of no association in a homogeneous sample of unrelated subjects, the phenotype values may be exchangeable across subjects conditional on the observed genotypes and on the multiset of phenotype values. If covariates affect the phenotype, however, exchanging phenotype values between people with very different covariates may no longer preserve their joint distribution. The correct response is not automatically to shuffle more carefully; it is to state the null model and find a rearrangement that preserves its relevant structure.
Phenotype and Genotype Permutations
In a phenotype permutation, the observed phenotypes are reassigned to subjects while genotypes remain attached to their original subjects. This is appropriate when, under the null and conditional on the design features being preserved, phenotype labels or values are exchangeable across the subjects being shuffled. For binary phenotypes, a common scheme holds the number of cases fixed and permutes the case labels.
In a genotype permutation, genotype observations are reassigned while phenotypes remain fixed. This requires the genotypes being permuted to be exchangeable across the subjects, conditional on the variables and sampling scheme being held fixed. In a study with multiple markers, it is often important to permute each subject's whole genotype vector as a unit. Permuting markers independently would break the observed linkage disequilibrium structure and could produce unrealistic joint genotype patterns.
Phenotype and genotype permutations are not interchangeable by default. In observational studies, genotype distributions can differ by ancestry, while phenotypes can differ by site or covariates. The data-generating process, rather than a preference for one type of shuffle, determines which rearrangement can be justified. If neither raw phenotype nor genotype values are exchangeable, a standard unrestricted permutation is not made valid merely by increasing the number of permutations.
Exactness: A Short Justification
The reason exchangeability matters can be seen directly. Let \(\mathcal{G}\) be the set of allowed rearrangements and let \(T_{\mathrm{obs}}\) be the observed statistic. Under the null, suppose each arrangement in \(\mathcal{G}\) is equally likely conditional on the fixed data features. Then the observed arrangement has no privileged position among the arrangements in \(\mathcal{G}\). Its rank, using the statistic values from all allowed arrangements and counting ties as at least as extreme, is therefore uniform or conservative. Consequently, the proportion of allowed arrangements with statistic at least as extreme as \(T_{\mathrm{obs}}\) is a valid conditional p-value.
This argument requires the stated invariance. If subjects with different covariates have different phenotype distributions, then some unrestricted phenotype arrangements are more probable under the null than others. Counting them equally no longer gives the correct null rank argument. Restricted permutations work by defining \(\mathcal{G}\) to contain only rearrangements that preserve the relevant design features, provided exchangeability holds within those restrictions.
Worked Example: An Exact Phenotype-Permutation Test
Consider six hypothetical unrelated subjects, three with a genotype coded as carrier and three as noncarrier. The binary phenotype has three cases and three controls. Suppose all three cases are observed among carriers. Let \(S\) be the number of cases assigned to the three carrier subjects, and use the statistic \(T=|S-1.5|\). Assume the null model makes the six phenotype labels exchangeable across subjects.
There are \(\binom{6}{3}=20\) equally likely assignments of the three case labels. For a given value \(s\), the number of assignments with \(S=s\) is \(\binom{3}{s}\binom{3}{3-s}\). Thus the counts for \(S=0,1,2,3\) are \(1,9,9,1\), respectively, and their probabilities are those counts divided by 20.
The observed value is \(S=3\), so \(T_{\mathrm{obs}}=|3-1.5|=1.5\). A permutation is at least as extreme when \(|S-1.5|\geq1.5\), which occurs for \(S=0\) or \(S=3\). Therefore,
Under the assumed exchangeability, the exact two-sided permutation p-value is 0.1000. This calculation does not establish that the null is true; it measures how often a statistic at least this extreme occurs under the specified conditional null. If the subjects differed in a way that made phenotype labels nonexchangeable, the same arithmetic would not justify this p-value.
Covariates and Population Structure
Covariates can invalidate unrestricted permutations because they can change the distribution of the phenotype, genotype, or both. For example, if phenotype prevalence differs across recruitment sites, cases are not equally likely to occupy every subject position under the null. If allele frequencies differ by ancestry, genotype rows are not generally exchangeable across ancestry groups. A global shuffle can then erase the relationship of these variables to site or ancestry, creating a reference distribution that does not match the null model.
A common remedy is restricted permutation: shuffle only within groups that are sufficiently homogeneous for the relevant exchangeability assumption, such as recruitment site, ancestry stratum, or matched set. The group definition must follow the design and null model. Creating many arbitrary groups can leave too few rearrangements for useful inference, and blocking on a variable does not solve unmodelled dependence within or between blocks.
Adjusting a regression model for covariates and then freely permuting its raw residuals is not automatically exact. Residuals from fitted models can have different variances and dependencies, and fitting the model changes their joint distribution. Residual-permutation procedures can be useful under specified conditions, but their validity needs a separate justification; “the model included the covariate” is not that justification.
Worked Example: Why Permute Within Strata
Suppose eight hypothetical unrelated participants come from two ancestry strata, with four participants in each. In each stratum, two are carriers and two are noncarriers; two participants are cases and two are controls. The observed cases are both carriers in each stratum, so the total overlap \(S\) is four. Use \(T=|S-2|\), where 2 is the expected overlap under a global allocation of four cases among eight participants.
Under the null of no association conditional on ancestry, suppose case labels are exchangeable within each stratum, but not across strata because phenotype distributions may differ between them. Within one stratum, there are \(\binom{4}{2}=6\) assignments of two case labels. The overlap \(S_j\) between the two cases and two carriers is 0, 1, or 2, with assignment counts 1, 4, and 1.
For the two strata, the restricted scheme combines their assignments, giving \(6\times6=36\) equally likely arrangements. The observed total \(S=4\) has \(T_{\mathrm{obs}}=|4-2|=2\). The equally extreme lower-tail arrangement has \(S=0\), requiring zero overlap in both strata. Each of \(S=4\) and \(S=0\) has one arrangement out of 36, so
If all eight subjects were shuffled together, the corresponding extreme probability would be \(\{ \binom{4}{4}\binom{4}{0}+\binom{4}{0}\binom{4}{4}\}/\binom{8}{4}=2/70=0.02857\). That smaller value is not justified by the stated null, because it treats cases as exchangeable across ancestry strata. Restricting permutations preserves the stratum-specific case counts and gives a reference distribution consistent with the assumption made here.
Related Samples and Dependence
Related subjects share genetic material and may also share environments. Their observations are therefore not generally exchangeable with those of unrelated subjects. Shuffling phenotypes among all members of a pedigree, or swapping genotype rows between families, can destroy the dependence structure that the null model should retain. A permutation scheme that ignores this dependence can produce misleadingly small or large p-values.
A restriction within family is justified only if the members being permuted are exchangeable under the null after conditioning on the relevant family features. For instance, swapping phenotype labels within a matched sibling pair may be appropriate for a within-pair analysis if the null makes the two siblings' phenotype assignments symmetric conditional on the pair's observed outcomes. It is not automatically valid when siblings differ systematically in age, sex, role, or environment. When no defensible exchangeability group exists, use an analysis that models the dependence, or a null simulation procedure that preserves the family structure, rather than an unrestricted shuffle.
Worked Example: A Within-Pair Permutation
In a hypothetical study, four sibling pairs are discordant for a binary phenotype, with one case and one control in each pair. For each pair, define \(d_f\) as the case sibling's allele count minus the control sibling's allele count. Suppose the observed differences are \(2,1,1\) for three informative pairs; the fourth pair has equal allele counts and contributes zero. Use \(T=|\sum_f d_f|\), so \(T_{\mathrm{obs}}=|2+1+1+0|=4\).
Assume that, under the null and conditional on each pair's two allele counts and discordant phenotype status, the case label is equally likely to be on either sibling. The three nonzero pair differences can therefore have either sign, giving \(2^3=8\) equally likely sign arrangements; the zero difference does not change the statistic. The largest possible absolute sum is four. Exactly two arrangements, with all three nonzero signs positive or all three negative, have absolute sum at least four. Thus,
This is a valid conditional calculation only under the stated within-pair symmetry assumption. It does not make all relatives exchangeable, nor does it license shuffling siblings across families. If pair members are not exchangeable, this sign-permutation reference distribution is not justified.
Choosing a Scheme for Genetic Tests
The following questions help make the permutation assumption explicit before calculating a p-value:
Identify whether the test concerns phenotype–genotype association conditional on covariates, or another specified null. State what the statistic measures.
For phenotype permutation, keep genotypes and design features fixed. For genotype permutation, keep phenotypes and relevant covariates fixed. Explain why the quantity being rearranged is exchangeable under the null.
Respect strata, matching, and family clusters when the null requires them. If testing multiple markers jointly, permute genotype vectors together when preserving linkage disequilibrium is necessary.
If residual dependence or nonexchangeable covariates remain, do not treat a convenient shuffle as exact. Use a model-based or structure-preserving null procedure with its assumptions stated.
For a genome-wide maximum-statistic procedure, the same valid rearrangement should be applied jointly across the tested markers in each permutation so the dependence among marker statistics is represented. This is why preserving multilocus genotype structure can matter. The maximum-statistic calculation cannot repair an invalid exchangeability assumption: it calibrates the chosen family of statistics only relative to the permutation distribution supplied to it.
Common Mistakes and an Arithmetic Check
- Assuming the null makes everyone exchangeable. No association does not imply identical phenotype distributions across sites, ancestry groups, or families. State the conditioning variables and restrict the shuffles when justified.
- Calling a covariate-adjusted analysis automatically permutation-valid. Adjustment in a fitted model does not prove residual exchangeability. The permutation or simulation scheme needs its own assumptions.
- Permuting individual markers independently. This can break linkage disequilibrium. When the joint marker structure is part of the null reference, rearrange whole subject genotype vectors.
- Assuming any within-family swap is valid. Family membership alone does not guarantee symmetry between relatives. Justify exchangeability within the particular units being swapped.
- Making a threshold-arithmetic error. For a statistic \(T=|2S-21|/2\), the condition \(T\geq3\) implies \(|2S-21|\geq6\), because \(2\times3=6\). For integer \(S\), this is \(S\leq7\) or \(S\geq14\). Using 9 instead of 6 would change which permutations count as extreme and therefore give the wrong p-value.
Check Your Understanding
For each question, identify the exchangeability claim that would need to be justified.
- In a phenotype-permutation test, why might freely shuffling case labels across recruitment sites be invalid even under no genetic association?
- A genotype-permutation analysis includes several markers in linkage disequilibrium. What should be permuted together, and why?
- What condition makes a restricted within-stratum permutation valid, and what does restriction fail to fix if dependence remains within strata?
- Why is permuting fitted-model residuals not automatically exact after covariate adjustment?
- In the sibling-pair example, what symmetry assumption justifies swapping case and control labels within a pair?