I have a problem where I need to find the chance of finding a collision in a two to one set of size $N$. For example: Let's say I have 10 indices. There are then 5 pairs that map to the same output. What is the probability of finding a collision when you draw $s$ samples from your set $N$.
The probability of such an event happening when you take $s$ samples from the set is:
$$ Pr(\text{at least one collision)} = 1 - \prod_{i -1}^{s-1} \frac{N-2i}{N-i} $$
Is there a way of writing this in a closed form?
Thanks in advance for any help!
From the introduction, $N$ is even. You have $1-\frac{N}{N}\frac{N-2}{N-1}\frac{N-4}{N-2}\cdots\frac{N-2s+2}{N-s+1}$ with $0 \le s \le \tfrac N2$
You can write this probability as $$1 - \dfrac{2^s \left(\frac N 2\right)!\, (N-s)!}{\left(\frac N 2 -s\right)!\, N! } = 1-2^s \dfrac{N/2 \choose s}{N \choose s}$$
either of which you might regard as being in a closed from