Expected value of the trace of a matrix Let $(\Omega, \mathcal{A}, \mathbb{P})$ be a probabilized space, $A = (A_{i,j})_{1\le i,j\le n}$ such that
$$
\forall i,j, 
\mathbb{P}(A_{i,j}=1) = \mathbb{P}(A_{i,j}=-1)= \frac 1 2
$$
and the random variables are mutually independent. Find $\mathbb{E}(\text{tr}(A^4))$ and $\mathbb{E}(\text{tr}(A^5))$. I tried to compute the sum and study each case (where there is at least two distinct coefficients or not in order to apply the formula with independent random variables on a product) but I'm wondering if there is not another way to do so.
 A: I think it is basically what you did. but one you start looking there are not many possibilities. Let me sketch what I did
$$
tr(A^4)=\sum_{ijkl}A_{ij}A_{jk}A_{kl}A_{lm}
$$
Then, there are the following possibilities in the sum


*

*$(i,j,k,l)$ are all equal, in which case you just get 1 (with probability 1)

*$(i,j,k,l)$ are three equal among them and one different. In this case you will have $A_{aa}A_{aa}A_{ab}A_{ba}=A_{ab}A_{ba}$ which has expected value $0$.

*$(i,j,k,l)$ are two equal and the other two different. Then, as you may check, all $A$'s are different and the expected value is once again 0

*$(i,j,k,l)$ equal two by two. In this case you get $1$ with probability one if the pairs are $i=k$ and $j=l$ otherwise you get expected value 0

*Finally if all are different you get expected value 0.


It may be helpful to notice that if you write the labels $(i,j,k,l)$ as the vertices of a square, you get the labels of the $A$'s as the (directed) edges. This makes easy to visualize.
Finally you get just a contribution from cases 1, from which there are $N$ and from cases $4$ from which there are $N(N-1)$. Then
$$
E[tr\,A^4]=N+N(N-1)=N^2.
$$
I believe this is alright but let me know if you find a problem. 
