For most hypothesis tests, we start with the assumptions and work forward to derive the sampling distribution of the test statistic under the null hypothesis. For permutation tests we will reverse the procedure, since the sampling distribution involves the permutations which give the procedure its name and are the key theoretical issue in understanding the test.
In mathematics, a permutation is a reordering of the numbers 1, ..., n. For example,
- (1, 2, 3, 4, 5, 6)
- (1, 3, 2, 4, 5, 6)
- (4, 5, 2, 6, 1, 3)
- (3, 2, 1, 6, 4, 5)
are all permutations of the numbers 1 through 6 (note that this includes the standard order in first line). There are n! (n factorial) permutations of n objects. In this case, 6! = 720, so you can see why they aren't all written out here.
The term permutation tests refers to rearrangements of the data. The null hypothesis of the test specifies that the permutations are all equally likely. A concise way to say this is that the distribution of the data under the null hypothesis satisfies exchangeability.
The sampling distribution of the test statistic under the null hypothesis is computed by forming all or many of the permutations, calculating the test statistic for each and considering these values all equally likely.
Consider the following two group example.
Group 1: 55 58 60
Group 2: 12 22 34
Clearly a t-test will not work with this small example, however a permutation test will do the job.
Here are the steps we will follow to use a permutation test to analyze the differences between the two groups.
- Analyze the problem
- Choose a test statistic
- Resample and recompute the test statistic
- Reject or fail to reject the null hypothesis
For the original order the sum for Group 1 is 173. In this example, if the groups were truly equal then ramdomly moving the observations among the groups would make no difference in the sum for Group 1. Some of the sums would be a little larger than the original sum and some would be a bit smaller. For the six observations there are 720 permutations of which there are 20 distinct combinations for which we can compute the sum of Group 1.
Order | Group 1 | Group 2 | Sum
1 | 55 58 60 | 12 22 34 | 173
2 | 55 58 12 | 60 22 34 | 125
3 | 55 58 22 | 12 60 34 | 135
4 | 55 58 34 | 12 22 60 | 148
5 | 55 12 60 | 58 22 34 | 127
6 | 55 22 60 | 12 58 34 | 137
7 | 55 34 60 | 12 22 58 | 149
8 | 12 58 60 | 55 22 34 | 130
9 | 22 58 60 | 12 55 34 | 140
10 | 34 58 60 | 12 22 55 | 152
11 | 12 22 60 | 55 58 34 | 94
12 | 12 58 22 | 55 60 34 | 92
13 | 55 12 22 | 12 55 58 | 89
14 | 12 34 60 | 55 22 58 | 106
15 | 12 58 34 | 55 22 60 | 104
16 | 55 12 34 | 58 22 60 | 101
17 | 22 34 60 | 12 55 58 | 116
18 | 22 58 34 | 12 55 60 | 114
19 | 55 22 34 | 12 58 60 | 111
20 | 12 22 34 | 55 58 60 | 68Of these 20 different orderings only one has a Group 1 sum that greater than or equal to the Group 1 sum from our original ordering. Therefor the probability that a sum this large or larger would occur by chance alone is 1/20 = 0.05 and can be considered to be statistically significant.
In this case the permutation yielded an exact test because we were able to enumerate all of the possible combinations. We will also demonstrate this using the Stata permute command using the data from above. The permute command randomly places observations into groups so we will use 200 replications to insure that all combinations have a chance to be present.
input y grp
55 1
58 1
60 1
12 0
22 0
34 0
end
permute grp r(sum) if grp, reps(200) nodots nodrop nowarn: summarize y
Monte Carlo permutation results Number of obs = 6
command: summarize y if grp
_pm_1: r(sum)
permute var: grp
------------------------------------------------------------------------------
T | T(obs) c n p=c/n SE(p) [95% Conf. Interval]
-------------+----------------------------------------------------------------
_pm_1 | 173 10 200 0.0500 0.0154 .0242342 .0900275
------------------------------------------------------------------------------
Note: Confidence interval is with respect to p=c/n.
Note: c = #{|T| >= |T(obs)|}In larger examples it won't be possible to enumerate every permutaion so we will have to take numerous random orderings. We will demonstrate this using the Stata permute command with the hsb2 dataset with 1,000 replications.
use http://www.philender.com/courses/data/hsb2, clear
ttest read, by(female)
Two-sample t test with equal variances
------------------------------------------------------------------------------
Group | Obs Mean Std. Err. Std. Dev. [95% Conf. Interval]
---------+--------------------------------------------------------------------
male | 91 52.82418 1.101403 10.50671 50.63605 55.0123
female | 109 51.73394 .9633659 10.05783 49.82439 53.6435
---------+--------------------------------------------------------------------
combined | 200 52.23 .7249921 10.25294 50.80035 53.65965
---------+--------------------------------------------------------------------
diff | 1.090231 1.457507 -1.783997 3.964459
------------------------------------------------------------------------------
Degrees of freedom: 198
Ho: mean(male) - mean(female) = diff = 0
Ha: diff < 0 Ha: diff ~= 0 Ha: diff > 0
t = 0.7480 t = 0.7480 t = 0.7480
P < t = 0.7723 P > |t| = 0.4553 P > t = 0.2277
/* use ~female because males have the larger mean and therefore larger sum */
permute female sum=r(sum), reps(1000) nodots nodrop nowarn: summarize read if ~female
command: summarize read if ~female
sum: r(sum)
permute var: female
Monte Carlo permutation statistics Number of obs = 200
Replications = 1000
------------------------------------------------------------------------------
T | T(obs) c n p=c/n SE(p) [95% Conf. Interval]
-------------+----------------------------------------------------------------
sum | 4807 255 1000 0.2550 0.0138 .2282394 .2832112
------------------------------------------------------------------------------
Note: confidence interval is with respect to p=c/n
Note: c = #{|T| >= |T(obs)|}
ttest science, by(female)
Two-sample t test with equal variances
------------------------------------------------------------------------------
Group | Obs Mean Std. Err. Std. Dev. [95% Conf. Interval]
---------+--------------------------------------------------------------------
male | 91 53.23077 1.125037 10.73217 50.99569 55.46585
female | 109 50.69725 .8657315 9.038503 48.98122 52.41328
---------+--------------------------------------------------------------------
combined | 200 51.85 .7000987 9.900891 50.46944 53.23056
---------+--------------------------------------------------------------------
diff | 2.533522 1.397901 -.223164 5.290207
------------------------------------------------------------------------------
Degrees of freedom: 198
Ho: mean(male) - mean(female) = diff = 0
Ha: diff < 0 Ha: diff ~= 0 Ha: diff > 0
t = 1.8124 t = 1.8124 t = 1.8124
P < t = 0.9643 P > |t| = 0.0714 P > t = 0.0357
/* use ~female because males have the larger mean and therefore larger sum */
permute female sum=r(sum), reps(1000) nodots nodrop nowarn: summarize science if ~female
command: summarize science if ~female
sum: r(sum)
permute var: female
Monte Carlo permutation statistics Number of obs = 200
Replications = 1000
------------------------------------------------------------------------------
T | T(obs) c n p=c/n SE(p) [95% Conf. Interval]
-------------+----------------------------------------------------------------
sum | 4844 43 1000 0.0430 0.0064 .0312912 .0574863
------------------------------------------------------------------------------
Note: confidence interval is with respect to p=c/n
Note: c = #{|T| >= |T(obs)|}
tabstat write, by(female) stat(median)
Summary for variables: write
by categories of: female
female | p50
-------+----------
male | 52
female | 57
-------+----------
Total | 54
------------------
median write, by(female)
Median test
Greater |
than the | female
median | male female | Total
-----------+----------------------+----------
no | 56 51 | 107
yes | 35 58 | 93
-----------+----------------------+----------
Total | 91 109 | 200
Pearson chi2(1) = 4.3369 Pr = 0.037
Continuity corrected:
Pearson chi2(1) = 3.7643 Pr = 0.052
/* use female since females have higher median */
permute female median=r(p50), reps(1000) nodots nodrop nowarn: summarize write if female, detail
command: summarize write if female, detail
median: r(p50)
permute var: female
Monte Carlo permutation statistics Number of obs = 200
Replications = 1000
------------------------------------------------------------------------------
T | T(obs) c n p=c/n SE(p) [95% Conf. Interval]
-------------+----------------------------------------------------------------
median | 57 66 1000 0.0660 0.0079 .0514086 .0832061
------------------------------------------------------------------------------
Note: confidence interval is with respect to p=c/n
Note: c = #{|T| >= |T(obs)|}
From: http://www.philender.com/courses/intro/notes/permute.html