Question

From the set $\{1, 2, 3, \dots, 20\},$ ten numbers are chosen at random, forming a subset. Let $M$ be the largest element among the ten numbers. Find the expected value of $M.$

Answer 1

The largest element can be as small as 10, which happens when the subset is {1, 2, ..., 10}.  The probability of choosing this subset is (1/2)^10 = 1/1024.  (Every element from 1 to 10 can either be in the subset, or not.)

The largest element can also be 11.  All the numbers in the subset must be from 1 to 10, and we must choose 1 to leave out, so the probability that the largest element is 11 is C(10,1)*1/1024.

The largest element can also be 12.  All the numbers in the subset must be from 1 to 11, and we must choose 2 to leave out, so the probability that the largest element is 12 is C(11,2)*1/1024.

We can do the other cases similarly:

Largest element is 13 -> C(12,3)*1/1024

Largest element is 14 -> C(13,4)*1/1024

Largest element is 15 -> C(14,5)*1/1024

Largest element is 16 -> C(15,6)*1/1024

Largest element is 17 -> C(16,7)*1/1024

Largest element is 18 -> C(17,8)*1/1024

Largest element is 19 -> C(18,9)*1/1024

Largest element is 20 -> C(19,10)*1/1024

Adding these up, we get (1 + C(10,1) + C(11,2) + ... + C(19,10))*1/1024.  Since 1 = C(9,0), we also get (C(9,0) + C(10,1) + C(11,2) + ... + C(19,10))*1/1024.

By the Hockey Stick Identity, C(9,0) + C(10,1) + C(11,2) + ... + C(19,10) = C(20,10), so the expected value of the largest element is 1/11*C(20,10)*1/1024 = 4199/256.