Estimating High Confidence Upper Bound for Quantile of Unknown Distribution

Question

I am given a random variable $X$ over $\mathbb R$ with an unknown distribution. I want to determine the smallest sample size $n$ needed to obtain a high confidence upper bound $\hat Q_{1-\alpha}$ for the $1-\alpha$ quantile of X. Specifically, I am interested in high percentiles, like the 95th or 99th percentile. For a given confidence level $1-\epsilon$, I want to ensure $\Pr(\Pr(X>\hat Q_{1-\alpha})<\alpha) \geq 1-\epsilon$, regardless of the distribution of $X$.

While this question seems quite general, I am unsure of how to address it with classical statistical methods. Intuitively, I would estimate the $1-\alpha$ quantile from my sample. With methods like bootstrapping, I could also get confidence intervals for that parameter. However, I am not sure how to exactly quantify the uncertainty of these methods based on the size $n$ of the underlying sample.

My question is two-fold.

First, are there statistical tools that can answer this question and estimate confidence of a parameter estimator based on the size of a sample? I seem to lack the statistical background to find relevant information. Sources or keywords to point me in the right direction are much appreciated as well.

Second, I am aware that this question can be solved with methods from PAC-Learning. However, despite the question being relatively general, I could not find examples of bounds like this being used either. I suspect that there are better tools to answer the question, or the question not being very interesting to begin with, as one can simply assume some distribution and then use parametric methods. If someone could give me some intuition if either of these two assumptions is true, it would be highly appreciated.

Answer 1

As @Michael M pointed out in a comment, this problem is actually quite easy for a one-sided bound as described in my question.

We can get the required sample complexity to obtain a high confidence upper bound by considering first the true quantile $Q_{1-\alpha}$. Per definition, $\Pr(X \leq Q_{1-\alpha}) = 1-\alpha$.

We now consider an iid sample $S$ of size $|S| = n$. $$\Pr(\forall x \in S: x \leq Q_{1-\alpha}) = (1-\alpha)^n$$. If we choose $n$ such that this probability is smaller than our $\epsilon$, we can pick the maximum value in our sample as high-confidence upper bound for the quantile: \begin{align} (1-\alpha)^n < \epsilon\\ n > \frac{\log(\epsilon)}{\log(1-\alpha)} \end{align}

I played around with this bound for a few example distributions and it seems to be tight.

For the interested, How to obtain a confidence interval for a percentile? and Calculation of a nonparametric equal-tailed (central) tolerance interval for an unknown continuous distribution contain a lot more info and good sources about obtaining such tolerance intervals.