1 Problem formulation and assumptions

The occupancy problem considers placing a fixed number of items (“balls”) into a fixed number of containers (“boxes”) according to a specified random mechanism. The primary interest lies in the resulting occupancy pattern—how many boxes receive no items, how many receive at least one item, and how many contain exactly a prescribed count.

A standard starting point specifies:

1 Problem formulation and assumptions

2 Exact probability results

3 Combinatorial tools used in occupancy problems

4 Asymptotic analysis and approximations

Different interpretations of these choices lead to distinct probability models, even when the question “how many boxes are empty?” sounds similar.

1.1 Variants of the random placement process

The model’s random mechanism can be varied along several axes, each affecting the exact formulas and limiting behavior.

1.1.1 Distinguishable vs. indistinguishable balls

If balls are distinguishable, each ball makes an independent random choice (or is placed sequentially). Outcomes are then typically counted by the number of assignments to boxes that produce a given occupancy vector. If balls are indistinguishable, only the final occupancy counts matter, and the counting method changes because permutations among identical balls do not create distinct outcomes.

1.1.2 Labeled vs. unlabeled boxes

When boxes are labeled, the identity of a box matters; for example, “box 1 is empty” is a distinct event from “box 2 is empty.” When boxes are unlabeled, the analysis focuses on occupancy patterns up to relabeling, which requires factoring out the symmetry among boxes. Many classical results assume labeled boxes for convenience.

1.1.3 Sampling with replacement vs. without replacement

In the “with replacement” version, each ball independently selects a box, possibly repeating earlier choices. In “without replacement” versions, the choices are constrained (for instance, there may be a limited number of placements per box, or the selection process may ensure distinct boxes for some subset of balls). These constraints alter the dependence structure among box counts and change the distributional forms.

1.2 Key random variables of interest

Occupancy problems typically study random variables derived from the occupancy counts.

1.2.1 Number of empty boxes

Let \(E\) denote the number of boxes that receive zero balls. This variable captures the “coverage” of the boxes by random assignments.

1.2.2 Number of non-empty boxes

Let \(N\) denote the number of boxes that receive at least one ball. It is directly related to \(E\) by \(N=m-E\) in the standard setting with exactly \(m\) boxes.

1.2.3 Box occupancy counts (exactly k balls in a box)

For a fixed integer \(k\ge 0\), one may define \(X_k\) as the number of boxes that contain exactly \(k\) balls. The collection \((X_0,X_1,X_2,\dots)\) summarizes the full histogram of occupancies across boxes.

2 Exact probability results

Exact results typically rely on combinatorial counting and careful use of indicator variables. Closed forms are available in many standard cases, especially when balls choose boxes independently and uniformly.

2.1 Distribution of the number of empty boxes

The distribution of the count of empty boxes is a central object because it is both interpretable and mathematically tractable.

2.1.1 Inclusion–exclusion approach

To compute \(\Pr(E=e)\), one counts assignments in which exactly \(e\) boxes are empty and the remaining boxes are non-empty. Inclusion–exclusion handles the “exactly” requirement by alternating sums over subsets of boxes that are forced to be empty, then subtracting overlaps. The method yields formulas involving sums of binomial coefficients and powers.

2.1.2 Factorial moment / counting derivation

Another route uses factorial moments of indicators for emptiness. By considering products of indicators (e.g., “these \(r\) specific boxes are empty”), one can compute \(\mathbb{E}[(E)_r]\), where \((E)_r\) is a falling factorial. The distribution of \(E\) can then be recovered by standard identities relating factorial moments to probabilities, often involving Stirling numbers or similar combinatorial transforms.

2.2 Distribution of the occupancy counts across boxes

The full occupancy histogram can be described using multinomial structure in the labeled-box, independent-choice setting.

2.2.1 Multinomial occupancy representation

When each ball independently selects one of \(m\) labeled boxes uniformly, the vector of occupancies \((Y_1,\dots,Y_m)\), with \(Y_i\) the number of balls in box \(i\), follows a multinomial distribution with parameters \((n;1/m,\dots,1/m)\). This representation enables exact probabilities for events expressed in terms of \((Y_1,\dots,Y_m)\), including distributions of \(X_k\) via combinatorial aggregation.

