I'm interested into sampling from a population, with a long time to get a sample (O(1), usually 1/2 mins), with lots of candidate populations to sample from (running a metaheuristic optimization). I would like to limit as much as possible the need for superfluous sampling.

The goal is to give a 95% confidence interval of the 5th centile of the population performance (95% of the population should have a higher performance).

Then I should be able given that CI to decide deterministicaly to resample or not, if the CI is tight enough.

Given I want to work with small samples, I thought of using a t-distribution. Using the one sided t-value (95% CI, n-1), with $\mu_5$ as the current sample 5th percentile of performance, $\sigma$ as the current sample standard deviation (SD), $n$ as the current sample size, I obtain the formula :

$$\mu_5 - \frac{\sigma}{\sqrt{n}} \times t_{value}$$

It means my 5th percentile has 95% chance to be superior to this value.

First, is it statistically correct ? Second, does it make sense to compute the difference between the computed 5th percentile and the obtained 95% confidence 5th percentile to decide if I should stop sampling ?

I'm also looking for any procedure that would make a more efficient use of the samples, since sampling is expensive in compute time (I thought about bootstrapping, but I have no clue on how to use it effectively for the problem at hand).

Thanks ! :)


1 Answer 1


If you do not know that your population is normally distributed or indeed anything about how your population is distributed, then that may not be an optimal approach

Instead, I would suggest choosing from the order statistics from your samples. I think you can use the inverse cumulative distribution function of the binomial, for example in R if you had a sample size of $10000$:

quantile   <- 0.05
confidence <- 0.95
samplesize <- 10000
qbinom((1-confidence)/2, samplesize, quantile)   
# 458
qbinom((1+confidence)/2, samplesize, quantile) + 1
# 544

to say that a $95\%$ confidence interval for the $5$th percentile of your population is $\left[x_{(458)}, x_{(544)}\right]$. It should not be a surprise that $x_{(500)}$ would be near the middle of this

  • $\begingroup$ Thanks for the answer ! Do you have any interesting resources to suggest, so I can look further into it ? :) Also, wouldn't the low quantity of samples tend to make the lower bound close or equal to the 1st lowest sample ? (I make use of 50 samples atm, which is too long for a qualitative search in the state space; when I see the low variance of some state space samples I think less than 10 samples may be appropriate) $\endgroup$
    – Seb
    Commented Apr 26, 2019 at 14:51
  • $\begingroup$ The problem is that if you have $71$ or fewer observations, the probability that all of them exceed the $5$th percentile of the population is more than $2.5\%$, since $0.95^{71}\approx 0.0262$. So if you do not know the shape of the distribution, this could be a problem and the lower end of your confidence interval should perhaps be $-\infty$ (or $0$ for a non-negative random variable). If you did have $72$ observations, a $95\%$ confidence interval for the $5$th percentile of your population would be $\left[x_{(1)}, x_{(8)}\right]$ $\endgroup$
    – Henry
    Commented Apr 26, 2019 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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