The Permutation Test

Purpose

The permutation test (also called the randomisation test) is a more powerful alternative to the sign test for determining whether System A is significantly better than System B. It naturally handles ties without the MLRD special tie rule, because it operates on the actual metric values rather than win/loss/tie counts.

Intuition

Under H0, both systems are equally good: their predictions for any given document are interchangeable. If we randomly swap the predictions of A and B for some documents, the overall performance difference should not systematically change. If the observed difference is larger than what we would see under random swapping, we have evidence that A is genuinely better.

Procedure

1. Compute observed difference: $\Delta_{\text{obs}} = \text{metric}(A) - \text{metric}(B)$, e.g., the difference in F1 scores.

2. Enumerate permutations: There are $2^N$ possible ways to swap predictions between A and B (for each of $N$ documents, either swap or do not swap).

3. For each permutation: apply the swaps, recompute $\Delta_{\text{perm}}$, and record the result.

4. Compute p-value: the proportion of permutations where $\vert \Delta_{\text{perm}} \rvert \geq \vert \Delta_{\text{obs}} \rvert$ (two-tailed) or $\Delta_{\text{perm}} \geq \Delta_{\text{obs}}$ (one-tailed).

5. Decision: if $p \leq 0.05$, reject H0.

Monte Carlo Approximation

For $N = 100$ documents, $2^{100}$ permutations is impossible to enumerate. In practice, we use a Monte Carlo permutation test: randomly sample a large number of permutations (e.g., 10,000) rather than exhaustively enumerating all. The p-value is the proportion of sampled permutations where the difference meets or exceeds the observed one.

Why More Powerful Than the Sign Test

The sign test reduces each document to a ternary outcome (A wins, B wins, tie) and discards the magnitude of the difference. If A beats B by a tiny margin on 60 documents and loses by a huge margin on 40, the sign test treats the 60 as “wins” and the 40 as “losses”, potentially missing the fact that B’s victories are much larger.

The permutation test uses the actual metric values. It captures both the direction and the magnitude of each difference. Ties are naturally absorbed into the metric, since identical predictions produce a difference of zero.

Worked Example

Suppose we have 10 documents. System A achieves F1 = 0.82; System B achieves F1 = 0.74. The observed difference: $\Delta_{\text{obs}} = 0.08$.

Under H0, each document’s pair of predictions (A’s label, B’s label) can be swapped or left as-is. We generate 1,000 random permutations. In each, we randomly swap the predictions for a random subset of documents, recompute F1 for both systems, and compute $\Delta_{\text{perm}}$.

Suppose 23 out of 1,000 permutations produce $\vert \Delta_{\text{perm}} \rvert \geq 0.08$.

$p = 23/1000 = 0.023$

Since $0.023 < 0.05$, reject H0. System A’s improvement is statistically significant.

Summary

Aspect	Sign Test	Permutation Test
Input	Win/loss/tie per item	Metric value (e.g., F1, accuracy)
Tie handling	Special MLRD rule required	Natural; ties produce zero difference
Power	Lower (discards magnitude)	Higher (uses actual values)
Computation	Lightweight	$2^N$ or Monte Carlo sampling

Past paper questions: y2023p3q8 (evaluation)