Valor esperado de max de tres números

Question

Este es un combo problema que un amigo vino hasta hace algún tiempo, y recientemente me mostraba. Afirma haber resuelto la primera vez que se le ocurría, pero no puede recordar la solución, y ni nosotros, ni muchas otras personas hemos pedido puede resolver ahora.

"A cierta edad preescolar, hay 30 niños, cada uno de los cuales tiene un spinner. Cada spinner tiene tres colores: rojo, azul, y verde, y en las tierras de cada color, con igual probabilidad. Cada niño hace girar sus spinner, entonces le dice el maestro el color obtenido. Luego, el maestro totales ¿cuántos alumnos tiene cada color (por ejemplo, 9 rojas, 10 azules, 11 verde) y, a continuación, lee el mayor número (en este caso, 11). ¿Cuál es el valor esperado del número que lee? (Si dos números son iguales, ella lee el valor común.)"

El principal obstáculo que he tenido al trabajar sobre esta cuestión fue que ninguna de las herramientas estándar para trabajar con los valores esperados (linealidad de la expectativa, la recursividad, etc.) parecía útil, y aunque es posible escribir directamente una expresión de la forma $\sum x P(x)$ para obtener el valor esperado, el resultado es tan difícil de manejar que es inútil. En particular, parece difícil incorporar perfectamente el max condición sin la necesidad de recurrir a un doble de la suma con muy torpe restricciones.

Si este problema tiene una bonita forma cerrada de la solución, también me gustaría estar muy interesado en el caso general de los $n$ estudiantes y $m$ colores, aunque parece menos probable que tiene una forma cerrada.

Cualquier ayuda es muy apreciada.

Answer 1

Supongamos que hay$n$ estudiantes y$m$ colores$1,2,\ldots,m$. Dados los enteros$x_1, \ldots, x_m \ge 0$ con$x_1 + \ldots + x_m = n$, sea$a(x_1, \ldots, x_n)$ la probabilidad de que cada color$j$ ocurra$x_j$ veces. Luego$$a(x_1,\ldots,x_m) = \dfrac{n!}{x_1! x_2! \ldots x_m!} m^{-n}$ $ Luego, desea tomar$$E[\max(X_1,\ldots,X_n)] = \sum_x a(x_1,\ldots,x_m) \max(x_1,\ldots,x_m)$ $

En el caso que nos ocupa,$m=3$ y$n=30$, obtengo$$ \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}$ $

Answer 2

Estás buscando la expectativa del máximo de un multinomial uniforme. No parece haber una solución de forma cerrada para este problema. Vea este enlace de MathOverflow para el comportamiento asintótico de la expectativa. Este enlace de MathOverflow da límites a la probabilidad de cola para el máximo, y también una referencia a un algoritmo para la distribución exacta del máximo.