คำถามถามว่าเราจะจากไปอย่างไร $\displaystyle p=1 - \frac{N!}{(N-k)!\,N^k}$ สำหรับความน่าจะเป็นของการชนกันของ $k$ ค่าสุ่มที่สม่ำเสมอระหว่าง $N$เพื่อการประมาณ $\displaystyle p\ประมาณ\frac{k(k-1)}{2N}$ (ซึ่งถือว่า $k$ มีขนาดเล็กเมื่อเทียบกับ $\sqrt N$ ).
ก่อนอื่นเราจะกลับไปที่ $\displaystyle1-p=\prod_{j=0}^{k-1}{\left(1-\frac j N\right)}$ซึ่งเป็นวิธีการ $p$ ถูกกำหนดมาแต่แรกแล้ว จากนั้นเราก็หาลอการิทึมทั้งสองข้างแล้วใช้มัน $u>0,v>0\implies\ln(u\,v)=\ln(u)+\ln(v)$ ที่จะได้รับ
$$\displaystyle\ln(1-p)=\sum_{j=0}^{k-1}{\ln\left(1-\frac j N\right)}$$
สำหรับขนาดเล็ก $|x|$มันถือ $\ln(1+x)\ประมาณ x$. ใช้สิ่งนี้กับ $x=p$ ทางด้านซ้ายและ $\displaystyle x=\frac j N$ ทางด้านขวาเราได้รับ $\displaystyle p\ประมาณ\sum_{j=0}^{k-1}\frac j N$. เราเขียนสิ่งนี้ใหม่เป็น $\displaystyle p\ประมาณ\frac 1 N\sum_{j=0}^{k-1}j$.
ตอนนี้เราใช้ผลรวมของจำนวนเต็มที่ไม่เป็นลบน้อยกว่า $k$ เป็น $\displaystyle\frac{k\,(k-1)}2$ และได้รับสิ่งที่ต้องการ $\displaystyle p\ประมาณ\frac{k(k-1)}{2N}$.
โดยไม่ต้องพิสูจน์: การประมาณนี้ของ $p$ เป็นส่วนเกินเสมอ มันปิดน้อยกว่า $+28\%$ เมื่อไร $k\le\sqrt N$, น้อยกว่า $+14\%$ เมื่อไร $k\le\sqrt{2N}$, น้อยกว่า $+7\%$ เมื่อไร $k\le2\sqrt N$.
ข้อผิดพลาดส่วนใหญ่มาจากการประมาณค่า $\ln(1-p)\ประมาณ-p$. การประมาณที่ดีกว่ามากคือ:
$$p\ประมาณ1-e^{-\frac{k(k-1)}{2N}}$$
ซึ่งสมมติขึ้นเท่านั้น $k\ll N$ ค่อนข้างมากกว่า $k\ll\sqrt N$. อย่างไรก็ตาม ระวังว่าสูตรทางเลือกนี้มีความไม่แน่นอนทางตัวเลขสำหรับรายย่อย $p$.
ในความคิดเห็นจะมีการถามเพิ่มเติม
จะเข้าใจได้อย่างไร (สูตรนี้) จาก $1/N$ อย่างละคู่? แต่ละคู่มีค่าเท่ากันสองเหตุการณ์ที่ไม่ปะติดปะต่อหรือไม่ ส่วนใดของการได้มาคือการประมาณ?
วิธีง่าย ๆ ในการหาค่าความน่าจะเป็น $p$ ว่ามีการปะทะกัน $k$ ค่าสม่ำเสมอระหว่าง $N$ (สำหรับ $0\le k\le N$) เป็นส่วนเติมเต็มของความน่าจะเป็นที่จะไม่มีการชนกัน
สำหรับการแก้ไข $N$, กำหนด $q_k$ ตามความน่าจะเป็นที่จะไม่มีการชนกันภายหลัง $k$ ค่า อย่างชัดเจน $q_0=q_1=1$. และสำหรับ $k\ge2$, $q_k$ คือความน่าจะเป็นที่จะไม่มีการชนกันระหว่างอันแรก $k-1$ ค่า (นั่นคือ $q_{k-1}$) เวลาความน่าจะเป็นที่จะไม่มีการชนกันระหว่าง $k-1$ ค่าก่อนหน้าและค่าสุดท้ายที่จับมา ซึ่งก็คือ $\displaystyle\frac{N-k}N$ (เหตุผลมีว่า $N-k$ ค่าระหว่าง $N$ ที่ไม่รั่วไหลไปชนกับค่าสุดท้ายที่ดึงมา)
มันเป็นไปตาม $\displaystyle q_k=q_{k-1}\left(1-\frac k N\right)$, ดังนั้น $\displaystyle q_k=\prod_{j=0}^{k-1}{\left(1-\frac j N\right)}$, ดังนั้น $$p=1-\prod_{j=0}^{k-1}{\left(1-\frac j N\right)}=1-\frac{N!}{(N-k)!\,N ^k}$$
นี้แน่นอน ดูสองส่วนแรกของคำตอบนี้เพื่อหาค่าประมาณ
แหล่งหนึ่งให้เหตุผลประมาณว่า:
วิธีหนึ่งในการมองสิ่งนี้คือถ้าคุณเลือก $k$ องค์ประกอบแล้วมี $k(kâ1)/2$ องค์ประกอบที่เป็นคู่ซึ่งแต่ละองค์ประกอบมี $1/N$ โอกาสที่จะเป็นคู่ที่มีค่าเท่ากัน
อาร์กิวเมนต์แบบโบกมือนี้ไม่ได้ให้ผลลัพธ์ที่แน่นอนทางคณิตศาสตร์ของ $\displaystyle p=\frac{k(k-1)}{2N}$เนื่องจากเหตุการณ์ไม่ปะติดปะต่อ ตราบเท่าที $p$ มีขนาดเล็ก เราสามารถหลีกเลี่ยงได้ แต่นั่นจะผิดพลาดอย่างร้ายแรงเมื่อ $k>\sqrt{2N}$.
เมื่อไร $k = \sqrt{N}$โอกาสนี้ใกล้ถึง 50% แล้ว
เป็นจริงถ้า 39.3% ใกล้เคียงกับ 50%