Limiting spectral distribution for large sample covariance matrices with
graph-dependent elements.

Pavel Yaskov111Steklov Mathematical Institute of RAS, Moscow, Russia
e-mail<EMAIL_ADDRESS>
This work is supported by the Russian Science Foundation under grant
18-71-10097.

###### Abstract

We obtain the limiting spectral distribution for large sample covariance
matrices associated with random vectors having graph-dependent entries under
the assumption that the interdependence among the entries grows with the
sample size $n$. Our results are tight. In particular, they give necessary and
sufficient conditions for the Marchenko-Pastur theorem for sample covariance
matrices with $m$-dependent orthonormal elements when $m=o(n)$.

Keywords: random matrices; covariance matrices; the Marchenko-Pastur law.

##  1 Introduction

The asymptotic behaviour of the spectrum of large sample covariance matrices
plays an important role in high-dimensional statistical problems, in
particular, those related to the least squares estimation and the covariance
matrix estimation (e.g., see the papers [6], [9], [14], and the references
therein). The present paper studies weak limits of the empirical spectral
distributions of sample covariance matrices

$\widehat{\Sigma}_{n}=\frac{1}{n}\sum_{k=1}^{n}\mathbf{x}_{pk}\mathbf{x}_{pk}^{\top}$
(1)

under the assumption that $p,n\to\infty$ and $p/n\to\rho>0,$ where
$\\{\mathbf{x}_{pk}\\}_{k=1}^{n}$ are i.i.d. copies of a random vector
$\mathbf{x}_{p}$ in ${\mathbb{R}}^{p}$ and the empirical spectral distribution
of a symmetric matrix $A\in{\mathbb{R}}^{p\times p}$ with eigenvalues
$\lambda_{1}\leqslant\lambda_{2}\leqslant\ldots\leqslant\lambda_{p}$ is
defined by

$\mu_{A}=\frac{1}{p}\sum_{i=1}^{p}\delta_{\lambda_{i}}$

with $\delta_{\lambda}$ being a Dirac measure with mass at
$\lambda\in{\mathbb{R}}$. Notice that in this construction, the sample mean
vector is not subtracted from $\mathbf{x}_{pk}$, since it does not affect the
limiting spectral distributions (see the rank inequality of Theorem A.43 in
[3]).

There is a number of results in random matrix theory, allowing to compute the
limiting spectral distribution of $\widehat{\Sigma}_{n}$ under different
distributional assumptions on $\mathbf{x}_{p}$. Let us mention the papers [1],
[2], [4], [7], [10], [16], [19], [20], [21], [26], among others. The most
general conditions imposed on $\mathbf{x}_{p}$ ensure that the quadratic forms
$\mathbf{x}_{p}^{\top}A_{p}\mathbf{x}_{p}$ weakly concentrate around their
expectations up to an error term $o(p)$ with probability $1-o(1)$, where
$A_{p}\in{\mathbb{C}}^{p\times p}$ is an arbitrary matrix with the spectral
norm $\|A_{p}\|\leqslant 1$. These conditions were studied in [2], [8], [16],
[22], [28], [29], and [30]. As shown in [29], the weak concentration property
for specific quadratic forms of $\mathbf{x}_{p}$ gives necessary and
sufficient conditions for the Marchenko-Pastur theorem [18].

In general, the weak concentration property for the quadratic forms could hard
to verify in practice. This presents a separate problem to be solved for a
given data model. In this paper, we obtain concentration inequalities for
$\mathbf{x}_{p}^{\top}A_{p}\mathbf{x}_{p}$ with $\mathbf{x}_{p}$ having graph-
dependent entries under the assumption that the interdependence among the
entries grows with $p$. As a corollary, we derive the limiting spectral
distribution for the large sample covariance matrices $\widehat{\Sigma}_{n}$
associated with $\mathbf{x}_{p}$. Our results are close to that of [7], [12],
and [25]. The paper [7] studies the block independent model for
$\mathbf{x}_{p}$ where the entries of $\mathbf{x}_{p}$ are partitioned into
blocks in such a way that the entries in different blocks are independent and
the blocks may grow with $p$. Following [12], the paper [25] considers the
$m$-dependent model for $\mathbf{x}_{p}$, where the entries of
$\mathbf{x}_{p}$ are $m$-dependent with $m$ growing with $p$. In contrast to
these papers, our results are more general and tight. In particular, they give
necessary and sufficient conditions in the isotropic case with
${\mathbb{E}}\mathbf{x}_{p}\mathbf{x}_{p}^{\top}$ being the identity matrix
(for details, see Section 2).

Also, despite the fact that graph-dependent data are frequently appears in
computer science problems, to the best of our knowledge, there are no well-
established methods for proving concentration inequalities for quadratic forms
in graph-dependent random variables with growing interdependence among them.
This is in contrast to linear functions, which could be efficiently analysed
via the method based on fractional coloring of the dependency graph [13], or
bounded-difference functions, which could be analysed via the method relying
on the forest complexity of the dependency graph [31]. In this paper, we use a
straightforward approach for analysing the quadratic forms, which is based on
an appropriate covering of the dependency graph by balls centered at vertices
from its dominating set.

The paper is structured as follows. Section 2 contains our main results.
Section 3 deals with the proofs. Some additional results are given in an
Appendix.

##  2 Main results

Let us introduce some notation. Set $[\\![a,b]\\!]=[a,b]\cap{\mathbb{Z}}$ for
all $a\leqslant b$ and denote by $|S|$ a cardinality of a set $S$. For all
$p\geqslant 1$, let $\mathbf{x}_{p}$ be a random vector in ${\mathbb{R}}^{p}$
and let $\Sigma_{p}\in{\mathbb{R}}^{p\times p}$ be symmetric positive
semidefinite, hereinafter ${\mathbb{R}}^{p\times p}$ stands for the set of all
real $p\times p$ matrices. For $A\in{\mathbb{R}}^{p\times p}$, $\|A\|$ will
denote its spectral norm. Also, set
${\mathbb{C}}_{+}:=\\{z\in{\mathbb{C}}:{\rm\,Im}(z)>0\\}$ and denote by
${\mathcal{B}}({\mathbb{R}}_{+})$ the Borel $\sigma$-algebra of
${\mathbb{R}}_{+}$. All random elements will be defined on the same
probability space.

First, let us recall some known results on the limiting spectral distribution
of $\widehat{\Sigma}_{n}$ from (1). They will be stated under the following
general assumptions:

(A1)
$(\mathbf{x}_{p}^{\top}A_{p}\mathbf{x}_{p}-{\mathrm{tr}}(\Sigma_{p}A_{p}))/p\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}0$
as $p\to\infty$ for all sequences of symmetric positive semidefinite
$A_{p}\in{\mathbb{R}}^{p\times p}$ with $\|A_{p}\|\leqslant 1$.

(A2) ${\mathrm{tr}}(\Sigma_{p}^{2})/p^{2}\to 0$ as $p\to\infty$.

######  Theorem 2.1.

Let $p=p(n)\in{\mathbb{N}}$ be such that $p/n\to\rho>0$ when $n\to\infty$. If
$\\{(\mathbf{x}_{p},\Sigma_{p})\\}_{p=p(n),n\geqslant 1}$ satisfies (A1)–(A2)
and $\mu_{\Sigma_{p}}$ converges weakly to a probability measure $\mu$ on
${\mathcal{B}}({\mathbb{R}}_{+})$, then

${\mathbb{P}}(\mu_{\widehat{\Sigma}_{n}}\to\nu\text{ weakly, }n\to\infty)=1,$

where $\nu$ is a probability measure on ${\mathcal{B}}({\mathbb{R}}_{+})$,
whose Stieltjes transform

$s(z)=\int_{{\mathbb{R}}_{+}}\frac{\nu(d\lambda)}{\lambda-z},\;z\in{\mathbb{C}}_{+},\;\text{satisfies}\;s(z)=\int_{{\mathbb{R}}_{+}}\frac{\mu(d\lambda)}{\lambda(1-\rho-\rho
zs(z))-z}.$

As is shown in [30], the above theorem follows from Theorem 2 in [30] and
Theorem 7.2.2 with Remark 7.2.6.(4) in [23]. In the case with i.i.d.
$\mathbf{x}_{pk}$, Theorem 2.1 extends Theorem 1.1 in [2] by allowing
$\|\Sigma_{p}\|$ to be unbounded and replacing convergence in $L_{2}$ by
convergence in probability in (A1). The general case with independent
$\mathbf{x}_{pk}$ could considered similarly (e.g., see Remark 1 in [27]).

