Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/probability-and-computing/2/a/solution

For each of the balls, let be the indicator random variable that ball survives the round of uniform balls-in-bins allocation. Condition on its chosen bin. Each of the other balls avoids that bin with probability , independently, so the probability that ball is served is . Hence, for ,
We used linearity of expectation to sum the indicator random variables; their mutual independence is unnecessary. For or , the next count is zero. This states the boundary cases without an ambiguous when .

New to topics? Read the docs here!