Probability of picking elements randomly without frequent repeats

Question

If I have a set S that has n unique elements, and I pick from it such that each element has an equal probability of being chosen, how many elements should S be so that the probability of seeing any elements repeated within a small subset of drawn elements (let's say, 5) is low (like less than .5)? To put it another way, if I am using a random number generator to pick 5 or so integers from 1 to n, how large should n be to ensure the probability of seeing the same number come up twice is less than .5? Sorry if my phrasing is confusing, I'm not a mathematician. I'm interested in this because it will simplify some code I'm working on by a lot.

Answer 1

Selecting $k$ from $n$ the probability of no collisions (all $k$ are distinct) is

$ (1) (1 - 1/n) (1-2/n) \dots (1- (k-1)/n)$.

For $n$ large relative to $k$ this is approximately $1 - (1/n + 2/n + \dots (k-1)/n) = 1 - k(k-1)/2n$.

In other words, if $n$ is comparable to $k^2$ there will be some non-negligible positive probability of a collision and if $n \gg k^2$ the probability will be low.

This is close to the "Birthday Problem".

(addition: ) To rigorously bound the probability $p$ of a collision, note that the expected number of collisions is $k(k-1)/2n$ and this quantity is larger than $p$. To guarantee that $p$ is less than $\epsilon$, taking $n > k(k-1)/2\epsilon$ is sufficient. This is not as good an estimate as the Poisson approximation which is asymptotically optimal. To find the minimum possible $n$ for given $p$ and $k$ one can use the formula for the probability of a collision and "solve for $n$" with a polynomial root-finder.

Answer 2

The Poisson approximation says that, choosing $k$ times from the set $\{1,2\,\dots n\}$, the probability of no collisions is about $\exp(-{k\choose 2}/n)$.

You may want this probability to be some value $p$. Setting the Poisson approximation to $p$ and solving for $n$ gives the formula $$n\approx {k(k-1)\over 2\ln(1/p)}.$$

For example with $k=5$ and $p=1/2$ we get $$n\approx {10\over\ln(2)}= 14.4269$$ which I'd round up to $n=15$.