Let $n,z,t$ be positive integers and let $X_1,\ldots,X_{z\cdot t}$ be i.i.d. random variables that are uniformly distributed over $\{0,\ldots,n\}$.

Let $X_{(t)}$ denote the $t^{th}$ smallest variable among the $X_i$'s. Then we have that $\mathbb E[X_{(t)}]=n\cdot\frac{ t}{z\cdot t+1}$.

Denoting by $\delta>0$ a target tail probability, I'm looking for bounds on $X_{(t)}$, denoted $\overline{X_{(t)}}$ and $\underline{X_{(t)}}$, such that

$$ \Pr[X_{(t)} > \overline{X_{(t)}}] \le \delta\qquad \mbox{and} \qquad \Pr[X_{(t)} < \underline{X_{(t)}}] \le \delta. $$

Any thoughts on how to get bounds that are easy to work with?

We can assume that $n$ is large (which means its almost as if the variables are distributed over $[0,1]$) is if helps to simplify the question.

The motivation for the question comes from the analysis of a fast algorithm to compute a quantile over a large array. Using the Median of Medians algorithm, we can deterministically compute any $\phi$'s quantile in linear time. However, this may be quite slow in practice.

In contrast, Quick Select chooses a random pivot element, and is not optimal for small or large quantiles.

I want to use sampling to select a "good" pivot that minimizes the expected number of iterations until we get the (say, $\phi=0.999$) quantile. To that end, I consider using setting $z\approx 1/\phi$ and am wondering what'd be a good value for $t$ to optimize the algorithm.


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.