When the weak limit of $\mu_{\Sigma_{p}}$ is $\delta_{1}$, the measure $\nu$
in Theorem 2.1 is just the Marchenko-Pastur law $\mu_{\rho}$ with parameter
$\rho>0$, which is defined by

$d\mu_{\rho}=\max\\{1-1/\rho,0\\}\,d\delta_{0}+\frac{\sqrt{(b-x)(x-a)}}{2\pi
x\rho}I(x\in[a,b])\,dx,$

where $a=(1-\sqrt{\rho})^{2}$ and $b=(1+\sqrt{\rho})^{2}.$ We can state a
stronger result in the isotropic case with
${\mathbb{E}}\mathbf{x}_{p}\mathbf{x}_{p}^{\top}=I_{p}$.

######  Theorem 2.2.

Let $p=p(n)\in{\mathbb{N}}$ satisfy $p/n\to\rho>0$ as $n\to\infty$. If, for
$p=p(n)$, $\mathbf{x}_{p}$ is a random vector in ${\mathbb{R}}^{p}$ with
${\mathbb{E}}\mathbf{x}_{p}\mathbf{x}_{p}^{\top}=I_{p}$ and (A1) holds for
$\Sigma_{p}=I_{p}$, then

${\mathbb{P}}(\mu_{\widehat{\Sigma}_{n}}\to\mu_{\rho}\text{ weakly,
}n\to\infty)=1.$ (2)

Furthermore, if (2) holds, then
$\mathbf{x}_{p}^{\top}\mathbf{x}_{p}/p\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}1$
as $p=p(n)\to\infty$.

The sufficient part of Theorem 2.2 follows from Theorem 2.1, the necessity
part follows from Theorem 2.1 in [29]. As we will see below, the necessary
condition
$\mathbf{x}_{p}^{\top}\mathbf{x}_{p}/p\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}1$
or its anisotropic analogue will be also a sufficient condition in the
following graph-dependent model.

######  Definition 2.3.

Consider a random vector $\mathbf{x}=(X_{k})_{k=1}^{p}$ in ${\mathbb{R}}^{p}$.
We say that $\mathbf{x}$ follows the graph dependent model with an undirected
graph $G=(V,E)$ having the vertex set $V=[\\![1,p]\\!]$ and an edge set $E$
such that the collections $\\{X_{i}\\}_{i\in I}$ and $\\{X_{j}\\}_{j\in J}$
are independent when $I,J\subseteq V$ are non-adjacent.222Here $I,J\subseteq
V$ are adjacent in $G$ if there are $i\in I,j\in J$ such $i=j$ or $i$ is a
neighbour of $j$ in $G$ and $I,J$ are non-adjacent in $G$ otherwise.

To state our main results, we need to introduce some more definitions for a
graph $G=(V,E)$. Let $d_{G}$ be the distance in $G$, i.e. $d_{G}(u,v)$ is the
number of edges in a shortest path connecting $u,v\in V$, $d_{G}(u,v)=0$ if
$u=v,$ and $d_{G}(u,v)=\infty$ if there is no path connecting $u,v$ and $u\neq
v$. In what follows, we also set $B_{d}(v)=B_{d}(v;G):=\\{u\in
G:d_{G}(u,v)\leqslant d\\}$. For $d\in{\mathbb{Z}}_{+},$ we will say that
$\mathcal{V}\subseteq V$ is a $d$-dominating set for $G$ if every vertex not
in $\mathcal{V}$ is adjacent to at least one vertex in $\mathcal{V}$ and, for
any $u\in V$, there are no more than $d$ vertices $v\in\mathcal{V}$ with
$d_{G}(u,v)\leqslant 3$. Recall also that the maximum degree of a graph is the
maximum of its vertices’ degrees.

We can now state our main concentration inequality for quadratic forms of
graph-dependent random variables.

######  Theorem 2.4.

Let $\mathbf{x}=(X_{k})_{k=1}^{p}$ be a random vector in ${\mathbb{R}}^{p}$
with mean zero and covariance matrix $\Sigma$. Suppose $\mathbf{x}$ follows
the graph dependent model with a graph $G$. If $G$ has the maximum degree
$\Delta\geqslant 0$ and a $d$-dominating set for some $d\in{\mathbb{N}}$,
then, for all symmetric $A=(a_{ij})_{i,j=1}^{p}\in{\mathbb{R}}^{p\times p}$,

${\rm Var}(\mathbf{x}^{\top}A\,\mathbf{x})\leqslant
C_{d}\|A\|^{2}(\Delta+1)\sum_{k=1}^{p}{\mathbb{E}}X_{k}^{4},$ (3)

where $C_{d}>0$ depends only on $d$. If, in addition, $a_{ij}=0$ when
$d_{G}(i,j)\leqslant 2$, then

${\rm Var}(\mathbf{x}^{\top}A\,\mathbf{x})\leqslant
2\|A\|^{2}{\mathrm{tr}}(\Sigma^{2}).$ (4)

The proof of Theorem 2.4 is deferred to Section 3. Inspecting the proof shows
that one could take $C_{d}=(d^{7}+2)2^{2d}$. Furthermore, the bounds (3)–(4)
will hold even if we correct Definition 2.3 by assuming that the entries of
$\mathbf{x}_{p}$ have finite fourth moments, the edge set $E$ is such that the
covariances $\mathrm{Cov}(X_{i}X_{j},X_{k}X_{l})$,
$\mathrm{Cov}(X_{i},X_{k})$, $\mathrm{Cov}(X_{i},X_{l})$,
$\mathrm{Cov}(X_{j},X_{k})$, $\mathrm{Cov}(X_{j},X_{l})$ are zero for all non-
adjacent sets $\\{i,j\\},\\{k,l\\}\subseteq V$ (here we allow the cases $i=j$
and $k=l$).

Theorem 2.4 allows to verify (A1) for
$\Sigma_{p}={\mathbb{E}}\mathbf{x}_{p}\mathbf{x}_{p}^{\top}$ in different
scenarios, where $\mathbf{x}_{p}$ follows a graph dependent model for each
$p\geqslant 1$ and the model parameters $d=d(p)=O(1)$ and
$\Delta=\Delta(p)=o(p)$ as $p\to\infty$.

######  Theorem 2.5.

Let $p=p(n)\in{\mathbb{N}}$ be such that $p/n\to\rho>0$, hereinafter all
limits are with respect to $n\to\infty$. Assume also that

(i) for each $p=p(n)$, a zero-mean random vector $\mathbf{x}_{p}$ in
${\mathbb{R}}^{p}$ follows the graph dependent model with a graph $G_{p}$
having the maximum degree $\Delta_{p}=o(p)$ and a $d_{p}$-dominating set with
$d_{p}=O(1)$,

(ii) there exist $c>0$ and a probability measure $\mu$ on
${\mathcal{B}}({\mathbb{R}}_{+})$ such that $\mu_{\Sigma_{p}}\to\mu$ weakly
and ${\mathrm{tr}}(\Sigma_{p})/p\to c$, where
$\Sigma_{p}={\mathbb{E}}\mathbf{x}_{p}\mathbf{x}_{p}^{\top}$.
If
$\mathbf{x}_{p}^{\top}\mathbf{x}_{p}/p\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}c$,
then ${\mathbb{P}}(\mu_{\widehat{\Sigma}_{n}}\to\nu\text{ weakly})=1,$ where
$\nu$ is defined in Theorem 2.1. Furthermore, if
${\mathbb{E}}\mathbf{x}_{p}\mathbf{x}_{p}^{\top}=I_{p}$ for each $p=p(n)$,
then

$\mathbf{x}_{p}^{\top}\mathbf{x}_{p}/p\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}1\quad\text{iff}\quad{\mathbb{P}}(\mu_{\widehat{\Sigma}_{n}}\to\mu_{\rho}\text{
weakly})=1,$

where $\mu_{\rho}$ is the Marchenko-Pastur law with parameter $\rho$.

The proof of the above theorem is deferred to Section 3 and based on Theorem
2.1 and 2.2. Let us consider two examples of graph dependent models.

######  Example 2.6.

(Block-independent model) Suppose the entries of
$\mathbf{x}_{p}=(X_{pk})_{k=1}^{p}$ can be partitioned into $q$ blocks
$I_{pk}$ each of length $d_{pk}$ ($k\in[\\![1,q]\\!]$), in such a way that the
entries in different blocks are independent. Assume also that the entries have
zero mean, unit variance, and fourth moment bounded by $K>0$. Then
$\mathbf{x}_{p}$ follows the graph dependent model with $G_{p}=(V_{p},E_{p})$,
where $V=[\\![1,p]\\!]$ and

