ทั้งสองอย่างนี้น่าจะเป็นการปะทะกันในการโจมตีวันเกิดหรือไม่?

เกี่ยวกับการโจมตีวันเกิด หนังสือ วิศวกรรมการเข้ารหัส พูดว่า:

โดยทั่วไป หากองค์ประกอบสามารถรับค่าที่แตกต่างกันได้ N ค่า คุณก็สามารถทำได้ คาดว่าจะเกิดการชนกันครั้งแรกหลังจากเลือกประมาณ $\sqrt{N}$ สุ่ม องค์ประกอบ เรากำลังทิ้งรายละเอียดที่แน่นอนไว้ที่นี่ แต่ $\sqrt{N}$ เป็น ค่อนข้างใกล้ชิด สำหรับความขัดแย้งวันเกิด เรามี N = 365 และ $\sqrt{N} \ประมาณ 19$. จำนวนคนที่ต้องการก่อนมีโอกาส วันเกิดซ้ำเกิน 50% คือ 23 จริง แต่ $\sqrt{N}$ ใกล้เข้ามาแล้ว เพียงพอสำหรับจุดประสงค์ของเราและเป็นค่าประมาณที่นักเข้ารหัส มักจะใช้

วิธีหนึ่งในการมองสิ่งนี้คือถ้าคุณเลือก $k$ องค์ประกอบแล้ว มี $k(k - 1)/2$ องค์ประกอบที่เป็นคู่ซึ่งแต่ละองค์ประกอบมี $1/N$ โอกาสที่จะเป็นคู่ที่มีค่าเท่ากัน ดังนั้นโอกาสที่จะพบ ใกล้จะชนกันแล้ว $k(k - 1)/2N$. เมื่อไร $k = \sqrt{N}$โอกาสนี้ อยู่ใกล้ถึง 50 % .

และ วิกิพีเดีย พูดว่า:

ตัวอย่างเช่น พิจารณาสถานการณ์ที่ครูที่มีนักเรียน 30 คนในชั้นเรียน (n = 30 คน) ถามวันเกิดของทุกคน (เพื่อความง่าย ไม่ต้องสนใจปีอธิกสุรทิน) เพื่อระบุว่านักเรียนสองคนมีวันเกิดเดียวกันหรือไม่ (ซึ่งสอดคล้องกับการชนกันของแฮช ดังจะอธิบายต่อไป) โอกาสนี้อาจดูน้อยนิด ตอบโต้โดยสัญชาตญาณ ความน่าจะเป็นที่นักเรียนอย่างน้อยหนึ่งคนจะมีวันเกิดเดียวกันกับนักเรียนคนอื่นๆ ในแต่ละวันคือประมาณ 70% (สำหรับ n = 30) จากสูตร ${\displaystyle 1-{\frac {365!}{(365-n)!\cdot 365^{n}}}}$.

ซึ่งสามารถใช้ถ้อยคำใหม่ในแง่ของภาษาใน วิศวกรรมการเข้ารหัส:

$$1 - \frac{N!}{(N-k)! * น^k}$$

มันควรจะเท่ากับต่อไปนี้จาก วิศวกรรมการเข้ารหัส:

$$ (k(k-1))/(2N) $$

ทำไม

คำถามถามว่าเราจะจากไปอย่างไร $\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%