# Help with rigorous derivation of multinomial distribution

$$\newcommand{\pset}[1]{2^{#1}} \newcommand{\NN}{\mathbb{N}} \newcommand{\PP}{\mathbf{P}} \newcommand{\OO}{\Omega} \newcommand{\oo}{\omega} \newcommand{\sal}{\sigma-algebra\xspace} % Sigma algebra \newcommand{\sals}{\sigma-algebras\xspace} % Sigma algebras (plural)$$

Background:

I'm trying to rigorously derive the multinomial distribution. Below I present the exercise and my attempted solution, with my specific questions at the end.

Exercise:

Let $$m \in \NN$$ and let $$p = (p_1, \dots, p_m)$$ be a probability vector on $$\{1, \dots, m\}$$. Let $$X_1, \dots, X_n$$ be independent random variables with values in $$1, \dots, m$$ and distribution $$p$$. We define an $$\NN_0^m$$-valued random variable $$Y = (Y_1, \dots, Y_m)$$ by $$$$Y_i := \#\{ k = 1, \dots, n \colon X_k = i\} \qquad \text{ for } i = 1, \dots, m$$$$ Show that for $$k = (k_1, \dots, k_m) \in \NN_0^m$$ with $$k_1 + \ldots + k_m = n$$, we have $$$$\PP[Y = k] = \text{Mul}_{n, p}\left(\{k\}\right) := \binom{n}{k}p^k$$$$ Here $$$$\binom{n}{k} = \binom{n}{k_1, \dots, k_m} = \frac{n!}{k_1! \cdots k_m!}$$$$ is the \textbf{multinomial coefficient} and $$p^k = p_1^{k_1} \dots p_m^{k_m}$$. The distribution $$\text{Mul}_{n, p}$$ on $$\NN_0^m$$ is called multinomial distribution with parameters $$n$$ and $$p$$.

My attempt:

Our probability space is $$\left( \{1, \dots, m\}, \pset{\{1, \dots, m\}}, \PP\right)$$, and we have a probability vector $$p = (p_1, \dots, p_m)$$ where $$\sum_{i = 1}^m p_i = 1$$. The probability measure $$\PP \colon \pset{\{1, \dots, m\}} \to [0, 1]$$ is defined by $$A \mapsto \sum_{i \in A} p_i$$, so it just adds up the probabilities of whichever elements of $$\{1, \dots, m\}$$ are in $$A \in \pset{\{1, \dots, m\}}$$.

We have random variables $$X_i \colon \{1, \dots, m\} \to \{1, \dots m\}$$ for $$i = 1, \dots, n$$, all of which have distribution $$p$$. I interpret this to mean that $$\PP[X_i \in A] = \PP\left[X_i^{-1}(A)\right] = \PP[A] = \sum_{i \in A} p_i$$.

My understanding is that we have second measure space $$\left(\{1, \dots, m\}^n, \pset{\{1, \dots, m\}^n}\right)$$ and random variables $$Y_i \colon \{1, \dots, m\}^n \to \NN_0$$, defined by $$\oo \mapsto \#\{ k = 1, \dots, n \colon X_k = i\}$$ for $$i = 1, \dots, m$$. These random variables count how many of the variables $$X_1, \dots, X_n$$ came up'' with value $$i$$.

For $$\oo \in \{1, \dots, m\}^n$$, write $$\oo = (\oo_1, \dots, \oo_n)$$. For $$i = 1, \dots, m$$ and $$j = 1, \dots, n$$, define $$f_{i, j} \colon \{1, \dots, m\} \to \{0, 1\}$$ by $$$$\oo_j \mapsto \begin{cases} 1, \text{ if } X_j(\oo_j) = i\\ 0, \text{ otherwise} \end{cases}$$$$

Therefore \begin{align*} \PP[Y = k] &= \PP\left[\left\{\oo \in \{1, \dots, m\}^n \colon Y_1(\oo) = k_1, \dots, Y_m(\oo) = k_m\right\}\right]\\ &= \PP\left[ \left\{ \oo \in \{1, \dots, m\}^n \colon \sum_{j = 1}^n f_{i, j}(\oo_j) = k_i \text{ for } i = 1, \dots, m \right\}\right]\\ % &= \sum \PP\left[ \left\{ \oo \in \{1, \dots, m\}^n \colon \sum_{j = 1}^n f_{i, j}(\oo_j) = k_i \text{ for } i = 1, \dots, m \right\}\right]\\ &= \binom{n}{k} \PP\left[X_1, \dots, X_{k_1} = 1, X_{k_1 + 1}, \dots X_{k_1 + k_2} = 2, \dots, X_{\sum_{i = 1}^{m - 1} k_i}, \dots, X_{\sum_{i = 1}^m k_i} = m \right]\\ &= \binom{n}{k} p^k \end{align*} In the last line we've used the independence assumption for $$X_1, \dots, X_n$$.

I'm pretty sure my solution is on the right track, but it's not rigorous enough. I'm not sure I've defined the various objects, for example the $$Y_i$$, correctly. I figure the $$Y_i$$ are measurable because I'm using the power set $$\sigma$$-algebra on both sides. But I don't have a measure on the $$Y$$ measure space, and it seems like I need one in order to compute $$\PP[Y = k]$$.

Is what I've laid out correct? How do I make my solution more rigorous?

• I dont understand why you need to be so formal (i.e dealing with probability spaces and so on) when you are trying essentially to solve a combinatorial problem. The axiomatic framework doesn’t seem all that useful here. Mar 6 at 17:56
• @YashaswiMohanty This is an exercise from a measure-theoretic probability theory textbook, so I think that formality is just what the doctor ordered here. Mar 6 at 17:57
• Well if you really wanted to be formal (but I believe this impedes probasbilistic thinking in a lot of settings) you would have to define a common ambient probability space for both $X$ and $Y$. It’s the outcome space here which is $\left(\{1,\ldots,m\}, \mathcal{P}(\{1,\ldots,m\})\right)$ etc although you could just let it be $\left(\mathbb{R},\mathcal{B}(\mathbb{R})\right)$. Mar 6 at 18:03
• If you use the standard framework, then both $X$ and $Y$ are defined on the same probability space $\left(\Omega, \mathcal{F}, \mathbb{P}\right)$ but have the distributions (i.e. image measures) as you define in the problem statement. Then $Y_i$ are measurable since they are the sum of indicators of measurable events… Mar 6 at 18:07
• In the very basics of probability theory, we don't really encounter random variables that don't live in the same space all that often, the notable exception being the theory of weak (weak* for analysts) convergence, which is really about the convergence of measures rather than random variables themselves. When you do find random variables on different spaces, there's a way to couple them together to be defined on one space. Mar 6 at 23:06

Even under the rigorous measure-theoretic framework, your proof is overly verbose, probably due to that you confused the underlying probability space $$(\Omega, \mathscr{F}, P)$$, where $$X_1, X_2, \ldots, X_n$$ and $$Y = (Y_1, \ldots, Y_m)$$ are defined, with their image space $$(\mathbb{R}^1, \mathscr{R}^1)$$. In particular, the range of $$X_i$$ is $$\{1, 2, \ldots, m\}$$ does not make "our probability space is $$(\{1, 2, \ldots, m\}, 2^{\{1, 2, \ldots, m\}}, P)$$". @Yashaswi Mohanty also pointed this out in the comment.

The formal proof may go as follows. Define \begin{align} \mathscr{M} = \left\{(i_1, i_2, \ldots, i_m) \in \mathbb{N}^m: 0 \leq i_j \leq n, 1 \leq j \leq m, \sum_{i = 1}^m i_j = n\right\}, \end{align} which is the range of $$Y$$ (by combinatorics, the cardinality of $$\mathscr{M}$$ is $$|\mathscr{M}| = \binom{m + n - 1}{m - 1}$$). For each $$(i_1, \ldots, i_m) \in \mathscr{M}$$, the event $$[Y_1 = i_1, \ldots, Y_m = i_m]$$, which is a member in $$\mathscr{F}$$, is a disjoint union of $$\mathscr{F}$$-sets $$[X_1 = k_1, \ldots, X_n = k_n]$$, where $$(k_1, \ldots, k_n)$$ extends over the set $$\mathscr{K}$$ consisting of all $$n$$-tuples in which $$i_j$$ elements take value $$j$$, $$1 \leq j \leq m$$. It is thus easy to see that $$|\mathscr{K}| = \binom{n}{i_1}\binom{n - i_1}{i_2}\cdots\binom{n - i_1 - \cdots - i_{m - 1}}{i_m} = \binom{n}{i_1, \ldots, i_m}$$. It then follows by the independence of $$(X_1, \ldots, X_n)$$ and finite additivity of the probability measure $$P$$ that \begin{align} & P[Y_1 = i_1, \ldots, Y_n = i_n] \\ =& P\left[\bigcup_{(k_1, \ldots, k_n) \in \mathscr{K}}[X_1 = k_1, \ldots, X_n = k_n]\right] \\ =& \sum_{(k_1, \ldots, k_n) \in \mathscr{K}}P[X_1 = k_1, \ldots, X_n = k_n] \\ =& \sum_{(k_1, \ldots, k_n) \in \mathscr{K}}P[X_1 = k_1]\cdots P[X_n = k_n] \\ =& \sum_{(k_1, \ldots, k_n) \in \mathscr{K}}p_{k_1}\cdots p_{k_n} \\ =& \sum_{(k_1, \ldots, k_n) \in \mathscr{K}}p_1^{i_1}\cdots p_m^{i_m} \\ =& p_1^{i_1}\cdots p_m^{i_m}|\mathscr{K}| \\ =& \binom{n}{i_1, \ldots, i_m}p_1^{i_1}\cdots p_m^{i_m}. \end{align} This completes the proof.

• This is rigorous as well as intuitive in that it only involves finding the cardinality of two relevant sets and the rest is taken care by the properties of probability measure. $+1$ (voila on $10\rm k.$). Mar 7 at 12:07
• @User1865345 Good summary of the proof outline. I am happy that the vital vote converting 9k to 10k is from you :) Mar 7 at 12:23
• As a student, it's a privilege to read your posts and above all learn the philosophy and approach to tackle a problem. Carry on! Mar 7 at 12:25

#### Your present attempted proof is question-begging

Firstly, well done on your initial attempt. You appear to have a basic idea of how you would like to proceed, and you are making an attempt to set this out rigorously, which is no easy task.

I see a couple of problems with your proof. The first problem is that your notation is horrible, and it complicates your working rather than clarifying it. (This makes your alleged proof less rigorous, not more.) I see several ambiguities in your notation that makes it hard to read and understand, including cases where quantities depend on indices that are not used explicitly in the notation. The second problem is that the actual guts of the proof is the combinatorial part (i.e., the fact that counting the combinations manifests in $${n \choose k}$$), which you just baldly assert rather than proving. Specifically, your final step is really just begging the question --- it is effectively making the same assertion you were asked to prove in the first place.

In order to remedy these defects, I would suggest you try proving the result without adding any additional notation beyond what is already defined for you in the question. Have a think about which step is the actual guts of the result, and see if you can prove that step, then build that up into a full proof.

Starting you off: If it were me, I'd approach a proof like this using induction. That is an obvious way to prove a quasi-combinatorial result that holds over a countable sequence of inputs. To do this, I'm going to use the notation $$\mathbf{Y}_n \equiv (Y_{n,1},...,Y_{n,m})$$ to denote the state of the counts after sampling $$n$$ objects. Start with the base case where $$n=0$$ where $$Y_{0,1} = \cdots = Y_{0,m} = 0$$ with probability one. For this base case we have:$$^\dagger$$

\begin{align} \mathbb{P}(\mathbf{Y}_0 = \mathbf{k}) &= \mathbb{I}(\mathbf{k} = \mathbf{0}) \\[14pt] &= \mathbb{I}(\mathbf{k} = \mathbf{0}) \times 1 \\[8pt] &= \mathbb{I}(\mathbf{k} = \mathbf{0}) \times \prod_{i=1}^m 1 \\ &= {0 \choose \mathbf{k}} \times \prod_{i=1}^m p_i^0 \\[6pt] &= {0 \choose \mathbf{k}} \times \prod_{i=1}^m p_i^{k_i} \\[12pt] &= \text{Mu}(\mathbf{k}|0, \mathbf{p}), \\[6pt] \end{align}

which establishes that the multinomial distribution holds for the base case. Now you need to prove the induction step --- assume that there is some $$n \in \mathbb{N}_{0}$$ such that:

$$\quad \mathbb{P}(\mathbf{Y}_n = \mathbf{k}) = \text{Mu}(\mathbf{k}|n, \mathbf{p}) \quad \quad \quad \quad \ \ \text{for all } \mathbf{k} \in \mathbb{N}_0^m,$$

and use this to prove that:

$$\mathbb{P}(\mathbf{Y}_{n+1} = \mathbf{k}) = \text{Mu}(\mathbf{k}|n+1, \mathbf{p}) \quad \quad \quad \text{for all } \mathbf{k} \in \mathbb{N}_0^m.$$

This latter step should be fairly simple, since you are only adding one sample object to the problem. It will involve writing the new probability as a sum of probabilities conditional on the previous state, using the law of total probability, and then using the properties of the multinomial coefficient to simplify. If you can do that, you will have proved the result using weak induction.

In my view, there is no need to add measure-theoretic bells and whistles to make the proof more "rigorous". The question already begins with well-defined random variables rather than events on an abstract sample space, so you can do the proof in terms of those random variables.

$$^\dagger$$ Note that the penultimate step in this working holds because $$p_i^{k_i} = p_i^0$$ when $$\mathbf{k}=\mathbf{0}$$ and the first term is zero (so the second terms doesn't matter) when $$\mathbf{k} \neq \mathbf{0}$$.