Which binomial prediction interval works well for tail probabilities, i.e. $\hat{p}=1/n$ for large $n$

Question

I'm working on a problem which has the following qualities.

• The available data $x$ is numerous - on the order of $10^6$
• The CDF $F_X$ has support over nonnegative real numbers.
• I don't know $F_X$.
• We can assume the data are iid.
• I am attempting to estimate the probability that a future sample drawn from $F_X$ falls below the sample minimum $x_{(1)}$. More to the point, I want to keep this probability below a specific value $\alpha.$

When one is concerned with confidence intervals, the approach is to pick some value $k>0$ (because $x$ has nonnegative support) and use $\hat{F_X}(k)=\hat{p}=\frac{\#(x_i\le k)}{n}$, then derive left-tail binomial confidence intervals using any of a number of options, such as applying the CLT or Casella's or Jeffreys's or Agresti's or any other of many methods.

This seems brittle for large $n$ and small $k$, especially because $k=x_{(1)}$. Moreover, in my case we are estimating a prediction interval for the future observations. Is there a binomial prediction interval that works well under these circumstances?

A Bayesian approach would estimate $F$ directly and work from there. That seems harder than is strictly necessary for the narrow scope of this problem.

The answer "Nope, life is unfair and there's no good solution this problem" is also helpful if there's a nice citation to go with it.

Answer 1

There is a simple nonparametric prediction limit. Recall that a prediction limit is a procedure consisting of two independent samples $\mathcal{X}=x_1,\ldots, x_n$ and $\mathcal{Y}=y_1, \ldots, y_m$, two statistics $t$ and $s$, and a size $1-\alpha$. When the chance that $s(\mathcal{Y})$ is less than $t(\mathcal{X})$ is $\alpha$ or smaller, we say that $t$ is a one-sided lower prediction limit for $s$ of size $1-\alpha$. The PL in question uses the smallest of the $x_i$ for $t(\mathcal{X})$. It is intended that all the $y_j$ should equal or exceed the PL with high probability. Equivalently, $s(\mathcal{Y})$ is the smallest of all the $y_j$.

This PL works when the $n$ observations are independent and identically distributed and the $m$ additional observations are also iid and independent of the first $n$ observations. These assumptions imply all $n+m$ observations are exchangeable, which in turn (easily) implies the smallest observation of them all is found among the first $n$ with probability at least $n/(n+m)$. The size is the chance that one (at least) of all the observations tied for smallest lies within the $n$ values of $\mathcal{X}$. This chance is no smaller than $n/(n+m)$. When the common underlying distribution is continuous, it is exactly $n/(n+m)$.

For example, the smallest of $n=95$ values is a $95\%$ lower prediction limit for $m=5$ additional values. The smallest of $n=10^6$ values is only a $50\%$ lower prediction limit for $m=10^6$ additional values.

Similar considerations (requiring more combinatorial sophistication) are used to compute the coverage of any order statistic qua prediction limit. See section 5.4 of Hahn & Meeker for a synopsis ("Distribution-free prediction intervals to contain at least $k$ of $m$ future observations.")

Reference

Gerald J. Hahn and William Q. Meeker, Statistical Intervals, A Guide For Practitioners. J. Wiley & Sons, 1991.