Expected Maximum Value of 10 Randomly Selected Balls from an Urn

Question

There are 20 balls in an urn labeled from 1 to 20. You randomly pick 10 balls out of this urn. What is the expected maximum value of the 10 balls you picked out?

I was able to solve the problem using quite tedious combinatorics as shown below. Is there any other method to solve it?

My Solution: $$\frac{20\cdot\binom{19}{9} + 19\cdot\binom{18}{9} +\dots+10\cdot\binom{9}{9}}{\binom{20}{10}} = \frac{210}{11} $$

Answer 1

Distribute the $20$ numbers in ascending order uniformly on a $0-1$ scale, so they're at $\frac{k}{21},$ for $k=1,2,3,...20$

On the other hand, in similar vein, the sampled numbers are at $\frac1{11}, \frac2{11}, \frac3{11} ... \frac{10}{11}$ on an average.

[The $20$ numbers partition a line of length $1$ into $21$ equal segments, and the $10$ samples on an average are expected to divide it into $11$ equal segments, each of which have the same distribution, and we want to find out at what point on the line the highest sampled point falls]

Thus for sampling $10$ numbers, $\frac{10}{11} = \frac{k}{21}, k = \frac{210}{11}$

If only $3$ numbers had been sampled, for example, we would directly get $k$ = $\frac{3\cdot21}{4} = \frac{63}{4}$

Note that the actual highest numbers could have been anything, we are dealing with expected values

Answer 2

You can use binomial coefficient identities to simplify the fraction: $$ \frac{\sum_{k=10}^{20} k \binom{k-1}{9}}{\binom{20}{10}} = \frac{\sum_{k=10}^{20} 10 \binom{k}{10}}{\binom{20}{10}} = \frac{10 \binom{21}{11}}{\binom{20}{10}} = \frac{10 \cdot\frac{21}{11}\binom{20}{10}}{\binom{20}{10}} = \frac{210}{11} $$

Answer 3

There is a clever method using linearity of expectation. I got this argument from two of joriki's answers: one about cards in a deck and one about the continuous version of points on a line.

First, imagine that there are $21$ balls in a circle. We make an ordered selection $11$ of these balls. We then delete the first selected ball, and rearrange the remaining $20$ balls into a line, such that clockwise nieghbor of the deleted ball is at the right end of the line. We now have a linear arrangement of $20$ balls, where $10$ of them have been selected, which is equivalent to the setup for your problem. However, the extra information about the circle will be useful.

For the circle, the $21-11=10$ unselected balls will be broken into $11$ circular segments by the selected balls (some of these segments might be empty). By symmetry, each segment has the same expected length, so the length of each segment is $10/11$ on average. Note that the number of balls which are above the maximum ball is exactly equal to the length of the segment which is clockwise of the deleted ball. We conclude that the largest selected ball has on average $10/11$ balls to the right of it, so the expected position of the largest ball is $$ 20-\frac{10}{11}=\frac{210}{11}. $$