$E_{p}=\\{\\{i,j\\}:\text{ $i,j\in V_{p}$ lie in the same block and $i\neq
j$}\\}.$

Any set $\mathcal{V}_{p}$ that contains at least one element from every block
and does not contain two elements from the same block forms a 1-dominating set
for $G$ with the maximum degree

$\Delta_{p}=\max_{1\leqslant k\leqslant q}d_{pk}-1.$

So, under the conditions of Theorem 2.4, (3) reduces to

${\rm Var}(\mathbf{x}_{p}^{\top}A_{p}\mathbf{x}_{p})\leqslant
C_{1}p\|A_{p}\|^{2}K\max_{1\leqslant k\leqslant q}d_{pk}.$

This bound should be compared with Theorem 1.8 of [7], stating that for the
isotropic case with ${\mathbb{E}}\mathbf{x}_{p}\mathbf{x}_{p}^{\top}=I_{p}$,

${\rm
Var}(\mathbf{x}_{p}^{\top}A_{p}\mathbf{x}_{p})\leqslant\|A_{p}\|^{2}\Big{(}K\sum_{k=1}^{q}d_{pk}^{2}+2p\Big{)}.$

In the asymptotic regime $p\to\infty$ and $K$ not depending on $p$, both the
bounds will yield (A1) for
$\Sigma_{p}={\mathbb{E}}\mathbf{x}_{p}\mathbf{x}_{p}^{\top}$ only if
$\max_{k}d_{pk}=o(p)$. As shown in [7], the last condition on $d_{pk}$ is an
optimal condition ensuring that the limiting spectral distribution of
$\widehat{\Sigma}_{n}$ is the Marchenko-Pastur law for the block-independent
model (in the case ${\mathbb{E}}\mathbf{x}_{p}\mathbf{x}_{p}^{\top}=I_{p}$).

Notice also that by the Gnedenko-Kolmogorov conditions for relative stability
(e.g., see (A) and (B) in [11]), the condition
$\mathbf{x}_{p}^{\top}\mathbf{x}_{p}/p\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}c$
in Theorem 2.5 could be equivalently replaced by the following Lindeberg
condition: for all $\varepsilon>0$,

$\sum_{k=1}^{q}{\mathbb{E}}Z_{pk}I(Z_{pk}>\varepsilon)\to 0,\quad p\to\infty,$
(5)

where $Z_{pk}=p^{-1}\sum_{i\in I_{pk}}X_{pi}^{2}$. As a result, Theorem 2.5
allows to compute the limiting spectral distribution of $\widehat{\Sigma}_{n}$
under the Lindeberg condition, which is much weaker than the fourth moment
condition of Theorem 1.3 in [7].

######  Example 2.7.

($m$-dependent model) Let $m\in[\\![0,p-1]\\!]$ and suppose the entries of
$\mathbf{x}_{p}=(X_{pi})_{i=1}^{p}$ are $m$-dependent, i.e.
$\\{X_{pi}\\}_{i\leqslant k}$ and $\\{X_{pj}\\}_{j>k+m}$ are independent for
all $k\in{\mathbb{N}}$ with $k+m\leqslant p$. Assume also that the entries
have zero mean and fourth moment bounded by $K>0$. Then $\mathbf{x}_{p}$
follows the graph dependent model with $G_{p}=(V_{p},E_{p})$, where
$V_{p}=[\\![1,p]\\!]$ and $E_{p}=\\{\\{i,i+k\\}:\text{ $i,i+k\in V_{p},$
$1\leqslant k\leqslant m$}\\}.$ The maximum degree of $G_{p}$ is $2m$ and one
can construct a 5-dominating set of $G_{p}$ as $\mathcal{V}_{p}=\\{k(m+1)\in
V_{p}:k\in[\\![1,p/(m+1)]\\!]\\}$. So, under the conditions of Theorem 2.4,
(3) reduces to

${\rm Var}(\mathbf{x}_{p}^{\top}A_{p}\mathbf{x}_{p})\leqslant
C_{5}(2m+1)pK\|A_{p}\|^{2}.$

In the asymptotic regime $p\to\infty$ with $m=m(p)$ and $K$ not depending on
$p$, the last inequality guarantees that (A1) holds only if $m=o(p)$. The last
condition on $m$ is tight. This follows from Example 2.6 and the fact that the
block-independent model could be considered as a particular case of
$m$-dependent model, as one can always rearrange the entries of
$\mathbf{x}_{p}$ in the block-independent model from Example 2.6 in a way that
$\mathbf{x}_{p}$ satisfies the $m$-dependent model with $m=\max_{k}d_{k}-1$.

By the Gnedenko-Kolmogorov conditions for relative stability, the condition
$\mathbf{x}_{p}^{\top}\mathbf{x}_{p}/p\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}c$
in Theorem 2.5 could be replaced by the Lindeberg condition (5) with

$Z_{pk}=\frac{1}{p}\sum_{i=(k-1)(m+1)+1}^{k(m+1)}X_{pi}^{2},\quad
k\in[\\![1,p/(m+1)]\\!].$

This could be verified by writing the sum
$\mathbf{x}_{p}^{\top}\mathbf{x}_{p}=\sum_{i=1}^{p}X_{pi}^{2}$ as two sums
with independent entries

$\sum_{k}Z_{pk}\,\mathrm{I}(k\text{ is
odd})+\sum_{k}Z_{pk}\,\mathrm{I}(k\text{ is even}).$

In fact, one could show that
$\mathbf{x}_{p}^{\top}\mathbf{x}_{p}/p\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}c$
is equivalent to the Lindeberg condition using the results of [11] and Lemma
3.1. In the case of the $m$-dependent model, the result of Theorem 2.5
improves the results of [12] (where fixed $m$ is considered) and [25] (where
$m=o(p^{1/4})$).

Notice that the above results could be easily extended to multidimensional
versions of the $m$-dependent model where the entries of
$\mathbf{x}_{p}=(X_{i})_{i\in V_{p}}$ are indexed by a set
$V_{p}\subset{\mathbb{R}}^{q}$ with $|V_{p}|=p$ and are such that
$\\{X_{i}\\}_{i\in I}$ and $\\{X_{j}\\}_{j\in J}$ are independent when some
given distance in ${\mathbb{R}}^{q}$ between $I,J\subseteq V_{p}$ is greater
than $m$.

##  3 Proofs

###### Proof of Theorem 2.4..

First, we will prove the second bound of the Theorem. Let symmetric
$A=(a_{ij})_{i,j=1}^{p}$ be such that $a_{ij}=0$ if $d_{G}(i,j)>2$. We have

${\rm Var}(\mathbf{x}^{\top}A\,\mathbf{x})=\sum_{1\leqslant i,j,k,l\leqslant
p}a_{ij}a_{kl}\mathrm{Cov}(X_{i}X_{j},X_{k}X_{l})\mathrm{I}(d_{G}(i,j)>2,d_{G}(k,l)>2)$

Introduce a zero-mean Gaussian vector $\mathbf{z}=(Z_{k})_{k=1}^{p}$ in
${\mathbb{R}}^{p}$ with
${\mathbb{E}}\mathbf{z}\mathbf{z}^{\top}=\Sigma={\mathbb{E}}\mathbf{x}\mathbf{x}^{\top}$.
We will show that

if $i,j,k,l\in V$ and $d_{G}(i,j)>2,$ $d_{G}(k,l)>2$, $\displaystyle\text{then
}\mathrm{Cov}(X_{i}X_{j},X_{k}X_{l})=\mathrm{Cov}(Z_{i}Z_{j},Z_{k}Z_{l}).$ (6)

Suppose for a moment that this is true. By Lemma 2.3 in [17],

${\rm Var}(\mathbf{x}^{\top}A\,\mathbf{x})={\rm
Var}(\mathbf{z}^{\top}A\,\mathbf{z})=2{\mathrm{tr}}((A\Sigma)^{2}).$

By the Cauchy-Schwartz inequality for traces,

${\mathrm{tr}}(A\Sigma A\Sigma)\leqslant\sqrt{{\mathrm{tr}}((A\Sigma
A)^{2}){\mathrm{tr}}(\Sigma^{2})}.$

Furthermore, $\|A\|^{2}I_{p}-A^{2}$ is a positive semidefinite matrix.
Therefore,

