# How to calculate a permutation confidence interval?

Mara Tableman, Minh Nguyen, and Michael D. Ernst note

The idea behind a permutation confidence interval is well known and fairly straightforward (Ernst 2004). The confidence interval is simply the set of all values of the parameter for which the null hypothesis is not rejected.

I am interested in algorithms for calculating such confidence intervals, especially using R. This Italian dissertation seems relevant

Tableman et al continue:

We present a method of calculating the permutation confidence interval in the two-sample problem that is computationally no more difficult than calculating a single permutation p-value. This method can be implemented in any programmable statistical software so that students can calculate permutation confidence intervals as easily as permutation test p-values.

• The first place to look would be the paper by Ernst - the reference at the bottom of your link. However, a quick glance at that paper doesn't seem to offer any fast way to invert the test though it's possible I missed something. One would have to see the poster (in this day and age it's not clear why pdfs of posters aren't uploaded as a matter of course after a conference) to know for sure. You might try contacting Ernst perhaps? May 22, 2019 at 0:19
• Ernst's paper does refer to a method by Garthwaite "Garthwaite (1996) described an efficient method for constructing confidence intervals from randomization tests, but this method is not implemented in any commercial software" but I doubt the poster can be just talking about a direct implementation of that (or surely Garthwaite would be included in the poster references). It's possible the poster relates to some extension or modification of Garthwaite, but it would still be odd to refer to Ernst and not refer to Garthwaite. May 22, 2019 at 0:33
• Further hinting that they had some improvement or extension: the poster abstract says "computation is no more difficult than" while Garthwaite's abstract says "Each search requires only slightly more permutations than" (where there are two such searches for the CI, so slightly more than twice), suggesting a possible improvement over Garthwaite. FWIW, the reference is Garthwaite, P.H. (1996). Confidence intervals from randomization tests. Biometrics 52 1387–1393 May 22, 2019 at 0:36

After requiring such confidence intervals myself and not finding any library, I have implemented Garthwaite's search method in this little function for a simple difference in population means. Not very flexible yet, but works for the basics.

https://github.com/stefgehrig/perm_test_ci

Let me know if there are any difficulties.

Best

The OP links to an abstract by Tableman, Nguyen, and Ernst (2014), who mentioned a method for permutation CIs but didn't actually describe it in their abstract.

Most likely, it was the method from this MS thesis paper by one of the authors:

Nguyen, M.D. (2009). "Nonparametric Inference using Randomization and Permutation Reference Distribution and their Monte-Carlo Approximation" [unpublished MS thesis; Mara Tableman, advisor], Portland State University. Dissertations and Theses. Paper 5927. https://archives.pdx.edu/ds/psu/37406.

Section 2.2, Lemma 1, and Theorem 1 of Nguyen (2009) define a method that matches the description in Tableman, Nguyen, and Ernst (2014)'s abstract. It really does require only a single set of permutations, and it is different from Garthwaite (1996).

I haven't found Nguyen's method implemented in code anywhere, so Emily Tupaj and I have coded it up as an R package, CIPerm:

I'd welcome any feedback.

We also included a brief summary of Nguyen (2009)'s method in our package vignette.
Here's an even briefer overview:

Let $$Y$$ be a vector of $$n$$ observations from one group, and let $$X$$ be $$m$$ observations from the other group. The difference in sample means is $$t_0 = \frac{\sum_{j=1}^n Y_j}{n} - \frac{\sum_{i=1}^m X_i}{m}$$ In the standard permutation or randomization test, at each permutation let $$k$$ denote the number of swapped labels (i.e., $$k$$ of the $$X_i$$s are assigned to the $$Y$$ group and vice versa). Then the permuted test statistics have the form $$t_{k,d} = \frac{\sum_{i=1}^k X_i + \sum_{j=k+1}^n Y_j}{n} - \frac{\sum_{j=1}^k Y_j + \sum_{i=k+1}^m X_i}{m}$$ (where $$d$$ indexes over different permutations with the same value of $$k$$ --- I should really show the indices for summation changing too but the notation would get messy --- hopefully the idea is clear).

• Naive approach: For a given mean difference $$\Delta$$, you could test $$H_0: \mu_Y-\mu_X = \Delta$$ vs $$H_A: \mu_Y-\mu_X \neq \Delta$$ by replacing all $$Y_j$$ values with $$Y_{j,\Delta}=Y_j-\Delta$$ and running the usual test for a null difference of 0. If you do this many times for many different $$\Delta$$ values, then the failed-to-reject values form a confidence interval.
• Nguyen's method: His Theorem 1 and its Corollaries show that the quantiles of $$w_{k,d}$$ give you the CI endpoints directly, where $$w_{k,d} = \frac{t_0-t_{k,d}}{k\left(\frac{1}{n}+\frac{1}{m}\right)}$$

Thus, you don't have to try out different $$\Delta$$ values or run new permutations. One set of permutations is enough, as long as you track $$k$$ at each permutation.

For small problems, the naive approach might be fine. But I consulted once for someone who had enough data that a single permutation test run took hours, and they wanted to run it daily. A naive grid search over many $$\Delta$$ values would have been impractical, but Nguyen's method worked just fine for them.