Limiting Distributions of Sums with Random Spectral Weights

Graph theoretic terminology may be found in [6]. A graph $G$ of order $n$ is an ordered pair $(V,E)$ consisting of a set $E=E(G)$ of edges and a set $V=V(G)$ of vertices such that $|V|=n$. We adopt standard notation and let $m=|E(G)|$ denote the number of edges in a graph $G$. A graph is simple if it contains no loops or multiple edges and it is connected if it contains no isolated vertices. If $G$ is a graph of order $n$, then its adjacency matrix is the $n\times n$ real symmetric matrix $A(G)$ whose entries are defined by setting $[A(G)]_{ij}=1$ if vertices $i$ and $j$ are connected by an edge and $[A(G)]_{ij}=0$ otherwise. The spectrum of $G$ is the spectrum of its adjacency matrix $A(G)$, and is therefore real since $A(G)$ is Hermitian. We adopt a standard convention and write the spectrum of $G$ in non-increasing order,

Moreover, the singular spectrum of $G$ consists of the singular values of $A(G)$. We remark that the singular values of the Hermitian matrix $A(G)$ correspond to the moduli of its eigenvalues. Again, we adopt a standard convention and write the singular spectrum of $G$ in non-increasing order,

For $q\geq 1$, we let $L^{q}(\Omega,\mathcal{F},\mathbb{P}_{\Omega})$ denote the vector space of random variables defined on the probability space $(\Omega,\mathcal{F},\mathbb{P}_{\Omega})$ with finite $L^{q}$-norm defined by

A random variable $X$ defined on a probability space $(\Omega,\mathcal{F},\mathbb{P}_{\Omega})$ is called sub-gaussian if $\|X\|_{q}\leq\|X\|_{\psi_{2}}\sqrt{q}$ for all $q\geq 1$, where

is called the sub-gaussian norm of $X$ [32, Def. 2.5.6]. Gaussian, Bernoulli and bounded random variables are typical examples of sub-gaussian random variables [32, Ex. 2.5.8].

This paper establishes central limit-type theorems for the sequences of weighted sums

in which $X_{1},X_{2},\ldots,X_{n}$ are i.i.d. random variables and $a_{1},a_{2},\ldots,a_{n}$ correspond to either the eigenvalues or the singular values of Erdős-Rényi-Gilbert graphs. Graphs in the Erdős-Rényi-Gilbert $\mathcal{G}(n,p)$ model are constructed by attaching edges between each vertex pair from a set of $n$ labeled vertices independently with probability $p\in[0,1]$. Here and henceforth we assume $p\neq 0,1$.

The first two theorems illustrate the relatively simple limiting distributions of $W_{n}(\boldsymbol{\lambda})$ in the case when certain symmetry conditions are imposed on $X_{1},X_{2},\ldots$. The third theorem illustrates the simple limiting distributions of $W_{n}(\boldsymbol{s})$ in the case when $X_{1},X_{2},\ldots$ are sub-gaussian with mean zero but not necessarily symmetric.

The final theorem illustrates, in particular, how sensitive the sequences $W_{n}(\boldsymbol{s})$ are with respect to the conditions imposed on $X_{1},X_{2},\ldots,X_{n}$. Very distinct behavior emerges by simply choosing random variables with non-zero mean. Ultimately, this distinction is rooted in the asymptotic behavior of the Schatten $q$ norm of a graph, which is defined for $q\geq 1$ by

In particular, the large $n$ behavior of $\|G\|_{S_{q}}$ is very different for the cases $q=1$ and $q>1$ [27, Thm. 5]. Note the sub-gaussian condition is also removed in the following theorem.

There exist various central limit-type theorems in the literature pertaining to sums of eigenvalues of random matrices e.g. [8, 21, 26, 28]. Among the earliest results in this direction are due to Johansson [21]. These specific results concern random Hermitian matrices distributed according to the probability measure

in which $\tau>0$, $V(x)$ is a polynomial with positive even degree and a positive leading coefficient and $dA$ denotes Lebesgue measure on the space of $n\times n$ complex Hermitian matrices. It bears worth mentioning that setting $\tau=n/2$ and $V(x)=x^{2}$ gives rise to the Gaussian unitary ensemble introduced by Dyson [12, 13]. The main result of [21] establishes that the linear eigenvalue statistic $\sum_{k}f(\lambda_{k})$ converges in distribution to a normal random variable with mean zero. The sums we consider in this paper can be thought of as randomized graph-theoretic versions of the sums originally considered by Johansson.

The following examples and simulations illustrate a few of the main theorems. All code used to generate these plots is made available by contacting the authors.

This paper, which is intended for a wide probabilistic audience, takes us on a short journey through the spectral analysis of large random matrices and is organized as follows. Section 2 highlights a few classic results in random matrix theory which serve as prerequisites for later sections. No background in random matrices is assumed. Section 3 provides a computational lemma that we use to expand the partial moments of $W_{n}(\boldsymbol{a})$ in terms of power sum symmetric functions. Section 4 establishes the asymptotics for the partial moments of $W_{n}(\boldsymbol{a})$ by analyzing the limiting behavior of the power sum symmetric functions. Theorems 1.1 and 1.2 are proved in Section 5. Theorem 1.3 is proved in Section 6 and Theorem 1.4 is proved in Section 7. Finally, we conclude with possible directions for future work and closing remarks.

