Probability question on keys

1. Jan 20, 2010

economist13

A total of r keys are to be put one at a time, in k boxes, with each key
independently being put in box i with probability pi ,
∑pi = 1. Each time a key is put in a nonempty box, we say that a collision occurs. Find
the expected number of collisions.

My professor hinted that we should use an indicator function, but I went about it a different way....(which I know to be wrong)

let X be the number of keys put into box i,

then E[X] = rpi. Since any key after key 1 will result in a collision, the rpi - 1 represents the expected number of collision for box i. then ∑(rpi -1) for all i and we get then that the total expected number of collisions is r-k.

Now, I know that cannot be correct, simply by thinking of the case where we have more boxes than keys (we cannot have negative collisions)

any hints?? what indicator function should I focus on?

2. Jan 22, 2010

bpet

one way is to determine E[Y] where Y=max(X-1,0)