La carga máxima es $O(\log\log n/\log\log\log n)$

Question

Hay $n$ cubos etiquetados $0,1,\ldots,n-1$ y $\log_2n$ jugadores. Cada jugador elige una ubicación inicial $k$ uniformemente al azar, y coloca una bola en cada uno de los recipientes $$k\bmod n,k+1\bmod n,\ldots,k+n/\log_2n-1\bmod n.$$ Demuestre que el número máximo de bolas en cualquier recipiente es $O(\log\log n/\log\log\log n)$ con alta probabilidad como $n\rightarrow\infty$ .

No estoy muy seguro de cómo empezar aquí.

Answer 1

Para simplificar, cuando digo $\log n$ Quiero decir $\log_2 n$ .

Utilizo el lema 5.1 del libro "Probabilidad y Computación": Cuando se lanzan n bolas de forma independiente y uniforme al azar en $n$ bins, la probabilidad de que la carga máxima sea superior a $3 \ln n / \ln \ln n$ es como máximo $1 / n$ para un tamaño suficientemente grande $n$ .

Dejemos que $X_i$ sea una variable aleatoria que denote el número de bolas en la bandeja $i$ . Equivale al número de jugadores cuya ubicación inicial está entre $i - n / \log n + 1$ y $i$ .

Consideremos ahora el conjunto de variables $V = \{X_1, X_{1+n / \log n}, X_{1+2 n / \log n}, \ldots$ } es decir, $X_i$ donde $i$ es congruente con $1$ modulo $n / \log n$ . Tenga en cuenta que hay $\log n$ tales variables. Considere cada jugador como una pelota y cada variable aleatoria como un recipiente -- cuando un jugador selecciona como posición inicial $k$ entonces de entre estas variables existe exactamente una variable cuyo valor se incrementa en $1$ . Dado que hay $\log n$ y los jugadores lanzan las bolas uniformemente al azar, podemos utilizar el Lemma 5.1 y, por tanto, la probabilidad de que el cualquiera de los $X_i$ es más que $3 \ln \log n / \ln \ln \log n$ es como máximo $1 / \log n$ . Por lo tanto, con una probabilidad de al menos $1 - 1 / \log n$ ninguna de las variables de $P$ está por encima de $3 \ln \log n / \ln \ln \log n$ .

Ahora, considere $X_i$ , donde $i$ no es congruente con $1$ modulo $N / \log n$ . Equivale al número de jugadores cuya ubicación inicial está entre $i - n / \log n + 1$ y $i$ Por lo tanto, este valor está limitado como máximo por la suma de dos variables en $V$ . Así, si sabemos que ninguna de las variables de $V$ está por encima de $3 \ln \log n / \ln \ln \log n$ , entonces no hay variables $X_i$ está por encima de $6 \ln \log n / \ln \ln \log n$ . Así, la probabilidad de que ninguna variable $X_i$ está por encima de $6 \ln \log n / \ln \ln \log n$ es al menos $1 - 1 / \log n$ que se acerca a $1$ como $n$ se acerca al infinito.