# How to prove that sample of size $O(\epsilon^{-2} log \delta^{-1})$ is enough to predict quantiles?

There is a known problem:

You are given a stream of numbers and you need to find it's $q$-th quantile ($0 \le q \le 1$). You may get wrong answer but you need to return answer between $q-\epsilon$-th and $q+\epsilon$-th quantiles with probability at least $1 - \delta$.

In several articles I've found statement that if you get random sample of size $O(\epsilon^{-2} log \delta^{-1})$ and you'll find it's $q$-th quantile and return it as the answer to original problem, you'll get what is needed i.e answer between $q-\epsilon$-th and $q+\epsilon$-th quantiles with probability at least $1 - \delta$.

I've seen this mentioned in several places, for example,

• Quantiles on Streams by Chiranjeeb Buragohain et al.
• Approximate Medians and other Quantiles in One Pass and with... by Gurmeet Singh Manku et al

But I didn't manage to either prove it myself of trace the source. Any ideas how to prove that?