Concentration of Occupancy Counts and Missing Cells

Occupancy Counts as Functions of Independent Assignments

Suppose balls are assigned independently to a finite collection of bins. Two natural statistics are the number of bins that receive at least one ball and the number that receive none. The first measures how widely the balls are spread; the second counts the missing cells. Although the indicators for different bins are generally dependent, both totals concentrate because changing the assignment of one ball can alter either total by at most one.

This is a direct setting for the bounded-difference inequality, also called McDiarmid’s inequality. The key is to work with the independent ball assignments as the inputs to the statistic, rather than to assume that bin-level indicators are independent.

Definition: Let $Z_1,\ldots,Z_n$ be independent random variables taking values in the bin set $\{1,\ldots,m\}$, where $n\geq 1$ and $m\geq 1$. For bin $j$, let $I_j$ equal 1 if at least one ball is assigned to bin $j$, and 0 otherwise. The occupied-bin count is $K=\sum_{j=1}^m I_j$. The missing-bin count is $M=\sum_{j=1}^m(1-I_j)$. Consequently, $M=m-K$.

The random variables $Z_i$ need not have identical distributions: ball $i$ may have its own assignment probabilities. Independence of the assignments is the essential assumption for the bounded-difference inequality. The especially common uniform model has $P(Z_i=j)=1/m$ for every ball $i$ and bin $j$.

Exact Means for Occupied and Missing Bins

For each bin $j$, write $p_{ij}=P(Z_i=j)$. Independence gives the probability that bin $j$ receives no balls as a product: ball $i$ avoids it with probability $1-p_{ij}$, and all balls avoid it with probability $\prod_{i=1}^n(1-p_{ij})$. Summing the bin indicators then gives the exact means.

Result: For independent assignments with probabilities $p_{ij}$, $$ E[M]=\sum_{j=1}^m\prod_{i=1}^n(1-p_{ij}),\qquad E[K]=\sum_{j=1}^m\left[1-\prod_{i=1}^n(1-p_{ij})\right]=m-E[M]. $$ If every ball uses the same bin probabilities $p_1,\ldots,p_m$, these become $E[M]=\sum_{j=1}^m(1-p_j)^n$ and $E[K]=\sum_{j=1}^m[1-(1-p_j)^n]$. In the uniform model, $E[M]=m(1-1/m)^n$ and $E[K]=m[1-(1-1/m)^n]$.

To verify the result, define $J_j=1-I_j$, the indicator that bin $j$ is empty. Then $M=\sum_j J_j$. By independence across balls,

E[J_j]=P(J_j=1)=P(Z_i\ne j\text{ for every }i) =\prod_{i=1}^n(1-p_{ij}).

Linearity of expectation gives the formula for $E[M]$; it does not require the indicators $J_j$ to be independent. Since $K=m-M$, the formula for $E[K]$ follows. This argument is useful in its own right: dependence between bin indicators does not prevent an exact calculation of the mean.

Worked Example: Expected Occupancy in a Uniform Allocation

Suppose $n=250$ balls are assigned independently and uniformly to $m=500$ bins. Find the expected number of occupied and missing bins.

For any particular bin, the probability that all 250 balls avoid it is $(499/500)^{250}$. Therefore,

E[M]=500\left(\frac{499}{500}\right)^{250}\approx303.1135, \qquad E[K]=500\left[1-\left(\frac{499}{500}\right)^{250}\right]\approx196.8865.

Thus the expected occupied-bin count is approximately 196.9 to one decimal place, and the expected missing-bin count is approximately 303.1. The two means sum to 500, as they must because every bin is either occupied or missing.

Worked Example: Expected Counts With Unequal Bin Probabilities

Three balls are assigned independently among four bins. Each ball goes to bin 1 with probability $1/2$, bin 2 with probability $1/4$, and bins 3 and 4 with probability $1/8$ each. Find the expected counts.

The probability that bin 1 is empty is $(1/2)^3=1/8$, while the probability that bin 2 is empty is $(3/4)^3=27/64$. Each of bins 3 and 4 is empty with probability $(7/8)^3=343/512$. Hence

E[M]=\frac18+\frac{27}{64}+2\left(\frac{343}{512}\right) =\frac{965}{512}\approx1.8867.

The expected occupied count is

E[K]=4-E[M]=\frac{1083}{512}\approx2.1133.

These are expectations, not claims that a particular allocation has a fractional number of bins. The unequal probabilities matter: a heavily favored bin is less likely to be missing than a rarely selected one.

Why One Assignment Has Bounded Influence

Regard $K$ as a function of the full vector of assignments $(Z_1,\ldots,Z_n)$. Hold all assignments fixed except that of one ball, and move that ball from its current bin to a different bin. The source bin can cease to be occupied only if the moved ball was its sole occupant. The destination bin can become occupied only if it was empty. Thus at most one bin is lost from the occupied set and at most one is added.

These two changes cannot produce a net change of 2 or $-2$: losing one occupied bin and gaining one occupied bin cancel, while either change can occur alone. Therefore the occupied count changes by at most one in absolute value. Since $M=m-K$, its change is also at most one.

