What is the error in this collision probability approximation? 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)&amp;= \prod_{i=1}^{Q-1} \left(1 - \dfrac{i}{M}\right)\\
       &amp;\approx \prod_{i=1}^{Q-1} e^{-i/M} \\
       &amp;= e^{-1/M} e^{-2/M} \dotsc\ e^{-(Q - 1)/M} \\
       &amp;= e^{-\sum_{i=1}^{Q-1} i/M} \\
       &amp;= e^{-\dfrac{1}{M} (Q-1)Q/2}\\
       &amp;= 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?
Clearly, for $x\in (0,1)$ which is our case,
$$
e^{-x}-(1-x)&lt; 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)}&lt;\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.