Motivation
When independent jobs are assigned uniformly to servers, the average load can be small while the busiest server receives many jobs. The maximum load, rather than the average, often controls the worst response time or memory requirement.
We study independent balls placed uniformly into bins. A union bound proves that very large loads are unlikely. To show that a moderately large load is also likely to occur, we count overloaded bins and control their variance. The two arguments meet at the scale .
Model
Let . Each of labeled balls independently chooses one of bins uniformly. Let be the number of balls in bin and . All logarithms are natural. The phrase “with high probability” here means that the stated failure probability tends to zero as .
Theorems
Theorem 3.3.1
(Maximum-load upper bound)
For every integer ,
Consequently, for and all sufficiently large , this probability is at most .
Theorem 3.3.2
(Maximum-load lower bound)
For and all sufficiently large ,
Together the two estimates give with high probability, with the displayed constants serving as convenient bounds rather than optimal constants.
The asymptotic choices of are used only when and , which holds for sufficiently large . The finite inequality in the first theorem is valid for every and , though it can exceed one and then gives a trivial bound.
Proofs
Upper bound by witness subsets
Proof
(Union bound over witness sets)
Fix a bin. If it receives at least balls, some set of labeled balls all chose that bin. A specified set does so with probability . The union bound gives
When , the left side and binomial coefficient are zero, so the inequality remains true. For , the standard bound proves the second inequality. A further union bound over all bins gives the finite upper bound. Independence is used for the specified set of balls; independence between bin-load events is not needed.
Set and choose . For sufficiently large , . Therefore
The constant six is chosen to make the calculation simple. A sharper analysis can improve it, but is not needed to establish the scale.
Proof X-ray
An overloaded bin has a small witness
Where each hypothesis enters: independence is used only to give a fixed set of balls probability of all choosing the same bin; independence between different bins is never needed. The key move is to replace the event “this bin has load at least ” by the larger event “some -subset of balls all chose this bin”, which can be counted. The estimate absorbs the counting factor, and the union bound over bins contributes the factor . The argument closes because exceeds by a constant multiple at the chosen scale, so is a negative power of . If one instead added witness probabilities and called the sum the exact tail probability, it would double-count placements that contain several witnesses.
Interpreting the upper bound
The combinatorial factor counts labeled subsets, not ordered lists of balls. If a bin receives exactly balls, there is one witness subset; if it receives more, there can be many. This overcounting is harmless in a union bound. It would be incorrect to add witness probabilities and call the result an exact load probability, because several witnesses can occur in the same placement.
The inequality can be seen from and . For the latter, compare with . The sum is at least the integral, giving the claimed lower bound on the factorial. These estimates are deliberately elementary; no normal approximation is used.
Why choose a threshold involving ? The logarithm of the upper bound is . If is a sufficiently large constant times , then is comparable to , and the negative term dominates . The proof makes that heuristic into an explicit inequality for sufficiently large . For small inputs, the finite bound or a direct computation can be used instead of the asymptotic threshold.
An upper tail bound remains correct even when it exceeds one, but it is not informative in that regime. It is always permissible to replace the right side by its minimum with one. At very small , the event that some bin has load at least may be almost certain, and a useful upper bound below one should not be expected from this counting argument.
Count bins with large load
Proof
(Expected number of overloaded bins)
For the lower bound, let . Then exactly when . For one fixed bin, . When ,
Indeed, , , and for . Hence .
For and sufficiently large , we have and . Thus , giving
A large mean alone does not prove that with high probability. We next show that the overload indicators have nonpositive pairwise covariance, giving a small enough variance.
Negative pairwise covariance
Proof
(Negative pairwise covariance and Chebyshev)
For distinct bins , condition on . The remaining balls are independently uniform over the other bins, so
The conditional probability is nonincreasing in : with fewer trials, a binomial count can be coupled as a subset of the successes from more trials. The indicator is nondecreasing.
If are independent copies of a random variable, then
Applying this identity with shows that the indicators of and have nonpositive covariance. Each indicator has variance at most its mean, so
Chebyshev's inequality gives
This proves the lower bound. We did not assume the bin loads or overload indicators were independent; the covariance sign was proved from the conditional distribution.
Counterexample mode
The bin loads are not independent
With two balls and two bins, always. If , then . Treating the two loads as independent would ignore this constraint. The lower-bound proof uses a conditional monotonicity argument instead.
Understanding the lower-bound estimates
The binomial calculation uses the event that a bin has exactly balls as a subset of the event that it has at least . Its probability includes a factor for the other balls avoiding that bin. At the chosen threshold grows much more slowly than , so requiring exactly balls still leaves a sufficiently large expected number of witnesses.
Proof X-ray
Why the lower bound needs a second moment
The aim is only that some bin reaches load . The first moment gives , but a large mean could come from rare huge values of , so the real idea is Chebyshev's inequality, which needs . The covariance sign is the hypothesis doing the work: the cross terms of are nonpositive, so only the diagonal terms remain. The condition is used only for the binomial estimate. The argument closes because .
For , every factor in is at least . Dividing by gives the stated lower bound on the binomial coefficient. The estimates and then trade sharp constants for a compact expression. The lower-bound proof needs that expression to grow after multiplication by ; it does not require the exact distribution of .
The covariance calculation has an intuitive coupling. Once balls are known to be in bin , the other balls choose independently among the remaining bins. Comparing this with a smaller value of adds trials that might land in bin but cannot remove existing successes. Thus the chance that bin reaches the threshold decreases as bin 's load increases. The independent-copy identity turns that monotonicity into the precise pairwise covariance inequality needed for the variance bound.
Chebyshev is applied to the nonnegative integer count , not to a single bin. On the event that no bin is overloaded, equals zero and deviates from its large mean by the entire mean. The variance bound makes that event unlikely. The conclusion is an existence statement for at least one heavily loaded bin; it does not identify which bin in advance.
The two thresholds have different constants: the upper proof rules out loads above a sufficiently large multiple of the scale, while the lower proof finds a load above a sufficiently small multiple. Their failure probabilities both tend to zero, so a union bound makes both conclusions hold simultaneously with high probability. This is exactly what the statement means here; it does not assert convergence to a particular constant.
Changing the number of balls or bins
The witness argument has a useful general form. If independent balls are placed uniformly in bins, then
There are choices for the bin and choices for a labeled witness set. This formula remains valid when and differ. Its best asymptotic interpretation depends on their relationship, however; the lower-bound threshold proved above is specific to and should not be transferred to every load regime without a new calculation.
For example, if there are far fewer balls than bins, most bins are empty and the busiest load may be much smaller than the -balls-in--bins scale. If there are many more balls than bins, the average load itself is larger than one. The fixed-bin distribution is then , and both the expected number of overloaded bins and the useful threshold must be recalculated. Stating the input regime is part of stating the probability theorem and helps prevent an otherwise correct estimate from being applied to the wrong system.
Worked examples
Worked example 3.3.3
(Two balls and two bins)
There are four equally likely ordered placements. In two of them both balls choose the same bin, giving maximum load two; in the other two they split, giving maximum load one. Thus . The finite union bound is valid but much looser in this tiny example.
Worked example 3.3.4
(A specified witness)
For , a specified set of three balls all choosing a specified bin has probability . There are choices of the set, so a union bound gives at most for that bin's load being at least three. The witness events overlap; adding their probabilities is an upper bound, not an exact count.
Worked example 3.3.5
(The average does not reveal the maximum)
With balls and bins, the average load is exactly one in every placement. Nevertheless, placing all balls in one bin gives maximum load , while placing one ball in each bin gives maximum one. The random-model theorem describes how likely different maximum loads are; the average alone cannot determine them.
Worked example 3.3.6
(An empty-bin analogy)
When one bin receives many balls, fewer balls remain available for the other bins. The conditional distribution above makes this precise. It does not say that every event involving two bins is independent, or that all possible load events have a simple product probability.
Common mistakes
Common mistake
(One overloaded bin is not some overloaded bin)
The probability that a fixed bin is overloaded is not the probability that some bin is overloaded. The latter is a union over bins. Omitting that factor can produce a bound that is far too optimistic.
Common mistake
(Treating bin loads as independent)
Conversely, multiplying probabilities for different bins as if their loads were independent is unjustified. The fixed total number of balls creates dependence. For the lower bound we established the particular covariance inequality needed and then used Chebyshev's inequality.
Common mistake
(A large mean does not give positivity)
Finally, an expectation of a positive count does not by itself imply that the count is positive with high probability. A random variable can have a large mean caused by rare large values. The variance estimate prevents that possibility from defeating the lower-bound argument here.
Summary
A large load has a witness set of balls, so two union bounds give the upper tail. A count of overloaded bins has large expectation at a smaller threshold, and negative pairwise covariance keeps its variance under control. Together these results locate the maximum load at order with high probability under independent uniform placement.
Exercises
Quick check
(For two balls and two bins, compute .)
List the four placements of the two labeled balls.
Solution · Answer
The two balls must choose different bins. Two of the four equally likely placements do so, giving probability .
Quick check
(For , bound the probability that a specified bin receives at least three balls using three-ball witnesses.)
Count the triples of balls, then multiply by the probability that a given triple all chooses the specified bin.
Solution · Answer
There are possible witness triples, each with probability . The union bound is .
Quick check
(Explain why the events and cannot both occur with two balls and two bins.)
Use the fact that the two loads add up to the number of balls.
Solution · Answer
Their loads sum to the total number of balls, namely two. Both being two would make the sum at least four.
Quick check
(If a nonnegative integer-valued has positive mean and , use Chebyshev's inequality to bound .)
The event is the event that is below its mean.
Solution · Answer
On , the deviation from its mean is at least . Chebyshev gives .