# Invalid Permutation Tests

Authors: Mikel Aickin
Journal: International Journal of Mathematics and Mathematical Sciences
 (2010)

---

## Abstract

Permutation tests are often presented in a rather casual manner, in both introductory and advanced statistics textbooks. The appeal of the cleverness of the procedure seems to replace the need for a rigorous argument that it produces valid hypothesis tests. The consequence of this educational failing has been a widespread belief in a “permutation principle”, which is supposed invariably to give tests that are valid by construction, under an absolute minimum of statistical assumptions. Several lines of argument are presented here to show that the permutation principle itself can be invalid, concentrating on the Fisher-Pitman permutation test for two means. A simple counterfactual example illustrates the general problem, and a slightly more elaborate counterfactual argument is used to explain why the main mathematical proof of the validity of permutation tests is mistaken. Two modifications of the permutation test are suggested to be valid in a very modest simulation. In instances where simulation software is readily available, investigating the validity of a specific permutation test can be done easily, requiring only a minimum understanding of statistical technicalities.


---

## Body

## 1. Introduction

Permutation tests are frequently recommended on two grounds. First, they require fewer assumptions than corresponding model-based tests, and secondly, their validity (as statistical hypothesis tests) is guaranteed by construction. The purpose of this note is to indicate a way in which the first property undermines the second property. The setting is the usual one in which the Mann-Whitney test is asserted to be appropriate, but going beyond this to the assertion of a more general permutation principle (Lehmann [1]).Users of statistical methods appear to be of two minds about permutation tests. On one hand, since the “randomization” test in the context of a randomized clinical trial is an example of a permutation test, much of the argument in favor of randomization as an experimental principle has been that there is a guaranteed correct statistical test. This argument has had an enormous impact on the design of biomedical studies, with virtually all researchers agreed that randomization is necessary for a study to be valid. If a randomization test is invalid, however, then the technical argument for randomization becomes rather thin. On the other hand, formal permutation tests occur fairly rarely in statistical practice. In the two-sample situation discussed here, the dominant statistical method is thet-test, and although randomization arguments have been used to justify it, it can also be recommended without mentioning randomization. Perhaps the only other analyses that are used with some frequency are the nonparametric alternatives to the t-tests, and these are often justified by appealing to a “permutation principle”, giving the impression that these alternatives minimize untestable assumptions. In fact, the often-used Wilcoxon and Mann-Whitney tests do not follow from a permutation principle, but even if they did I will argue here that this principle is invalid.First, I will present an exaggerated example that indicates in a practical sense how the logic of the general permutation test can break down. Secondly, using the notion of counterfactuals, I will show in a slightly more theoretical way what the source of the problem is. Thirdly, I will suggest two potential alternatives to the permutation test, and argue in their favor on the basis of a small simulation. Finally, I will indicate how Fisher’s exact test fails to follow counterfactual principles, based on an example.


## 2. Regression Example

The two-sample location problem can be expressed as a model for individual pairs(y,x) of the form y=θx+e, where x takes the values 1 and -1 (indicating two groups), e is a chance perturbation, having mean 0 and being uncorrelated with x, and θ is the parameter of interest.  In this paper, I will only consider the case in which half of the observations have x=1, and so the total sample size n is even. Given data of this form, the conventional estimate of θ is(2.1)θ̂=∑xyn.The null hypothesis is thatθ=0, and the permutation test of this hypothesis is based on the putative null distribution of the above estimate, obtained in the following way. Let x̃ denote a random permutation of the x-values. For simulation purposes, (y,x) is replaced by (y,x̃), a large number of random permutations x̃ are generated,  with y fixed, and for each one the corresponding estimate of θ is computed. Finally, this large sample of θs is taken to estimate the null hypothesis distribution of θ̂.A difficulty with this approach is illustrated in Figures1 and 2. Figure 1(a) shows a unit Normal distribution, intended as the distribution of y (or e) under the null hypothesis that θ=0. Half of the values from this distribution are regarded as being cases when x=-1, the remainder when x=1. Figure 1(b) shows the simulated permutation null distribution of the estimate of θ. Figure 2(a) shows a another distribution for y (or e), again under the null hypothesis. Figure 2(b) shows the simulated permutation null distribution of the estimate of θ in this case. Both of these cases are correct, in the sense that if the distribution of e is given on the left, then the null distribution of θ̂ is validly approximated on the right.A null situation for generating a permutation distribution.
(a)(b)A situation that can be either null or non-null, for simulating a permutation distribution.
(a)(b)Now let us look at the situation with different eyes. Suppose that Figure1(a) shows the distribution of e, but that θ is large enough to produce the distribution of y seen in Figure 2(a). The distribution of the parameter estimate under the null hypothesis is still shown in Figure 1(b). But the permutation null distribution that will be computed from data coming from the distribution in Figure 2(a) appears in Figure 2(b). This shows an example of the following: in the situation where, as a matter of fact, the null hypothesis is false, the permutation estimate of the null distribution can also be false.


