A total of r keys are to be put one at a time, in k boxes, with each key(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Probability question on keys

**Physics Forums | Science Articles, Homework Help, Discussion**