# How concentrated is the $t^{th}$ smallest discrete uniform order statistic?

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.