Întrebarea se întreabă de unde mergem $\displaystyle p=1 - \frac{N!}{(N-k)!\,N^k}$ pentru probabilitatea de coliziune a $k$ valori uniform aleatoare între $N$, la aproximare $\displaystyle p\aprox\frac{k(k-1)}{2N}$ (care presupune $k$ este mic în comparație cu $\sqrt N$ ).
Mai întâi ne întoarcem la $\displaystyle1-p=\prod_{j=0}^{k-1}{\left(1-\frac j N\right)}$, care este cum $p$ a fost determinată în primul rând. Apoi luăm logaritmul pe ambele părți și îl folosim $u>0,v>0\implies\ln(u\,v)=\ln(u)+\ln(v)$ a obține
$$\displaystyle\ln(1-p)=\sum_{j=0}^{k-1}{\ln\left(1-\frac j N\right)}$$
Pentru mici $|x|$, ține $\ln(1+x)\aproximativ x$. Aplicând acest lucru la $x=p$ pe partea stângă și $\displaystyle x=\frac j N$ pe partea dreaptă, primim $\displaystyle p\aprox\sum_{j=0}^{k-1}\frac j N$. Rescriem asta ca $\displaystyle p\aprox\frac 1 N\sum_{j=0}^{k-1}j$.
Acum folosim că suma numerelor întregi nenegative mai mică decât $k$ este $\displaystyle\frac{k\,(k-1)}2$ și obțineți ceea ce doriți $\displaystyle p\aprox\frac{k(k-1)}{2N}$.
Fără dovadă: această aproximare a $p$ este întotdeauna prin exces. Se reduce cu mai puțin de $+28\%$ când $k\le\sqrt N$, mai puțin decât $+14\%$ când $k\le\sqrt{2N}$, mai puțin decât $+7\%$ când $k\le2\sqrt N$.
Cea mai mare parte a erorii provine din aproximare $\ln(1-p)\aprox-p$. O aproximare mult mai bună este:
$$p\approx1-e^{-\frac{k(k-1)}{2N}}$$
care presupune doar $k\ll N$ Decat $k\ll\sqrt N$. Cu toate acestea, aveți grijă că această formulă alternativă este instabilă numeric pentru mici $p$.
În comentariu se cere suplimentar
Cum să înțeleg (această formulă) din 1 USD/N$ pentru fiecare pereche? Perechile au fiecare două evenimente disjunctive de valori egale? Care parte din derivarea sa este aproximarea?
O modalitate ușoară de a obține probabilitatea $p$ că există o coliziune între $k$ valori uniforme între $N$ (pentru $0\le k\le N$) este ca complement al probabilității să nu existe o coliziune.
Pentru un fix $N$, defini $q_k$ ca probabilitatea ca după aceea să nu existe o coliziune $k$ valorile. Evident $q_0=q_1=1$. Si pentru $k\ge2$, $q_k$ este probabilitatea ca între primii să nu fi fost nicio coliziune $k-1$ valori (adică $q_{k-1}$), cronologic probabilitatea ca nu există nicio coliziune între $k-1$ valorile anterioare și ultima desenată, care este $\displaystyle\frac{N-k}N$ (justificare acolo exact $N-k$ valori printre $N$ care nu se scurg până la coliziune pentru ultima valoare trasă).
Urmează $\displaystyle q_k=q_{k-1}\stanga(1-\frac k N\dreapta)$, prin urmare $\displaystyle q_k=\prod_{j=0}^{k-1}{\left(1-\frac j N\right)}$, prin urmare $$p=1-\prod_{j=0}^{k-1}{\left(1-\frac j N\right)}=1-\frac{N!}{(N-k)!\,N ^k}$$
Acesta este exact. Consultați primele două secțiuni ale acestui răspuns pentru derivarea aproximărilor.
O sursă a justificat aproximarea astfel:
Un mod de a privi acest lucru este că dacă alegi $k$ elemente, apoi există $k(kâ1)/2$ perechi de elemente, fiecare dintre ele având a 1 USD/N$ șansa de a fi o pereche de valori egale.
Acest argument cu mâna nu dă o derivație exactă din punct de vedere matematic a $\displaystyle p=\frac{k(k-1)}{2N}$, deoarece evenimentele nu sunt disjunctive. Atâta timp cât $p$ este mic, putem scăpa de asta, dar asta devine extrem de greșit când $k>\sqrt{2N}$.
Când $k = \sqrt{N}$, această șansă este aproape de 50%.
Este adevărat dacă 39,3% este aproape de 50%.