${\mathrm{tr}}((A\Sigma A)^{2})={\mathrm{tr}}(A\Sigma A^{2}\Sigma
A)\leqslant\|A\|^{2}{\mathrm{tr}}(A\Sigma^{2}A)=\|A\|^{2}{\mathrm{tr}}(\Sigma
A^{2}\Sigma)\leqslant\|A\|^{4}{\mathrm{tr}}(\Sigma^{2})$

and we get the desired bound ${\rm
Var}(\mathbf{x}^{\top}A\,\mathbf{x})\leqslant
2\|A\|^{2}{\mathrm{tr}}(\Sigma^{2})$.

So, it remains to verify (3). We claim that either the sets $\\{i,k\\}$ and
$\\{j,l\\}$ or the sets $\\{i,l\\}$ and $\\{j,k\\}$ are non-adjacent. If
$\\{i,j\\}$ and $\\{k,l\\}$ are non-adjacent, then the claim is obvious.
Suppose $\\{i,j\\}$ and $\\{k,l\\}$ are adjacent. W.l.o.g.
$d_{G}(i,k)\leqslant 1$. We have $d_{G}(i,j)>2$, $d_{G}(k,l)>2,$
$d_{G}(i,l)>1$, and $d_{G}(k,j)>1$, where the last two inequalities follow
from

$\displaystyle 2$ $\displaystyle<d_{G}(k,l)\leqslant
d_{G}(k,i)+d_{G}(i,l)\leqslant 1+d_{G}(i,l),$ $\displaystyle 2$
$\displaystyle<d_{G}(i,j)\leqslant d_{G}(i,k)+d_{G}(k,j)\leqslant
1+d_{G}(k,j).$

So, $\\{j,l\\}$ and $\\{i,k\\}$ are non-adjacent. The claim is verified.

Consider the case when $\\{i,k\\}$ and $\\{j,l\\}$ are non-adjacent. The
definition of the graph dependent model gives
${\mathbb{E}}X_{i}X_{j}X_{k}X_{l}={\mathbb{E}}X_{i}X_{k}{\mathbb{E}}X_{j}X_{l}$
and ${\mathbb{E}}X_{q}X_{r}={\mathbb{E}}Z_{q}Z_{r}=0$ for all $q\in\\{i,k\\},$
$r\in\\{j,l\\}$. As a result, $(Z_{i},Z_{k})$ and $(Z_{j},Z_{l})$ are
independent and

$\mathrm{Cov}(X_{i}X_{j},X_{k}X_{l})={\mathbb{E}}X_{i}X_{j}X_{k}X_{l}={\mathbb{E}}X_{i}X_{k}{\mathbb{E}}X_{j}X_{l}=$
$={\mathbb{E}}Z_{i}Z_{k}{\mathbb{E}}Z_{j}Z_{l}={\mathbb{E}}Z_{i}Z_{k}Z_{j}Z_{l}=\mathrm{Cov}(Z_{i}Z_{j},Z_{k}Z_{l}).$

Likewise, we get (3) in the case when $\\{i,l\\}$ and $\\{j,k\\}$ are non-
adjacent.

Let us prove the first bound of the Theorem. Let
$\mathring{A}=(\mathring{a}_{ij})_{i,j=1}^{p}$ be defined by

$\mathring{a}_{ij}=a_{ij}$ if there exists $v\in\mathcal{V}$ such that $i,j\in
B_{2}(v)$ and $\mathring{a}_{ij}=0$ otherwise, (7)

where $\mathcal{V}$ is a $d$-dominating set of $G$. By the Cauchy inequality,

${\rm Var}(\mathbf{x}^{\top}A\,\mathbf{x})\leqslant 2{\rm
Var}(\mathbf{x}^{\top}\mathring{A}\,\mathbf{x})+2{\rm
Var}(\mathbf{x}^{\top}(A-\mathring{A})\,\mathbf{x}).$ (8)

For any $i\in V$, we can always find $v_{i}\in\mathcal{V}$ with
$d_{G}(i,v_{i})\leqslant 1$. In view of the definition of a $d$-dominating set
$\mathcal{V}$, the latter implies that for all $(i,j)\in V$,

$\sum_{v\in\mathcal{V}}\mathrm{I}((i,j)\in
B_{2}^{2}(v))\leqslant\sum_{v\in\mathcal{V}}\mathrm{I}(i\in
B_{2}(v))\leqslant\sum_{v\in\mathcal{V}}\mathrm{I}(v_{i}\in B_{3}(v))\leqslant
d.$ (9)

Let further $\nu_{s}$ be a subset of $\mathcal{V}$ with $|\nu_{s}|=s$
($\leqslant p$) and set

$B_{\nu_{s}}:=\bigcap_{v\in\nu_{s}}B_{2}(v).$

By the standard properties of the Cartesian product with respect to
intersections,

$B_{\nu_{s}}^{2}=\bigcap_{v\in\nu_{s}}B_{2}^{2}(v).$

Also, by (9), $B_{\nu_{s}}^{2}=\varnothing$ when $s>d$ and

$\mathrm{I}\Big{(}\bigcup_{v\in\mathcal{V}}B_{2}^{2}(v)\Big{)}=1-\prod_{v\in\mathcal{V}}(1-\mathrm{I}(B_{2}^{2}(v)))=\sum_{s=1}^{d}(-1)^{s-1}\sum_{\nu_{s}}\mathrm{I}(B^{2}_{\nu_{s}}),$

where the last sum is taken over all possible $\nu_{s}$. In particular, we
infer that

$\displaystyle\mathbf{x}^{\top}\mathring{A}\,\mathbf{x}$
$\displaystyle=\sum_{i,j=1}^{p}a_{ij}X_{i}X_{j}\mathrm{I}\Big{(}(i,j)\in\bigcup_{v\in\mathcal{V}}B_{2}^{2}(v)\Big{)}$
(10)
$\displaystyle=\sum_{s=1}^{d}(-1)^{s-1}\sum_{\nu_{s}}\sum_{i,j=1}^{p}a_{ij}X_{i}X_{j}\mathrm{I}((i,j)\in
B^{2}_{\nu_{s}})$ (11)
$\displaystyle=\sum_{s=1}^{d}(-1)^{s-1}\sum_{\nu_{s}}\mathbf{x}_{\nu_{s}}^{\top}A_{\nu_{s}}\mathbf{x}_{\nu_{s}},$
(12)

hereinafter $\mathbf{x}_{\nu_{s}}=(X_{i}:i\in B_{\nu_{s}})$ and
$A_{\nu_{s}}=(a_{ij}:i,j\in B_{\nu_{s}})$ if $B_{\nu_{s}}\not=\varnothing$ and
$\mathbf{x}_{\nu_{s}}=A_{\nu_{s}}=0$ otherwise. As $A_{\nu_{s}}$ is a
principal submatrix of $A$, we have that $\|A_{\nu_{s}}\|\leqslant\|A\|$ and

$|\mathbf{x}^{\top}\mathring{A}\,\mathbf{x}|\leqslant\|A\|\sum_{s=1}^{d}\sum_{\nu_{s}}\mathbf{x}_{\nu_{s}}^{\top}\mathbf{x}_{\nu_{s}}=\|A\|\sum_{s=1}^{d}\sum_{\nu_{s}}\sum_{i\in
B_{\nu_{s}}}X_{i}^{2}=\|A\|\sum_{s=1}^{d}\sum_{i=1}^{p}X_{i}^{2}\sum_{\nu_{s}}\mathrm{I}(i\in
B_{\nu_{s}})$

Since any $i\in V$ belongs to no more than $d$ sets $B_{2}(v)$ with
$v\in\mathcal{V}$ (see (9)), there are no more than ${d}\choose{s}$ sets of
the form $B_{\nu_{s}}=\bigcap_{v\in\nu_{s}}B_{2}(v)$ that cover $i$, i.e.

$\sum_{\nu_{s}}\mathrm{I}(i\in B_{\nu_{s}})\leqslant{{d}\choose{s}}.$ (13)

Therefore,

$|\mathbf{x}^{\top}\mathring{A}\,\mathbf{x}|\leqslant\|A\|\sum_{s=1}^{d}\sum_{i=1}^{p}X_{i}^{2}{{d}\choose{s}}\leqslant(2^{d}-1)\|A\|\mathbf{x}^{\top}\mathbf{x}$
(14)

