Paired Permutation Tests by Sign Flipping

Why Paired Differences Need Their Own Test

When measurements come in pairs, the meaningful information is often the difference within each pair. For example, a hypothetical group of patients might have a measurement taken before and after a treatment. Comparing the two sets of measurements as if they came from unrelated people would discard the pairing. Instead, choose a consistent direction, such as after minus before, and analyze the resulting differences.

A paired sign-flipping test asks whether the observed differences are unusually far from zero under a null model in which positive and negative differences are equally plausible at each observed magnitude. The method is simple to calculate, but its validity depends on a specific symmetry condition. A mean difference of zero, by itself, does not guarantee that condition.

Definition: For pair \(i\), let \(D_i\) be the first measurement minus the second measurement, or the reverse, chosen consistently for every pair. The observed mean difference is \(\bar{D}=\frac{1}{n}\sum_{i=1}^{n}D_i\). A sign-flipping reference distribution is formed by replacing each observed \(D_i\) by either \(D_i\) or \(-D_i\), independently across pairs, and recalculating a chosen statistic for every resulting sign pattern.

The choice of direction determines what a positive difference means; it does not change the test’s logic. For instance, if \(D_i\) is after minus before, a positive value means the measurement increased after the intervention. The test statistic may be the sum \(T=\sum_i D_i\) or the mean \(\bar{D}=T/n\). Since \(n\) is fixed, using the sum or mean gives the same ordering of results and therefore the same p-value.

Assumptions and the Meaning of the Null

The key model for the usual paired sign-flipping test is that the pair differences are independent draws from a distribution symmetric about zero under the null hypothesis. Symmetry about zero means that, for any possible set of values, positive and negative differences of the same magnitude have equal probability. For continuous differences, this can be expressed as \(D_i\) and \(-D_i\) having the same distribution. If the differences have a finite mean, symmetry about zero implies that the mean difference is zero.

This is stronger than the statement that the population mean difference is zero. A distribution can have mean zero while having more small negative values and fewer large positive values, for example. Its signs are then not equally likely after conditioning on the magnitudes, so independently flipping the observed signs does not reproduce the null distribution.

The procedure also assumes that pairs are independent of one another when the goal is to generalize to a population. Dependence within a pair is expected and is exactly why differences are used. If a pair difference is exactly zero, flipping its sign changes nothing; it can remain in the calculation, though it contributes no variation to the statistic.

Null model: Under the standard paired sign-flipping model, the differences \(D_1,\ldots,D_n\) are independent and each has a distribution symmetric about zero. The test uses the null distribution of a statistic obtained by independently changing each observed difference’s sign. This is not, in general, a valid test of only \(H_0:\mu_D=0\) when the difference distribution may be asymmetric.

This reference distribution is built from the observed magnitudes, not by resampling new pairs. With \(n\) nonzero differences there are \(2^n\) sign patterns. An exact test calculates the statistic for every pattern; a Monte Carlo approximation samples some patterns when enumerating all of them is impractical. A two-sided test counts statistics at least as extreme in absolute value as the observed statistic. A one-sided test counts outcomes in the direction specified by \(H_a\). In either case, outcomes tied with the observed statistic are included in the tail.

Worked Examples

Worked Example: An Exact Two-Sided Test

Suppose four hypothetical pairs have differences, measured in points, of \(-1, 2, 3,\) and \(4\), with the direction defined so positive means an increase. Test against a symmetric-about-zero null using a two-sided sign-flipping test.

The observed sum and mean are

T_{\mathrm{obs}}=-1+2+3+4=8,\qquad \bar{D}_{\mathrm{obs}}=\frac{8}{4}=2\text{ points}.

There are \(2^4=16\) equally likely sign patterns under the null model. The four magnitudes sum to 10. If the magnitudes assigned negative signs sum to \(q\), the sign-flipped sum is \(T^*=10-2q\). The two-sided tail condition is \(|T^*|\geq 8\), so

|10-2q|\geq 8 \quad\Longleftrightarrow\quad q\leq 1\ \text{or}\ q\geq 9.

Among the magnitudes \(1,2,3,4\), subsets with sum at most 1 are the empty subset and the subset containing only 1: two patterns. Subsets with sum at least 9 are \(\{2,3,4\}\), with sum 9, and \(\{1,2,3,4\}\), with sum 10: two more patterns. Thus four of the 16 sign patterns are at least as extreme as the observed result.

p=\frac{4}{16}=0.25.

The exact two-sided p-value is 0.25. At significance level \(\alpha=0.05\), this test does not provide sufficient evidence against the symmetric-about-zero null. The result is not evidence that the null is true; it says that the observed sum is not especially unusual within this reference distribution.

Worked Example: A One-Sided Exact Test

In a second hypothetical setting, three paired differences in seconds are \(2,1,-1\). Positive values represent longer times under the first condition. Test whether the first condition tends to produce longer times, using \(H_a\) in the positive direction.