2.2.2 Stirling numbers connections (set partitions)

Stirling numbers of the second kind appear naturally when counting surjections from the set of balls into boxes with the boxes restricted to be used. For example, the number of ways to partition balls into \(t\) non-empty labeled groups is tied to Stirling numbers. In occupancy problems, these groups correspond to the subset of boxes that become non-empty.

2.3 Expectation and variance of common metrics

Even when full distributions are complex, first and second moments are often obtainable in simple closed forms.

2.3.1 Expected number of empty/non-empty boxes

For empty boxes, a typical approach uses an indicator \(I_i\) for the event that box \(i\) is empty. Then \(E=\sum_{i=1}^m I_i\), and \(\mathbb{E}[I_i]\) is the probability that no ball chooses box \(i\). Summing gives \(\mathbb{E}[E]\), and consequently \(\mathbb{E}[N]=m-\mathbb{E}[E]\).

2.3.2 Variance and covariance structure

The variance of \(E\) depends not only on \(\mathrm{Var}(I_i)\) but also on \(\mathrm{Cov}(I_i,I_j)\) for distinct boxes \(i\neq j\). The covariance terms arise because events like “box \(i\) is empty” and “box \(j\) is empty” are not independent (both constraints restrict where balls can go). Similar reasoning extends to variances and covariances of \(X_k\) under multinomial models, though formulas can become longer.

3 Combinatorial tools used in occupancy problems

Many standard solution techniques are reused across occupancy settings. These tools translate probabilistic questions into counting problems.

3.1 Indicator variable method

Indicators convert “global” occupancy events into sums of simpler random variables. For example, the event that a given box is empty becomes a single Bernoulli indicator. Linear expectation then reduces the calculation to computing the probability for one box, while second moments require pairwise probabilities.

3.2 Counting via multinomial coefficients

In the labeled independent-choice model, multinomial coefficients count the number of assignments producing a particular occupancy vector. This can be used directly for probabilities of exact count patterns or indirectly by summing over occupancy vectors consistent with a given event.

Inclusion–exclusion provides a systematic method for computing probabilities of “exactly” constraints (exactly these boxes are empty, or exactly a certain set is hit). It often leads to alternating sums whose terms correspond to choosing which boxes are forced to be empty, then counting allocations compatible with those constraints.

3.4 Stirling numbers and surjections

Stirling numbers of the second kind count partitions of a set into a specified number of non-empty subsets. When boxes correspond to used subsets and each used subset must contain at least one ball, Stirling numbers encode the combinatorics of surjections, producing compact expressions for quantities tied to the number of non-empty boxes.

3.5 Generating function techniques

Generating functions provide an efficient calculus for sums and distributions derived from counting arguments.

3.5.1 Probability generating functions

For a nonnegative integer-valued random variable \(X\), the probability generating function \(G_X(s)=\mathbb{E}[s^X]\) can simplify the extraction of factorial moments and sometimes enables derivation of distributions. In occupancy, generating functions can be applied to \(X_k\) or counts of empty boxes by encoding occupancy constraints into polynomial expansions.

3.5.2 Exponential generating functions

Exponential generating functions (EGFs) are especially useful when the combinatorics involves set partitions and labeled structures. They naturally incorporate Stirling-number relationships, since EGFs are well suited to counting assemblies of indistinguishable subcomponents assembled from labeled atoms like balls.

4 Asymptotic analysis and approximations

Asymptotic regimes—how \(n\) and \(m\) scale—often yield simpler limit laws and reveal phase transitions in occupancy behavior.

4.1 Sparse regime and Poisson approximation

A common sparse regime is when the average number of balls per box remains small or bounded as \(n,m\to\infty\).

4.1.1 Poissonization ideas

Poissonization replaces the fixed number of balls \(n\) by a Poisson random variable \(N\) with mean \(n\), while keeping independent box choices. This converts some combinatorial dependencies into a product structure across boxes, making computations tractable. After deriving results in the Poissonized model, de-Poissonization arguments are used to transfer asymptotics back to the fixed-\(n\) case.

