Xrfgtjtk

I want to calculate the expectation value for the trace of the $m$-th power of the $ntimes 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}^nnu_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}{2pi sigma^2}sqrt{4sigma^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^mrangle=(n-1)int_{-infty}^infty f(nu)nu^mdnu+langle nu_n^mrangle.$

However, I believe I still need the convolution of semicircle distributions for calculating

$langle nu_n^mrangle = (-1)^mlangle sum_{i=1}^{n-1} nu_i^mrangle.$

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$.