Collisions in a sample of uniform distribution

Asked at a Microsoft interview: Assume you have a uniform distribution (can be discrete or continuous) of size X and you randomly select a sample of size Y. 1) What is the probability in terms of X and Y of a collision? 2) What is the expected number of collisions in terms of X and Y?

-
You are supposed to come up with these solutions during an interview? Yikes! –  Byron Schmuland Apr 9 '11 at 2:42
These are hard if you've never seen them before, but they're standard problems. Now if the distribution were anything but uniform... –  Michael Lugo Apr 9 '11 at 3:30
@Byron Yeah I was interviewing for a position in the machine learning group. I don't think I'll make it :( –  user9326 Apr 9 '11 at 15:06

For the chance of a collision, see this question. Derek Jennings's answer there with your notation reads:

$$\mathbb{P}(\mbox{collision})=1 - \left( 1- \frac{1}{X} \right)\left( 1- \frac{2}{X} \right)\cdots \left( 1- \frac{Y-1}{X} \right),$$

To answer the second question, we should decide what counts as a collision. For instance, if the sample is $1,2,1,1,3$ then you could say there is only one collision, since only one value is repeated. On the other hand, twice during the course of the sampling we could say "Hey, I've already seen that value". Under this second interpretation, there were two collisions.

Interpretation 1:

To find the expected number of collisions, it is useful to introduce the identically distributed indicator random variables $Z(i)$ for $1\leq i\leq X$ where $Z(i)=1$ if item $i$ appears more than once, and $Z(i)=0$ otherwise.

The number $N(i)$ of times that item $i$ appears is a binomial$(Y,1/X)$ random variable so $$\mathbb{P}(Z(i)=0)=\mathbb{P}(N(i)\leq 1)=\left({X-1\over X}\right)^{Y}+Y\left({X-1\over X}\right)^{Y-1}\left({1\over X}\right),$$ and
$$\mathbb{E}(\mbox{number of collisions})=\sum_{i=1}^X \mathbb{E}(Z(i)) =X\mathbb{P}(Z(1)=1) =X-X\left({X-1\over X}\right)^Y -Y \left({X-1\over X}\right)^{Y-1}.$$

Interpretation 2:

With similar arguments, you can calculate $$\mathbb{E}(\mbox{number of collisions})=Y+X\left({X-1\over X}\right)^Y -X.$$

-
Awesome, thanks! –  user9326 Apr 9 '11 at 15:06

For the continuous version, the probability of a collision will be $0$. That is, if the random variable $W$ has uniform distribution on the interval $[a, b]$, and we take a sample of size $n$, the probability of a collision is $0$. Indeed this is true for any continuous distribution.

For the discrete version, the answer is obviously different. This is a standard first probability course problem. You can find full information by searching under "Birthday Problem".

-