## 3. Counterfactuals

One way of understanding this situation is based on the method of counterfactuals (Rubin, [2]). In the two-sample circumstance, we would write the outcomes as y(θ,ψ), considered as a stochastic process indexed by the parameter of interest (θ) and the nuisance parameter (ψ). Again, in our situation this would be y(θ,ψ)=θx+y(0,ψ), where now y(0,ψ) plays the role of e above. In the exposition by Lehmann [1], the parameter ψ would represent a probability density, and y(0,ψ) would have density ψ. The value y(0,ψ) is generated by some chance mechanism, and then y(θ,ψ) is generated by the model equation above. The values we observe are y(θ,ψ), but for values of θ and ψ that we do not know. Counterfactuality comes in because y(0,ψ) is the value we would have observed if the null hypothesis had been true. As is usually the case in counterfactual arguments, we can only actually observe y(0,ψ) under special circumstances (when the null hypothesis is true), so that in general it is only a hypothetical quantity.Here is the argument of Lehmann [1]. The set of values {y(0,ψ)} (equivalent to the order statistic) is complete and sufficient for the model defined by θ=0 and ψ = any density. It follows that the null conditional distribution of the sampley(0,ψ) given the order statistic {y(0,ψ)} is based on the permutation distribution, irrespective of the value of ψ. This is the basis for the permutation test. In practice, however, it is not {y(0,ψ)} that is observed, but {y(θ,ψ)}. The conventional permutation distribution is based on the observed order statistic, but this is not the order statistic that would have been observed if the null hypothesis had been true. This is the core of the counterfactual objection to the permutation test; it conditions on the observed order statistic {y(θ,ψ)} instead of conditioning on the null order statistic {y(0,ψ)}, which Lehmann used for his proof. Because it is conditioning on the latter that justifies the test, the argument for conditioning on the former is not obviously correct.In Lehmann’s theorem where the permutation test is derived, he implicitly considers only observations of the formy(0,ψ), and shows that the (unbiased) rejection region R must satisfy P[R∣{y(0,ψ)}]=α, the level of the test. In his examples, he implies that R can be found by solving P[R∣{y(θ,ψ)}]=α. But since his theorem implicitly assumed the null hypothesis, he did not show that R must satisfy this latter equation, and as we have seen in the example above, it need not be satisfied.There is yet another way of seeing the problem, which connects it more meaningfully to the example. The observed order statistic{y(θ,ψ)} has the same distribution as an order statistic {y(0,ψ0)}, where ψ0 is a distribution that depends on θ and ψ. The permutation distribution based on {y(0,ψ0)} is indeed a possible null distribution, but it is not the null distribution that would have been obtained if θ had been 0, and ψ had been left unchanged. Thus, it is precisely the fact that the permutation argument permits different values of (θ,ψ) to produce the same order statistic that creates the problem.Finally, there is a way of seeing how the sufficiency argument actually misleads the inference. The argument of Lehmann [1] is that conditional on the order statistic, the distribution of the sample does not depend on the nuisance parameter ψ, in the submodel where θ=0. This is perhaps naturally interpreted to mean that the nuisance parameter has been eliminated from the problem. But this is not the correct interpretation of Lehmann’s equations. What they really say is that the only influence that the nuisance parameter ψ has on the distribution of the sample is carried by the order statistic. The order statistic completely mediates the effect of ψ on the distribution of the sample. Thus, both θ and ψ jointly influence the permutation distribution of the sample, but the permutation test does not separate their individual influences.


## 4. Better Estimates of the Null Distribution

One obvious strategy to repair the permutation test is to replace the order statistic by{y(θ,ψ)-θ̂x}. This is an attempt to estimate the true null order statistic {y(0,ψ)}. The potential objection is that the variability of this estimate might be less than the variability of the true null order statistic, producing an invalid test. The permutation test based on this replacement is called the adjusted permutation test.Another approach is to use a simulation based on a random permutationx̃, but conditioned so that it is orthogonal to x. The corresponding simulation sample of estimates are then of the form(4.1)∑x̃y(θ,ψ)n=∑x̃y(0,ψ)n.The simulated distribution of the estimate is thus based on order statistics that would have counterfactually been seen under the null hypothesis, but with a restriction on the permutations. It is not clear that this procedure is fully justified, because of the orthogonality restriction. Here we call this theorthogonal permutation test.In the simulation, we call the usual permutation test theconventional permutation test. Because everything is based on a simulation, we know the true null order statistic, and the permutation test based on it is called the null permutation test. This gives us altogether four permutation tests, of which only the null permutation test is (within simulation variation) known to be correct.


