การกระจายจำนวนการชนสูงสุด
ให้ $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} $$
เป็นทิศทางที่ดีหรือไม่?
คำตอบ
คุณกำลังขอการแจกแจงสถิติการสั่งซื้อสูงสุดของตัวแปรสุ่มพหุนามที่มีความน่าจะเป็นเท่ากัน Googling "สถิติคำสั่งซื้อหลายชื่อ" ให้ข้อมูลที่เกี่ยวข้องมากมาย
ดูเหมือนจะไม่มีฟังก์ชันมวลความน่าจะเป็นรูปแบบปิดให้ดูที่ : การคำนวณการแจกแจงที่แน่นอนของฟังก์ชันบางอย่างของจำนวนพหุนามที่เรียงลำดับ: สถิติสูงสุดต่ำสุดช่วงและผลรวมของคำสั่งซื้อโดย Marco Bonetti, Pasquale Cirillo และ Anton Ogay (ตุลาคม 2019 ราชสมาคม)
"ในการทดสอบสมมติฐานความสามารถในการเทียบเคียงสถิติทั้งหมดข้างต้นอาศัยการประมาณ (เช่นค่าปกติค่า $\chi^{2}$, เบต้า, ดิริชเล็ตหรือกัมเบล) ซึ่งไม่ทราบการแจกแจงที่แน่นอน "
*** เอกสารของพวกเขาถือว่าความเหมาะสมและกล่าวถึงอัลกอริทึมสำหรับการคำนวณการแจกแจงของค่าสูงสุด (สมการ 4.1) รวมทั้งการประมาณ สิ่งนี้ดูเหมือนจะดีที่สุดทุกคนในโลกที่รู้วิธีทำ การตั้งค่า$n=m$ อาจดูเหมือนจะไม่เป็นกรณีพิเศษใด ๆ ที่ทำให้สิ่งต่างๆง่ายขึ้น ***
(ผลงานหลักของพวกเขาคือ: "เรานำเสนออัลกอริทึมทั่วไปแบบใหม่สำหรับการคำนวณการแจกแจงที่แน่นอนของพหุนามขั้นต่ำของช่วงและผลรวมของ $J$ สถิติการสั่งซื้อที่ใหญ่ที่สุด ")