Вопрос спрашивает, как мы идем от $\displaystyle p=1 - \frac{N!}{(Nk)!\,N^k}$ для вероятности столкновения $к$ равномерно случайные значения среди $N$, в приближении $\displaystyle p\приблизительно\frac{k(k-1)}{2N}$ (что предполагает $к$ мал по сравнению с $\квт N$ ).
Сначала мы возвращаемся к $\displaystyle1-p=\prod_{j=0}^{k-1}{\left(1-\frac j N\right)}$, вот как $р$ было определено в первую очередь. Затем мы логарифмируем обе стороны и используем это $u>0,v>0\имплицитно\ln(u\,v)=\ln(u)+\ln(v)$ получить
$$\displaystyle\ln(1-p)=\sum_{j=0}^{k-1}{\ln\left(1-\frac j N\right)}$$
Для маленьких $|х|$, он держит $\ln(1+x)\приблизительно x$. Применив это к $х=р$ с левой стороны и $\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$.
Теперь мы используем, что сумма неотрицательных целых чисел меньше, чем $к$ является $\displaystyle\frac{k\,(k-1)}2$ и получить желаемое $\displaystyle p\приблизительно\frac{k(k-1)}{2N}$.
Без доказательства: это приближение $р$ всегда в избытке. Это меньше, чем $+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$. Однако имейте в виду, что эта альтернативная формула численно нестабильна для малых $р$.
В комментарии дополнительно спрашивается
Как мне понять (эту формулу) из $1/N$ для каждой пары? Являются ли пары, каждая из которых имеет два одинаковых значения, непересекающимися событиями? Какая часть в его выводе является приближением?
Один простой способ получить вероятность $р$ что происходит столкновение между $к$ единые ценности среди $N$ (за $0\le k\le N$) является дополнением вероятности отсутствия столкновения.
Для фиксированного $N$, определять $q_k$ как вероятность того, что столкновения не будет после $к$ ценности. Очевидно $q_0=q_1=1$. И для $k\ge2$, $q_k$ есть вероятность того, что не было столкновения среди первых $к-1$ ценности (то есть $q_{k-1}$), время вероятность того, что нет столкновения между $к-1$ предыдущие значения и последнее нарисованное, которое $\displaystyle\frac{Nk}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!}{(Nk)!\,N ^к}$$
Это точно. См. Первые два раздела этого ответа для получения приближений.
Один источник оправдал приближение следующим образом:
Один из способов взглянуть на это так: если вы выберете $к$ элементы, то есть $k(kâ1)/2$ пары элементов, каждый из которых имеет $1/N$ шанс быть парой равных значений.
Этот махающий рукой аргумент не дает математически точного вывода $\displaystyle p=\frac{k(k-1)}{2N}$, так как события не пересекаются. Так долго как $р$ мала, нам это может сойти с рук, но это становится совершенно неправильным, когда $k>\sqrt{2N}$.
Когда $k = \sqrt{N}$, этот шанс близок к 50%.
Это верно, если 39,3% близко к 50%.
