Place labelled balls independently into labelled bins, each with probability . The vector of bin counts has a multinomial distribution, and each count separately has the binomial distribution . Distinct bin counts have covariance , so they are dependent for and . Counts of bins of a specified size are sums of indicator variables; their expectations follow from the linearity of expectation, without any independence between bins.
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 givesFor 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.
For balls in uniformly and independently chosen boxes, put . The empty-box indicators in uniform allocation have negative pairwise covariance, so . Chebyshev's inequality givesSince , this proves the displayed convergence in probability. The centring and the negative covariance are essential to this short proof; an expectation limit alone would not establish concentration.
Place balls independently and uniformly into boxes. If indicates that box is empty, then , , and, for ,Indeed all balls avoid one specified box with probability and two specified boxes with probability . The indicator random variable identities give the expectations, variances, and covariance. Finally proves strict negativity. Thus the number of empty boxes has and by the variance of a sum.
In a uniform balls-in-bins allocation with and , a fixed bin count has convergence in distribution to a Poisson distribution variable of mean by the Poisson limit theorem. If counts bins containing exactly balls, symmetry and the linearity of expectation give for each fixed . In particular the expected empty fraction tends to , and the expected fraction with at least two balls tends to . These are statements about expectations; convergence of the random fractions requires an additional argument.
Articles by others on the same topic
There are currently no matching articles.