随机算法 (Fall 2011)/Balls-into-balls Occupancy Problem

From EtoneWiki
Jump to: navigation, search

Now we ask about the loads of bins. Assuming that balls are uniformly and independently assigned to bins, for , let be the load of the th bin, i.e. the number of balls in the th bin.

An easy analysis shows that for every bin , the expected load is equal to the average load .

Because there are totally balls, it is always true that .

Therefore, due to the linearity of expectations,

Because for each ball, the bin to which the ball is assigned is uniformly and independently chosen, the distributions of the loads of bins are identical. Thus is the same for each . Combining with the above equation, it holds that for every , . So the average is indeed the average!


Next we analyze the distribution of the maximum load. We show that when , i.e. balls are uniformly and independently thrown into bins, the maximum load is with high probability.

Theorem
Suppose that balls are thrown independently and uniformly at random into bins. For , let be the random variable denoting the number of balls in the th bin. Then
Proof.
Let be an integer. Take bin 1. For any particular balls, these balls are all thrown to bin 1 with probability , and there are totally distinct sets of balls. Therefore, applying the union bound,

According to Stirling's approximation, , thus

Figure 1

Due to the symmetry. All have the same distribution. Apply the union bound again,

When ,

Therefore,

When , Figure 1 illustrates the results of several random experiments, which show that the distribution of the loads of bins becomes more even as the number of balls grows larger than the number of bins.

Formally, it can be proved that for , with high probability, the maximum load is within , which is asymptotically equal to the average load.