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.


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 

enter image description here

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)

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))
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  126.1   207.0   224.6   227.0   244.9   367.4 

enter image description here

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.)

| cite | improve this answer | |
  • 1
    $\begingroup$ I don't think you need to appeal to a Normal approximation, because easily computed nonparametric confidence intervals on any percentile are available to you (by means of the order statistics). I discuss the details for the case of a median at stats.stackexchange.com/questions/122001, but it will be obvious how that extends to any quantile. This addresses the OP's concern about the possibility of a heavy tail. $\endgroup$ – whuber Oct 8 '18 at 14:49
  • $\begingroup$ @whuber. Thanks for link, which I'll read carefully; addresses several topics of personal interest. // Would have said more about bootstrap here, but OP has this artificial constraint to use minimal computation. $\endgroup$ – BruceET Oct 8 '18 at 17:53

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.