Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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