Occupancy Counts in Multinomial Sampling

From Multinomial Counts to Occupancy

A multinomial sample records how many times each category occurs. A different question is how many categories occur at least once. This number is the occupancy count. It is useful when the categories represent, for example, species detected, types of response observed, or possible outcomes represented in a sample. The sample size alone does not determine the occupancy count: it also depends on the category probabilities.

Suppose $n\geq 1$ independent draws are made, each with values in the finite set of categories $\{1,\ldots,m\}$. Let the probability of category $j$ on any draw be $p_j$, where $p_j\geq 0$ and $\sum_{j=1}^m p_j=1$. Write $N_j$ for the number of draws in category $j$. Then $(N_1,\ldots,N_m)$ has a multinomial distribution, and the occupancy count is

K=\sum_{j=1}^m I_j,\qquad I_j=\mathbf{1}\{N_j>0\}.

Here $I_j$ is an indicator: it equals 1 if category $j$ appears at least once and 0 otherwise. Thus $K$ is an integer between 0 and $\min(n,m)$; for $n\geq1$, it is at least 1 with probability 1. Categories with $p_j=0$ are allowed, but they can never be occupied.

Definition: The occupancy count $K$ is the number of distinct categories represented among the $n$ independent multinomial draws. Equivalently, it is the sum of the indicators $I_j=\mathbf{1}\{N_j>0\}$ over all $m$ categories.

Exact Probabilities by Inclusion-Exclusion

First fix a set of categories $S$. The event that the occupied categories are exactly $S$ requires two things: every draw lies in $S$, and every category in $S$ occurs at least once. To enforce the second requirement, subtract outcomes missing one or more members of $S$ using inclusion-exclusion. For any subset $T\subseteq S$, the probability that all draws lie in $T$ is $(\sum_{j\in T}p_j)^n$. Inclusion-exclusion therefore gives an exact probability for each specified occupied set.

Theorem: For a specified set $S\subseteq\{1,\ldots,m\}$, the probability that the occupied categories are exactly $S$ is $$ P(\{j:N_j>0\}=S) = \sum_{T\subseteq S}(-1)^{|S|-|T|} \left(\sum_{j\in T}p_j\right)^n. $$ Consequently, for $r=0,\ldots,m$, $$ P(K=r)= \sum_{\substack{S\subseteq\{1,\ldots,m\}\\|S|=r}} \ \sum_{T\subseteq S}(-1)^{r-|T|} \left(\sum_{j\in T}p_j\right)^n. $$ An empty sum of probabilities is 0; since $n\geq1$, its $n$th power is also 0.

To justify the first formula, begin with the event that every draw lies in $S$. For each $j\in S$, let the excluded event be that category $j$ is missing. For a subset $A\subseteq S$, requiring all categories in $A$ to be missing leaves only categories in $S\setminus A$ available, an event with probability $(\sum_{j\in S\setminus A}p_j)^n$. Inclusion-exclusion sums these probabilities with sign $(-1)^{|A|}$. Substituting $T=S\setminus A$ gives the stated formula. Events with different exact occupied sets are disjoint, so summing over the sets $S$ of size $r$ gives $P(K=r)$.

Worked Example: Three Equally Likely Categories

Four independent draws are made from three categories, each with probability $1/3$. Find the distribution of $K$.

For $K=1$, all four draws must be in one category. There are three choices, and each has probability $(1/3)^4$:

P(K=1)=3\left(\frac13\right)^4=\frac{3}{81}=\frac{1}{27}.

For $K=2$, first choose the two categories, in $\binom32=3$ ways. For a fixed pair, the probability that all draws lie in that pair is $(2/3)^4=16/81$. Of these outcomes, the ones using only the first category have probability $1/81$, and the ones using only the second also have probability $1/81$. Subtracting both cases leaves $14/81$ for this pair, so

P(K=2)=3\left[\left(\frac23\right)^4-2\left(\frac13\right)^4\right] =3\left(\frac{14}{81}\right)=\frac{42}{81}=\frac{14}{27}.

Since $K\leq3$, the remaining probability is

P(K=3)=1-\frac{1}{27}-\frac{14}{27} =\frac{12}{27}=\frac49.

The probabilities sum to $(1+14+12)/27=1$, as required. In particular, four draws can occupy at most three categories, even though the sample contains four observations.

Expectation and Variance from Indicators

The indicator representation gives the expectation without first finding the full distribution. Category $j$ is unoccupied only if all $n$ draws avoid it, which has probability $(1-p_j)^n$. Thus its occupancy probability is $1-(1-p_j)^n$. Linearity of expectation then adds these probabilities across categories.

Theorem: For the multinomial occupancy count, $$ E[K]=\sum_{j=1}^m\left[1-(1-p_j)^n\right]. $$ For distinct categories $i$ and $j$, $$ \operatorname{Cov}(I_i,I_j) =(1-p_i-p_j)^n-(1-p_i)^n(1-p_j)^n. $$ Consequently, $$ \operatorname{Var}(K) =\sum_{j=1}^m q_j(1-q_j) +2\sum_{1\leq i<j\leq m} \left[(1-p_i-p_j)^n-(1-p_i)^n(1-p_j)^n\right], \qquad q_j=1-(1-p_j)^n. $$

