5
$\begingroup$

I want to cut my data of size N into k equal-sized bins. But I am happy with roughly equal-sized bins, with some $\varepsilon$ error. As precise quantiles of the data are computationally costly (sorting time grows at rate $O(N \log N)$), I am happy to estimate the quantiles. Taking the quantiles of some random subsample of size n is an obvious way forward. But what is the recommendation / theory / formula for how large a sample to take? At what rate should that sample or the $\frac{n}{N}$ sampling ratio grow for the same precision (proportional deviations of bin shares)?

There are algorithms estimating population quantiles from small samples (like Harrell-Davis) or approximate quantiles from data streams. I am not sure if either is related to the problem at hand, namely having access to the entire population, just looking for a sensible way to ease the computation of quantiles at the cost of some precision.

Page 3 of this survey says that with simple random sampling,

in order to estimate the quantiles with precision $\varepsilon n$, with probability at least $1 − \delta$, a sample of size $\Theta ( \frac{1}{\varepsilon^2} \log \frac{1}{\delta} )$ is required, where 0 < δ < 1.

This suggests a sample around 20,000 for $\varepsilon = 0.1$ and $\delta = 0.1$? What is $\Theta$?

As 19 vingtiles cut the data into 20 bins, any of those being off must have a higher probability than a single one. Though oversampling in the 3rd population percentile, all vingtiles will be too high. That said, a biased series of quantiles (6%, 11% etc. instead of 5%, 10% etc.) still let me grasp a distribution quite well.

$\endgroup$
  • 1
    $\begingroup$ depending on how much data you're dealing with, loading your data into monetdb might circumvent this issue. if you make a monet.frame object as shown here, you can run the quantile function on it and get an answer from 67 million records in a few seconds. $\endgroup$ – Anthony Damico Aug 24 '13 at 14:36
  • $\begingroup$ @AnthonyDamico, This sounds great. Sadly, I cannot use R for my implementation, but maybe it still gives us clues how it does it faster. Thanks! $\endgroup$ – László Aug 24 '13 at 14:50
  • $\begingroup$ Can you name the resource that proved the statement in order to estimate the quantiles with precision 𝜀𝑛, with probability at least 1−𝛿, a sample of size Θ(1𝜀2log1𝛿) is required, where 0 < δ < 1 Also for the above to hold true, should the variable be normally distributed ? $\endgroup$ – bicepjai Sep 11 '19 at 0:21
3
$\begingroup$

For the order of the sample size, there is direct reference here (with big-Theta notation):

in order to estimate the quantiles with precision $\varepsilon n$, with probability at least $1 − \delta$, a sample of size $\Theta ( \frac{1}{\varepsilon^2} \log \frac{1}{\delta} )$ is required, where 0 < δ < 1.

But I think this might be an easier problem than it looked like, at least with an asymptotic approximation. For any true/population/full-sample/N p-th quantile $q = F^{-1}(p)$ the limiting distribution is $$ \sqrt{n}(\hat{q}-q) = \sqrt{n}\Delta q \sim N \left(0,\frac{p(1-p)}{f(q)^2} \right) $$

but if we care about (say) 1 percentage point deviations ($\varepsilon = 0.01$) in the form $F(q + \Delta q) \in (p-0.01,p+0.01)$, we can approximate the mass in the $\Delta q$ neighborhood with $f(q) \Delta q$ and try to bound that. Saying that $|f(q) \Delta q | < 0.01$ with a 99% probability ($1-\delta$ above) then becomes the problem of which normal distribution has its 0.995 quantile at 0.01, because its variance then is the bounding $\frac{p(1-p)}{n}$. Solving for the worst-case scenario of $p=0.5$, this gives the critical sample size to be $n = 16,556$ as long as the approximations hold.

$\endgroup$

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.