Derivation of the Covariance Matrix of the Multinomial Distribution
Formula
If a random vector $\mathbf{X} := \left( X_{1} , \cdots , X_{k} \right)$ follows a multinomial distribution $M_{k} \left( n, \mathbf{p} \right)$, then its covariance matrix is as follows. $$ \operatorname{Cov} \left( \mathbf{X} \right) = n \begin{bmatrix} p_{1} \left( 1 - p_{1} \right) & - p_{1} p_{2} & \cdots & - p_{1} p_{k} \\ - p_{2} p_{1} & p_{2} \left( 1 - p_{2} \right) & \cdots & - p_{2} p_{2} \\ \vdots & \vdots & \ddots & \vdots \\ - p_{k} p_{1} & - p_{k} p_{2} & \cdots & p_{k} \left( 1 - p_{k} \right) \end{bmatrix} $$
Description
The components of the multinomial distribution are almost mutually exclusive rather than just non-independent because of the constraint that the sum of the random vector must be $n$. Therefore, when $i \ne j$, each component necessarily has a negative correlation.
Derivation 1
If $i = j$ then $\operatorname{Cov} \left( X_{i} , X_{i} \right) = \operatorname{Var} \left( X_{i} \right)$ and $X_{i}$, each component independently follows a binomial distribution $\text{Bin} \left( n , p_{i} \right)$. Thus, the $i$-th diagonal component of the covariance matrix becomes $n p_{i} \left( 1 - p_{i} \right)$.
Properties of the multinomial distribution: For $i \ne j$, $X_{i} + X_{j}$ follows a binomial distribution $\text{Bin} \left( n , p_{i} + p_{j} \right)$. $$ X_{i} + X_{j} \sim \text{Bin} \left( n , p_{i} + p_{j} \right) $$
If $i \ne j$, the bundle properties yield the following. $$ \begin{align*} && \operatorname{Var} \left( X_{i} + X_{j} \right) =& \operatorname{Var} X_{i} + \operatorname{Var} X_{j} + 2 \operatorname{Cov} \left( X_{i} , X_{j} \right) \\ \implies && n \left( p_{i} + p_{j} \right) \left( 1 - p_{i} - p_{j} \right) =& n p_{i} \left( 1 - p_{i} \right) + n p_{j} \left( 1 - p_{j} \right)+ 2 \operatorname{Cov} \left( X_{i} , X_{j} \right) \\ \implies && n \left( p_{i} + p_{j} \right) \left( - p_{i} - p_{j} \right) =& n p_{i} \left( - p_{i} \right) + n p_{j} \left( - p_{j} \right)+ 2 \operatorname{Cov} \left( X_{i} , X_{j} \right) \\ \implies && - 2 n p_{i} p_{j} =& 2 \operatorname{Cov} \left( X_{i} , X_{j} \right) \\ \implies && \operatorname{Cov} \left( X_{i} , X_{j} \right) =& - n p_{i} p_{j} \end{align*} $$
■