Trace of power of random matrix / sum of random variables with semicircle distribution I want to calculate the expectation value for the trace of the $m$-th power of the $n\times n$ adjacency matrix $A$ of a large Erdos-Renyi random graph (without self-coupling, i.e., all diagonal elements of $A$ are equal to zero). I was planning to use the invariance of trace under a change of basis and write
$\forall m<n:\:\:\:tr(A^m)=\sum_{i=1}^n\nu_i^m.$
Wigner's semicircle law states that in the asymptotic limit, the $(n-1)$ eigenvalues $\nu_1,\dots\,\nu_{n-1}$ have the semicircle probability distribution function
$f(\nu) = \frac{1}{2\pi \sigma^2}\sqrt{4\sigma^2-\frac{\nu^2}{n}}$
with second moment $\sigma^2$ of the distribution of the non-diagonal elements of $A$.
Since $tr(A)=0$ (no self-coupling), I know that $\nu_n=-\sum_{i=1}^{n-1}\nu_i$. My plan was to calculate the pdfs for $\nu_i^m$ and $tr(A^m)$ via multiple convolutions of $f(\nu_i)$ with itself. However, I already struggle with calculating the convolution of two semicircle pdfs,
$f(\nu_i)\star f(\nu_j):=\int_{-\infty}^\infty f(\nu_i)f(\nu_j-\nu_i)d \nu_i$.
How can I calculate this convolution? Or is there a better way to calculate the expectation value of $tr(A^m)$, that is, the expectation value of a non-linear function of $(n-1)$ iid random variables with semicircle pdf?
EDIT:
Since I am only interested in the expectation value of $tr(A^m)$, I do not need a pdf for $tr(A^m)$, because
$\langle tr(A^m)\rangle=\sum_{i=1}^{n}\langle \nu_i^m\rangle=(n-1)\int_{-\infty}^\infty f(\nu)\nu^md\nu+\langle \nu_n^m\rangle.$
However, I believe I still need the convolution of semicircle distributions for calculating
$\langle \nu_n^m\rangle = (-1)^m\langle \sum_{i=1}^{n-1} \nu_i^m\rangle.$
 A: Here's my attempt on an exact answer, which is not yet complete.
(if you want an answer in the form of a limit as $n \to \infty$, take a look at the proof of Proposition 4.1 of these lecture notes, on which this answer is heavily inspired)
It is well known that given the adjacency matrix $A$ of a graph $G$,
$\operatorname{Tr}(A^m)$ is the number of
closed walks of length $m$ in $G$
(since $(A^m)_{ij}$ is the number of walks of length $m$
beginning at $i$ and ending at $j$).
So here's a combinatorial approach to
$\left< \operatorname{Tr}(A^m) \right>$.
Assuming that we are dealing with a $G(n, p)$ graph
on the vertex set $[n]$, we have that
$\left< \operatorname{Tr}(A^m) \right>
= \sum_{i=1}^n \left< (A^m)_{ii} \right>
= \sum_{(i_1, \dots, i_m) \in [n]^m} \left< A_{i_1i_2} A_{i_2i_3} \dots A_{i_mi_1} \right>$
For $i = (i_1, \dots, i_m) \in [n]^m$,
denote $A_{i_1i_2} \dots A_{i_mi_1}$ by $A_i$
and let $E_i$ be the edge set
$\{i_1i_2, i_2i_3, \dots, i_mi_1\}$.
Since all $A_{jk}$, $j \neq k$, are independent indicator
random variables with probability $p$,
then $\left< A_i \right> = p^{|E_i|}$
(provided there are no self-loops in $E_i$,
in which case $\left< A_i \right> = 0$).
Let $W^m_e$ be the set of all closed walks of length $m$
on the vertex set $[n]$ with no self-loops
using $e$ distinct edges. Then
$\left< \operatorname{Tr}(A^m) \right>
= \sum_{i=1}^m \sum_{W \in W_i^m} p^i
= \sum_{i=1}^m p^i \#\{W \in W_i^m\}$
And all we are left to do is count how many walks we have in $W_i^m$.
