Why Build a Permutation Distribution?
A permutation test asks what values a statistic could take if the observed outcomes stayed fixed but the group labels were reassigned under the null hypothesis. The resulting permutation distribution is the reference distribution for judging how unusual the observed statistic is under that null model. If the number of possible assignments is manageable, we can calculate the distribution exactly by examining every assignment. If there are too many, we can approximate it by repeatedly drawing random assignments.
The two approaches have the same foundation: each permitted assignment of observational units to groups must be treated according to the null model. Exact enumeration lists them all; Monte Carlo sampling selects some at random. The distinction matters because the exact distribution has no simulation variability, while a Monte Carlo distribution can differ from it simply because only a limited number of random shuffles were drawn.
Counting Assignments and Defining the Null Model
For a two-group comparison with \(n\) observed units, suppose group 1 must contain \(n_1\) units and group 2 must contain \(n_2=n-n_1\). An assignment is determined by choosing which \(n_1\) units go into group 1; all remaining units go into group 2. The order of units within a group does not create a new assignment. Therefore, the number of fixed-size assignments is
This tutorial uses the mean difference \(T=\bar{x}_1-\bar{x}_2\) as its running statistic. Under the null model for a two-group permutation test, the observed values are exchangeable between the groups: conditional on the pooled values and the group sizes, each eligible assignment is equally likely. This condition is appropriate, for example, under a null of identical group distributions or under a sharp null in a randomized experiment. Equality of population means alone does not generally guarantee exchangeability.
For an exact distribution, calculate \(T\) for each allowed assignment. Different assignments can produce the same statistic, especially when observed values are tied. Each assignment still contributes its own probability. Thus the probability of a statistic value is the number of assignments producing it divided by the total number of assignments.
Worked Example: Enumerating Every Assignment
Worked Example: Enumerating Every Assignment
Suppose four hypothetical observational units have values 2, 4, 7, and 9. Two units are assigned to group 1 and the other two to group 2. Find the exact permutation distribution of \(T=\bar{x}_1-\bar{x}_2\). Assume the null model makes all fixed-size assignments equally likely.
There are
possible assignments. The total of the four values is 22. If group 1 has sum \(S_1\), group 2 has sum \(22-S_1\). Since each group contains two units,
The six possible group 1 pairs, their sums, and resulting statistics are:
| Group 1 values | \(S_1\) | \(T=S_1-11\) |
|---|---|---|
| 2, 4 | 6 | -5 |
| 2, 7 | 9 | -2 |
| 2, 9 | 11 | 0 |
| 4, 7 | 11 | 0 |
| 4, 9 | 13 | 2 |
| 7, 9 | 16 | 5 |
Each row is one assignment and has probability \(1/6\). The exact distribution therefore has outcomes \(-5,-2,0,0,2,5\), each with probability \(1/6\) as an assignment outcome. When equal statistic values are combined, \(T=0\) has probability \(2/6=1/3\); each of \(-5,-2,2,5\) has probability \(1/6\). If the observed assignment were group 1 = {2, 4}, the observed statistic would be \((2+4)/2-(7+9)/2=-5\).
Why Enumeration Gives the Exact Distribution
The exactness follows directly from counting under the stated null model. There are \(N=\binom{n}{n_1}\) eligible assignments, and exchangeability gives each probability \(1/N\). For any possible statistic value \(t\), the event \(T=t\) consists of precisely the \(m(t)\) assignments that produce that value. Adding their equal probabilities gives:
This argument also explains why an exact distribution can have fewer distinct statistic values than assignments: several equally likely assignments may land on the same value. The outcomes of the statistic are not necessarily equally likely, even though the assignments are.
The permutation calculation rearranges group membership; it does not resample new outcome values.
For two groups of fixed sizes, choose which units enter group 1. There are \(\binom{n}{n_1}\) such assignments.
Apply the same statistic to each assignment, keeping repeated results or recording their frequencies.
Under exchangeability, divide each statistic's assignment count by the total number of assignments.
Worked Example: Tied Values and Assignment Multiplicity
Worked Example: Tied Values and Assignment Multiplicity
Suppose four distinct units have values 1, 1, 3, and 5, with two units assigned to each group. The two units with value 1 are different observational units, even though their recorded values match. Find the exact distribution of \(T=\bar{x}_1-\bar{x}_2\), assuming all six unit assignments are equally likely.
The pooled total is 10, so for group 1 sum \(S_1\),
Label the two units with value 1 as \(a\) and \(b\). The six assignments for group 1 are \(\{a,b\},\{a,3\},\{a,5\},\{b,3\},\{b,5\},\{3,5\}\). Their statistics are respectively \(-3,-1,1,-1,1,3\). Consequently, the exact distribution assigns probability \(1/6\) to each assignment outcome; after combining ties, \(T=-1\) has probability \(2/6\), \(T=1\) has probability \(2/6\), and \(T=-3\) and \(T=3\) each have probability \(1/6\).
There are only four distinct value-pair patterns if we ignore the identities of \(a\) and \(b\): {1,1}, {1,3}, {1,5}, and {3,5}. Counting those four patterns once each would incorrectly give them equal probability. The {1,3} and {1,5} patterns each arise from two unit assignments, so each has twice the weight of either remaining pattern. Counting units, or explicitly retaining multiplicities, preserves the correct distribution.
Monte Carlo Permutation Distributions
When \(\binom{n}{n_1}\) is too large to enumerate, repeatedly draw a random assignment from the allowed set and calculate the statistic. To sample uniformly, shuffle the \(n\) observational units and place \(n_1\) of them in group 1, with the rest in group 2. A new shuffle can reproduce an assignment already drawn; this is expected when assignments are sampled randomly with replacement.
If \(B\) random assignments are drawn and \(m_B(t)\) of them produce statistic value \(t\), the Monte Carlo estimate of its probability is \(m_B(t)/B\). These relative frequencies form the Monte Carlo permutation distribution. Increasing \(B\) generally makes its frequencies more stable, but a finite simulation does not guarantee that every statistic value will appear, nor that the estimated frequencies equal the exact probabilities.
Worked Example: Comparing a Monte Carlo Distribution with the Exact One
Use the four values 2, 4, 7, and 9, split two per group, from the first example. The exact distribution is \(-5,-2,0,0,2,5\), with six equally likely assignments. Suppose a hypothetical Monte Carlo run draws 12 assignments at random and produces these statistics in order:
Count the outcomes: \(-5\) occurs once, \(-2\) occurs three times, \(0\) occurs four times, \(2\) occurs three times, and \(5\) occurs once. The estimated probabilities are therefore \(1/12\), \(3/12\), \(4/12\), \(3/12\), and \(1/12\), respectively. For example, the estimated probability of \(T=0\) is \(4/12=0.3333\), compared with its exact probability \(2/6=0.3333\). Other frequencies differ: the exact probability of \(T=-2\) is \(1/6=0.1667\), while this run estimates it as \(3/12=0.2500\).
As another comparison, the exact fraction of assignments with \(|T|\geq 5\) is \(2/6=0.3333\). In this simulation, two of the 12 draws meet that condition, giving \(2/12=0.1667\). This difference is possible because a small random run can overrepresent or underrepresent parts of the exact distribution. A Monte Carlo approximation is not a different null model; it is a random, incomplete summary of the same assignment distribution.
When Is Monte Carlo Necessary?
The number of assignments rises quickly with sample size. For two groups of 10 and 10 units, the exact calculation requires
assignments. For two groups of 20 and 20 units, it requires
The first total may be manageable with efficient software, while the second is generally too large for straightforward exhaustive evaluation. In the latter situation, Monte Carlo shuffling provides a practical approximation. The choice is computational, not a change to the statistic or null hypothesis: use exact enumeration when feasible and random sampling when it is not.
Common Mistakes and Practical Checks
- Counting ordered lists instead of group assignments. Swapping the order of two units within a group does not change the assignment or the statistic. Use \(\binom{n}{n_1}\), not \(n!\), when the group sizes are fixed.
- Removing duplicate statistic values. If several assignments produce \(T=0\), each still contributes probability. Combine those outcomes only after counting their multiplicity.
- Treating equal recorded values as the same unit. Units with tied measurements remain distinct assignments. If calculations use value patterns instead, weight each pattern by the number of unit assignments that produce it.
- Calling a Monte Carlo frequency exact. A relative frequency from a finite number of random shuffles is an estimate. Exact probabilities require complete enumeration or a separate mathematical calculation.
- Assuming equal means automatically justify shuffling labels. The reference distribution requires exchangeability under the null assignment model. Mean equality by itself is not enough to establish that condition.
A useful check is that the assignment probabilities sum to 1. In exact enumeration, the frequencies over all statistic values must add to \(N\), so their probabilities add to \(N/N=1\). In a Monte Carlo run, the counts must add to \(B\), so estimated frequencies add to \(B/B=1\).
Exact and Monte Carlo permutation distributions therefore differ in how they are constructed, not in what they represent. Exact enumeration assigns the full null-model probability to every possible statistic outcome. Monte Carlo sampling estimates those probabilities from a random subset of assignments, with the quality of the approximation depending on the simulation.
Check Your Understanding
Use the definitions and procedures in this tutorial to answer the following questions.
- How many fixed-size assignments are possible for 3 units in group 1 and 4 units in group 2? Write the binomial-coefficient calculation.
- Why can an exact permutation distribution assign probability \(2/6\) to one statistic value even when each assignment has probability \(1/6\)?
- If two observational units have the same recorded value, should they be treated as one unit when enumerating assignments? Explain.
- In a Monte Carlo run of 500 shuffles, a statistic value occurs 35 times. What is its estimated probability, and why need it not equal the exact probability?
- Why is equality of group means alone not sufficient to justify every permutation distribution?