3
$\begingroup$

Theorem: Choose $Q$ random natural numbers in the set $\{1,2, \dots, M\}.$ The probability of getting at least one collision is

$$P_C(Q) = 1 - \frac{M - (Q - 1)}{M} P_{\neg C}(Q-1).$$

Notation: By $P_C$, I mean the probability of getting a collision. By $P_{\neg C}$ I mean the probability of not getting a collision.

Remark: This is the birthday problem.

Remark: So $P_C(Q)$ is just being computed by using its complement. The reason I express the theorem this way is because its induction proof relates directly to it being enunciated this way.

Theorem: $$P_C(Q) \approx 1 - e^{-\tfrac{(Q-1)Q}{2M}}.$$

Proof: We know $$e^{-x} = 1 - x + \frac{x^2}{2!} - \frac{x^3}{3!} + \frac{x^4}{4!} - \ldots$$

If we take the two terms of this expansion, we get $e^{-x} \approx 1 - x$. Then

\begin{align} P_{\neg C}(Q)&= \prod_{i=1}^{Q-1} \left(1 - \dfrac{i}{M}\right)\\ &\approx \prod_{i=1}^{Q-1} e^{-i/M} \\ &= e^{-1/M} e^{-2/M} \dotsc\ e^{-(Q - 1)/M} \\ &= e^{-\sum_{i=1}^{Q-1} i/M} \\ &= e^{-\dfrac{1}{M} (Q-1)Q/2}\\ &= e^{-\dfrac{(Q-1)Q}{2M}}, \end{align}

So $P_C(Q) \approx 1 - P_{\neg C}(Q),$ as desired.

Question: How can I (at least) have some notion of how off the right number I am if I use this estimation to compute the probability of getting a collision in a concrete case?

$\endgroup$
  • 1
    $\begingroup$ Are you asking because you want to know the precise error of the approximation or because you want to know if the equation is good enough for casual estimation purposes for certain Q/M? $\endgroup$ – Future Security Jan 7 at 19:45
  • $\begingroup$ I'd like to know the precise error of the approximation. (What's Q/M?) $\endgroup$ – user45491 Jan 7 at 20:50
  • $\begingroup$ The precise error can (probably) only be calculated by calculating exact probabilities for each combination of set size and number of samples. It's only easy to calculate exact probabilities for very small set sizes. The math stack exchange can better address the birthday paradox and combinatoric aspects of this problem. And maybe if they can't think of any method they might be able to think of a way to find bounds on the error. $\endgroup$ – Future Security Jan 7 at 21:36
2
$\begingroup$

Clearly, for $x\in (0,1)$ which is our case, $$ e^{-x}-(1-x)< x^2/2, $$ and thus the relative multiplicative error between the estimate and actual answer satisfies $$ \frac{\widehat{P}_{\neg C}(Q)}{P_{\neg C}(Q)}<\prod_{i=1}^{Q} \frac{(i/M)^2}{2(1-(i/M))}\leq 2^{-Q} M^{-2Q} \frac{Q(Q+1)(2Q+1)}{6}\frac{1}{(M+1-(Q+1)/2))}, $$ by using the sum of first $Q$ squares on the numerator and the arithmetic geometric mean inequality in the denominator. So $$ \frac{Q^3/3}{ 2^Q M^{2Q}(M-Q/2)} $$ is a good approximation to the error.

$\endgroup$
  • 1
    $\begingroup$ Yes. Watch that the expression derived is the relative error on $P_{\neg C}(Q)$, not on $P_C(Q)$. Note: when applying $P_C(Q) \approx 1 - e^{-\tfrac{(Q-1)Q}{2M}}$ with $Q\ll\sqrt M$ using a computer with fixed-width arithmetic (including most spreadsheets), we can encounter a numerical stability issue because the second term of the subtraction is very close to $1$. We can avoid this by using a function giving $e^x-1$, often called expm1(), with $P_C(Q)=-\mathtt{expm1}\left(-\tfrac{(Q-1)Q}{2M}\right)$. Another option is using $P_C(Q) \approx \dfrac{(Q-1)Q}{2M}$ when $Q\ll\sqrt M$. $\endgroup$ – fgrieu Jan 8 at 7:52

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.