In fact, the last inequalities hold for any nonrandom
$\mathbf{x}\in{\mathbb{R}}^{p},$ as follows from the proof. Hence,
$\|A-\mathring{A}\|\leqslant\|A\|+\|\mathring{A}\|\leqslant 2^{d}\|A\|$.
Putting $(b_{ij})_{i,j=1}^{p}:=A-\mathring{A}$, let us show that $b_{ij}=0$
when $d_{G}(i,j)\leqslant 2$. First, suppose $d_{G}(i,j)\leqslant 1$. We can
always find $v_{i}\in\mathcal{V}$ such that $d_{G}(v_{i},i)\leqslant 1$. This
shows that

$d_{G}(v_{i},j)\leqslant d_{G}(v_{i},i)+d_{G}(i,j)\leqslant 2,$

i.e. $j\in B_{2}(v_{i})$, and, by the definition of $\mathring{A}$,
$b_{ij}=0$. Suppose that $d_{G}(i,j)=2$. Then there is $k\in V$ such that
$d_{G}(i,k)=d_{G}(k,j)=1$. As we have just shown, the latter implies that
$i,j\in B_{2}(v_{k})$ and $b_{ij}=0$.

Applying the second bound of the Theorem yields

${\rm Var}(\mathbf{x}^{\top}(A-\mathring{A})\,\mathbf{x})\leqslant
2\|A-\mathring{A}\|^{2}{\mathrm{tr}}(\Sigma^{2})\leqslant
2^{2d+1}\|A\|^{2}{\mathrm{tr}}(\Sigma^{2}).$ (15)

Noticing that ${\mathbb{E}}X_{i}X_{j}=0$ when $d_{G}(i,j)>1$, we conclude that

${\mathrm{tr}}(\Sigma^{2})=\sum_{i=1}^{p}({\mathbb{E}}X_{i}^{2})^{2}+\sum_{\begin{subarray}{c}1\leqslant
i,j\leqslant p\\\
d_{G}(i,j)=1\end{subarray}}2({\mathbb{E}}X_{i}X_{j})^{2}\leqslant\sum_{i=1}^{p}({\mathbb{E}}X_{i}^{2})^{2}+$
$+\sum_{\begin{subarray}{c}1\leqslant i,j\leqslant p\\\
d_{G}(i,j)=1\end{subarray}}\big{(}({\mathbb{E}}X_{i}^{2})^{2}+({\mathbb{E}}X_{j}^{2})^{2}\big{)}=\sum_{i=1}^{p}({\mathbb{E}}X_{i}^{2})^{2}|B_{1}(i)|\leqslant(\Delta+1)\sum_{i=1}^{p}{\mathbb{E}}X_{i}^{4}.$
(16)

Also, by the Cauchy–Bunyakovsky–Schwarz inequality and (10),

${\rm Var}(\mathbf{x}^{\top}\mathring{A}\,\mathbf{x})\leqslant
d\sum_{s=1}^{d}{\rm
Var}\Big{(}\sum_{\nu_{s}}\mathbf{x}_{\nu_{s}}^{\top}A_{\nu_{s}}\mathbf{x}_{\nu_{s}}\Big{)}.$

For an arbitrary term in the last sum, we have

${\rm
Var}\Big{(}\sum_{\nu_{s}}\mathbf{x}_{\nu_{s}}^{\top}A_{\nu_{s}}\mathbf{x}_{\nu_{s}}\Big{)}=\sum_{\nu_{s},\kappa_{s}}\mathrm{Cov}(\mathbf{x}_{\nu_{s}}^{\top}A_{\nu_{s}}\mathbf{x}_{\nu_{s}},\mathbf{x}_{\kappa_{s}}^{\top}A_{\kappa_{s}}\mathbf{x}_{\kappa_{s}}),$

where the sum is taken over all $\nu_{s},\kappa_{s}\subseteq\mathcal{V}$ with
$|\nu_{s}|=|\kappa_{s}|=s$. Notice that since $A_{\nu_{s}}$ is a principal
submatrix of $A$, we have that $\|A_{\nu_{s}}\|\leqslant\|A\|$ and

$\displaystyle{\rm
Var}(\mathbf{x}_{\nu_{s}}^{\top}A_{\nu_{s}}\mathbf{x}_{\nu_{s}})\leqslant{\mathbb{E}}|\mathbf{x}_{\nu_{s}}^{\top}A_{\nu_{s}}\mathbf{x}_{\nu_{s}}|^{2}\leqslant\|A_{\nu_{s}}\|^{2}{\mathbb{E}}|\mathbf{x}_{\nu_{s}}^{\top}\mathbf{x}_{\nu_{s}}|^{2}\leqslant\|A\|^{2}|B_{\nu_{s}}|\sum_{i\in
B_{\nu_{s}}}{\mathbb{E}}X_{i}^{4}.$

This and the Cauchy–Bunyakovsky–Schwarz inequality imply that

$\mathrm{Cov}(\mathbf{x}_{\nu_{s}}^{\top}A_{\nu_{s}}\mathbf{x}_{\nu_{s}},\mathbf{x}_{\kappa_{s}}^{\top}A_{\kappa_{s}}\mathbf{x}_{\kappa_{s}})\leqslant\frac{1}{2}({\rm
Var}(\mathbf{x}_{\nu_{s}}^{\top}A_{\nu_{s}}\mathbf{x}_{\nu_{s}})+{\rm
Var}(\mathbf{x}_{\kappa_{s}}^{\top}A_{\kappa_{s}}\mathbf{x}_{\kappa_{s}}))\leqslant$
$\leqslant\frac{\|A\|^{2}}{2}\Big{(}|B_{\nu_{s}}|\sum_{i\in
B_{\nu_{s}}}{\mathbb{E}}X_{i}^{4}+|B_{\kappa_{s}}|\sum_{i\in
B_{\kappa_{s}}}{\mathbb{E}}X_{i}^{4}\Big{)}.$

Noting that $\mathbf{x}_{\nu_{s}}$ and $\mathbf{x}_{\kappa_{s}}$ are
independent when $B_{\nu_{s}},B_{\kappa_{s}}$ are non-adjacent and setting
$\mathrm{I}(\nu_{s},\kappa_{s}):=\mathrm{I}(\text{$B_{\nu_{s}},B_{\kappa_{s}}$
are adjacent and nonempty})$, we get that

${\rm
Var}\Big{(}\sum_{\nu_{s}}\mathbf{x}_{\nu_{s}}^{\top}A_{\nu_{s}}\mathbf{x}_{\nu_{s}}\Big{)}\leqslant\frac{\|A\|^{2}}{2}\sum_{\nu_{s},\kappa_{s}}\Big{(}|B_{\nu_{s}}|\sum_{i\in
B_{\nu_{s}}}{\mathbb{E}}X_{i}^{4}+|B_{\kappa_{s}}|\sum_{i\in
B_{\kappa_{s}}}{\mathbb{E}}X_{i}^{4}\Big{)}\mathrm{I}(\nu_{s},\kappa_{s})=$
$=\|A\|^{2}\sum_{\nu_{s},\kappa_{s}}|B_{\nu_{s}}|\mathrm{I}(\nu_{s},\kappa_{s})\sum_{i\in
B_{\nu_{s}}}{\mathbb{E}}X_{i}^{4}=\|A\|^{2}\sum_{\nu_{s}}|B_{\nu_{s}}|\sum_{i\in
B_{\nu_{s}}}{\mathbb{E}}X_{i}^{4}\sum_{\kappa_{s}}\mathrm{I}(\nu_{s},\kappa_{s}).$
(17)

Let us estimate the last sum (over $\kappa_{s}$), which is simply the number
of $B_{\kappa_{s}}$ such that $B_{\nu_{s}},B_{\kappa_{s}}$ are adjacent. Fix
$s\in[\\![1,d]\\!]$. By the definition of $\nu_{s}$ and $\kappa_{s}$, if
$B_{\nu_{s}},B_{\kappa_{s}}$ are adjacent, then there are $v\in\nu_{s},$
$u\in\kappa_{s}$, $k,l\in V$ such that $d_{G}(v,k)\leqslant 2$,
$d_{G}(u,l)\leqslant 2$, and $d_{G}(k,l)\leqslant 1$. Then, denoting as above
by $v_{i}\in\mathcal{V}$ any vertex adjacent to $i\in V$ and using the
triangle inequality, we see that $d_{G}(v,v_{k})\leqslant 3$,
$d_{G}(v_{k},v_{l})\leqslant 3$, and $d_{G}(v_{l},u)\leqslant 3$. By the
definition of $d=d(\mathcal{V})$, the number of such sequences
$(v,v_{k},v_{l},u,\kappa_{s})$ does not exceed $sd^{3}{{d}\choose{s}}$ when
$\nu_{s}$ is fixed. Indeed, replacing $v_{k},v_{l}$ by arbitrary
$w,r\in\mathcal{V}$, we may count such sequences as follows.

