# For the confidence interval of median using the binomial distribution why is it called exact and how does it differ from the naive loop-based method?

When I searched across documentation of various statistical packages, I noticed that the confidence interval for median based on either the binomial or beta distribution is called exact.

For example:

sort(x)[qbinom(c(.025, 0.975), length(x), 0.5) + c(0, 1)]


or without adding the 1 at the end (I'm not sure is this good or bad)

sort(x)[qbinom(c(.025, 0.975), length(x), 0.5)]


At the same time, I found implementation, which went entirely through all combinations of indexes with the O(N2) complexity, but it gave different results than the previous methods.

Example of the true exact method (language doesn't matter, just wanted to show the loops)

 if(method == 1){ # exact
CI.mat <- matrix(NA, ncol = 2, nrow = n-1)
pcov.vec <- numeric(n-1)
for(i in 1:(n-1)){
for(j in (i+1):n){
pcov <- pbinom(j-1, size = n, prob = prob)-pbinom(i-1, size = n, prob = prob)
if(pcov > conf.level){
pcov.vec[i] <- pcov
CI.mat[i,] <- c(xs[i], xs[j])
break
}
}
}
if(all(pcov.vec == 0)){
CI <- matrix(c(xs[1], xs[n]), nrow = 1)
attr(CI, "conf.level") <- 1
alpha <- 0
rownames(CI) <- rep(paste(100*prob, "% quantile"), nrow(CI))
colnames(CI) <- c("lower", "upper")
}else{
CI.mat <- CI.mat[pcov.vec > 0,,drop = FALSE]
pcov.vec <- pcov.vec[pcov.vec > 0]
pcov.min <- min(pcov.vec)
CI <- CI.mat[pcov.vec == pcov.min,,drop = FALSE]
if(minLength){
CI <- CI[which.min(diff(t(CI))),,drop = FALSE]
}
attr(CI, "conf.level") <- pcov.min
rownames(CI) <- rep(paste(100*prob, "% quantile"), nrow(CI))
colnames(CI) <- c("lower", "upper")
}
}


One would expect, that "exact means exact", so the 2 approaches give the same results, but it does not:

set.seed(100)
x <- rnorm(100)


For the "exact based on binomial"

> sort(x)[qbinom(c(.025, 0.975), length(x), 0.5)]   # no "+1"
[1] -0.2016340  0.1315312


For the "true exact"

> MKmisc::medianCI(x)

exact confidence interval

95.23684 percent confidence intervals:
lower     upper
median -0.3598621 0.1298341
median -0.1379296 0.2163679


2 CIs with same coverage have been found.

OK, let's forget it's R and make it general.

Which of the methods above is truly exact?

Which one would you choose, if you didn't want to use bootstrap (for time complexity on big data), the one using binomial distribution or the loop-based (using the binomial d.) one?

Or maybe the beta distribution-based approach?

They are both exact. Exact is a weaker property than you probably think it is.

A confidence interval method is exact if the probability of a $$1-\alpha$$ confidence interval covering the true value is at least $$1-\alpha$$. Here's an exact 95% confidence interval method for any real-valued parameter: roll a twenty-sided die. If you get a 20, the interval is the empty set, otherwise it's the whole real line.

So, the fact that there's more than one exact interval isn't really surprising. It's still a fair question which one you should use. There are two other useful properties of a confidence interval on top of being exact: it should be short (on average) and it shouldn't over-cover. My stupid all-purpose confidence interval has infinite length; you can do better.

The MKmisc::medianCI help says

If the result is not unique, i.e. there is more than one interval with coverage probability closest to conf.level, then a matrix of confidence intervals is returned. If minLength = TRUE, an exact confidence interval with minimum length is returned

The function looks for all the exact confidence intervals and it tries to get coverage of at least $$1-\alpha$$ (so it's exact) but not too much higher. The minLength option also allows for the shortest exact interval.

• Ah, got it! It makes sense! I compared the results. Those fast (using the ready-to-use binomial distribution) return longer, but indeed wider than 95% CIs. The O(N2) method gives the shortest one, but takes some time. That' the cost - it's the slowest "in the class of exact tests". Got it! DescTools::MedianCI(x) gives [-0.2016340; 0.1788648] with coverage prob. 96.5%. EnvStats::eqnpar(x, ci = TRUE, ci.method = "exact") gives [-0.2016340 ; 0.1315312] with PC=95.4%. MKmisc::medianCI(x, minLength = T) gives [-0.1379296; 0.2163679] PC=95.2%. Slow-shortest vs. fast-less-efficient. Thank you! – StatNovice Jan 10 at 4:47
• Just one more question - I'm wondering, why the method using the binomial distribution doesn't return the shortest CI, but rather we need to search for it. Both are exact, both use binomial distribution, but the sort(x)[qbinom(c(.025, 0.975), length(x), 0.5) + c(0, 1)] isn't the best one. Is this because of some approximation? – StatNovice Jan 10 at 15:39
• I found the book the Author of the all-pairs method used. It's in German. I translate it with dictionary. The code present in the book matches perfectly the sort(x)[qbinom(c(.025, 0.975), length(x), 0.5) + c(0, 1)]. The code used in the package - doesn't. Yet indeed it returns the shortest CI, while the code in the book (and the qbinom...) - does not. – StatNovice Jan 10 at 16:53
• I found the qbinom() method can return an index of 0 if q is short. – Simon Woodward Jun 10 at 20:25