최대 충돌 수 분포

Aug 20 2020

주어진 $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$.


이것은 임의 할당 문제에 대한 최대로드입니다.

Wikipedia 는$\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} $$

이것은 좋은 방향입니까?

답변

1 SherwinLott Aug 30 2020 at 07:51

확률이 같은 다항 랜덤 변수의 최대 주문 통계 분포를 요청합니다. 인터넷 검색 "다항 주문 통계"는 많은 관련 정보를 제공합니다.

폐쇄 형 확률 질량 함수가없는 것 같습니다. 참조 : 정렬 된 다항 계수의 일부 함수에 대한 정확한 분포 계산 : 최대, 최소, 범위 및 주문 통계 합계 , Marco Bonetti, Pasquale Cirillo 및 Anton Ogay (2019 년 10 월, The Royal Society).

"등가성 가설을 테스트 할 때 위의 모든 통계는 근사치 (예 : 정규, $\chi^{2}$, 베타, 디리클레 또는 검벨), 정확한 분포는 알려지지 않았습니다. "

*** 그들의 논문은 등 확률을 가정하고 최대 분포 (방정식 4.1)와 근사값을 계산하는 알고리즘에 대해 설명합니다. 이것은 세계에서 누구든지 할 줄 아는 가장 좋은 것 같습니다. 환경$n=m$ 일이 단순화되는 특별한 경우는 아닌 것 같습니다. ***

(그들의 주요 기여는 : "우리는 다항 최소값, 범위 및 합계의 정확한 분포를 계산하기위한 새로운 일반 알고리즘을 제시합니다. $J$ 가장 큰 주문 통계. ")