Fix bins. In repeated uniform balls-in-bins allocation, throw each remaining ball independently into those same bins, remove every ball that is alone in its bin, and repeat with the survivors. Let be the number remaining before round .
Conditional on , a specified ball is alone with probability . Its survival probability is therefore , so linearity of expectation gives
For or the next count is zero. Here denotes the fixed bin count, not the current number of balls; confusing those two quantities changes the process.
The survival indicator random variables are generally dependent. For two initial balls and two bins, they survive together exactly when they choose the same bin, of probability each round. Hence and for . In particular, replacing the conditional formula by the same nonlinear function of would not be justified by linearity of expectation.

Articles by others on the same topic (0)

There are currently no matching articles.