Section 7.4

Occupancy

Balls dropped into bins: no bin empty, every value hit, conditional occupancy.

Toolkit

Occupancy problems concern $n$ balls placed independently and uniformly into $m$ bins, asking about empty bins, surjectivity, or conditional configurations given which values appear.

Key tool: inclusion–exclusion on the “bin $i$ empty” events gives, for $n$ balls into $m$ bins,

\mathbb{P}(\text{no bin empty})=\sum_{j=0}^{m}(-1)^j\binom{m}{j}\Big(\frac{m-j}{m}\Big)^n,

and the number of surjections from an $n$ -set onto an $m$ -set is

m!\,S(n,m)=\sum_{j=0}^{m}(-1)^j\binom{m}{j}(m-j)^n.

When $n$ itself is random (e.g. geometric or Poisson), compute $\mathbb{P}(\text{event}\mid n)$ first, then average over $n$ ’s distribution, often collapsing into a geometric series. Conditioning on which values are missing or hit reduces the bin count and makes the remaining map uniform over the smaller set.

Problems

7.26 Every Value but One Chosen Medium Free
7.27 Geometric Number of Balls Medium