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?

Question

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?

Answer 1

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.