Expected value of max of three numbers

Question

This is a combo problem that a friend came up with some time ago, and recently showed to me. He claims he solved it when it first occurred to him, but can no longer remember the solution, and neither we, nor several other people we've asked can solve it now.

"At a certain preschool, there are 30 children, each of whom has a spinner. Each spinner has three colors: red, blue, and green, and lands on each color with equal probability. Every child spins his spinner, then tells the teacher the color they obtained. The teacher then totals how many students got each color (e.g. 9 red, 10 blue, 11 green) and then reads out the largest number (in this case, 11). What is the expected value of the number she reads? (If two numbers are equal, she reads out the common value.)"

The main obstacle I had when working on this question was that none of the standard tools for working with expected values (linearity of expectation, recursion, etc.) seemed helpful, and while it is possible to directly write an expression of the form $\sum x P(x)$ to give the expected value, the result is so unwieldy that it's useless. In particular, it seems hard to neatly incorporate the max condition without resorting to a double sum with very awkward constraints.

If this problem has a nice closed-form solution, I'd also be very interested in the general case of $n$ students and $m$ colors, although it seems less likely that has a closed form.

Any help is much appreciated.

Answer 1

You're looking for the expectation of the maximum of a uniform multinomial. There doesn't seem to be a closed form solution to this problem. See this MathOverflow link for the asymptotic behavior of the expectation. This MathOverflow link gives bounds on the tail probability for the maximum, and also a reference to an algorithm for the exact distribution of the maximum.

Answer 2

Suppose there are $n$ students and $m$ colours $1,2,\ldots,m$. Given integers $x_1, \ldots, x_m \ge 0$ with $x_1 + \ldots + x_m = n$, let $a(x_1, \ldots, x_n)$ be the probability that each colour $j$ occurs $x_j$ times. Then $$a(x_1,\ldots,x_m) = \dfrac{n!}{x_1! x_2! \ldots x_m!} m^{-n}$$ You then want to take $$E[\max(X_1,\ldots,X_n)] = \sum_x a(x_1,\ldots,x_m) \max(x_1,\ldots,x_m)$$

In the case at hand, $m=3$ and $n=30$, I get $$ \sum_{x_1 = 0}^{30} \sum_{x_2 = 0}^{30 - x_1} a(x_1,x_2, 30-x_1-x_2) \max(x_1,x_2,30-x_1-x_2) = \dfrac{290931313777810}{22876792454961}$$