## 5. A Simulation

To compare these four tests, I performed a small simulation in the above regression situation. The simulation used sample size 16, since the orthogonal permutation test is only possible forx̃ taking values -1 and 1 if n is divisible by 4. The distribution of e was Normal (0,1), values of θ were 0(.1)1.3, the number of simulated tests for each value of the parameter was 1000, and the number of permutations in each test was 100. The simulation was carried out in Stata (version 9), using a permutation routine that was written specifically for this research.The results of the simulation are shown in Tables1–4. Table 1 shows the average estimate (each based on 1000 replications), verifying that all estimates of the null distribution have the correct mean of 0. For the null case this can be shown theoretically, and so the values here serve as a positive control on the simulations. The standard deviations of the estimates (SDE) are shown in Table 2. Again the null test values are constant, as they should be within the simulation variation. The orthogonal test has essentially the same SDEs as the null test, and the adjusted test is only slightly higher. In contrast, the conventional test estimates an SDE that grows with the size of the parameter, another result that can be verified theoretically (see the Appendix).Table 1
Simulated means of effect estimates.
θNullConventionalAdjustedOrthogonal0-0.00027-0.00027-0.00021-0.000030.1-0.00007-0.000060.000020.000100.2-0.00005-0.000170.00005-0.000490.30.000220.000220.00026-0.000240.40.000210.000270.000210.000330.50.000510.000470.00048-0.000090.6-0.00015-0.00005-0.00005-0.000380.70.000500.000530.000460.000180.8-0.00025-0.00035-0.000330.000070.9-0.00066-0.00070-0.00060-0.000381-0.00007-0.00030-0.000050.000041.1-0.000150.00032-0.000070.000061.20.00013-0.000120.00012-0.000091.30.00014-0.000350.00011-0.00019Means of the sampling distributions of estimates of the null mean, using four procedures:(1) null, the usual method when the null is true, (2) conventional, the usual method when the null is false, (3) adjusted, subtracting off the estimate, (4) orthogonal, using only orthogonal permutations.Table 2
Simulated SDs of effect estimates.
θNullConventionalAdjustedOrthogonal00.2460.2460.2370.2460.10.2460.2470.2370.2460.20.2460.2510.2370.2460.30.2460.2570.2370.2460.40.2460.2650.2370.2460.50.2460.2760.2370.2460.60.2460.2880.2370.2460.70.2460.3020.2370.2460.80.2470.3180.2380.2460.90.2460.3350.2380.24610.2460.3530.2370.2461.10.2460.3720.2370.2461.20.2470.3920.2380.2461.30.2460.4120.2370.246Standard deviations of the estimators in Table1.Table 3
Simulated power of tests.
θNullConventionalAdjustedOrthogonal00.0530.0530.0670.0610.10.1120.10.1320.1230.20.2120.1860.2210.2120.30.3370.2830.340.3160.40.4870.4260.4870.470.50.6430.5740.6450.6190.60.7590.7260.7680.7560.70.8570.8350.8760.8620.80.9240.9130.940.9290.90.9630.9650.9780.97410.9840.9860.9910.9911.10.9960.9950.9960.9961.20.9970.9980.9990.9991.30.9990.99910.999Powers of the tests based on the estimators in Table1.Table 4
Simulated sample-size efficiency of the conventional test versus other tests.
θNullAdjustedOrthogonal0.10.9920.9210.9890.20.9640.8950.9610.30.9190.8530.9150.40.8610.8010.8590.50.7980.7410.7930.60.730.6780.730.70.6640.6170.6610.80.6010.5580.5970.90.5410.5030.53810.4870.4520.4851.10.4370.4060.4361.20.3960.3680.3941.30.3580.3320.356Efficiency of the estimators in Table1.The probability of rejecting the null hypothesis is shown in Table3. Again the results of the orthogonal test are essentially the same as the correct null test, with the adjusted test losing only a small amount of power. Although the conventional test is worse than both the adjusted and orthogonal tests, the difference is rather small. Note that the adjusted and orthogonal tests appear to have been slightly larger than nominal levels, suggesting that possibly some adjustment needs to be made. (In the simulations a value equal to the observed was included in the rejection region, and the number of permutations per test was small, both of which might account for some of the excess level, but more research is warranted.) Table 4 shows the efficiency of the conventional test relative to the others, in terms of sample size. This is an estimation-based rather than a test-based comparison. Clearly the conventional test fares poorly relative to the other tests, and the deficit grows with the size of the effect parameter.