4.1.2 Limits for empty-box counts

In sparse settings, the indicators of emptiness for different boxes often behave approximately independently. Consequently, \(E\) can converge in distribution to a normal or Poisson law depending on the scaling, and the probability that a given box is empty approaches \(\exp(-n/m)\) in the uniform-choice model. Similar approximations apply to \(X_k\) for fixed \(k\).

4.2 Large-box or large-load regimes

When load is heavy (many balls relative to boxes) or boxes become numerous, different approximations become accurate.

4.2.1 Normal approximations

If a metric is the sum of many weakly dependent indicators (e.g., non-empty boxes when emptiness is neither extremely rare nor extremely common), central limit theorems may apply. The resulting normal approximations require estimating the variance growth rate, which depends on the covariance between box indicators.

4.2.2 Concentration results (informal overview)

Beyond distributional convergence, one can often show that quantities like the number of empty boxes concentrate sharply around their mean, meaning relative fluctuations shrink as the system grows. Such results typically rely on bounding variances and applying concentration inequalities, with the precise conditions depending on the scaling regime.

4.3 Threshold behavior (e.g., when empty boxes disappear)

Occupancy problems exhibit threshold phenomena: as \(n\) increases relative to \(m\), the number of empty boxes drops rapidly and may reach a regime where almost all boxes are non-empty. The location of such thresholds depends on the metric of interest (e.g., “first moment” disappearance vs. high-probability elimination) and is often linked to coupon-collector-style scaling.

5 Applications and interpretations

Occupancy models serve as mathematical abstractions for systems where repeated random choices produce collisions, coverage gaps, or histogram-like counts.

5.1 Hashing and collision modeling

In hashing, items are mapped to table slots (boxes). Occupancy counts represent how many keys land in each slot, with empty slots corresponding to unused capacity and collisions corresponding to multiple keys in one slot. Performance metrics such as expected collisions or load distribution are analyzed using occupancy methods.

5.2 Load balancing and random assignment

Random assignment of tasks to servers is another direct application: tasks correspond to balls and servers to boxes. The occupancy histogram describes server utilization and can guide analysis of expected imbalance and probability of overload, especially when task assignment is independent and uniform.

The coupon collector problem asks how many random draws are needed to collect all “coupons.” In occupancy terms, it is the time (in number of balls) until there are no empty boxes. This relationship makes occupancy tools valuable for studying coverage times and the likelihood that all boxes have been hit.

5.4 Classifying repeated observations (histogram occupancy)

In statistics and data processing, repeated samples can be binned into categories. The count in each bin follows an occupancy distribution, connecting occupancy problems to the behavior of empirical histograms, sparse categories, and expected counts of bins with particular frequencies.

5.5 Network and caching analogies (high level)

In networked systems, content requests may be served from caches indexed by identifiers. Mapping requests to cache slots resembles ball-to-box assignment, so occupancy quantities inform how often caches are empty (misses) or heavily used (frequent hits), at least in stylized models that ignore deeper protocol constraints.

6 Extensions and generalizations

Many practical models generalize the basic uniform, independent placement rule by altering probabilities, constraints, or the structure of the boxes.

6.1 Unequal box probabilities (non-uniform occupancy)

If each box \(i\) is selected with probability \(p_i\) rather than \(1/m\), occupancy counts follow a multinomial distribution with unequal cell probabilities. Empty-box probabilities become \((1-p_i)^n\), and the expected number of empty boxes becomes \(\sum_{i=1}^m (1-p_i)^n\). Non-uniformity can substantially change tail behavior and the likelihood of rare boxes being hit.

6.2 Occupancy with constraints (capacity-limited boxes)

If boxes have capacities (e.g., a maximum number of balls per box), placement may be rejected, redirected, or redistributed. Such constraints prevent unrestricted multinomial counts and introduce state-dependent rules. Analyzing these models often requires Markov chains or coupling arguments, depending on how overflow is handled.

6.3 Random number of balls (compound occupancy)

