Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Probability question on keys

  1. Jan 20, 2010 #1
    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. jcsd
  3. Jan 22, 2010 #2
    one way is to determine E[Y] where Y=max(X-1,0)
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook