1
$\begingroup$

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.

$\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.