Proof of Multinomial Distribution of Cell Counts for Independent Identically Distributed Points

For $1\le i\le n$ write $F_{i,j}=V_i^{-1}(A_j)=\{V_i\in A_j\}\in\mathcal{F}$. Since $A_1,\dots,A_m$ are pairwise disjoint with union $\mathbb{R}$, for each $i$ the events $F_{i,1},\dots,F_{i,m}$ are pairwise disjoint with union $\Omega$: every value $V_i(\omega)$ lies in exactly one cell.

Measurability of the cell counts. For $q$ points $V_1,\dots,V_q$ ($1\le q\le n$) and $0\le c\le q$, the level set of the count $S_j^{(q)}=\sum_{i=1}^{q}\mathbf{1}_{\{V_i\in A_j\}}$ is

$$\{S_j^{(q)}=c\}=\bigcup_{T}\ \Bigl(\bigcap_{i\in T}F_{i,j}\cap\bigcap_{i\in\{1,\dots,q\}\setminus T}(\Omega\setminus F_{i,j})\Bigr),$$

the union over the finitely many subsets $T\subseteq\{1,\dots,q\}$ with $c$ elements; this is a finite union of finite intersections of events, hence an event, and moreover it lies in the generated $\sigma$-algebra $\sigma(V_i:1\le i\le q)$, because each $F_{i,j}$ and each complement $\Omega\setminus F_{i,j}=V_i^{-1}(\mathbb{R}\setminus A_j)$ is a generator. Since $S_j^{(q)}$ takes only the finitely many values $0,\dots,q$, the preimage of any Borel set $B$ is the finite union of the level sets $\{S_j^{(q)}=c\}$ over values $c\in B$, so $S_j^{(q)}$ is a random variable, $\sigma(V_i:1\le i\le q)$-measurable; in particular each $S_j=S_j^{(n)}$ is. Consequently, for any $(c_1,\dots,c_m)$ the pattern event

$$E_q(c_1,\dots,c_m)=\bigcap_{j=1}^{m}\{S_j^{(q)}=c_j\}$$

lies in $\sigma(V_i:1\le i\le q)$.

We prove the displayed probability formula by induction on $n$; more precisely we prove, for every $q$ with $1\le q\le n$: for all $(n_1,\dots,n_m)\in\mathbb{N}_0^m$ with $n_1+\dots+n_m=q$,

$$P\bigl(E_q(n_1,\dots,n_m)\bigr)=\frac{q!}{n_1!\cdots n_m!}\prod_{j=1}^{m}p_j^{\,n_j}.\tag{$*$}$$

The case $q=n$ is the lemma.

Base case $q=1$. A tuple of nonnegative integers summing to $1$ has exactly one entry equal to $1$, say entry $j^*$, and all others $0$. Then $E_1=\{ \mathbf{1}_{F_{1,j^*}}=1 \}\cap\bigcap_{j\ne j^*}\{\mathbf{1}_{F_{1,j}}=0\}$. Since the $F_{1,j}$ partition $\Omega$, this intersection equals $F_{1,j^*}$, whose probability is $\nu(A_{j^*})=p_{j^*}$ because $V_1$ has distribution $\nu$. The right side of ($*$) is $\frac{1!}{0!\cdots1!\cdots0!}\,p_{j^*}^{1}\prod_{j\ne j^*}p_j^{0}=p_{j^*}$, using the conventions $0!=1$ and $x^0=1$. So ($*$) holds.

Induction step. Let $2\le q\le n$, assume ($*$) for $q-1$, and fix $(n_1,\dots,n_m)$ summing to $q$. Since the events $F_{q,1},\dots,F_{q,m}$ partition $\Omega$, and since on $F_{q,j}$ the last point contributes $1$ to cell $j$ and $0$ to every other cell,

$$E_q(n_1,\dots,n_m)=\bigcup_{j:\,n_j\ge1}\Bigl(F_{q,j}\cap E_{q-1}(n_1,\dots,n_j-1,\dots,n_m)\Bigr),$$

a disjoint union (the sets are disjoint because the $F_{q,j}$ are; and on $F_{q,j}$ with $n_j=0$ the event $E_q$ cannot occur, since $S_j^{(q)}\ge\mathbf{1}_{F_{q,j}}=1$ there). By Grouping Lemma for Independent Random Variables applied to the independent family $V_1,\dots,V_q$ (every finite subfamily of the independent family $V_1,\dots,V_n$ is independent by Independence of Events and of Random Variables) with the two disjoint blocks $\{1,\dots,q-1\}$ and $\{q\}$, the $\sigma$-algebras $\sigma(V_i:i\le q-1)$ and $\sigma(V_q)$ are independent; since $E_{q-1}(\dots)$ lies in the former and $F_{q,j}$ in the latter,

$$P\bigl(F_{q,j}\cap E_{q-1}(n_1,\dots,n_j-1,\dots,n_m)\bigr)=p_j\,P\bigl(E_{q-1}(n_1,\dots,n_j-1,\dots,n_m)\bigr).$$

By finite additivity of $P$, the induction hypothesis, and the factorial recursion $n_j!=n_j\,(n_j-1)!$ (valid for $n_j\ge1$, with $0!=1$),

$$P\bigl(E_q\bigr)=\sum_{j:\,n_j\ge1}p_j\cdot\frac{(q-1)!}{n_1!\cdots(n_j-1)!\cdots n_m!}\prod_{l\ne j}p_l^{\,n_l}\,p_j^{\,n_j-1}=\sum_{j:\,n_j\ge1}\frac{(q-1)!\;n_j}{n_1!\cdots n_m!}\prod_{l=1}^{m}p_l^{\,n_l}.$$

The summand vanishes for $n_j=0$, so the sum may run over all $j$, and $\sum_{j=1}^{m}n_j=q$ gives

$$P\bigl(E_q\bigr)=\frac{(q-1)!\;q}{n_1!\cdots n_m!}\prod_{l=1}^{m}p_l^{\,n_l}=\frac{q!}{n_1!\cdots n_m!}\prod_{l=1}^{m}p_l^{\,n_l},$$

using $q!=q\,(q-1)!$ from Factorial of a Natural Number. This is ($*$) for $q$, completing the induction. $\blacksquare$