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?

  • $\begingroup$ 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. $\endgroup$ – 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*}$$

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

Verifying by simulation of a million iterations in R:

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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.