Répartition du nombre maximum de collisions
Donné $n$ bacs et $m$balles, lancez chaque balle dans une poubelle choisie uniformément au hasard. Chaque lancer est indépendant.
Quelle est la distribution du nombre maximum de collisions (c'est-à-dire le nombre maximum de balles dans un bac)?
Laisser $X_{ij}$ être une variable aléatoire indicatrice indiquant si la balle $i$ est dans la poubelle $j$; nous avons:$$ \mathbb{E}[X_{ij}] = \Pr(X_{ij} = 1) = \frac1n $$
Laisser $Y_j$ compter le nombre de balles dans le bac $j$ après $m$jette; nous avons:$$ 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} $$
Laisser $Z$ être le nombre maximum de balles dans un bac après $m$ jette, c'est-à-dire: $$ 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 $$
Je suis intéressé à trouver la distribution de $Z$, en particulier pour le cas où $n = m$.
Il s'agit de la charge maximale pour le problème d'allocation aléatoire.
Wikipedia donne un lien étroit sur$\mathbb{E}[Z]$ quand $n = m$ comme: $$ \mathbb{E}[Z] = \Gamma^{-1}(n) - \frac32 + o(1) $$
Cependant, je veux trouver la distribution réelle, si possible.
Une approche possible que j'avais à l'esprit est qu'étant donné les définitions ci-dessus pour les variables aléatoires, je dois trouver la distribution de $\left( Z \ \big| \ S = n \right)$ est ou: $$ S = \left ( \sum_{j=1}^{n} Y_j \right) \sim \mathsf{Binomial}\left(n^2, \frac1n\right) $$
Et depuis pour $n=m$ nous avons ça $1 \leq Z \leq n$, alors je suppose que je peux calculer: $$ \Pr(Z=k \ | \ S=n), \ k \in \overline{1,\dots,n} $$
Est-ce une bonne direction?
Réponses
Vous demandez la distribution de la statistique d'ordre maximum des variables aléatoires multinomiales avec des probabilités égales. Google "statistiques d'ordre multinomial" donne beaucoup d'informations pertinentes.
Il ne semble pas y avoir de fonction de masse de probabilité de forme fermée, voir : Calcul des distributions exactes de certaines fonctions des comptes multinomiaux ordonnés: statistiques maximum, minimum, plage et sommes d'ordre , par Marco Bonetti, Pasquale Cirillo et Anton Ogay (Octobre 2019, The Royal Society).
«En testant l'hypothèse d'équiprobabilité, toutes les statistiques ci-dessus reposent sur des approximations (comme la normale, la $\chi^{2}$, le Beta, le Dirichlet ou le Gumbel), étant leurs distributions exactes inconnues. "
*** Leur article suppose l'équiprobabilité et discute des algorithmes de calcul de la distribution du maximum (équation 4.1) ainsi que des approximations. Cela semble être le meilleur que quiconque au monde sache faire. Réglage$n=m$ ne semble probablement pas être un cas particulier où les choses se simplifient. ***
(Leur contribution principale est: "nous présentons de nouveaux algorithmes généraux pour calculer les distributions exactes du minimum multinomial, de l'intervalle et de la somme des $J$ statistiques d'ordre le plus élevé. ")