Problem source

An examiner has to assign a mark between 1 and $m$ inclusive to each of $n$ examination scripts ($n\leqslant m$). He does this randomly, but never assigns the same mark twice. If $K$ is the highest mark that he assigns, explain why 
\[
\mathrm{P}(K=k)=\left.\binom{k-1}{n-1}\right/\binom{m}{n}
\]
for $n\leqslant k\leqslant m,$ and deduce that 
\[
\sum_{k=n}^{m}\binom{k-1}{n-1}=\binom{m}{n}\,.
\]
Find the expected value of $K$.

Solution source

If the highest mark is $k$, then there are $n-1$ remaining marks to give, and they have to be chosen from the numbers $1, 2, \ldots, k-1$, ie in $\binom{k-1}{n-1}$ ways. There are $n$ numbers to be chosen from $1, 2, \ldots, m$ in total, therefore $\displaystyle \mathbb{P}(K=k) = \left.\binom{k-1}{n-1} \right/ \binom{m}{n}$

Since $K$ can take any of the values $n, \cdots, m$, we must have

\begin{align*}
&& 1 &= \sum_{k=n}^m \mathbb{P}(K=k) \\
&&&=  \sum_{k=n}^m  \left.\binom{k-1}{n-1} \right/ \binom{m}{n} \\
\Rightarrow && \binom{m}{n} &=  \sum_{k=n}^m  \binom{k-1}{n-1} \\
\\
&& \mathbb{E}(K) &= \sum_{k=n}^m k \cdot \mathbb{P}(K=k) \\
&&&= \sum_{k=n}^m k \cdot  \left.\binom{k-1}{n-1} \right/ \binom{m}{n}  \\
&&&= n\binom{m}{n}^{-1}  \sum_{k=n}^m \frac{k}{n} \cdot  \binom{k-1}{n-1} \\
&&&= n\binom{m}{n}^{-1}  \sum_{k=n}^m \binom{k}{n} \\
&&&= n\binom{m}{n}^{-1}  \sum_{k=n+1}^{m+1} \binom{k-1}{n+1-1} \\
&&&= n\binom{m}{n}^{-1}  \binom{m+1}{n+1} \\
&&&= n \cdot \frac{m+1}{n+1}
\end{align*}