Given $\nu_{s},$ one can choose $v\in\nu_{s}$ in $s$ ways.

Given $v$, one can choose $w\in\mathcal{V}$ with $d_{G}(v,w)\leqslant 3$ in no
more than $d$ ways.

Given $w$, one can choose $r\in\mathcal{V}$ with $d_{G}(w,r)\leqslant 3$ in no
more than $d$ ways.

Given $r$, one can choose $u\in\mathcal{V}$ with $d_{G}(r,u)\leqslant 3$ in no
more than $d$ ways.

Given $u$, one can choose $\kappa_{s}\subseteq\mathcal{V}$ with
$|\kappa_{s}|=s$, $u\in B_{\nu_{s}}$, and $B_{\kappa_{s}}\not=\varnothing$ in
no more than ${d}\choose{s}$ ways. This follows from
$\sum_{\kappa_{s}}\mathrm{I}(u\in B_{\kappa_{s}})\leqslant{{d}\choose{s}}$
(see (13)).

This proves that

$\sum_{\nu_{s}}I(\nu_{s},\kappa_{s})\leqslant sd^{3}{{d}\choose{s}}\leqslant
d^{4}2^{d}$

and, by (13),

${\rm
Var}\Big{(}\sum_{\nu_{s}}\mathbf{x}_{\nu_{s}}^{\top}A_{\nu_{s}}\mathbf{x}_{\nu_{s}}\Big{)}\leqslant
d^{4}2^{d}\|A\|^{2}\sum_{\nu_{s}}|B_{\nu_{s}}|\sum_{i=1}^{p}{\mathbb{E}}X_{i}^{4}\mathrm{I}(i\in
B_{\nu_{s}})\leqslant$ $\leqslant
d^{4}2^{d}\|A\|^{2}m\sum_{i=1}^{p}{\mathbb{E}}X_{i}^{4}\sum_{\nu_{s}}\mathrm{I}(i\in
B_{\nu_{s}})\leqslant
d^{4}2^{d}\|A\|^{2}m{{d}\choose{s}}\sum_{i=1}^{p}{\mathbb{E}}X_{i}^{4},$

where $m=\max\\{|B_{2}(v)|:v\in\mathcal{V}\\}.$ Let us bound $m$ from above.
Fix $v\in\mathcal{V}$. If $i\in B_{2}(v)$, then $d_{G}(i,v)\leqslant 2$ and
$d_{G}(v_{i},v)\leqslant 3$, where as above, $v_{i}\in\mathcal{V}$ is such
that $d_{G}(i,v_{i})\leqslant 1$. The set $B_{1}(v_{i})$ contains no more than
$\Delta+1$ vertices and there are no more than $d$ different
$v_{i}\in\mathcal{V}$ with $d_{G}(v_{i},v)\leqslant 3$. Therefore,
$|B_{2}(v)|\leqslant d(\Delta+1)$.

Combining the above bounds yields

${\rm Var}(\mathbf{x}^{\top}\mathring{A}\,\mathbf{x})\leqslant
d^{7}2^{d}\|A\|^{2}(\Delta+1)\sum_{s=1}^{d}{{d}\choose{s}}\sum_{i=1}^{p}{\mathbb{E}}X_{i}^{4}\leqslant
d^{7}2^{2d}\|A\|^{2}(\Delta+1)\sum_{i=1}^{p}{\mathbb{E}}X_{i}^{4}.$

The latter, (8), and (16) prove the first inequality of the Theorem. ∎

###### Proof of Theorem 2.5..

The desired results will follow from Theorem 2.1 and 2.2 if we verify (A1) and
(A2) for $\Sigma_{p}={\mathbb{E}}\mathbf{x}_{p}\mathbf{x}_{p}^{\top}$. First,
note that (A2) follows from (16), $\Delta_{p}=o(p)$, and the fact that the
entries of $\mathbf{x}_{p}=(X_{ip})_{i=1}^{p}$ have uniformly bounded second
moments.

Let us verify (A1). Let $\mathcal{V}_{p}$ be a $d_{p}$-dominating set of
$G_{p}$ for any $p=p(n)$. We will use the notation and constructions from the
proof of Theorem 2.3. For $p=p(n)$, consider arbitrary symmetric
$A_{p}=(a_{ijp})_{i,j=1}^{p}\in{\mathbb{R}}^{p\times p}$ with
$\|A_{p}\|\leqslant 1$ and define
$\mathring{A}_{p}=(\mathring{a}_{ijp})_{i,j=1}^{p}$ as in (7), i.e.

$\mathring{a}_{ijp}=a_{ijp}$ if $i,j\in
B_{2p}(v):=\\{k\in[\\![1,p]\\!]:d_{G_{p}}(k,v)\leqslant 2\\}$ for some
$v\in\mathcal{V}_{p}$.

It is shown above (16) that the $(i,j)$th element of $A_{p}-\mathring{A}_{p}$
is zero when the distance between $i$ and $j$ in $G_{p}$ does not exceed 2.
This implies that

${\mathbb{E}}\mathbf{x}_{p}^{\top}(A_{p}-\mathring{A}_{p})\mathbf{x}_{p}=\sum_{i,j=1}^{p}\Big{(}a_{ijp}-\mathring{a}_{ijp}\Big{)}{\mathbb{E}}X_{ip}X_{jp}\mathrm{I}(d_{G_{p}}(i,j)>2)=0,$
${\mathbb{E}}\mathbf{x}_{p}^{\top}\mathring{A}_{p}\mathbf{x}_{p}={\mathbb{E}}\mathbf{x}_{p}^{\top}A_{p}\mathbf{x}_{p}={\mathbb{E}}\,{\mathrm{tr}}(\mathbf{x}_{p}\mathbf{x}_{p}^{\top}A_{p})={\mathrm{tr}}({\mathbb{E}}\mathbf{x}_{p}\mathbf{x}_{p}^{\top}A_{p})={\mathrm{tr}}(\Sigma_{p}A_{p}).$

Furthermore, as $d_{p}=O(1)$, (15) implies that

${\rm
Var}(\mathbf{x}_{p}^{\top}(A_{p}-\mathring{A}_{p})\mathbf{x}_{p})={\mathbb{E}}|\mathbf{x}_{p}^{\top}(A_{p}-\mathring{A}_{p})\mathbf{x}_{p}|^{2}\leqslant
O(1){\mathrm{tr}}(\Sigma_{p}^{2})$

and, as a result, by (A2),

$\frac{\mathbf{x}_{p}^{\top}(A_{p}-\mathring{A}_{p})\mathbf{x}_{p}}{p}\to 0.$

To finish the proof of (A1), we need to show that

$\frac{\mathbf{x}_{p}^{\top}\mathring{A}_{p}\mathbf{x}_{p}-{\mathbb{E}}\mathbf{x}_{p}^{\top}\mathring{A}_{p}\mathbf{x}_{p}}{p}\to
0.$

As in the proof of Theorem 2.4, we let further
$\nu_{s}=\nu_{s}(p)\subseteq\mathcal{V}_{p}$ with $|\nu_{s}|=s$ for
$s\in[\\![1,d_{p}]\\!]$ and set

$B_{\nu_{s}p}=\bigcap\limits_{v\in\nu_{s}}B_{2p}(v)$,
$\mathbf{x}_{\nu_{s}p}=(X_{ip}:i\in B_{\nu_{s}p})$, and
$A_{\nu_{s}p}=(a_{ijp}:i,j\in B_{\nu_{s}p})$,

we can write

$\mathbf{x}_{\nu_{s}p}^{\top}A_{\nu_{s}p}\mathbf{x}_{\nu_{s}p}=\mathbf{x}_{vp}^{\top}\bar{A}_{\nu_{s}p}\mathbf{x}_{vp},$

where $v=\min\\{u:u\in\nu_{s}\\},$ $\mathbf{x}_{vp}=\big{(}X_{ip}:i\in
B_{2p}(v)\big{)},$ and

$\bar{A}_{\nu_{s}p}=(a_{ijp}\mathrm{I}\big{(}i,j\in B_{\nu_{s}p})):i,j\in
B_{2p}(v)\big{)}.$