Coordinate-sensitivity result: If two assignment vectors differ in only one coordinate, their occupied counts differ by at most 1, and their missing counts differ by at most 1. Thus both functions have bounded differences $c_i=1$ for every ball $i$.

More formally, let $A$ be the set of bins occupied before moving a ball, and $A'$ the set afterward. The only bins whose membership in these sets can change are the source and destination. The source can only be removed from $A$, and the destination can only be added. Hence $|\,|A'|-|A|\,|\leq1$. The identity $M=m-K$ gives the same bound for missing bins. This verifies the sensitivity condition for every possible assignment vector, not merely with high probability.

Concentration Around the Exact Means

The bounded-difference inequality states that if $Z_1,\ldots,Z_n$ are independent and a function $g(Z_1,\ldots,Z_n)$ changes by at most $c_i$ when only coordinate $i$ changes, then for every $t>0$,

P\{g-E[g]\geq t\}\leq \exp\left(-\frac{2t^2}{\sum_{i=1}^n c_i^2}\right), \qquad P\{|g-E[g]|\geq t\}\leq 2\exp\left(-\frac{2t^2}{\sum_{i=1}^n c_i^2}\right).

The result applies to bounded measurable functions of independent inputs; here the assignment space is finite, so measurability is automatic. Applying it with $g=K$ or $g=M$ and $c_i=1$ gives the occupancy bounds below.

Theorem: For $n\geq1$ independent ball assignments to $m$ bins, and every $t>0$, $$ P\{K-E[K]\geq t\}\leq e^{-2t^2/n}, \qquad P\{|K-E[K]|\geq t\}\leq2e^{-2t^2/n}, $$ and the same two inequalities hold with $M$ in place of $K$.

For completeness, the application follows by checking the theorem’s hypotheses and substituting the sensitivities. The assignments are independent by assumption; the occupied and missing counts are bounded functions on the finite assignment space; and the coordinate-sensitivity result gives $\sum_i c_i^2=\sum_i1=n$. The displayed bounds therefore follow directly from the bounded-difference inequality. Also, $M=m-K$, so $M-E[M]=-(K-E[K])$; the missing-count upper-tail bound is the occupied-count lower-tail bound, and its two-sided bound is identical. The bounds are valid even when their right sides exceed 1, though in that case the trivial probability bound 1 is sharper. $\square$

Worked Example: A Two-Sided Occupancy Bound

In the uniform model with $n=m=100$, find a bounded-difference bound for the probability that the occupied count differs from its expectation by at least 10.

The exact mean is

E[K]=100\left[1-\left(\frac{99}{100}\right)^{100}\right] \approx100(1-0.3660323)=63.3968.

Using $t=10$ and $n=100$ in the two-sided bound gives

P\{|K-63.3968|\geq10\} \leq2\exp\left(-\frac{2(10)^2}{100}\right) =2e^{-2}\approx0.2707.

The same numerical bound applies to the missing-bin count around its mean $E[M]\approx36.6032$. The statement concerns deviations from the mean; it does not say that 10 bins are occupied or missing.

Reading the Bounds and Avoiding a Common Error

The exponent depends on the number of independent assignments, not directly on the number of bins. This reflects the fact that there are $n$ independent inputs, each with sensitivity at most one. For fixed $n$, increasing the number of bins changes the exact expectation but does not change the denominator $n$ in this particular concentration bound.

A common mistake is to treat the indicators $I_1,\ldots,I_m$ as independent and apply an independent-sum inequality to them. They are generally dependent: if a ball is assigned to one bin, it cannot simultaneously be assigned to another, and the total number of occupied bins is constrained by $n$. In the one-ball, two-bin case, for example, exactly one bin is occupied, so the two occupied indicators cannot be independent. The correction is to apply bounded differences to the independent ball assignments $Z_i$, after verifying how much changing one assignment can alter the statistic.

Another pitfall is to confuse the exact expectation with a likely observed value. An expectation can be non-integer, and a concentration inequality controls a probability of deviation rather than identifying the most likely count. The bound may also be conservative: it uses only the maximum coordinate sensitivity and not the detailed allocation probabilities. Its value is that it applies uniformly to the uniform and nonuniform independent-assignment models.

Key takeaway: Occupied and missing counts have exact means obtained by summing binwise probabilities, while their concentration follows from a different fact: changing one ball’s assignment changes either count by at most one. Independence belongs to the ball assignments; independence of the bin indicators is neither needed nor generally true.

Check Your Understanding

Use the definitions and bounded-difference argument to answer the following.

For independent assignments with probabilities $p_{ij}$, write the probability that bin $j$ is empty and the resulting formula for $E[M]$.
Explain why moving one ball can change the occupied-bin count by at most one, even though two bin occupancies may change.
In the uniform model with $n$ balls and $m$ bins, give the exact formulas for $E[K]$ and $E[M]$.
State the two-sided bounded-difference bound for $K$ in terms of $n$ and $t$.
Why is it generally incorrect to treat the occupied-bin indicators as independent when applying a concentration inequality?