Recently a friend posed me a problem:
You have $n$ dice, all of which have integer values ranging from $1$ to $j$, take on each of those values with probability $\frac{1}{j}$, and are independent of each other. If you roll those $n$ dice, then take the $k$ highest values that appear and sum them together, what is the expected value of this sum?
Now, when $k = 1$, this is simply the expected value of the maximum of $n$ i.i.d. random variables, which is not difficult to compute. But it becomes significantly trickier for even $k = 2$ (as then you are trying to maximize over the sum of two dice, which need not be independent), and so I am curious if anyone here has any good ideas.
Thank you in advance for your help!
Best Answer
The term you're looking for is "order statistics". The expectation of the sum of the largest $k$ values is equal (by linearity of expectation) to the sum of the expectations of the highest $k$ order statistics.
Calculating those expectations in closed form is not trivial, but for your specific dice setup one could certainly write the answer as a summation and calculate it. Another example of estimating expectations of order statistics can be found in these notes.