By such definitions, $\|\bar{A}_{\nu_{s}p}\|=0$ if $B_{\nu_{s}p}=\varnothing$
and $\|\bar{A}_{\nu_{s}p}\|=\|A_{\nu_{s}p}\|\leqslant\|A_{p}\|\leqslant 1$
otherwise. Therefore, by (10),

$\mathbf{x}_{p}^{\top}\mathring{A}_{p}\mathbf{x}_{p}=\sum_{s=1}^{d_{p}}(-1)^{s-1}\sum_{\nu_{s}}\mathbf{x}_{\nu_{s}p}^{\top}A_{\nu_{s}p}\mathbf{x}_{\nu_{s}p}=\sum_{v\in\mathcal{V}_{p}}\mathbf{x}_{vp}^{\top}D_{vp}\mathbf{x}_{vp},$

where

$D_{vp}=\sum_{s=1}^{d_{p}}(-1)^{s-1}\sum_{\nu_{s}}\bar{A}_{\nu_{s}p}\mathrm{I}(v=\min\\{u:u\in\nu_{s}\\},B_{\nu_{s}p}\not=\varnothing).$

By construction and (14),

$|\mathbf{x}_{vp}^{\top}D_{vp}\mathbf{x}_{vp}|=\Big{|}\sum_{s=1}^{d_{p}}(-1)^{s-1}\sum_{\nu_{s}}\mathbf{x}_{\nu_{s}p}^{\top}A_{\nu_{s}p}\mathbf{x}_{\nu_{s}p}\mathrm{I}(v=\min\\{u:u\in\nu_{s}\\},B_{\nu_{s}p}\not=\varnothing)\Big{|}\leqslant$
$\leqslant\sum_{s=1}^{d_{p}}\sum_{\nu_{s}}|\mathbf{x}_{\nu_{s}p}^{\top}A_{\nu_{s}p}\mathbf{x}_{\nu_{s}p}|\leqslant\sum_{s=1}^{d_{p}}\sum_{\nu_{s}}\mathbf{x}_{\nu_{s}p}^{\top}\mathbf{x}_{\nu_{s}p}\leqslant
2^{d_{p}}\mathbf{x}_{p}^{\top}\mathbf{x}_{p}.$

In fact, the last inequality holds for any nonrandom
$\mathbf{x}_{p}\in{\mathbb{R}}^{p}$ (see the proof of (14)). In particular,
this shows that $\|D_{vp}\|\leqslant 2^{d_{p}}$ for all $v\in\mathcal{V}_{p}.$

Consider a new graph $\Gamma_{p}$ with the vertex set $\mathcal{V}_{p}$ and
the edge set

$\\{\\{u,v\\}:B_{2p}(u),B_{2p}(v)\text{ are adjacent}\\}.$

The maximum degree of $\Gamma_{p}$ does not exceed $d_{p}^{3}$, as shown in
the proof of Theorem 2.4 after (17). Therefore, its vertices can be
partitioned into no more than $d_{p}^{3}+1$ sets $I_{kp}$ ($1\leqslant
k\leqslant d_{p}^{3}+1$) in a way that in each set, no two vertices are
adjacent (this follows from so-called greedy coloring of the graph
$\Gamma_{p}$). This means that for each $k,$ the vectors $\mathbf{x}_{vp}$ are
mutually independent over $v\in I_{kp}$. Note that
$|\mathbf{x}_{vp}^{\top}D_{vp}\mathbf{x}_{vp}|\leqslant\|D_{vp}\|\mathbf{x}_{vp}^{\top}\mathbf{x}_{vp}\leqslant
2^{d_{p}}\mathbf{x}_{vp}^{\top}\mathbf{x}_{vp}$ and

$\frac{1}{2^{d_{p}}p}\Big{|}\sum_{v\in
I_{kp}}\mathbf{x}_{vp}^{\top}D_{vp}\mathbf{x}_{vp}\Big{|}\leqslant\frac{1}{p}\sum_{v\in
I_{kp}}\mathbf{x}_{vp}^{\top}\mathbf{x}_{vp}\leqslant\frac{\mathbf{x}_{p}^{\top}\mathbf{x}_{p}}{p}\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}c.$

We need the following lemma.

######  Lemma 3.1.

Let $\\{X_{nk}:1\leqslant k\leqslant k_{n},n\in{\mathbb{N}}\\}$ be a row-wise
independent triangular array of random variables with finite means and such
that for each $\varepsilon>0,$

$\lim_{n\to\infty}\max_{1\leqslant k\leqslant
k_{n}}{\mathbb{P}}(|X_{nk}|>\varepsilon)=0.$ (18)

Suppose also $\\{T_{n}\\}_{n\geqslant 1}$ are nonnegative random variables
satisfying for all $n\in{\mathbb{N}},$ ${\mathbb{E}}T_{n}<\infty$ and
$|S_{n}|\leqslant T_{n}$ a.s., where $S_{n}=\sum_{k=1}^{k_{n}}X_{nk}$. If
there exists $c>0$ such that
$T_{n}\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}c$ and
${\mathbb{E}}T_{n}\to c$ as $n\to\infty$, then
$S_{n}-{\mathbb{E}}S_{n}\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}0.$

The proof of the Lemma can be found in the Appendix. By the assumptions of the
Theorem,

$\frac{\mathbf{x}_{p}^{\top}\mathbf{x}_{p}}{p}\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}c\quad\text{and}\quad\frac{{\mathbb{E}}\mathbf{x}_{p}^{\top}\mathbf{x}_{p}}{p}=\frac{{\mathrm{tr}}(\Sigma_{p})}{p}\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}c.$

Also,

${\mathbb{P}}(|\mathbf{x}_{vp}^{\top}D_{vp}\mathbf{x}_{vp}|>\varepsilon
2^{d_{p}}p)\leqslant\frac{{\mathbb{E}}|\mathbf{x}_{vp}^{\top}D_{vp}\mathbf{x}_{vp}|}{\varepsilon
2^{d_{p}}p}\leqslant$
$\leqslant\frac{{\mathbb{E}}\mathbf{x}_{vp}^{\top}\mathbf{x}_{vp}}{\varepsilon
p}\leqslant\frac{K|B_{2}(v)|}{\varepsilon
p}\leqslant\frac{d_{p}(\Delta_{p}+1)K}{\varepsilon p}\to 0$

uniformly in $v\in\mathcal{V}_{p}$ for any $\varepsilon\to 0$, where the bound
$|B_{2}(v)|\leqslant d_{p}(\Delta_{p}+1)$ was established at the end of the
proof of Theorem 2.4. Hence, applying Lemma 3.1 yields

$\frac{1}{2^{d_{p}}p}\sum_{v\in
I_{kp}}(\mathbf{x}_{vp}^{\top}D_{vp}\mathbf{x}_{vp}-{\mathbb{E}}\mathbf{x}_{vp}^{\top}D_{vp}\mathbf{x}_{vp})\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}0$

for all sequences $k=k(p)$ with values $1\leqslant k(p)\leqslant d_{p}^{3}+1$.
As $d_{p}=O(1)$, the latter implies that

$\frac{\mathbf{x}_{p}^{\top}\mathring{A}_{p}\mathbf{x}_{p}-{\mathbb{E}}\mathbf{x}_{p}^{\top}\mathring{A}_{p}\mathbf{x}_{p}}{p}=\frac{1}{p}\sum_{1\leqslant
k\leqslant d_{p}^{3}+1}\sum_{v\in
I_{kp}}(\mathbf{x}_{vp}^{\top}D_{vp}\mathbf{x}_{vp}-{\mathbb{E}}\mathbf{x}_{vp}^{\top}D_{vp}\mathbf{x}_{vp})\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}0.$

The proof of the Theorem is finished. ∎

## Appendix

###### Proof of Lemma 3.1.

We will prove the desired result by contradiction. Suppose
$S_{n}-{\mathbb{E}}S_{n}$ does not tend to zero in probability. Therefore, one
can find $\varepsilon,\delta>0$ and an infinite set
$\mathcal{N}\subseteq{\mathbb{N}}$ such that

${\mathbb{P}}(|S_{n}-{\mathbb{E}}S_{n}|>\varepsilon)\geqslant\delta$ for all
$n\in\mathcal{N}$. (19)

Taking $K>0$ large enough we can make ${\mathbb{P}}(|S_{n}|>K)$ arbitrarily
small, as

