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

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.

• Your fourth (last) bullet suggests you aren't computing confidence intervals: you seem to be asking for the coverage of a prediction limit. Is that a correct interpretation?
– whuber
Mar 6 '17 at 22:09
• @whuber Yes, that is correct: we will have some future data coming in and I'd like to estimate the probability that one of those new values falls below the sample minimum that I have today.
– Sycorax
Mar 6 '17 at 22:30
• I guess you are familiar with this thread: stats.stackexchange.com/questions/82720/… , but posting it for reference (see also the quoted paper).
– Tim
Mar 6 '17 at 22:38
• @Tim Yes, thank you. I had actually edited out that link in one of my edits. The A-C interval recommendation would appear to (1) only address the large $n$ condition but not the small $p$ condition and (2) refer to confidence intervals vice prediction intervals. My reading my be flawed.
– Sycorax
Mar 6 '17 at 22:41
• @Sycorax your reading is not flawed, I'm providing this one for reference since it is related but you are right that is is only about CI's.
– Tim
Mar 6 '17 at 22:43

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.

• Extending this line of reasoning farther, this must be exactly how we get to the two-sample bootstrap procedure to estimate quantiles outlined in Hogg McKean and Craig: the bootstrap approximates the more elaborate combinatorial result.
– Sycorax
Mar 6 '17 at 23:36
• That's conceivable. (I'm not familiar with H, McK, and C.) But if that's all the bootstrap is doing, you ought to consider obtaining exact answers (with much less computation) using the combinatorial formulas. They have the advantage of letting you invert the problem in order to find sample sizes to achieve any desired size in a PL, for instance.
– whuber
Mar 6 '17 at 23:39
• It's an introductory mathematical statistics text, so I think the procedure is outlined for primarily pedagogical reasons. Your point about exact quantities and inversion is well-taken. Thank you for this well-considered answer.
– Sycorax
Mar 7 '17 at 0:08
• I'm stumbling over part of the reasoning. The probability that the next draw from $F$ is at or below some $k$ is $F(k)$. Across $m$ iid draws, the number of draws below $k$ has a binomial $m, F(k)$ distribution. Is it the case that the distinction between your answer and this binomial model is that the binomial model supposes $k$ is fixed up front, whereas in my problem, we are interested in $x_{(1)}$?
– Sycorax
Mar 7 '17 at 19:54
• I believe so. Indeed, according to the third bullet of the question you don't really know what $F(k)$ is for any $k$--the best you could do (if you had to) is to estimate it.
– whuber
Mar 7 '17 at 20:07