The form of (2.2) that we need for later sections is due to Arnold. In particular, suppose $B_{n}$ is an $n\times n$ real symmetric matrix whose entries, modulo the symmetry condition $\xi_{ij}=\xi_{ji}$, are independent. Assume the upper-triangular entries share a common distribution with finite positive variance $\sigma^{2}$. In addition, we assume the diagonal entries also share a common distribution. Furthermore, assume the entries $\xi_{ij}$ have finite fourth and sixth moments for $i>j$ and the diagonal entries $\xi_{ii}$ have finite second and fourth moments. Define the normalized matrix $A_{n}=B_{n}/(\sigma\sqrt{n})$. Arnold proves that $\mu_{A_{n}}\to\mu_{\operatorname{sc}}$ almost surely in the sense that

for all continuous and compactly supported test functions $\phi:\mathbb{R}\to\mathbb{R}$ [2, Thm. 2].

Here and throughout we adopt standard asymptotic notation. In particular, we write $f(n)=O\big{(}g(n)\big{)}$ if there exists a constant $C$ such that $|f(n)|\leq Cg(n)$ for all $n$ sufficiently large. Moreover, we write $f(n)=o\big{(}g(n)\big{)}$ whenever $f(n)/g(n)\to 0$ as $n\to\infty$.

A result due to Füredi and Komlós allows us to analyze the limiting behavior of polynomials in $a_{1},a_{2},\ldots,a_{n}$. Suppose $A_{n}$ is an $n\times n$ real symmetric matrix with bounded entries. Moreover, we assume the entries of $A_{n}$, modulo the constraint $\xi_{ij}=\xi_{ji}$, are independent. Let $\mu=\mathbb{E}\xi_{ij}>0$ denote the common mean of the upper-triangular entries and let $\sigma^{2}=\mathbb{E}(\xi_{ij}-\mu)^{2}$ denote their common variance. Furthermore, suppose the diagonal entries share a common mean, $\nu=\mathbb{E}\xi_{ii}$. Füredi and Komlós [17, Thm. 1] show that the distribution of the largest eigenvalue $\lambda_{1}$ of $A_{n}$ can be approximated in order $n^{-1/2}$ by a normal distribution with mean $(n-1)\mu+\nu+\sigma^{2}/\mu$ and variance $2\sigma^{2}$. Moreover, with high probability (w.h.p.) we have

whenever $i\neq 1$.

We now establish the limiting behavior for the partial moments $f_{j}(\boldsymbol{\lambda})=\mathbb{E}_{\Omega}(\lambda_{1}X_{1}+\lambda_{2}X_{2}+\cdots+\lambda_{n}X_{n})^{j}$ in which $X_{1},X_{2},\ldots,X_{n}$ are i.i.d. random variables defined on $(\Omega,\mathcal{F},\mathbb{P}_{\Omega})$ and $\lambda_{1},\lambda_{2},\ldots,\lambda_{n}$ correspond to eigenvalues in the Erdős-Rényi-Gilbert model. We recall $\mathpzc{p}_{k}(\boldsymbol{\lambda})$ denotes the power sum symmetric polynomial of degree $k$ in the variables $\lambda_{1},\lambda_{2},\ldots,\lambda_{n}$.

We now establish the limiting behavior for the partial moments $f_{j}(\boldsymbol{s})=\mathbb{E}_{\Omega}(s_{1}X_{1}+s_{2}X_{2}+\cdots+s_{n}X_{n})^{j}$ in which $X_{1},X_{2},\ldots,X_{n}$ are i.i.d. random variables defined on $(\Omega,\mathcal{F},\mathbb{P}_{\Omega})$ and $s_{1},s_{2},\ldots,s_{n}$ correspond to singular values in the Erdős-Rényi-Gilbert model.

Suppose $X_{1},X_{2},\ldots,X_{n}\sim X$ are i.i.d. random variables defined on a probability space $(\Omega,\mathcal{F}_{\Omega},\mathbb{P}_{\Omega})$ in which $X$ is a sub-gaussian random variable with mean $\mu$ and variance $\sigma^{2}$. Define the auxiliary variables $\xi_{i}=\sigma^{-2}(X_{i}-\mu)$ and let $j\geq 1$ be any integer. The sum $W_{n}(\boldsymbol{\lambda})$ satisfies

since simple graphs are traceless. The random variables $\xi_{1},\xi_{2},\ldots\xi_{n}$ are mean zero sub-gaussian random variables with unit variances. Relations (5.1) and (5.2), together with the inequality $2m\leq n(n-1)$, imply that there exists a constant $c>0$, which is independent of $n$, such that

Therefore, $\mathbb{E}_{\mathcal{G}}\mathbb{E}_{\Omega}|W_{n}(\boldsymbol{\lambda})|^{j}$ is finite and the Fubini-Tonelli theorem [16, Thm. 2.16] ensures

in which $\mathbb{E}[\cdot]$ denotes expectation with respect to the product measure $\mathbb{P}_{\mathcal{G}}\otimes\mathbb{P}_{\Omega}$.

Proposition 4.2 and the uniform boundedness of the variables $\mathbb{E}_{\Omega}|W_{n}(\boldsymbol{\lambda})|^{j}$ allow us to compute the limit for the total expectation of $[W_{n}(\boldsymbol{\lambda})]^{j}$, which we now highlight. Define $E_{j}=\{G\,:\,n^{-j}f_{j}(\boldsymbol{\lambda})=\alpha_{j}\}$, where $\alpha_{j}=\alpha_{j}(n)$ is a real number to be chosen momentarily. Relation (5.4) implies