Trace of power of multinomial co-variance matrix

Question

Consider the covariance matrix of multinomial random variable $A = \mathbf{P} - \mathbf{p}\mathbf{p}^{T}$, where $\mathbf{p} = (p_{1},\ldots,p_{n})^{T}$ and $\mathbf{P} = \rm{diag}(\mathbf{p})$. Is there any formula for $\rm{trace}(A^{n})$?

Answer 1

It is easy to see that $\mathrm{tr}(A^n)$ is a symmetric function of the $p_i$, without needing a formula for $\mathrm{tr}(A^n)$. Let $S$ be a permutation matrix, let $\mathbf q=S\mathbf p$, $\mathbf Q=S\mathbf PS^T$, and $B=\mathbf Q-\mathbf q\mathbf q^T$, so the entries $q_i$ of $\mathbf q$ are a permutation of the $p_i$. Note that all permutations of the $p_i$ are obtainable this way. If the vector $X$ has a multinomial distribution with parameters $\mathbf p$ and $n$, then the vector $Y=SX$ is multinomial with parameters $\mathbf q$ and $n$. Note that $$B^n=(SAS^T)^n = (SAS^T)(SAS^T)\cdots(SAS^T) = S A (S^TS) A (S^TS) A \cdots(S^TS) A S^T = SA^nS^T$$ and so $\mathrm{tr}(B^n)=\mathrm{tr}(A^n)$.