Máxima de carga de una bandeja en la $n$ bolas con pesos en $m$ papeleras problema

Question

$n$ bolas, cada uno con un peso $p_i$, son arrojados a $m$ papeleras. Cada contenedor es elegido con el uniforme de probabilidad.

Probar o refutar que el valor esperado de la carga máxima entre las cargas de contenedores es $\frac1m\sum_{j=1}^n p_j$, donde con "carga" significa la suma de los pesos de las bolas en ese compartimiento.

Ahora, yo era capaz de modelar el problema en el valor esperado de cada bin y esta es: $E[X_i]=\frac1m\sum_{j=1}^n p_j$ donde $X_i$ es la carga de la tolva $i$.

Debo calcular algo como esto: $$E[\max_{1 \leq i \leq n} {X_i}]$$

¿Tiene usted alguna idea? O es la ecuación para refutar? Pero, no tengo idea de cómo tiene que encontrar un contraejemplo para refutar con valores esperados.

Answer 1

Quiero desmentir que $s = \frac1m\sum_{j=1}^n p_j$ es el valor esperado de la cantidad máxima por la $m>1$.

(Al $m=1$, esto es trivialmente cierto - todas las bolas están en el mismo y único de reciclaje).

Pero, al $m>1$, esta expresión es el valor esperado de la carga en cualquiera de los recipientes (uso de la linealidad de la expectativa a ver esto - cada bola tiene probabilidad de $\frac{1}{m}$ para ser lanzado en una bandeja específica). Así que si dejamos $X_i = \text{load of bin }i$, tenemos $$\forall i: EX_i = s$$ $$\sum_{i} X_i = \sum_{j} p_j = ms$$

Desde $\sum_{i} X_i = ms$, a menos que $X_i=s$ por cada $i$,$\max_{i} X_i > s$. Así $$E \max_{i} X_i = Pr(X_1 = X_2 = \cdots = X_n=s) s + $$ $$Pr(\text{Not all }X_i \text{ are equal})E(\max_{i} X_i | \text{Not all }X_i\text{ are equal})$$ Al $Pr(\text{Not all }X_i \text{ are equal}) > 0$ (true siempre $m>1,n>0$ - por ejemplo, usted puede tener el primer recipiente se vacía y el último pleno, y viceversa), tenemos: $$E \max_{i} X_i > ( Pr(X_1 = X_2 = \cdots = X_n=s) + Pr(\text{Not all }X_i \text{ are equal})) s = s$$ desde $E(\max_{i} X_i | \text{Not all }X_i\text{ are equal}) > s$.