Distribusi jumlah tabrakan maksimum

Question

Diberikan $n$ tempat sampah dan $m$bola, lempar setiap bola ke tempat sampah yang dipilih secara acak. Setiap lemparan bersifat independen.

Berapa distribusi jumlah maksimum tumbukan (yaitu jumlah bola maksimum dalam satu wadah)?

Membiarkan $X_{ij}$ menjadi variabel acak indikator yang menunjukkan apakah bola $i$ berada di tempat sampah $j$; kita punya:$$ \mathbb{E}[X_{ij}] = \Pr(X_{ij} = 1) = \frac1n $$

Membiarkan $Y_j$ hitung jumlah bola di tempat sampah $j$ setelah $m$melempar; kita punya:$$ 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} $$

Membiarkan $Z$ menjadi jumlah bola maksimum dalam satu tempat setelahnya $m$ lemparan, yaitu: $$ 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 $$

Saya tertarik untuk menemukan distribusi $Z$, terutama untuk kasus ketika $n = m$.

---

Ini adalah beban maksimum untuk masalah alokasi acak.

Wikipedia sangat terikat$\mathbb{E}[Z]$ kapan $n = m$ sebagai: $$ \mathbb{E}[Z] = \Gamma^{-1}(n) - \frac32 + o(1) $$

---

Namun, saya ingin mencari distribusi sebenarnya, jika memungkinkan.

Salah satu pendekatan yang mungkin saya pikirkan adalah bahwa dengan definisi di atas untuk variabel acak, saya harus mencari distribusi $\left( Z \ \big| \ S = n \right)$ adalah, dimana: $$ S = \left ( \sum_{j=1}^{n} Y_j \right) \sim \mathsf{Binomial}\left(n^2, \frac1n\right) $$

Dan sejak untuk $n=m$ kita punya itu $1 \leq Z \leq n$, maka saya berasumsi bahwa saya dapat menghitung: $$ \Pr(Z=k \ | \ S=n), \ k \in \overline{1,\dots,n} $$

Apakah ini arah yang baik?

Answer 1

Anda meminta distribusi statistik urutan maksimum variabel acak multinomial dengan probabilitas yang sama. Googling "statistik pesanan multinomial" memberikan banyak informasi yang relevan.

Tampaknya tidak ada fungsi massa probabilitas bentuk-tertutup, lihat : Menghitung distribusi yang tepat dari beberapa fungsi hitungan multinomial terurut: statistik maksimum, minimum, rentang, dan jumlah pesanan , oleh Marco Bonetti, Pasquale Cirillo dan Anton Ogay (Oktober 2019, The Royal Society).

"Dalam menguji hipotesis ekuiprobabilitas, semua statistik di atas bergantung pada perkiraan (seperti Normal, $\chi^{2}$, Beta, Dirichlet atau Gumbel), karena distribusi persisnya tidak diketahui. "

*** Makalah mereka mengasumsikan ekuiprobabilitas dan membahas algoritma untuk menghitung distribusi maksimum (persamaan 4.1) serta perkiraan. Tampaknya ini adalah cara terbaik yang diketahui siapa pun di dunia. Pengaturan$n=m$ mungkin sepertinya bukan kasus khusus di mana segala sesuatunya disederhanakan. ***

(Kontribusi utama mereka adalah: "kami menyajikan algoritme umum baru untuk menghitung distribusi yang tepat dari minimum multinomial, rentang dan jumlah $J$ statistik pesanan terbesar. ")