2
$\begingroup$

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?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.