- #1
economist13
- 15
- 0
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?
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?