## 6. Fisher’s Exact Test Example

A similar problem affects the exact test for2×2 tables. When the margins of a 2×2 table are indeed fixed by the design of the experiment, then the permutation distribution may well make sense. To the contrary, the exact test has been advocated as a general testing procedure that is valid even when the margins are not fixed. The counterfactual approach can be portrayed in these cases by defining indicators as follows: br(ur,βr,βc,βrc) = ind(ur<βr),bc(uc,βr,βc,βrc) = ind(uc<βc). brc(urc,βr,βc,βrc) = ind(urc<βrc), where the u’s are independent uniform chance variables, and “ind” means “indicator variable of”. The row indicator is the larger of br and brc, and the column indicator is the larger of bc and brc. The null hypothesis is independent of row and column, which is the same as βrc = 0.  The nuisance parameter is (βr,βc).Here is an illustrative example. Table5 shows the result of a single simulation with βr = 0.6, βc = 0.6, and βrc = 0.3. The one-sided P-value from Fisher’s exact test is   .517 (according to Stata). If we eliminate brc (counterfactually imposing the null hypothesis), then the results are as in Table 6. If we take it that there were 10 observations in the lower-right cell (as in Table 5), but with the margins of Table 6, the one-sided P-value is   .0124 (again from Stata). This example makes it clear that the failure of the null hypothesis has an effect on the conditioning statistic, which in this case consists of the marginal frequencies in the table. The conditioning in Fisher’s exact test is not on the frequencies that would have been seen under the null hypothesis with βrc = 0 but βr and βc unchanged, but rather under a different version of the null hypothesis in which the actual nonnull value of βrc implicitly gives different values to βr and βc. From the counterfactual standpoint, Fisher’s exact test uses the wrong margins.Table 5
Single simulation (dependent).
1455101561420Simulated data based onbr, bc, and brc, exhibiting dependence of row and column, but with P=.517Table 6
Single simulation (independent).
257761391120Data from the simulation in Table5, but omitting the brc factor, thereby correctly estimating the null margins. 10 observations in the lower right cell would result in a P-value of  .0124.


## 7. Discussion

It has become increasingly common in the statistical and biomedical literature to see assertions that amount to a general “permutation principle”. The issue is whether two (or more) variables are related, and a test is performed based on an estimated null distribution, which is produced by permuting one (or more) of the variables while leaving the remainder fixed. In randomized trials, this is called the “randomization test”, and more recently “re-randomization” has also been used for it, even in situations where no original randomization has been performed. The impression is given that either no or very few assumptions are necessary for the correctness of this procedure.For example, one now sees the justification for the Wilcoxon one-sample test as the application of this general permutation principle to the signed ranks of the observations, as if no further assumptions were required. The Wilcoxon test is, to the contrary, the consequence of a careful argument (Pratt and Gibbon [3]) that requires the symmetry of the underlying distribution, the disregard of which has been noted for some time (Kruskal [4]). It is known that the Wilcoxon test can be invalid in the presence of asymmetry; that is, the test detects the asymmetry rather than a departure from the null hypothesis, when the null hypothesis regarding the mean is true. Thus it is a specific argument based on symmetry and not a general permutation principle that justifies the Wilcoxon test. Similar comments apply to the Mann-Whitney test. There have been some cautionary articles about the general validity of the permutation principle (Romano [5], Hayes [6], Zimmerman [7], Lu et al. [8], Zimmerman [9], Modarres et al. [10]), but the dominant statistical thinking has been to ignore the cautions.Based on the counterfactual argument and simulation of a regression case presented here, it seems warranted to say that permutation tests need to be revisited. Despite the fact that permutation tests are not widely used in practice, there is a very large literature on them, and several books that explain in detail how they can be used in a wide variety of situations. This literature is attractive because it seems to offer valid statistical procedures, even in complex cases, and in cases where there are technical barriers to obtaining theoretical results. Indeed, when a permutation principle does apply to a specific situation, the argument in favor of using it seems considerable, due to the reduction of untestable assumptions. But when the permutation principle fails, then there is a risk of raising false confidence in an unreliable procedure, with obvious negative consequences. The conclusion is that a substantial amount of new research is required to distinguish between valid and invalid permutation tests, and potentially also to devise modifications of the generally recommended tests that would be appropriate in practice. In any case, it should be recognized that the general assertion of a permutation principle that automatically produces valid tests appears itself to be invalid.



---

*Source: 769780-2010-05-25.xml*