Распределение максимального количества коллизий
Дано $n$ урны и $m$шары, бросьте каждый шар в корзину, выбранную наугад. Каждый бросок независим.
Каково распределение максимального количества столкновений (т. Е. Максимального количества шаров в одном контейнере)?
Позволять $X_{ij}$ - индикаторная случайная величина, обозначающая, $i$ находится в корзине $j$; у нас есть:$$ \mathbb{E}[X_{ij}] = \Pr(X_{ij} = 1) = \frac1n $$
Позволять $Y_j$ подсчитать количество шаров в корзине $j$ после $m$бросает; у нас есть:$$ 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} $$
Позволять $Z$ быть максимальным количеством шаров в одной корзине после $m$ бросает, то есть: $$ 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 $$
Мне интересно найти распределение $Z$, особенно для случая, когда $n = m$.
Это максимальная нагрузка для задачи случайного распределения.
Википедия дает жесткие рамки$\mathbb{E}[Z]$ когда $n = m$ в виде: $$ \mathbb{E}[Z] = \Gamma^{-1}(n) - \frac32 + o(1) $$
Однако я хочу, если возможно, найти реальное распределение.
Один из возможных подходов, который я имел в виду, заключается в том, что, учитывая приведенные выше определения случайных величин, я должен найти распределение $\left( Z \ \big| \ S = n \right)$ это здесь: $$ S = \left ( \sum_{j=1}^{n} Y_j \right) \sim \mathsf{Binomial}\left(n^2, \frac1n\right) $$
А поскольку для $n=m$ у нас есть это $1 \leq Z \leq n$, то я предполагаю, что могу вычислить: $$ \Pr(Z=k \ | \ S=n), \ k \in \overline{1,\dots,n} $$
Это хорошее направление?
Ответы
Вы запрашиваете распределение статистики максимального порядка полиномиальных случайных величин с равными вероятностями. Поиск в Google "статистики полиномиального порядка" дает много полезной информации.
Кажется, что не существует функции вероятности и массы в замкнутой форме, см . : Вычисление точных распределений некоторых функций упорядоченных полиномиальных счетчиков: максимум, минимум, диапазон и суммы порядковых статистик , Марко Бонетти, Паскуале Чирилло и Антон Огай (Октябрь 2019 г., Королевское общество).
"При проверке гипотезы равновероятности все приведенные выше статистические данные основаны на приближении (например, Нормальный, $\chi^{2}$, Бета, Дирихле или Гумбель), поскольку их точное распределение неизвестно ".
*** В их статье предполагается равновероятность и обсуждаются алгоритмы вычисления распределения максимума (уравнение 4.1), а также приближения. Кажется, это лучшее, что кто-либо в мире умеет делать. Настройка$n=m$ вероятно, это не какой-то особый случай, когда все упрощается. ***
(Их главный вклад: «мы представляем новые общие алгоритмы для вычисления точных распределений полиномиального минимума, диапазона и суммы $J$ статистика крупнейших заказов. ")