Within-Stratum Permutation for Association Calibration

Why Permute Phenotypes Within Strata?

Ancestry strata can differ in both allele frequencies and disease prevalence. If case labels are shuffled across the whole sample, a permutation can disrupt the relationship between ancestry and case status that was present in the observed data. The resulting reference distribution may therefore fail to represent the null hypothesis relevant to a stratification-controlled association test.

Within-stratum phenotype permutation addresses this by keeping the observed ancestry group, genotype, and number of cases in each stratum fixed. It tests whether the observed arrangement of case labels among genotypes is unusually associated, given those stratum-specific case counts. The procedure is only valid when the phenotype labels are exchangeable within each stratum under the null; preserving counts alone does not guarantee validity.

Definition: In within-stratum phenotype permutation, genotypes and stratum memberships are held fixed, and phenotype labels are reassigned only among individuals in the same stratum. For a binary case-control phenotype, the reassignment preserves the observed number of cases in every stratum.

The Permutation Set and Test

Let $G_i$ denote the genotype for individual $i$, $Y_i$ the binary phenotype (1 for a case and 0 for a control), and $S_i$ the individual’s ancestry stratum. In stratum $s$, let $n_s$ be the number of individuals and $k_s=\sum_{i:S_i=s}Y_i$ the observed number of cases. A permissible reassignment changes which individuals are cases but keeps $k_s$ fixed for every stratum.

Write $\Omega$ for the set of all permissible assignments. If there are $S$ strata and assignments are unrestricted within each one, the number of assignments is

|\Omega|=\prod_{s=1}^{S}\binom{n_s}{k_s}.

A test statistic $T(G,Y,S)$ measures association while accounting for strata. It could be a stratum-adjusted score or another statistic chosen before examining the permutation results. For a two-sided test based on a signed statistic, a common extremeness measure is $|T|$. The observed statistic is compared with the statistic from every permissible assignment, or with a random sample of them.

