How to estimate high end percentile (e.g. >90%)

Question

Say my dataset is of size $N$, and I want to calculate the 90th percentile.

Suppose $N$ is too large that I can't compute the percentile by going through the entire dataset, what is the best way to proceed?

(This might be an unrealistic assumption as modern computing can get quite powerful. But for this question's sake let's just assume that to be the case)

I can take a simple random sample and estimate the quantile there, but I guess the estimation will be very poor given I am estimating the tail?

So, is there a non-simple random sampling scheme that I should use, or some bias-corrected estimator from SRS that I should use?

Bear in mind that I don't know what the distribution looks like, so it might be heavy-tailed.

Answer 1

Background. Suppose I have a random (and un-sorted) sample of size $N = 100,000.$ Because you say the population from which they were sampled may be skewed, let's suppose the population is exponential with mean $\mu = 100$ (rate $\lambda = 0.01).$ Theoretically, the 90th percentile of the population is 230.26.

qexp(.90, 0.01)
[1] 230.2585

Let's generate an exponential sample of size $N$ to these specifications (rounded to integers). What is the 90th percentile of that large sample? For my large sample, this turns out to be 230. So we know the large sample gives a good indication of the 90th percentile of the population. [Of course, this is the step we're pretending is not possible, but in this discussion it's nice to know estimating the 90th percentile of the large sample isn't futile.]

set.seed(1008);  N = 10^5;  lam = 0.01
x = round(rexp(N, lam));  summary(x);  quantile(x, .90)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
   0.00   29.00   69.00   99.82  139.00 1479.00 
90% 
230 

Your question. Now suppose you can take a random sample of size $n = 100$ from the larger sample of 100,000 and find its 90th percentile. How close are we likely to get to 230? The first time I tried, I happened to get 229. But that was a lucky draw. Six successive samples of size $n = 100$ had 90th percentiles as low as 173 and as high as 278.

x.100 = sample(x, 100);  quantile(x.100, .90)
  90% 
229.1 

Comments on feasibility. As you hinted in your question, this kind of procedure doesn't work really well for strongly right-skewed distributions. (There may be large gaps between observed values in the tail.)

Because you are assuming limited computing power, I suppose you wouldn't be able to do this next step, but by taking a large number of samples of size 100 we could get an idea of the sampling distribution of their 90th percentiles.

pctl.90 = replicate(10000, quantile(sample(x,100),.9))
summary(pctl.90)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  126.1   207.0   224.6   227.0   244.9   367.4 

My initial half dozen runs gave a fairly good idea how successful estimating the 90th percentile of 100,000 observation by looking at a subsample of 100 is likely to be.

Note: There is a limit theorem that quantiles (except max and min) of large samples from continuous data, in regions where the density function is positive, tend to be normally distributed. So the histogram of pctl.90, although not exactly normal with $n = 100,$ suggests convergence to normal. (One reference: Bain & Englehardt (1992), Sect. 7.5.)

Answer 2

Check out Wilks' method.

Given a sample of size $n$, Wilks gives you a way to estimate any percentile (denoted by $\alpha$) with a target confidence interval $\beta$. The estimate is the $j$-th element in your sorted sample, where $j$ is the lowest integer for which $\sum\limits_{k=1}^{j-1}\mathcal{C}_n^k \alpha^k (1-\alpha)^{n-k} > \beta$

Of course, your estimator is better when $n$ is large.

This method does not require any assumption on the random variable distribution (except it has to be continuous). It is quite widely used in fields where an observation is very expensive (heavy computer calculation) and has an unknown and strange distribution.