What is the error in this collision probability approximation?
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.