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.

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?

share|improve this question
    
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
add comment

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
Awesome, thanks! –  user9326 Apr 9 '11 at 15:06
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

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