${\mathbb{P}}(|S_{n}|>K)\leqslant\frac{{\mathbb{E}}|S_{n}|}{K}\leqslant\frac{{\mathbb{E}}T_{n}}{K}\to\frac{c}{K}.$

With this, one can easily deduce that $\\{\mu_{n}\\}_{n\in\mathcal{N}}$ is a
tight collection of probability measures, where $\mu_{n}$ is the distribution
of $S_{n}$. By Prokhorov’s theorem, there exists an increasing sequence
$(n_{l})_{l=1}^{\infty}$ with $n_{l}\in\mathcal{N}$ and a random variable
$\sigma$ such that $S_{n_{l}}$ converges in distribution to $\sigma$. In view
of (18), the Khintchin theorem implies that $\sigma$ has an infinitely
divisible distribution (see Theorem 3.1 in [24]). As $|S_{n}|\leqslant
T_{n}\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}c$, $\sigma$ should be
bounded a.s. This is possible only if $\sigma$ is constant a.s. (see Corollary
3 in [3]). Therefore, $S_{n_{l}}$ also converges to $\sigma$ in probability.

Suppose for a moment that the collection $\\{T_{n}\\}_{n=1}^{\infty}$ is
uniformly integrable. Then the collection $\\{S_{n}\\}_{n=1}^{\infty}$ is
uniformly integrable and, by the Lebesgue-Vitali theorem (Theorem 4.5.4 in
[5]), ${\mathbb{E}}|S_{n_{l}}-\sigma|\to 0$ and, in particular,
${\mathbb{E}}S_{n_{l}}-\sigma\to 0$ as $l\to\infty.$ The latter would
contradict to the assumption (19). This would prove that (19) could not hold
and
$S_{n}-{\mathbb{E}}S_{n}\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}0$.

To finish the proof, we need to prove the uniform integrability of $T_{n}$.
This follows from $0\leqslant T_{n}\to c$ and ${\mathbb{E}}T_{n}\to c.$
Indeed, by the Lebesgue dominated convergence theorem,
${\mathbb{E}}T_{n}\mathrm{I}(T_{n}\leqslant 2c)\to c\mathrm{I}(c\leqslant
2c)=c$. Hence,

$\lim_{n\to\infty}\sup_{k\geqslant n}{\mathbb{E}}T_{k}\mathrm{I}(T_{k}>2c)=0.$

By the absolute continuity of the Lebesgue integral, we can find
$(C_{n})_{n=1}^{\infty}$ such that $2c\leqslant C_{n}\to\infty$ and

$\sup_{1\leqslant k\leqslant n}{\mathbb{E}}T_{k}\mathrm{I}(T_{k}>C_{n})\to 0.$

As a result, we see that ${\mathbb{E}}T_{k}\mathrm{I}(T_{k}>C_{n})\to 0$ as
$n\to\infty$ uniformly in $k$. This means that the sequence
$(T_{n})_{n=1}^{\infty}$ is uniformly integrable. The proof of the Lemma is
finished. ∎

## References

  * [1] Adamczak, R.: On the Marchenko-Pastur and circular laws for some classes of random matrices with dependent entries. Electronic Journal of Probability, 16, (2011), 1065–1095.
  * [2] Bai, Z., and Zhou, W.: Large sample covariance matrices without independence structures in columns. Stat. Sinica, 18, (2008), 425-–442.
  * [3] Bai, Z., and Silverstein, J.: Spectral analysis of large dimensional random matrices. Second edition. New York: Springer, 2010.
  * [4] Banna, M., Merlevéde, F., and Peligrad, M.: On the limiting spectral distribution for a large class of symmetric random matrices with correlated entries. Stoch. Proc. Appl., 125, (2015), 2700–2726.
  * [5] Bogachev, V.I.: Measure Theory. Volume I, Springer, (2007).
  * [6] Bun, J., Bouchaud, J.-P., and Potters, M.: Cleaning large correlation matrices: Tools from Random Matrix Theory, Physics Reports, 666, (2017), 1-109.
  * [7] Bryson, J., Vershynin, R., and Zhao, H.: Marchenko–Pastur law with relaxed independence conditions. Random Matrices: Theory and Applications, (2021), DOI: 10.1142/S2010326321500404.
  * [8] Girko, V., and Gupta, A.K.: Asymptotic behavior of spectral function of empirical covariance matrices. Random Oper. and Stoch. Eqs., 2(1), (1994), 44–60.
  * [9] Dobriban E., and Wager, S.: High-dimensional asymptotics of prediction: Ridge regression and classification. Annals of Statistics, 46(1), (2018), 247–279.
  * [10] Götze, F., Naumov, A.A., and Tikhomirov, A.N.: Limit theorems for two classes of random matrices with dependent entries, Teor. Veroyatnost. i Primenen., 59(1), (2014), 61–-80. [In Russian]
  * [11] Hall, P.: On the $L_{p}$ convergence of sums of independent random variables, Math. Proc. Cambridge Philos. Soc., 82, (1977), 439–446.
  * [12] Hui, J., and Pan, G.M.: Limiting spectral distribution for large sample covariance matrices with $m$-dependent elements. Commun. Stat.– Theory Methods, 39, (2010), 935–941.
  * [13] Janson, S.: Large deviations for sums of partly dependent random variables. Random Structures $\&$ Algorithms, 24(3), (2004), 234–248.
  * [14] El Karoui, N.: Random matrices and high-dimensional statistics: beyond covariance matrices. Proc. Int. Cong. Math. – 2018, Rio de Janeiro, 4, (2018), 2875–2894.
  * [15] El Karoui, N.: Concentration of measure and spectra of random matrices: applications to correlation matrices, elliptical distributions and beyond, Ann. Appl. Probab., 19(6), (2009), 2362–2405.
  * [16] Lytova, A.: Central limit theorem for linear eigenvalue statistics for a tensor product version of sample covariance matrices, J. Theor. Probab., 31, (2018), 1024–1057.
  * [17] Magnus, J.R. The Moments of products of quadratic forms in normal variables, Statistica Neerlandica, 32, (1978), 201–210.
  * [18] Marcenko, V.A., and Pastur, L.A.: Distribution of eigenvalues in certain sets of random matrices, Mat. Sb. (N.S.), 72, (1967), 507–536.
  * [19] Merlevede, F., and Peligrad, M.: On the empirical spectral distribution for matrices with long memory and independent rows. Stochastic Processes and their Applications, 126 (9), (2016), 2734–2760.
  * [20] Merlevede, F., Peligrad, C., and Peligrad, M.: On the universality of spectral limit for random matrices with martingale differences entries. Random Matrices: Theory Appl., 04, 1550003 (2015), 33p.
  * [21] O’Rourke, S.: A note on the Marchenko-Pastur law for a class of random matrices with dependent entries. Elect. Comm. Probab., 17, (2012), Article no. 28, 1–13.
  * [22] Pajor, A., and Pastur L.: On the limiting empirical measure of eigenvalues of the sum of rank one matrices with log-concave distribution. Studia Math., 195, (2009), 11–29.
  * [23] Pastur, L., and Shcherbina, M.: Eigenvalue distribution of large random matrices. Mathematical Surveys and Monographs, 171. American Mathematical Society, Providence, RI, 2011.
  * [24] Petrov, V.V.: Limit theorems of probability theory. Clarendon Press – Oxford, (1995).
  * [25] Wei, M., Yang, G., and Ying, L.: The limiting spectral distribution for large sample covariance matrices with unbounded m-dependent entries. Commun. Stat. Theory Methods, 45, (2016), 6651–6662.
  * [26] Yao, J.: A note on a Marćenko-Pastur type theorem for time series. Statist. Probab. Lett., 82, (2012), 22–28.
  * [27] Yaskov, P.: The universality principle for spectral distributions of sample covariance matrices, (2015), arXiv:1410.5190.
  * [28] Yaskov, P.: Variance inequalities for quadratic forms with applications, Math. Methods Statist., 24:4, (2015), 309–319.
  * [29] Yaskov, P.: Necessary and sufficient conditions for the Marchenko-Pastur theorem. Electronic Communications in Probability, 21, Article no. 73, (2016), 1–8.
  * [30] Yaskov, P.: LLN for quadratic forms of long memory time series and its applications in random matrix theory. Journal of Theoretical Probability, 31(4), (2018), 2032–2055.
  * [31] Zhang, R., Liu, X., Wang, Y., and Wang, L.: McDiarmid-type inequalities for graph-dependent variables and stability bounds, Advances in Neural Information Processing Systems 32 (NeurIPS 2019), (2019), arXiv:1909.02330.