Exact permutation p-value: For a prespecified extremeness measure $E(T)$, the exact conditional p-value is $$ p_{\mathrm{perm}}= \frac{\#\{Y^*\in\Omega:E(T(G,Y^*,S))\ge E(T(G,Y,S))\}}{|\Omega|}. $$ The comparison includes ties. The p-value is the proportion of permissible assignments at least as extreme as the observed assignment, conditional on the fixed genotypes, strata, and stratum-specific case counts.

This is a conditional calibration: it does not claim to describe every possible population or sampling design. Its validity rests on the null distribution making all assignments in $\Omega$ equally likely, or on a permutation scheme that correctly represents their relative probabilities.

Worked Examples

Worked Example: Constructing the Permissible Assignments

Suppose a hypothetical sample has two ancestry strata. Stratum A has four people, two cases and two controls; stratum B has three people, one case and two controls. List the number of permissible label assignments and show one valid reassignment.

In stratum A, the two case labels can be assigned to any two of four people, giving $\binom{4}{2}=6$ assignments. In stratum B, the one case label can be assigned to any one of three people, giving $\binom{3}{1}=3$ assignments. Choices in the strata combine independently, so

|\Omega|=\binom{4}{2}\binom{3}{1}=6(3)=18.

For example, suppose the original case labels in A are on people A1 and A2, and in B on B1. A valid reassignment could put the A cases on A3 and A4 and the B case on B3. It still has two cases in A and one in B. Assigning three cases to A and none to B would not be permissible, even though the overall number of cases would remain three.

Worked Example: An Exact Two-Sided Permutation p-Value

Consider two hypothetical strata, each with four individuals and two cases. In each stratum, two individuals carry a genotype coded $G_i=1$ and two have $G_i=0$. Define $U_s$ as the number of carriers among the cases in stratum $s$, and use the centered statistic

D=\sum_{s=1}^{2}\left(U_s-\frac{k_s}{n_s}\sum_{i:S_i=s}G_i\right).

Here $k_s/n_s=2/4=0.5$, and the total genotype count in each stratum is 2. The expected case-carrier count under uniform reassignment is therefore $0.5(2)=1$ in each stratum. Suppose the observed cases include both carriers in A ($U_A=2$) and one carrier in B ($U_B=1$). Then

D_{\mathrm{obs}}=(2-1)+(1-1)=1.

Within either stratum, the two cases are a uniform selection of two from four people, of whom two are carriers. Thus $U_s$ has probabilities $1/6,4/6,1/6$ for values 0, 1, and 2, respectively. The centered contribution $U_s-1$ consequently takes values $-1,0,1$ with those probabilities. The two strata are permuted independently, so

P(D=0)=\left(\frac{1}{6}\right)^2+ \left(\frac{4}{6}\right)^2+ \left(\frac{1}{6}\right)^2 =\frac{18}{36}=\frac{1}{2}.

For a two-sided test using $|D|$, all assignments with $D\ne0$ are at least as extreme as the observed $|D_{\mathrm{obs}}|=1$. Therefore $p_{\mathrm{perm}}=1-P(D=0)=0.5$. This small example gives little evidence against the null; the value is not the probability that the null hypothesis is true.

Worked Example: A Monte Carlo Permutation p-Value

Suppose a hypothetical study has 10 cases among 20 people: stratum A contains 8 cases among 10 people, and stratum B contains 2 cases among 10 people. A prespecified stratified association statistic has observed absolute value 2.31. Instead of enumerating every permissible assignment, the analyst draws $B=999$ random assignments uniformly from the within-stratum permutation set and recalculates the statistic each time. Suppose 47 of the 999 simulated statistics have absolute value at least 2.31.

Using the standard plus-one estimate, the Monte Carlo p-value is

\hat p_{\mathrm{MC}}=\frac{b+1}{B+1} =\frac{47+1}{999+1} =\frac{48}{1000}=0.048.

The plus-one calculation accounts for the observed assignment along with the simulated assignments and avoids reporting a p-value of zero merely because none of a finite number of random draws was as extreme. Under the specified two-sided test, this result is just below a significance level of $\alpha=0.05$. It is a Monte Carlo approximation, so its precision depends on the number of draws; it is not an exact enumeration of all assignments.

Why the Exchangeability Condition Matters

The central assumption is within-stratum exchangeability under the null: conditional on the fixed genotypes, stratum memberships, and observed case count in each stratum, the phenotype labels are equally likely to occupy any of the $k_s$-case allocations in stratum $s$. In formal terms, the conditional distribution of $Y$ is invariant to every permutation of labels within a stratum that preserves its case count.

One setting where this condition is plausible is a case-control sample in which, under the null, case status is independent of genotype within each stratum, and selection into the study is uniform among cases and uniform among controls within each stratum. Conditioning on the sampled case count then leaves the case labels exchangeable among the individuals in that stratum. In a population-based setting, equal case probabilities for individuals within a stratum under the null can also support this conditional exchangeability.

Exchangeability is stronger than saying that cases and controls have the same average genotype under the null. For example, if individuals within a stratum have different disease risks because of age, sex, or an environmental exposure associated with genotype, their labels are not generally interchangeable. A permutation that ignores such differences can produce an incorrect reference distribution. The analysis must incorporate relevant covariates using a valid conditional or model-based procedure; simply shuffling labels within broad ancestry groups does not adjust for every source of structure.

Similarly, related individuals may have correlated phenotypes, so arbitrary individual-level shuffling can break the dependence structure. A valid scheme may need to permute clusters or otherwise preserve the dependence assumed by the null model. Strata should also be defined independently of the tested phenotype and, where possible, without using the tested marker in a way that makes the assignments nonexchangeable. A permutation test cannot repair poorly chosen strata, residual ancestry confounding, or a statistic that does not match the intended null.

A Short Justification of Exact Calibration

Under the null exchangeability condition, the observed assignment is uniformly distributed over $\Omega$, conditional on the fixed information. Order the assignments by their extremeness $E(T)$. For a threshold $a$, the event $p_{\mathrm{perm}}\le a$ can occur only when the observed assignment falls among the most extreme assignments whose cumulative fraction is at most $a$. The number of such assignments cannot exceed $a|\Omega|$. Consequently,

P_{H_0}(p_{\mathrm{perm}}\le a\mid G,S,\{k_s\})\le a.

This is the defining type-I error control property of a valid p-value; discreteness and ties typically make the test conservative rather than anti-conservative. The argument depends on uniform conditional assignment probabilities. If that distributional condition fails, counting assignments equally need not control the type-I error rate.

Fix the conditioning information.
Record genotypes, stratum memberships, and the observed case count $k_s$ in every stratum.

Check the null and exchangeability.
Ask whether case labels are interchangeable within each stratum under the null, accounting for sampling, covariates, and dependence.

Choose and calculate the statistic.
Specify the stratification-aware association statistic and its one- or two-sided extremeness rule before looking at the permutation distribution.

Permute and calibrate.
Enumerate permissible assignments or draw them uniformly, recalculate the statistic, and report the exact or plus-one Monte Carlo p-value.

Common Pitfalls and Practical Interpretation

Shuffling cases across the whole sample. This can change the number of cases in each ancestry stratum. Permute separately within strata so each $k_s$ remains fixed.
Assuming preserved case counts prove validity. The counts define the assignments, but validity additionally requires exchangeability within each stratum under the null.
Reporting $b/B$ when no draw is extreme. A finite simulation with $b=0$ does not establish a zero p-value. Use $(b+1)/(B+1)$ for the Monte Carlo estimate.
Interpreting a permutation p-value as a null probability. A p-value describes how often an equally or more extreme result occurs under the specified conditional null procedure. It is not the probability that the null hypothesis is true.
Using a two-sided rule after seeing the result. Define extremeness in advance, such as $|T|$ for a signed statistic, so the permutation comparison matches the stated hypothesis.

Within-stratum permutation is useful when the null distribution should preserve the observed ancestry-specific case proportions rather than treat the pooled sample as exchangeable. It supplies a calibration for a chosen association statistic, not a substitute for choosing appropriate strata, controlling relevant covariates, or checking the assumptions that justify rearranging labels.

Check Your Understanding

Answer each question using the definitions and conditions above.

A study has 12 cases among 30 individuals in stratum A and 4 cases among 20 in stratum B. Which counts must remain unchanged in every permissible binary-phenotype permutation?
If strata have sizes 5 and 6, with 2 and 3 cases respectively, how many permissible assignments are there?
Why can a phenotype permutation within ancestry strata still be invalid when age affects disease risk and age varies within each stratum?
In a two-sided test, 22 of 499 simulated statistics are at least as extreme as observed. Calculate the plus-one Monte Carlo p-value.
What does exchangeability require about phenotype assignments within a stratum, conditional on the observed case count?