Distribución del número máximo de colisiones
Dado $n$ contenedores y $m$bolas, arroje cada bola en un contenedor que se elige uniformemente al azar. Cada lanzamiento es independiente.
¿Cuál es la distribución del número máximo de colisiones (es decir, el número máximo de bolas en un contenedor)?
Dejar $X_{ij}$ ser una variable aleatoria indicadora que denota si la bola $i$ está en la papelera $j$; tenemos:$$ \mathbb{E}[X_{ij}] = \Pr(X_{ij} = 1) = \frac1n $$
Dejar $Y_j$ cuenta el número de bolas en el contenedor $j$ después $m$lanza tenemos:$$ Y_j \sim \mathsf{Binomial}\left( m, \ \frac1n \right) $$ $$ \mathbb{E}[Y_j] = \mathbb{E}\left[\sum_{i=1}^{m}X_{ij}\right] = \sum_{i=1}^{m}\mathbb{E}[X_{ij}] = \frac{m}{n} $$
Dejar $Z$ ser el número máximo de bolas en un contenedor después $m$ lanza, es decir: $$ Z = \max_{1\leq j \leq n} Y_j = \max_{1\leq j \leq n} \sum_{i=1}^{m}X_{ij} $$ $$ \frac{m}{n} \leq Z \leq m $$
Estoy interesado en encontrar la distribución de $Z$, particularmente para el caso cuando $n = m$.
Ésta es la carga máxima para el problema de asignación aleatoria.
Wikipedia ofrece un límite estricto$\mathbb{E}[Z]$ cuando $n = m$ como: $$ \mathbb{E}[Z] = \Gamma^{-1}(n) - \frac32 + o(1) $$
Sin embargo, quiero encontrar la distribución real, si es posible.
Un posible enfoque que tenía en mente es que, dadas las definiciones anteriores para las variables aleatorias, tengo que encontrar la distribución de $\left( Z \ \big| \ S = n \right)$ es donde: $$ S = \left ( \sum_{j=1}^{n} Y_j \right) \sim \mathsf{Binomial}\left(n^2, \frac1n\right) $$
Y ya que para $n=m$ tenemos eso $1 \leq Z \leq n$, entonces supongo que puedo calcular: $$ \Pr(Z=k \ | \ S=n), \ k \in \overline{1,\dots,n} $$
¿Es esta una buena dirección?
Respuestas
Solicita la distribución de la estadística de orden máximo de variables aleatorias multinomiales con probabilidades iguales. Buscar en Google "estadísticas de pedidos multinomiales" proporciona mucha información relevante.
No parece haber una función de masa de probabilidad de forma cerrada, ver : Calcular las distribuciones exactas de algunas funciones de los conteos multinomiales ordenados: máximo, mínimo, rango y sumas de estadísticas de orden , por Marco Bonetti, Pasquale Cirillo y Anton Ogay (Octubre de 2019, The Royal Society).
"Al probar la hipótesis de equiprobabilidad, todas las estadísticas anteriores se basan en aproximaciones (como el Normal, el $\chi^{2}$, Beta, Dirichlet o Gumbel), siendo sus distribuciones exactas desconocidas ".
*** Su artículo asume equiprobabilidad y analiza algoritmos para calcular la distribución del máximo (ecuación 4.1), así como aproximaciones. Esto parece ser lo mejor que nadie en el mundo sabe hacer. Ajuste$n=m$ probablemente no parece ser ningún caso especial en particular donde las cosas se simplifiquen. ***
(Su principal contribución es: "presentamos novedosos algoritmos generales para calcular las distribuciones exactas del mínimo multinomial, del rango y de la suma de los $J$ estadísticas de pedidos más grandes. ")