Distribuzione del numero massimo di collisioni
Dato $n$ bidoni e $m$palle, lancia ogni palla in un cestino che viene scelto uniformemente a caso. Ogni lancio è indipendente.
Qual è la distribuzione del numero massimo di collisioni (ovvero il numero massimo di palline in un contenitore)?
Permettere $X_{ij}$ essere un indicatore variabile casuale che denota se palla $i$ è nel cestino $j$; noi abbiamo:$$ \mathbb{E}[X_{ij}] = \Pr(X_{ij} = 1) = \frac1n $$
Permettere $Y_j$ conta il numero di palline nel cestino $j$ dopo $m$lanci; noi abbiamo:$$ 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} $$
Permettere $Z$ essere il numero massimo di palline in un contenitore dopo $m$ lanci, ovvero: $$ 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 $$
Mi interessa trovare la distribuzione di $Z$, in particolare per il caso in cui $n = m$.
Questo è il carico massimo per il problema di allocazione casuale.
Wikipedia dà un limite stretto$\mathbb{E}[Z]$ quando $n = m$ come: $$ \mathbb{E}[Z] = \Gamma^{-1}(n) - \frac32 + o(1) $$
Tuttavia, se possibile, voglio trovare la distribuzione effettiva.
Un possibile approccio che avevo in mente è che, date le definizioni di cui sopra per le variabili casuali, devo trovare la distribuzione di $\left( Z \ \big| \ S = n \right)$ dov'è: $$ S = \left ( \sum_{j=1}^{n} Y_j \right) \sim \mathsf{Binomial}\left(n^2, \frac1n\right) $$
E da allora per $n=m$ ce l'abbiamo $1 \leq Z \leq n$, quindi presumo di poter calcolare: $$ \Pr(Z=k \ | \ S=n), \ k \in \overline{1,\dots,n} $$
È una buona direzione?
Risposte
Stai chiedendo la distribuzione della statistica di ordine massimo di variabili casuali multinomiali con probabilità uguali. Googling "statistiche degli ordini multinomiali" fornisce molte informazioni rilevanti.
Non sembra esserci una funzione di massa di probabilità in forma chiusa, vedi : Calcolo delle distribuzioni esatte di alcune funzioni dei conteggi multinomiali ordinati: massimo, minimo, intervallo e somma delle statistiche degli ordini , di Marco Bonetti, Pasquale Cirillo e Anton Ogay (Ottobre 2019, The Royal Society).
"Nel testare l'ipotesi di equiprobabilità, tutte le statistiche di cui sopra si basano su approssimazioni (come il normale, il $\chi^{2}$, Beta, Dirichlet o Gumbel), essendo la loro esatta distribuzione non nota. "
*** Il loro articolo presuppone l'equiprobabilità e discute algoritmi per il calcolo della distribuzione del massimo (equazione 4.1) così come le approssimazioni. Questo sembra essere il meglio che chiunque al mondo sappia fare. Ambientazione$n=m$ probabilmente non sembra essere un caso particolare in cui le cose si semplificano. ***
(Il loro contributo principale è: "presentiamo nuovi algoritmi generali per calcolare le distribuzioni esatte del minimo multinomiale, del range e della somma dei $J$ statistiche sugli ordini più grandi. ")