# Drawing numbers from a set, quantile

We have a set containing $$20$$ numbers from $$1$$ to $$20$$. Each time we draw only one number, and repeat it $$15$$ times (without replacement). Let's denote $$X-$$ the largest drawn number. Find the smallest $${{16} \choose {15}}/{20 \choose 15}$$-fractile of a random variable $$X$$.

So, we look for such $$x_p$$ that $$F(x_p)\geq {{16} \choose {15}}/{20 \choose 15}.$$ If $$X$$ is maximum of all drawn numbers, then $$F_X(t)=\Bbb P(X\leq t)=\Bbb P(X_1\leq t, ...,X_m\leq t)$$ and, if all of $$X_1,...X_m$$ are iid then we have $$\Bbb P(X_1\leq t)\cdot...\cdot\Bbb P(X_m\leq t)$$. But... how to proceed?

• If you take 15 numbers from among 1, 2, ..., 20, then the maximum number drawn cannot be below 15 and intuitively seems it will rarely be below 16. – BruceET Dec 2 '20 at 9:48

There are $$\binom {20} {15}$$ ways to choose 15 numbers from the set.

$$\binom{16}{15}$$ is the number of ways to choose 15 numbers only from $$1$$ to $$16$$ inclusive. The maximum of such subset is at most $$16$$. So the cumulative probability up to and including $$t=16$$ is the $$\binom {16} {15} / \binom {20} {15}$$.

Alternatively, consider breaking down to individual probabilitites $$\Pr(X=t)$$, where $$15\le t \le 20$$.

To choose a subset with a maximum of $$t$$, the subset will have 14 elements between $$1$$ and $$t-1$$. The number of subsets with a maximum $$t$$ is $$\binom {t-1}{14}$$.

Verify that the total number of subset is $$\binom {20}{15}$$: (the hockey-stick identity)

$$\sum_{t=15}^{20}\binom{t-1}{14} = \sum_{t'=14}^{19}\binom{t'}{14} = \binom {20}{15}$$

And similarly the $$\binom {16}{15}$$ is the sum

$$\sum_{t=15}^{16}\binom{t-1}{14} = \sum_{t'=14}^{15}\binom{t'}{14} = \binom {16}{15}$$

And so

\begin{align*} \Pr(X \le 16) &= \sum_{t=15}^{16} \Pr(X = t)\\ &= \sum_{t=15}^{16} \frac{\binom{t-1}{14}}{\binom {20}{15}}\\ &= \frac{\binom{16}{15}}{\binom {20}{15}} \end{align*}

• so the answer is simply 16? – itsme Nov 28 '20 at 13:36
• @itsme I think yes, that the required fractile is 16. – peterwhy Nov 28 '20 at 19:29

Verifying by simulation of a million iterations in R:

set.seed(2020)
q = 16/choose(20,15); q
[1] 0.001031992
x = replicate(10^6, max(sample(1:20, 15)))
mean(x <= 16)
[1] 0.001032


Agrees with the elegant Answer of @peterwhy (+1), which IMHO @itsme should Accept and upvote.

Note: Vector x contains a million observed maximums and x <= 16 is a logical vector of a million TRUEs and FALSEs, the mean of which is its proportion of TRUEs.