¿cuál es el número máximo esperado de bolas en la misma caja?

Question

Si tengo $m$ cajas distintas, y $n$ bolas distintas. Pongo todas estas bolas en las cajas con una caja que posiblemente contenga más de una bola. ¿Cuál es el número máximo esperado de bolas en una caja?

Le agradezco sus ideas para resolver este problema.

Answer 1

Esto se responde en un documento de Raab y Steger (cambian su $n$ y $m$ ). El caso $n=m$ es más sencillo y ya se conocía (véase su introducción).

Intuitivamente, para encontrar la respuesta "correcta", se calcula el número esperado de bins $X_t$ que obtienen al menos $t$ bolas; el valor de $t$ tal que $X_t \approx 1$ debe estar "cerca" de la expectativa.

Para que esto sea riguroso, siga estos pasos:

1. Encontrar un valor crítico $t_0$ de manera que si $t \ll t_0$ entonces la probabilidad de que una caja determinada obtenga al menos $t$ bolas está muy cerca de $1$ y si $t \gg t_0$ entonces está muy cerca de $0$ .
2. Cuando $t \gg t_0$ una cota de unión muestra que con alta probabilidad ninguna caja obtiene al menos $t$ bolas.
3. Cuando $t \ll t_0$ el número esperado de cajas con al menos $t$ bolas está muy cerca de $m$ por lo que la probabilidad de que ninguna caja obtenga al menos $t$ bolas es muy pequeño.
4. Deducir que la mayor parte de la masa de probabilidad de la expectativa se concentra alrededor de $t_0$ y, por tanto, la propia expectativa se aproxima a $t_0$ .

Al hacer los cálculos, nos encontramos con un problema en el paso 3: el número de cajas esperadas con al menos $t$ bolas no es $m$ pero algo más pequeño. Raab y Steger muestran que la variable $X_t$ se concentra en torno a su expectativa (utilizando el "método del segundo momento", es decir, la desigualdad de Chebyshev), y así $\Pr[X_t = 0]$ es realmente pequeño.

La mayor parte del trabajo consiste en estimar la distribución binomial del número de bolas en cada caja, encontrar el $t_0$ para cada caso; el método falla cuando el número de bolas es significativamente menor que el número de contenedores.

---

Aquí hay un código de Sage:

def analyze_partition(partition, bins):
    last = partition[0]
    counts = [1]
    for part in partition[1:]:
        if part != last:
            last = part
            counts += [1]
        else:
            counts[-1] += 1
    counts.append(bins - sum(counts))
    return multinomial(*partition) * multinomial(*counts)

def expected_max(balls, bins):
    return sum([max(partition) * analyze_partition(partition, bins)
                for partition in partitions(balls)
                if len(partition) <= bins])/bins^balls

Cuando se enchufa $10$ bolas y $5$ contenedores, obtengo $$1467026/390625 \approx 3.76.$$