Instead of a fixed \(n\), one may let the number of balls be random. This “compound” occupancy is useful when the demand level fluctuates. The resulting distribution is a mixture over \(n\), and Poisson mixtures are especially tractable because of the natural compatibility with Poissonization.

6.4 Multidimensional or structured boxes

If boxes correspond to multi-index categories (e.g., pairs or tuples), the occupancy problem extends to multidimensional bins. Structure can also mean boxes have an adjacency or hierarchy influencing placement probabilities, which affects dependence across counts and complicates the combinatorics.

6.5 Markovian or sequential placement models

In sequential placement, the choice of box for the next ball may depend on previous allocations. Such dependence can model learning, preferential attachment, or resource-aware routing. These variants typically require dynamic probabilistic tools rather than purely static multinomial counting.

7 Worked examples and reference computations

Worked examples illustrate how the general tools translate into explicit probabilities and expectations.

7.1 Small-parameter exact calculations

For small \(n\) and \(m\), direct enumeration or summation over occupancy vectors can produce exact probabilities. These cases serve as sanity checks for asymptotic formulas and demonstrate how combinatorial factors enter.

7.2 Deriving the probability a given number of boxes are non-empty

To find \(\Pr(N=t)\), one can express the event that exactly \(t\) boxes are non-empty as a sum over which \(t\) boxes are used. For labeled boxes, there are \(\binom{m}{t}\) choices of the used set, and the remaining \(m-t\) boxes must receive zero balls. The distribution then reduces to counting surjections from \(n\) balls onto \(t\) labeled boxes, often represented using Stirling numbers.

7.3 Expected collisions and “birthday” style comparisons

In the “birthday” scenario, items are mapped to boxes and one asks about collisions—two items landing in the same box. In occupancy language, the expected number of colliding pairs can be computed using pair indicators: for each pair of balls, the probability they share a box is \(1/m\) under uniform independent placement. This yields classical birthday-type approximations for collision probability.

7.4 Example using generating functions

Generating functions can package inclusion–exclusion or partition counts into compact expansions. For instance, the probability generating function of occupancy counts in a Poissonized model may factor into a product over boxes, enabling direct extraction of the distribution of \(X_0\) or related quantities. The example demonstrates how generating function algebra replaces repeated summations.

7.5 Example using inclusion–exclusion

An inclusion–exclusion example typically targets \(\Pr(E=0)\) (all boxes non-empty) or \(\Pr(E=e)\). One chooses a candidate set of boxes that are allowed to be empty, forces those to be empty, counts placements into the remaining boxes, and then alternates over subset sizes to enforce “exactly \(e\)” empties. The resulting expression includes terms of the form \((m-e)^n\) with alternating binomial coefficients.

8 Common pitfalls and checks

Occupancy results are sensitive to modeling assumptions and to subtle counting steps. Common errors can often be detected by consistency checks.

8.1 Miscounting distinguishability and labeling

A frequent mistake is using formulas valid for labeled boxes with unlabeled-box reasoning (or vice versa). Similarly, treating indistinguishable balls as distinguishable (or the reverse) changes multiplicities. A quick check is to verify whether the count of total assignments matches the expected sample space size under the stated model.

8.2 Incorrect independence assumptions

Indicator variables for occupancy events are generally dependent. For example, emptiness indicators for two different boxes are correlated because balls must avoid both boxes simultaneously. Approximations that treat them as independent require justification via limiting regimes (e.g., sparse scaling) and should not be used blindly.

8.3 Validity ranges of asymptotic approximations

Asymptotic approximations depend on how \(n\) grows with \(m\). Using a Poisson approximation outside the regime where emptiness becomes approximately independent can lead to noticeable errors. One check is to compare the approximation’s implied mean and variance scaling with the exact moment formulas where available.

8.4 Interpreting limiting regimes correctly

Threshold statements can be misread: “empty boxes disappear” may mean the expected number tends to zero, or it may mean the probability of having any empty box tends to zero. These are related but distinct criteria. The interpretation determines which scaling constant (and which probability notion) is correct.