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.

$n$ items are distributed into $n$ boxes such that each item is independently put with probability $p_j$ to be put in box $j$, for $j=1,2,\ldots,n$, where $\sum_{j=1}^np_j=1$. A collision occurs whenever an item is put into a non-empty box. Find the expected number of collisions.

What's wrong with the following reasoning? Let $C_i$ be the number of collisions in box $i$. Then $C_i+1$ is the number of items in box $i$, so $E[C_i+1]=np_j$ and $E[C_i]=np_j-1$. Therefore the expected number of collisions is $\sum_{j=1}^n(np_j-1)=0$. Obviously the number cannot be zero, because the number is sometimes positive but never negative.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

Let $C_i$ be the number of collisions in box $i$. Then $C_i+1$ is the number of items in box $i$...

That's wrong. More precisely, that's correct only if $C_i >0$. If $C_i=0$ then the number of items in box $i$ can be 0 or 1.

share|improve this answer
    
Oh right, I see. Thanks. –  strake Apr 19 '12 at 13:52
    
@strake If this is correct, you might consider accepting the answer by clicking the green checkmark. –  Fixee Apr 19 '12 at 16:18

Let $X$ be the number of boxes that end up with $0$ items, and let $Y$ be the number of boxes that end up with $1$ item. Then we have $n-Y$ remaining items, to be distributed between the remaining $n-X-Y$ boxes.

The number of collisions is $n-Y$ minus the number of boxes with more than $1$ item (since the first item put in such a box does not produce a collision). So the number of collisions is $(n-Y)-(n-X-Y)$, which is simply $X$. This is intuitively obvious (though I wasn't immediately sure). Every empty box causes a collision, that's the only way collisions are created, since the number of items and the number of boxes is the same.

What is the expected number of boxes that contain $0$ items? Define the random variable $V_i$ ($V$ for void) by $V_i=1$ if box $i$ ends up empty, and by $V_i=0$ otherwise. Then the number $V$ of empty boxes is given by $V=V_1+V_2+\cdots +V_n$.

Thus, by the linearity of expectation, we have $$E(V)=E(V_1+V_2+\cdots +V_n)=E(V_1)+E(V_2)+\cdots +E(V_n).$$ It remains to find $E(V_i)$. This is the probability that $V_i=1$, which is $(1-p_i)^n$.

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.