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?