For the expectation, $E[I_j]=P(I_j=1)=q_j$, and $K=\sum_j I_j$. Therefore

E[K]=\sum_{j=1}^m E[I_j] =\sum_{j=1}^m q_j =\sum_{j=1}^m\left[1-(1-p_j)^n\right].

For the covariance, set $A_i=\{I_i=0\}$, the event that category $i$ is absent. Since $I_i=1-\mathbf{1}_{A_i}$, the covariance of $I_i$ and $I_j$ equals the covariance of the two absence indicators. The probability that both categories are absent is $(1-p_i-p_j)^n$, while the probability that category $i$ is absent is $(1-p_i)^n$, with the corresponding expression for $j$. Hence

\operatorname{Cov}(I_i,I_j) =P(A_i\cap A_j)-P(A_i)P(A_j) =(1-p_i-p_j)^n-(1-p_i)^n(1-p_j)^n.

Finally, expanding the variance of a sum gives $\operatorname{Var}(K)=\sum_j\operatorname{Var}(I_j)+2\sum_{i<j}\operatorname{Cov}(I_i,I_j)$. An indicator with success probability $q_j$ has variance $q_j(1-q_j)$, yielding the formula. This derivation uses no independence assumption between the occupancy indicators.

Worked Example: Moments with Unequal Category Probabilities

Suppose $n=2$ and the three category probabilities are $0.5$, $0.3$, and $0.2$. Find $E[K]$ and $\operatorname{Var}(K)$, checking them against the distribution.

The occupancy probabilities for the individual categories are $q_1=1-0.5^2=0.75$, $q_2=1-0.7^2=0.51$, and $q_3=1-0.8^2=0.36$. Thus

$$ E[K]=0.75+0.51+0.36=1.62. $$

The individual indicator variances sum to $0.75(0.25)+0.51(0.49)+0.36(0.64)=0.1875+0.2499+0.2304=0.6678$. The three pairwise covariances are

\begin{aligned} \operatorname{Cov}(I_1,I_2)&=0.2^2-(0.5)^2(0.7)^2=0.04-0.1225=-0.0825,\\ \operatorname{Cov}(I_1,I_3)&=0.3^2-(0.5)^2(0.8)^2=0.09-0.16=-0.07,\\ \operatorname{Cov}(I_2,I_3)&=0.5^2-(0.7)^2(0.8)^2=0.25-0.3136=-0.0636. \end{aligned}

Therefore

\operatorname{Var}(K)=0.6678+2(-0.0825-0.07-0.0636)=0.2356.

As a check, with two draws $K=1$ exactly when both draws agree. Its probability is $0.5^2+0.3^2+0.2^2=0.38$, so $K=2$ has probability $0.62$. A variable taking values 1 and 2 with these probabilities has mean $1(0.38)+2(0.62)=1.62$ and variance $0.38(0.62)=0.2356$, matching the indicator calculations.

Why the Indicators Are Negatively Correlated

For distinct $i$ and $j$, the covariance formula is nonpositive. Indeed, because $p_i,p_j\geq0$,

1-p_i-p_j\leq (1-p_i)(1-p_j).

Both sides are nonnegative: $p_i+p_j\leq1$, and $1-p_i,1-p_j\geq0$. Raising the inequality to the positive integer power $n$ gives $(1-p_i-p_j)^n\leq (1-p_i)^n(1-p_j)^n$, so $\operatorname{Cov}(I_i,I_j)\leq0$. Intuitively, draws allocated to one category leave fewer opportunities for another category to appear. This is a pairwise covariance statement; the variance formula follows from it, but it does not assert that all occupancy indicators are mutually independent.

The exact distribution is especially helpful when the probabilities are unequal, because a formula depending only on $m$ and $n$ would lose relevant information. When probabilities are equal, symmetry can simplify the set sums, but the indicator formulas remain valid without that assumption.

Common Mistake

A tempting but incorrect shortcut is to treat $I_1,\ldots,I_m$ as independent Bernoulli variables and write $\operatorname{Var}(K)=\sum_j q_j(1-q_j)$. The indicator means $q_j$ are correct, but independence does not follow from the multinomial model. For the unequal-probability example above, this shortcut gives $0.6678$, rather than the correct variance $0.2356$. The missing terms are the pairwise covariances, whose sum here is negative. Use the variance-of-a-sum identity with all covariance terms unless independence has actually been established.

Key takeaway: The occupancy count is a sum of category-presence indicators. Inclusion-exclusion gives its exact probability mass function, while indicator expectations and covariances give its moments directly.

Check Your Understanding

Try these questions using the formulas and reasoning above.

For $n$ draws from $m$ categories, why is $P(I_j=1)=1-(1-p_j)^n$?
In the exact-set probability formula, what event is represented by $(\sum_{j\in T}p_j)^n$?
Two draws are made from four equally likely categories. Find $P(K=1)$, $P(K=2)$, and $E[K]$.
Explain why the covariance of two distinct occupancy indicators is nonpositive.
What terms would be omitted by treating all occupancy indicators as independent when computing $\operatorname{Var}(K)$?

Occupancy Counts in Multinomial Sampling

What You'll Learn