The observed sum is \(T_{\mathrm{obs}}=2+1-1=2\) seconds. The magnitudes are \(2,1,1\), whose total is 4. For each sign pattern, write \(q\) for the total magnitude assigned a negative sign; then \(T^*=4-2q\). The one-sided tail includes \(T^*\geq 2\), which requires \(q\leq 1\). The eligible choices are to assign no magnitude a negative sign, or to assign either one of the two magnitude-1 differences a negative sign. There are three such patterns out of \(2^3=8\).

p=P(T^*\geq 2)=\frac{3}{8}=0.375.

The one-sided p-value is 0.375. The observed result is not statistically significant at \(\alpha=0.05\); these data do not give strong evidence, under the stated model, that the first condition tends to produce longer times. The two magnitude-1 observations count as separate pairs, so flipping either one gives a distinct sign pattern.

Worked Example: Why a Zero Mean Does Not Establish Symmetry

Imagine a hypothetical population of pair differences measured in units, with \(D=-1\) occurring with probability 0.75 and \(D=3\) occurring with probability 0.25. Its mean is

$$ E(D)=(-1)(0.75)+(3)(0.25)=-0.75+0.75=0. $$

Despite having mean zero, this distribution is not symmetric about zero: a difference of \(-1\) occurs with probability 0.75, while a difference of \(+1\) never occurs; likewise, \(+3\) occurs with probability 0.25, while \(-3\) never occurs. Consequently, conditional on seeing magnitude 1, the sign is not an equally likely choice between positive and negative. Flipping observed signs would impose a balance that this null distribution does not have.

Therefore, a sign-flipping test is not justified for this population merely because its mean difference is zero. The example shows why the symmetry condition must be considered separately from the mean-null statement.

Why the Sign-Flipping Distribution Works

For independent differences symmetric about zero, each nonzero difference has an equally likely positive or negative sign once its magnitude is fixed. Independence means this holds jointly across pairs: conditional on the observed magnitudes, each of the \(2^n\) sign patterns has probability \(1/2^n\) when there are no zeros. Thus the observed signs are one equally likely member of the sign-flipping set under the null.

This gives the central justification for the exact p-value. Fix the observed magnitudes and calculate a statistic for every sign pattern. For a specified alternative, call a pattern at least as extreme when its statistic is in the relevant tail; for a two-sided alternative, use the absolute statistic. The exact p-value is the fraction of sign patterns at least as extreme as the observed one. Because all patterns are equally likely under the null, this fraction is the null probability of a statistic in that tail, conditional on those magnitudes. Including ties makes the test conservative when the distribution is discrete.

If only \(B\) randomly selected sign patterns are used, the result is a Monte Carlo approximation rather than an exhaustive exact calculation. The estimate \((b+1)/(B+1)\), where \(b\) sampled patterns are at least as extreme as the observed statistic, avoids reporting a simulated p-value of zero. Its precision depends on the number of sampled patterns; it does not repair a failure of the symmetry assumption.

What Sign Flipping Does—and Does Not—Represent

Sign flipping preserves every pair’s observed magnitude and changes only its direction. It is therefore tailored to a null model in which signs are balanced at each magnitude. It is not the same operation as reassigning treatment labels within pairs. Whether treatment labels could have been randomly assigned, and which assignments would be valid to compare, depends on the study design and is a different justification for a randomization test.

A paired sign-flipping test is useful when the pair differences are reasonably modeled as independent and symmetric around zero, especially when a direct calculation based on a normal model is not desired. If the differences are strongly skewed, have influential outliers, or are dependent across pairs, the reference distribution may not represent the null behavior. A small p-value is evidence against the stated symmetric null model, not proof of a causal effect or a guarantee that the assumptions hold.

Common Mistakes

Flipping the original measurements instead of the differences. First compute one consistently directed difference per pair; the sign-flipping operation applies to those differences.
Treating a zero mean as sufficient justification. A zero mean does not imply sign symmetry. Check whether positive and negative values of the same magnitude are plausibly equally likely under the null.
Counting only strict tail outcomes. Include sign patterns tied with the observed statistic when calculating an exact p-value.
Using a two-sided tail for a directional alternative. Choose the tail to match \(H_a\); for a two-sided test, compare absolute statistics.
Interpreting the procedure as treatment reassignment. Sign flipping is justified here by the symmetry model for pair differences, not automatically by a study’s treatment-allocation mechanism.

Key takeaway: A paired sign-flipping test builds its null distribution by independently reversing the signs of the observed within-pair differences. Its exact reference distribution is justified when independent pair differences are symmetric about zero; a zero mean alone is not enough.

Check Your Understanding

Answer each question using the definitions and conditions from this tutorial.

A study records a measurement before and after an intervention. State a valid way to define \(D_i\), and explain why the same direction must be used for every pair.
There are five nonzero paired differences. How many sign patterns are included in the exact sign-flipping reference distribution?
For a two-sided test, the observed sum is 6. Which sign-flipped sums count in the p-value tail?
Why does a population of pair differences with mean zero not necessarily satisfy the sign-flipping assumption?
What is the distinction between flipping the signs of pair differences and reassigning treatment labels within pairs?