Câu hỏi hỏi làm thế nào chúng ta đi từ $\displaystyle p=1 - \frac{N!}{(N-k)!\,N^k}$ cho xác suất va chạm của $k$ các giá trị ngẫu nhiên thống nhất giữa $N$, gần đúng $\displaystyle p\approx\frac{k(k-1)}{2N}$ (giả sử $k$ là nhỏ so với $\sqrt N$ ).
Đầu tiên chúng ta quay lại $\displaystyle1-p=\prod_{j=0}^{k-1}{\left(1-\frac j N\right)}$, đó là cách $p$ đã được xác định ở nơi đầu tiên. Sau đó, chúng tôi lấy logarit ở cả hai bên và sử dụng nó $u>0,v>0\implies\ln(u\,v)=\ln(u)+\ln(v)$ để có được
$$\displaystyle\ln(1-p)=\sum_{j=0}^{k-1}{\ln\left(1-\frac j N\right)}$$
cho nhỏ $|x|$, nó giữ $\ln(1+x)\xấp xỉ x$. Áp dụng điều này cho $x=p$ ở phía bên trái và $\displaystyle x=\frac j N$ ở phía bên phải, chúng tôi nhận được $\displaystyle p\approx\sum_{j=0}^{k-1}\frac j N$. Chúng tôi viết lại điều này như $\displaystyle p\approx\frac 1 N\sum_{j=0}^{k-1}j$.
Bây giờ chúng ta sử dụng tổng các số nguyên không âm nhỏ hơn $k$ Là $\displaystyle\frac{k\,(k-1)}2$ và nhận được mong muốn $\displaystyle p\approx\frac{k(k-1)}{2N}$.
Không có bằng chứng: xấp xỉ này của $p$ luôn luôn là dư thừa. Nó tắt ít hơn $+28\%$ khi nào $k\le\sqrt N$, ít hơn $+14\%$ khi nào $k\le\sqrt{2N}$, ít hơn $+7\%$ khi nào $k\le2\sqrt N$.
Hầu hết các lỗi là từ xấp xỉ $\ln(1-p)\approx-p$. Một xấp xỉ tốt hơn nhiều là:
$$p\approx1-e^{-\frac{k(k-1)}{2N}}$$
giả sử chỉ $k\ll N$ còn hơn là $k\ll\sqrt N$. Tuy nhiên, hãy lưu ý rằng công thức thay thế này không ổn định về mặt số lượng đối với các công thức nhỏ $p$.
Trong bình luận, nó được hỏi thêm
Làm thế nào để tôi hiểu (công thức này) từ $1/N$ cho mỗi cặp? Các cặp có hai giá trị bằng nhau có phải là các sự kiện rời nhau không? Phần nào trong dẫn xuất của nó là gần đúng?
Một cách dễ dàng để lấy được xác suất $p$ rằng có một sự va chạm giữa $k$ giá trị thống nhất giữa $N$ (vì $0\le k\le N$) là phần bù của xác suất không va chạm.
Đối với một cố định $N$, định nghĩa $q_k$ như xác suất không có va chạm sau $k$ các giá trị. Chắc chắn $q_0=q_1=1$. Va cho $k\ge2$, $q_k$ là xác suất không có va chạm giữa những người đầu tiên $k-1$ các giá trị (nghĩa là $q_{k-1}$), tính xác suất không có xung đột giữa $k-1$ các giá trị trước đó và giá trị được vẽ cuối cùng, đó là $\displaystyle\frac{N-k}N$ (biện minh có một chính xác $N-k$ giá trị giữa $N$ không bị rò rỉ do va chạm đối với giá trị cuối cùng được rút ra).
Nó theo sau $\displaystyle q_k=q_{k-1}\left(1-\frac k N\right)$, do đó $\displaystyle q_k=\prod_{j=0}^{k-1}{\left(1-\frac j N\right)}$, do đó $$p=1-\prod_{j=0}^{k-1}{\left(1-\frac j N\right)}=1-\frac{N!}{(N-k)!\,N ^k}$$
Điều này là chính xác. Xem hai phần đầu tiên của câu trả lời này để biết nguồn gốc của các xấp xỉ.
Một nguồn biện minh cho xấp xỉ là:
Một cách để xem xét điều này là nếu bạn chọn $k$ các phần tử, sau đó có $k(kâ1)/2$ cặp phần tử, mỗi phần tử có một $1/N$ cơ hội trở thành một cặp có giá trị bằng nhau.
Đối số vẫy tay này không mang lại một dẫn xuất chính xác về mặt toán học của $\displaystyle p=\frac{k(k-1)}{2N}$, vì các sự kiện không rời rạc. Miễn là $p$ là nhỏ, chúng ta có thể thoát khỏi nó, nhưng điều đó trở nên sai lầm nghiêm trọng khi $k>\sqrt{2N}$.
Khi nào $k = \sqrt{N}$, cơ hội này là gần 50%.
Điều đó đúng nếu 39,3% là gần 50%.
