XLVI OM - I - Problem 11

Given are natural numbers $ n > m > 1 $. From the set $ \{1,2, \ldots ,n\} $, we draw $ m $ numbers without replacement. Calculate the expected value of the difference between the largest and the smallest drawn number.
An elementary event is the selection of an $m$-element subset from an $n$-element set. These elementary events are equally probable; there are $ {n}\choose{m} $ of them. Let the largest and smallest selected number be denoted by $a$ and $b$, respectively. The random variable $X$ under consideration, which is the difference $a - b$, can take any integer value from $m - 1$ to $n - 1$.

Let us fix a natural number $r$ satisfying the inequalities $m - 1 \leq r \leq n - 1$. In the set $\{1, 2, \ldots, n\}$, there are $n - r$ pairs of numbers $a$, $b$ with the difference $a - b = r$. For a fixed position of the numbers $a$ and $b$, there are $ {r-1}\choose{m-2} $ ways to choose the remaining $m-2$ numbers from the set $\{b+1, \ldots, a-1\}$. Therefore, the product $(n - r) {{r-1}\choose{m-2}}$ represents the number of $m$-element subsets of the set $\{1, 2, \ldots, n\}$ in which the difference between the largest and smallest element is $r$—that is, the number of elementary events in which the random variable $X$ takes the value $r$.

Dividing this product by the number of all elementary events gives the probability that $X = r$; let us denote this probability by $p_r$. Thus,

\[
p_r = \frac{(n - r) {{r-1}\choose{m-2}}}{{n}\choose{m}}
\]

Using the easily justified relationships

\[
{n \choose m} = \frac{n!}{m!(n-m)!} \quad \text{and} \quad {r-1 \choose m-2} = \frac{(r-1)!}{(m-2)!(r-m+1)!}
\]

we transform the obtained expression as follows:

\[
p_r = \frac{(n - r) \frac{(r-1)!}{(m-2)!(r-m+1)!}}{\frac{n!}{m!(n-m)!}} = \frac{(n - r) (r-1)! m! (n-m)!}{(m-2)! (r-m+1)! n!}
\]

Since $r$ takes values from $m-1$ to $n-1$, the expected value of the random variable $X$, which is the number

\[
E(X) = \sum_{r=m-1}^{n-1} r p_r
\]

is equal to

\[
E(X) = \sum_{r=m-1}^{n-1} r \frac{(n - r) (r-1)! m! (n-m)!}{(m-2)! (r-m+1)! n!}
\]

To simplify the sums in the square brackets, we use the formula

\[
\sum_{r=j}^{N} {r \choose j} = {N+1 \choose j+1}
\]

(see: Note). By setting $N = n - 1$ and $j = m - 1$ in this formula, and then $N = n$ and $j = m$, we obtain, respectively:

\[
\sum_{r=m-1}^{n-1} {r \choose m-1} = {n \choose m}
\]

and

\[
\sum_{r=m}^{n} {r \choose m} = {n+1 \choose m+1}
\]

(applying a change of the summation index: $s = r + 1$). We can now complete the calculation (1):

\[
E(X) = \sum_{r=m-1}^{n-1} r \frac{(n - r) (r-1)! m! (n-m)!}{(m-2)! (r-m+1)! n!} = \frac{m(n-1)}{n-m+1}
\]

This is the sought value.

Note. Formula (2) is well-known. It can be easily proven by induction on $N$ for a fixed $j$. It can also be "seen" by carefully examining Pascal's triangle; we recommend this as a pleasant exercise in observation for the readers.