from Equation 4.4 and to illustrate the model’s applicability.

A more extensive application concerning sample frequency matrices of block
Markov chains is considered in Section 7.3. There, we establish new
improvements upon previous results from the literature. We note that we are
not aware of any other method in the literature which could be used to
establish the sharp concentration result in Theorem 7.5.

###  7.1 Random graphs with dependent edges

In this application, we study the adjacency matrix of an Erdős–Rényi graph
from the $\cG(d,m)$ model. The $\cG(d,m)$ model here refers to the uniform
distribution over all simple graphs with $d$ nodes and $m$ edges.

Let $G=(V,E)$ denote a $\cG(d,m)$-distributed random graph. We will be
concerned with the asymptotic regime where $m=m_{d}$ depends on $d$ and
$d\to\infty$. Let us pick some bijection
$e:\\{1,\ldots,\binom{d}{m}\\}\to\\{(i,j):1\leq i\leq j\leq d\\}$ and denote
$Y_{t}\vcentcolon=\mathbbm{1}\\{e(t)\in E\\}$ for every $1\leq
t\leq\binom{d}{m}$. The main input required for our results is a bound on the
classical cumulants of the collection of random variables $Y_{t}$.
Conveniently, such a bound is already available in the literature:

######  Proposition 7.1 (Féray, [16, Proposition 7.1]).

Assume that $\lim_{d\to\infty}m_{d}=\infty$. Then, for any $k\geq 3$ there
exists a constant $C_{k}>0$ such that for any $d\geq 1$ and
$t_{1},\ldots,t_{k}\in\\{1,\ldots,\binom{d}{2}\\}$

$\displaystyle\lvert\kappa(Y_{t_{1}},\ldots,Y_{t_{k}})\rvert\leq
C_{k}m^{1-\ell}p^{k}$ (7.1)

where $\ell\vcentcolon=\\#\\{t_{1},\ldots,t_{k}\\}$ is the number of distinct
indices and $p\vcentcolon=m/\binom{d}{2}$.

Similarly to eq. 7.9, we define that the _eigenvalue distribution_ of a self-
adjoint matrix $\bM$ is the measure $\mu_{\bM}$ given by

$\displaystyle\mu_{\bM}([a,b])\vcentcolon=\frac{1}{d}\\#\bigl{\\{}i\in\\{1,\ldots,d\\}:a\leq\lambda_{i}(\bM)\leq
b\bigr{\\}}.$ (7.2)

Recall that a sequence of random probability measures $\mu_{n}$ is said to
converge weakly in probability to a deterministic probability measure $\mu$ if
$\int f(x){\rm d}\mu_{n}(x)$ converges in probability to $\int f(x){\rm
d}\mu(x)$ for every continuous bounded function $f:\bbR\to\bbR$. The
_semicircular law_ is the measure, supported on $[-2,2]$, which is given by
${\rm
d}\mu_{\operatorname{sc}}(x)=\frac{1}{2\pi}\mathbbm{1}\\{x\in[-2,2]\\}\sqrt{2-x^{2}}{\rm
d}x$. We denote $\cA$ for the adjacency matrix of a $\cG(d,m)$-distributed
random graph.

Proposition 7.2 establishes convergence of the empirical eigenvalue
distribution to $\mu_{\operatorname{sc}}$. This result could probably also be
established by simpler means. The advantage of our approach is however that it
can be extended to yield sharp concentration inequalities for the extremal
eigenvalues; recall Remark 3.5. Such concentration inequalities would namely
follow if one quantifies the dependence of $C_{k}$ on $k$ in Proposition 7.1.
It should further be possible to study more complicated random graph models.
For instance, cumulant bounds for the configuration model have been
established in [24]. Sharp estimates on the leading eigenvalue of the
configuration model are relevant in the study of ensemble equivalence. It has
namely been found in [12, Theorem 1.2] that the greatest eigenvalue
distinguishes the configuration model from a _canonical ensemble_ where
degrees are only constrained in an averaged sense.

######  Proposition 7.2.

Assume that $\lim_{d\to\infty}d/\min\\{m_{d},\binom{d}{2}-m_{d}\\}=0$. Then,
$\mu_{\cA/\sqrt{p(1-p)d}}$ converges weakly in probability to
$\mu_{\operatorname{sc}}$.

The details for the proof of this result are given in Appendix F. The main
idea is that Proposition 7.1 implies that there exists some absolute constant
$C_{k}^{\prime}>0$ such that
$D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{k}(Y)\leq C_{k}^{\prime}$ with
$\eta=p$ and $\gamma=0$. Then, Theorems 4.2 and 4.3 yield universality for the
tracial moments. The fact that we take $\eta=p$ is important in the estimates:
if one takes $\eta=1$ then only a suboptimal estimate on the moments is
recovered and this is insufficient for universality of the empirical
eigenvalue distribution.

###  7.2 Independent heavy-tailed entries

To clarify the meaning of the parameter $\gamma$ in the matrix series model we
here consider coefficients whose tails are heavier than exponential.
Concretely, let us call a real-valued random variable $Y$ _sub-Weibull with
tail parameter $\theta\geq 1$_ if there exists some constant $L>0$ such that

$\displaystyle\bbP\bigl{(}\lvert Y\rvert>x\bigr{)}\leq
2\exp\Bigl{(}-\Bigl{(}\frac{x}{L}\Bigr{)}^{\frac{1}{\theta}}\Bigr{)}$ (7.3)

for all $x\geq 0$.

A $d\times d$ self-adjoint random matrix $\bW$ is said to be a _Wigner matrix_
if the upper triangle $(\bW_{i,j})_{i\leq j}$ consists of independent and
identically distributed random variables with mean zero and variance one. When
$\bbE[\lvert\bW_{1,1}\rvert^{4}]<\infty$ it follows from the Bai–Yin theorem
[6] that $d^{-\frac{1}{2}}\|\bW\|$ converges almost surely to $2$ as $d$ tends
to infinity. Provided the stronger assumption that the entries are sub-
Weibull, we achieve a nonasymptotic concentration inequality whose leading-
order term matches the limiting value $2$ from the Bai–Yin theorem.

######  Proposition 7.3.

Assume that $\bW$ is a Wigner matrix for which $\bW_{1,1}$ is sub-Weibull with
parameters $\theta\geq 1$ and $L>0$. Then, for every $0<\delta\leq 1$ and
$x>1$

$\displaystyle\bbP\bigl{(}d^{-\frac{1}{2}}\|\bW\|\geq
2+\cE^{{\text{{$($}{}$\theta${$)$}}}}_{\delta}(x)\bigr{)}\leq(d+1)(1+\delta)^{-x}$

where

$\displaystyle\cE^{{\text{{$($}{}$\theta${$)$}}}}_{\delta}(x)\vcentcolon=2\delta+c^{\prime}\Bigl{(}d^{-\frac{1}{4}}x^{\frac{3}{4}}+d^{-\frac{1}{6}}x^{\theta-\frac{1}{3}}+d^{-\frac{1}{2}}x^{\theta}\Bigr{)}$

for some constant $c^{\prime}>0$ depending only on $\theta$ and $L$.

The proof of this result is given in Appendix E and relies on Theorem 4.1. The
main input required for the proof is an estimate on the cumulants of sub-
Weibull random variables. Fortunately, such an estimate is available: due to
[1, 49], a sub-Weibull random variable $Y$ with tail parameter $\theta$ admits
a constant $\Delta>0$ such that the $k$-th order cumulant satisfies
$\kappa(Y,Y,\ldots,Y)\leq\Delta^{k-2}(k!)^{\theta}$ for all $k\geq 3$. This
yields a bound on the cumulant-based parameter in eq. 4.4 provided that
$\gamma=\theta-1$.

###  7.3 Block Markov chains

Let $d\geq K\geq 1$ be positive integers, consider a partition
$(\cV_{i})_{i=1}^{K}$ of $\\{1,\ldots,d\\}$ into nonempty subsets, and let
$\mathbf{p}\in[0,1]^{K\times K}$ be the transition matrix of an ergodic Markov
chain on $\\{1,\ldots,K\\}$. Then, the _block Markov chain_ with cluster
transition matrix $\mathbf{p}$ and clusters $(\cV_{i})_{i=1}^{K}$ is the
Markov chain $(Z_{t})_{t=1}^{n}$ on $\\{1,\ldots,d\\}$ with transition
probabilities given by

$\displaystyle\bbP(Z_{t}=j\mid Z_{t-1}=i)=\frac{\mathbf{p}_{k,m}}{\\#\cV_{m}}\
\text{ for all }\ i\in\cV_{k}\ \text{ and }\ j\in\cV_{m}.$ (7.4)

A schematic depiction of a block Markov chain, and a sample path thereof, may
be found in Figure 4. For the sake of simplicity, we assume in all results of
this section that $(Z_{t})_{t=1}^{n}$ starts from equilibrium. This is to say
that $\bbP(Z_{1}=i)=\pi_{k}/\\#\cV_{k}$ for all $i\in\cV_{k}$ and all
$k\in\\{1,\ldots,K\\}$ where $\pi\in[0,1]^{K}$ is the equilibrium distribution
of the Markov chain on $\\{1,\ldots,K\\}$ associated with $\mathbf{p}$.

Figure 4: Visualization of a block Markov chain on $K=4$ clusters with cluster
transition matrix
$\mathbf{p}=\allowbreak[[0.3,0.7,0,0],\allowbreak[0,0,0.2,0.8],[0.2,0.7,0,0.1],[0,0,0.7,0.3]]$
where we number the clusters from left to right. The thick arrows here
visualize the transition probabilities $\mathbf{p}_{i,j}$ whereas the thin
arrows visualize the transitions $(Z_{t},Z_{t+1})$ in the observed sample path
$(Z_{t})_{t=1}^{n}$.

The _sample frequency matrix_ associated with the sample path
$(Z_{t})_{t=1}^{n}$ is defined by

$\displaystyle\hat{\bN}\vcentcolon=(\hat{\bN}_{i,j})_{i,j=1}^{d}\ \text{ where
}\
\hat{\bN}_{i,j}\vcentcolon=\sum_{t=1}^{n-1}\mathbbm{1}\\{Z_{t}=i,Z_{t+1}=j\\}.$
(7.5)

The concentration of $\|\hat{\bN}-\bbE[\hat{\bN}]\|$ is essential in the
analysis of clustering algorithms which recover the clusters $\cV_{i}$ based
on the sample path $(Z_{t})_{t=1}^{n}$ [38, 39, 50, 25].

####  7.3.1 Concentration and sharp limiting value

Let us denote $\bM\vcentcolon=\sqrt{d/n}(\hat{\bN}-\bbE[\hat{\bN}])$. The goal
of this section is to estimate $\|\bM\|$. Since the matrix $\bM$ is not self-
adjoint with high probability, we need to consider a preliminary reduction
before applying our results. We namely define a $2d\times 2d$ matrix, called
the _self-adjoint dilation_ of $\bM$, by

$\displaystyle\bS\vcentcolon=\begin{pmatrix}0&\bM\\\ \bM^{{\rm
T}}&0\end{pmatrix}.$ (7.6)

Note that $\|\bS\|=\|\bM\|$. One can represent $\bS$ in terms of a Markovian
model associated with the Markov chain of transitions
$E\vcentcolon=(E_{t})_{t=1}^{n-1}$ defined by
$E_{t}\vcentcolon=(Z_{t},Z_{t+1})$. Namely, note that with $e_{i}\in\bbR^{d}$
the $i$th standard basis vector we can write $\bS=\sum_{t=1}^{n-1}\bX_{t}$
with

$\displaystyle\bX_{t}\vcentcolon=\sqrt{\frac{d}{n}}\sum_{i,j=1}^{d}\bigl{(}\mathbbm{1}(E_{t}=(i,j))-\bbP(E_{t}=(i,j))\bigr{)}\begin{pmatrix}0&e_{i}e_{j}^{\rm
T}\\\ e_{j}e_{i}^{\rm T}&0\end{pmatrix}.$ (7.7)

Let us write $\hat{\alpha}_{i}\vcentcolon=\\#\cV_{i}/d$. The following lemma
provides an indication of the typical size of the matrix parameters.

######  Lemma 7.4.

There exist constants $c_{1},\ldots,c_{5}>0$ depending only on $\mathbf{p}$
and $\hat{\alpha}_{1},\ldots,\hat{\alpha}_{K}$ such that

$\displaystyle R(\bX)\leq c_{1}\sqrt{d/n},\qquad\Psi(E)\leq$ $\displaystyle
c_{2},\qquad\varsigma(\bX)^{2}\leq c_{3},$ $\displaystyle\sigma(\bS)^{2}\leq
c_{4},\qquad$ $\displaystyle\qquad v(\bS)^{2}\leq c_{5}d^{-1}.$

###### Proof.

This is immediate from Lemma D.4 which provides precise estimates on the
constants $c_{1},\ldots,c_{5}$. ∎

Using Lemma 7.4 together with Theorem 3.1 it follows that $\|\bS\|$ is not
much greater than $\|\bS_{\operatorname{free}}\|$. In the asymptotic regime
where $d\to\infty$, this allows us to refine one of the main results in [39].
We let $n$ and the clusters $(\cV_{k})_{k=1}^{K}$ depend on $d$ but assume
that the cluster transition matrix $\mathbf{p}$ is kept fixed. Further, assume
that there exist strictly positive rational numbers
$\alpha_{1},\ldots,\alpha_{k}>0$ such that
$\lim_{d\to\infty}\\#\cV_{k}/d=\alpha_{k}$ for every $k$. Then, in the regime
where $n\gg d\ln(d)^{4}$, the following theorem improves upon [39, Theorem 3]
in the fact that we can determine the exact limiting value whereas [39] only
proves a nonexplicit upper bound. Let us note however that [39] has a weaker
assumption: it is there assumed that $n\gg d\ln(d)$.

######  Theorem 7.5.

Assume that $\lim_{d\to\infty}d\ln(d)^{4}/n=0$. Then, the random variable
$\|\bM\|$ converges in probability to the scalar $\mathfrak{m}>0$ defined by

$\displaystyle\mathfrak{m}$
$\displaystyle\vcentcolon=\mathop{\mathrm{inf}\vphantom{\mathrm{sup}}}_{x\in\bbR_{>0}^{2K}}\max_{i=1,\ldots,2K}\Bigl{\\{}\frac{1}{x_{i}}+\sum_{j=1}^{2K}c_{i,j}x_{j}\Bigr{\\}}$
(7.8)

where the infimum runs over all vectors $x$ with strictly positive coordinates
and the coefficients $(c_{i,j})_{i,j=1}^{2K}$ are defined by

$\displaystyle c_{i,j}\vcentcolon=\begin{cases}0&\text{ if }i\leq K\text{ and
}j\leq K,\\\ \alpha_{i}^{-1}\pi_{i}\mathbf{p}_{i,j-K}&\text{ if }i\leq K\text{
and }j>K,\\\ 0&\text{ if }i>K\text{ and }j>K,\\\
\alpha_{i-K}^{-1}\pi_{j}\mathbf{p}_{j,i-K}&\text{ if }i>K\text{ and }j\leq
K.\end{cases}$

The proof of this result is given in Section D.3 and relies on Theorem 3.1. A
nonasymptotic concentration inequality with leading-order term given by eq.
7.8 can also be achieved; see Theorem D.14.

Recall that Theorem 3.1 only provides an upper bound on $\|\bS\|$.
Correspondingly, it should be surprising that Theorem 7.5 is a two-sided
result: we get the exact limiting value and not just an upper bound. The proof
of this two-sidedness relies on the fact that the free-probabilistic leading-
order term in Theorem 3.1 can be proved to be asymptotically sharp in the
current setting. In fact, it follows from the next result that there is an
abundance of singular values which are close to the upper bound in Theorem
3.1; see Proposition 7.6 and recall Figure 1 from the introduction.

####  7.3.2 Limiting singular value distribution

We start by introducing some terminology. The $i$th largest singular value of
a square matrix $\bM\in\bbC^{d\times d}$ can be defined in terms of the $i$th
largest eigenvalue of $\bM\bM^{*}$ as
$s_{i}(\bM)\vcentcolon=(\lambda_{i}(\bM\bM^{*}))^{1/2}$. The _singular value
distribution_ of $\bM$ is then the probability measure $\nu_{\bM}$ defined by

$\displaystyle\nu_{\bM}([a,b])\vcentcolon=\frac{1}{d}\\#\bigl{\\{}i\in\\{1,\ldots,d\\}:a\leq
s_{i}(\bM)\leq b\bigr{\\}}.$ (7.9)

A sequence of random probability measures $\nu_{n}$ is said to converge
_weakly in probability_ to a deterministic probability measure $\nu$ if $\int
f(x){\rm d}\nu_{n}(x)$ converges in probability to $\int f(x){\rm d}\nu(x)$
for every continuous bounded function $f:\bbR\to\bbR$.

The _Stieltjes transform_ of a probability measure $\nu$ on $\bbR$ is the
analytic function $s:\bbC^{+}\to\bbC^{-}$ given by $s(z)\vcentcolon=\int
1/(z-x){\rm d}\nu(x)$ where
$\bbC^{+}\vcentcolon=\\{z\in\bbC:\operatorname{Im}(z)>0\\}$ is the upper half-
plane and $\bbC^{-}\vcentcolon=\\{z\in\bbC:\operatorname{Im}(z)<0\\}$ is the
lower half-plane. The measure can be recovered from its Stieltjes transform
due to the Stieltjes inversion formula [5, Theorem B.8] which states that for
any continuity points $a<b$ of $\nu$,

$\displaystyle\nu([a,b])=-\frac{1}{\pi}\lim_{\varepsilon\to
0^{+}}\int_{a}^{b}\operatorname{Im}\bigl{(}s(x+\sqrt{-1}\varepsilon)\bigr{)}.$
(7.10)

Let us warn that [5] employs a definition for the Stieltjes transform which
differs from the one used here by a minus sign. Finally, the _symmetrization_
of a measure $\nu$ on $\bbR_{\geq 0}$ is the measure $\operatorname{sym}(\nu)$
on $\bbR$ given by $A\mapsto(\nu(A\cap\bbR_{\geq 0})+\nu((-A)\cap\bbR_{\geq
0})/2$ where $A$ ranges over all measurable subsets of $\bbR$ and
$-A\vcentcolon=\\{-a:a\in A\\}$.

The following results improve upon [40, Theorem 1.1]. In [40] it was namely
assumed that $n\approx cd^{2}$ for some constant $c>0$ whereas the following
result only requires that $n\gg d$. This relaxed assumption allows one to also
deal with short sample paths which give rise to a sparser sample frequency
matrix. The assumption that $n\gg d$ is optimal. When $K=1$ and $n\approx cd$
for some $c>0$ one can namely find some $u>0$ such that the number of nodes in
$\cV$ which are not visited by $Z_{t}$ is at least $ud$ with high probability.
Then, $\bM$ has at least $ud$ rows equal to zero which implies that
$\nu_{\bM}(0)\geq u$. On the other hand, when $K=1$, the distribution
$\operatorname{sym}(\nu_{\infty})$ in Proposition 7.6 is the semicircular law
and hence continuous. Considering $\int f(x){\rm d}\nu_{\bM}(x)$ with
$f:\bbR\to\bbR$ supported in a small neighborhood of $0$ then shows that
$\nu_{\bM}$ does not converge weakly in probability to $\nu_{\infty}$.

######  Proposition 7.6.

Assume that $\lim_{d\to\infty}d/n=0$. Then, $\nu_{\bM}$ converges weakly in
probability to a compactly supported probability measure $\nu_{\infty}$ on
$\bbR_{\geq 0}$. Moreover, $\operatorname{sym}(\nu_{\infty})$ has Stieltjes
transform $s(z)=\sum_{i=1}^{K}\alpha_{i}(a_{i}(z)\allowbreak+a_{K+i}(z))/2$
where $a_{1},\ldots,a_{2K}$ are the unique analytic functions from
$\mathbb{C}^{+}$ to $\mathbb{C}^{-}$ such that the following system of
equations is satisfied

$\displaystyle a_{i}(z)^{-1}$
$\displaystyle=z-\sum_{j=1}^{K}\alpha_{i}^{-1}\pi_{i}\mathbf{p}_{i,j}a_{K+j}(z)$
$\displaystyle a_{i+K}(z)^{-1}$
$\displaystyle=z-\sum_{j=1}^{K}\alpha_{i}^{-1}\pi_{j}\mathbf{p}_{j,i}a_{j}(z)$

for $i=1,\ldots,K$.

######  Corollary 7.7.

Assume that $\lim_{d\to\infty}d/n=0$ and let $\nu_{\infty}$ be as in
Proposition 7.6. Then, $\nu_{\sqrt{d/n}\hat{\bN}}$ converges weakly in
probability to $\nu_{\infty}$.

The proof for these results is provided in Section D.2 and relies on the
moment universality from Theorems 3.2 and 3.3. It is interesting to note that
our approach gives rise to a simpler proof than in [40]. The main difficulty
in [40] is namely that one has to show that all joint moments of the entries
of $\bM$ behave approximately as in the independent case. For the second
moments, i.e., covariance, this is not too difficult and can be done with an
elegant proof [40, Proposition 4.8]. The estimation of higher-order joint
moments is significantly more technical; see [40, Section 6.3.4]. Our
univerality-based approach allows us to bypass this technical step: we reduce
to the Gaussian case and exploit that the higher moments of a Gaussian are
determined by its covariance.

####  7.3.3 Visualization of results

Recall that Figure 1 from the introduction visualizes Proposition 7.6 and
Theorem 7.5. The bars in this figure correspond to the empirical singular
value distribution $\nu_{\bM}=\nu_{\sqrt{d/n}(\hat{\bN}-\bbE[\hat{\bN}])}$
where $\hat{\bN}$ is sampled from a block Markov chain with $K=4$,
$\mathbf{p}=\allowbreak[[0.3,0.7,0,0],\allowbreak[0,0,0.2,0.8],[0.2,0.7,0,0.1],[0,0,0.7,0.3]]$,
$(\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4})=(0.2,0.1,0.4,0.3)$, $d=10000$,
and $n=100d$. The system of equations in Proposition 7.6 was solved using the
algorithm of [21] as implemented in BMCToolkit [48].

## Acknowledgments

This work is part of the project Clustering and Spectral Concentration in
Markov Chains with project number OCENW.KLEIN.324 of the research programme
Open Competition Domain Science – M which is partly financed by the Dutch
Research Council (NWO).

We thank Ramon van Handel for discussions at the 50th Probability Summer
School of Saint–Flour which led to a simplified proof for Lemma 5.4.

## References

  * [1] [author] Amosova, N. N.N. N. (2002). Necessity of the Cramer, Linnik, and Statulevičius Conditions for Large-Deviation Probabilities. Journal of Mathematical Sciences.
  * [2] [author] Anderson, G. W.G. W., Guionnet, A.A. and Zeitouni, O.O. (2010). An introduction to random matrices. Cambridge University Press.
  * [3] [author] Arizmendi, O.O., Hasebe, T.T., Lehner, F.F. and Vargas, C.C. (2015). Relations between cumulants in noncommutative probability. Advances in Mathematics.
  * [4] [author] Bacry, E.E., Gaïffas, S.S. and Muzy, J. F.J. F. (2018). Concentration inequalities for matrix martingales in continuous time. Probability Theory and Related Fields.
  * [5] [author] Bai, Z.Z. and Silverstein, J. W.J. W. (2010). Spectral analysis of large dimensional random matrices. Springer.
  * [6] [author] Bai, Z. D.Z. D. and Yin, Y. Q.Y. Q. (1988). Necessary and sufficient conditions for almost sure convergence of the largest eigenvalue of a Wigner matrix. The Annals of Probability.
  * [7] [author] Bandeira, A. S.A. S., Boedihardjo, M. T.M. T. and van Handel, R.R. (2023). Matrix concentration inequalities and free probability. Inventiones Mathematicae.
  * [8] [author] Banna, M.M., Merlevède, F.F. and Youssef, P.P. (2016). Bernstein-type inequality for a class of dependent random matrices. Random Matrices: Theory and Applications.
  * [9] [author] Billingsley, P.P. (2008). Probability and measure, Third ed. John Wiley & Sons.
  * [10] [author] Blum, J. R.J. R., Hanson, D. L.D. L. and Koopmans, L. H.L. H. (1963). On the Strong Law of Large numbers for a Class of Stochastic Processes. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete.
  * [11] [author] Brailovskaya, T.T. and van Handel, R.R. (2022). Universality and sharp matrix concentration inequalities. arXiv:2201.05142.
  * [12] [author] Dionigi, P.P., Garlaschelli, D.D., den Hollander, F.F. and Mandjes, M.M. (2021). A spectral signature of breaking of ensemble equivalence for constrained random graphs. Electronic Communications in Probability.
  * [13] [author] Döring, H.H., Jansen, S.S. and Schubert, K.K. (2022). The method of cumulants for the normal approximation. Probability Surveys.
  * [14] [author] Dudley, R. M.R. M. (2002). Real analysis and probability. Cambridge University Press.
  * [15] [author] Eaton, M. L.M. L. (1983). Multivariate statistics: a vector space approach. Institute of Mathematical Statistics.
  * [16] [author] Féray, V.V. (2018). Weighted dependency graphs. Electronic Journal of Probability.
  * [17] [author] Gantmacher, F. R.F. R. (2000). The theory of matrices 2\. American Mathematical Society.
  * [18] [author] Garg, A.A., Lee, Y. T.Y. T., Song, Z.Z. and Srivastava, N.N. (2018). A Matrix Expander Chernoff Bound. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC’18).
  * [19] [author] Guionnet, A.A. Bernoulli Random Matrices. Proceedings of the 8th European Congress in Mathematics. To appear, arXiv:2112.05506.
  * [20] [author] Han, F.F. and Li, Y.Y. (2020). Moment bounds for large autocovariance matrices under dependence. Journal of Theoretical Probability.
  * [21] [author] Helton, J. W.J. W., Far, R. R.R. R. and Speicher, R.R. (2007). Operator-valued semicircular elements: solving a quadratic matrix equation with positivity constraints. International Mathematics Research Notices.
  * [22] [author] Horn, R. A.R. A. and Johnson, C. R.C. R. (2012). Matrix analysis, second ed. Cambridge University Press.
  * [23] [author] Ibragimov, I.I. and Linnik, Y. V.Y. V. (1975). Independent and stationary sequences of random variables. Wolters, Noordhoff Publishing Groningen.
  * [24] [author] Janson, SvanteS. (2020). Asymptotic normality in random graphs with given vertex degrees. Random Structures & Algorithms.
  * [25] [author] Jedra, Y.Y., Lee, J.J., Proutière, A.A. and Yun, S. Y.S. Y. (2023). Nearly Optimal Latent State Decoding in Block MDPs. In International Conference on Artificial Intelligence and Statistics.
  * [26] [author] Lehner, F.F. (1999). Computing norms of free operators with matrix coefficients. American Journal of Mathematics.
  * [27] [author] Levin, D. A.D. A., Peres, Y.Y. and Wilmer, E. L.E. L. (2017). Markov Chains and Mixing Times: Second Edition. American Mathematical Society.
  * [28] [author] Lust-Piquard, F.F. (1986). Inégalités de Khintchine dans $C_{p}$ $(1<p<\infty)$. Comptes Rendus de l’Académie des Sciences Paris.
  * [29] [author] Mackey, L.L., Jordan, M. I.M. I., Chen, R. Y.R. Y., Farrell, B.B. and Tropp, J. A.J. A. (2014). Matrix concentration inequalities via the method of exchangeable pairs. The Annals of Probability.
  * [30] [author] Neeman, J.J., Shi, B.B. and Ward, R.R. (2023). Concentration inequalities for sums of Markov dependent random matrices. arXiv:2303.02150.
  * [31] [author] Nelson, E.E. (1974). Notes on non-commutative integration. Journal of Functional Analysis.
  * [32] [author] Nica, A.A. and Speicher, R.R. (2006). Lectures on the Combinatorics of Free Probability. Cambridge University Press.
  * [33] [author] Oliveira, R. I.R. I. (2009). Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges. arXiv preprint arXiv:0911.0600.
  * [34] [author] Paulin, D.D., Mackey, L.L. and Tropp, J. A.J. A. (2016). Efron–Stein inequalities for random matrices. The Annals of Probability.
  * [35] [author] Pisier, G.G. (2003). Introduction to operator space theory. Cambridge University Press.
  * [36] [author] Qiu, J.J., Wang, C.C., Liao, B.B., Peng, R.R. and Tang, J.J. (2020). A Matrix Chernoff Bound for Markov Chains and Its Application to Co-occurrence Matrices. Advances in Neural Information Processing Systems.
  * [37] [author] Robbins, H.H. (1955). A remark on Stirling’s formula. The American mathematical monthly.
  * [38] [author] Sanders, J.J., Proutière, A.A. and Yun, S. Y.S. Y. (2020). Clustering in block Markov chains. The Annals of Statistics.
  * [39] [author] Sanders, J.J. and Senen-Cerda, A.A. (2023). Spectral norm bounds for block Markov chain random matrices. Stochastic Processes and their Applications.
  * [40] [author] Sanders, J.J. and Van Werde, A.A. (2023). Singular value distribution of dense random matrices with block Markovian dependence. Stochastic Processes and their Applications.
  * [41] [author] Saulis, L.L. and Statulevičius, V. A.V. A. (1991). Limit theorems for large deviations. Springer Science & Business Media.
  * [42] [author] Speed, T. P.T. P. (1983). Cumulants and partition lattices 1. Australian Journal of Statistics.
  * [43] [author] Speicher, R.R. and Woroudi, R.R. (1997). Boolean convolutions. Fields Institute Communications.
  * [44] [author] Statulevičius, V.V. (1969, 1970). Limit theorems for the sums of random variables related to a Markov chain. I, II, III. Lithuanian Mathematical Journal.
  * [45] [author] Tao, T.T. (2012). Topics in random matrix theory. American Mathematical Soc.
  * [46] [author] Tropp, J. A.J. A. (2011). Freedman’s inequality for matrix martingales. Electronic Communications in Probability.
  * [47] [author] Tropp, J. A.J. A. (2018). Second-order matrix concentration inequalities. Applied and Computational Harmonic Analysis.
  * [48] [author] Van Werde, A.A., Senen Cerda, A.A., Kosmella, G.G. and Sanders, J.J. (2022). Detection and Evaluation of Clusters within Sequential Data. arXiv preprint arXiv:2210.01679.
  * [49] [author] Vladimirova, M.M., Girard, S.S., Nguyen, H.H. and Arbel, J.J. (2020). Sub-Weibull distributions: Generalizing sub-Gaussian and sub-Exponential properties to heavier tailed distributions. Stat.
  * [50] [author] Zhang, A.A. and Wang, M.M. (2019). Spectral state compression of Markov processes. IEEE Transactions on Information Theory.
  * [51] [author] Zhang, H.H. and Wei, H.H. (2022). Sharper sub-Weibull concentrations. Mathematics.

##  Appendix A Proofs for the matrix series model

We here provide the details for the proofs of the universality of tracial
moments and the variance thereof in the matrix series model. Recall that a
sketch of the proof approach was provided in Section 5.5.

###  A.1 Universality for all tracial moments

The goal of this part is to establish Theorem 4.2. The proof of the following
result proceeds similarly to the proof of Lemma 5.5.

######  Proposition A.1.

Let $p\geq 3$ be a positive integer such that $\bbE[Y_{i}^{2p}]<\infty$ for
all $i\in\\{1,\ldots,n\\}$. Then, in the matrix series model, for any $\eta>0$
and $\gamma\geq 0$

$\displaystyle\lvert\bbE[\operatorname{tr}\bS^{p}]-$
$\displaystyle\bbE[\operatorname{tr}\bG^{p}]\rvert\leq
4^{(1+\gamma)p}p^{3(1+\gamma)}\eta
R(\bA)D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{p}(Y)^{3}\varsigma(\bA)^{2}\bigl{(}\bbE[\operatorname{tr}\bG^{2p}]^{\frac{1}{2p}}$
$\displaystyle+\eta^{\frac{1}{3}}R(\bA)^{\frac{1}{3}}D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{2p}(Y)\varsigma(\bA)^{\frac{2}{3}}p^{\frac{2+3\gamma}{3}}+R(\bA)D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{2p}(Y)p^{1+\gamma}\bigr{)}^{p-3}.$

###### Proof.

Due to Lemma 5.1 it is sufficient to consider the case where
$\|Y_{i}\|_{\sL^{\infty}}<\infty$ for every $i$. Precisely as in steps eq.
5.15–eq. 5.21 in the proof of Lemma 5.7 one can then use Proposition 5.2 and
Lemma 5.3 together with the bound
$\bbE[\operatorname{tr}\lvert\bS(t)\rvert^{p-k}]\leq\bbE[\operatorname{tr}\bS(t)^{2p}]^{\frac{p-k}{2p}}$
to deduce that

$\displaystyle\Bigl{\lvert}\frac{\rm{d}}{{\rm{d}}t}$
$\displaystyle\bbE[\operatorname{tr}\bS(t)^{p}]\Bigr{\rvert}\leq\frac{t^{\frac{1}{2}}}{2}\sum_{k=3}^{p}(k!)^{\gamma}\Bigl{(}\frac{3p}{2}\Bigr{)}^{k}\eta
R(\bA)^{k-2}D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{p}(Y)^{k}\varsigma(\bA)^{2}\bbE[\operatorname{tr}\bS(t)^{2p}]^{\frac{p-k}{2p}}.$
(A.1)

The fact that $(3p/2)^{k}$ here replaces the factor $(3p)^{k}$ in Equation
5.21 is due to the fact that the inequality $k!\binom{p}{k}\leq p^{k}$
replaces the role of the inequality $k!\binom{2p}{k}\leq(2p)^{k}$. We now
proceed as in eq. 5.22 using that $\sum_{k=3}^{p}(3/4)^{k}\leq 2$,
$t^{1/2}\leq 1$, and $k!\leq p^{k}$

$\displaystyle\Bigl{\lvert}\frac{\rm{d}}{{\rm{d}}t}\bbE[\operatorname{tr}\bS(t)^{p}]\Bigr{\rvert}$
$\displaystyle\leq\frac{1}{2}\sum_{k=3}^{p}\Bigl{(}\frac{3}{4}\Bigr{)}^{k}(2p^{1+\gamma})^{k}\eta
R(\bA)^{k-2}D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{p}(Y)^{k}\varsigma(\bA)^{2}\bbE[\operatorname{tr}\bS(t)^{2p}]^{\frac{p-k}{2p}}$
$\displaystyle\leq\max_{k=3,\ldots,p}(2p^{1+\gamma})^{k}\eta
R(\bA)^{k-2}D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{p}(Y)^{k}\varsigma(\bA)^{2}\bbE[\operatorname{tr}\bS(t)^{2p}]^{\frac{p-k}{2p}}.$
(A.2)

By Lemma 5.7 it here holds that

$\displaystyle\bbE[\operatorname{tr}\bS(t)^{2p}]^{\frac{1}{2p}}$
$\displaystyle\leq\bbE[\operatorname{tr}\bG^{2p}]^{\frac{1}{2p}}$
$\displaystyle+4^{1+\gamma}\eta^{\frac{1}{3}}R(\bA)^{\frac{1}{3}}D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{2p}(Y)\varsigma(\bA)^{\frac{2}{3}}p^{\frac{2+3\gamma}{3}}+4^{1+\gamma}R(\bA)D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{2p}(Y)p^{1+\gamma}.$
(A.3)

Finally, substitute eq. A.3 in Equation A.2 to find that
$\lvert\frac{\rm{d}}{{\rm{d}}t}\bbE[\operatorname{tr}\bS(t)^{p}]\rvert\leq
c\max_{k=3,\ldots,p}x^{k}y^{p-k}$ with $c=\eta R(\bA)^{-2}\varsigma(\bA)^{2}$,
$x=2p^{1+\gamma}R(\bA)D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{p}(Y)$, and
where $y$ is given by the right-hand side of eq. A.3. It here holds that
$x\leq y$ since $4^{1+\gamma}\geq 2$ and
$D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{2p}(Y)\geq
D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{p}(Y)$. This implies that
$x^{k}y^{p-k}$ is a nonincreasing function of $k$. Consequently, the maximum
is achieved at $k=3$ and we find that
$\lvert\frac{\rm{d}}{{\rm{d}}t}\bbE[\operatorname{tr}\bS(t)^{p}]\rvert\leq
cx^{3}y^{p-3}$. The desired result now follows from the fundamental theorem of
calculus. ∎

###### Proof of Theorem 4.2.

Recall that $\bbE[\bG]=\bX_{0}$ is deterministic and denote
$\widetilde{\bG}\vcentcolon=\bG-\bX_{0}$. By the triangle inequality with
respect to the norm $\|\cdot\|_{p}$ one has that
$\bbE[\operatorname{tr}\bG^{2p}]^{1/2p}\leq(\operatorname{tr}\bX_{0}^{2p})^{1/2p}+\bbE[\operatorname{tr}\widetilde{\bG}^{2p}]^{1/2p}$.
By combining the Gaussian bound in [7, Theorem 2.7] with the estimate
$(\operatorname{tr}\otimes\tau)(\widetilde{\bG}_{\operatorname{free}}^{2p})^{1/2p}\allowbreak\leq\|\widetilde{\bG}_{\operatorname{free}}^{2p}\|^{1/2p}=\|\widetilde{\bG}_{\operatorname{free}}\|\leq
2\sigma(\bS)$ which follows from [32, Proposition 3.8], [32, (3.2)], and eq.
1.4 it now follows that

$\displaystyle\bbE[\operatorname{tr}\bG^{2p}]^{\frac{1}{2p}}\leq(\operatorname{tr}\bX_{0}^{2p})^{\frac{1}{2p}}+2\sigma(\bS)+2v(\bS)^{\frac{1}{2}}\sigma(\bS)^{\frac{1}{2}}p^{\frac{3}{4}}.$
(A.4)

Combine eq. A.4 with Proposition A.1 and use that
$D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{p}(Y)\leq
D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{2p}(Y)$ to conclude the proof. ∎

###  A.2 Universality for variance of tracial moments

The goal of this part is to establish Theorem 4.3.

######  Proposition A.2.

Let $p\geq 2$ be a positive integer and assume that $\bbE[Y_{i}^{2p}]<\infty$
for every $i\in\\{1,\ldots,n\\}$. Then, in the matrix series model, for any
$\eta>0$ and $\gamma\geq 0$

$\displaystyle\lvert\bbE[(\operatorname{tr}\bS^{p})^{2}]-$
$\displaystyle\bbE[(\operatorname{tr}\bG^{p})^{2}]\rvert$ $\displaystyle\leq
16^{(1+\gamma)p}p^{3(1+\gamma)}\eta
R(\bA)D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{2p}(Y)^{3}\varsigma(\bA)^{2}H^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{p}(\bA,Y)^{2p-3}$

where $H^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{p}(\bA,Y)$ is as in Theorem
4.2.

###### Proof.

Due to Lemma 5.1 we may assume that the $\|Y_{i}\|_{\sL^{\infty}}<\infty$ for
every $i\in\\{1,\ldots,n\\}$. By Proposition 5.2 and the product rule for
directional derivatives it then holds that

$\displaystyle\frac{\rm{d}}{{\rm{d}}t}\bbE[(\operatorname{tr}$
$\displaystyle\bS(t)^{p})^{2}]=\frac{1}{2}\sum_{k=3}^{2p}\sum_{S\subseteq\\{1,\ldots,k\\}}\frac{t^{\frac{k}{2}-1}}{(k-1)!}\times$
(A.5)
$\displaystyle\bbE\Bigl{[}\sum_{i_{1},\ldots,i_{k}=1}^{n}\kappa(Y_{i_{1}},\ldots,Y_{i_{k}})\Bigl{(}\Bigl{(}\prod_{j\in
S}\partial_{\bA_{i_{j}}}\Bigr{)}\operatorname{tr}\bS(t)^{p}\Bigr{)}\Bigl{(}\Bigl{(}\prod_{j\in\\{1,\ldots,k\\}\setminus
S}\partial_{\bA_{i_{j}}}\Bigr{)}\operatorname{tr}\bS(t)^{p}\Bigr{)}\Bigr{]}.$

It is here to be understood that the empty product is the multiplicative unit,
i.e., $\prod_{j\in\emptyset}=1$. Let us consider a term in eq. A.5 with
$\\#S\not\in\\{0,k\\}$, the case where $\\#S\in\\{0,k\\}$ is treated
separately. By the Cauchy–Schwarz inequality we can estimate

$\displaystyle\bbE\Bigl{[}$
$\displaystyle\sum_{i_{1},\ldots,i_{k}=1}^{n}\kappa(Y_{i_{1}},\ldots,Y_{i_{k}})\Bigl{(}\Bigl{(}\prod_{j\in
S}\partial_{\bA_{i_{j}}}\Bigr{)}\operatorname{tr}\bS(t)^{p}\Bigr{)}\Bigl{(}\Bigl{(}\prod_{j\in\\{1,\ldots,k\\}\setminus
S}\partial_{\bA_{i_{j}}}\Bigr{)}\operatorname{tr}\bS(t)^{p}\Bigr{)}\Bigr{]}$
(A.6)
$\displaystyle\leq\bbE\Bigl{[}\sum_{i_{1},\ldots,i_{k}=1}^{n}\lvert\kappa(Y_{i_{1}},\ldots,Y_{i_{k}})\rvert\Bigl{(}\Bigl{(}\prod_{j\in
S}\partial_{\bA_{i_{j}}}\Bigr{)}\operatorname{tr}\bS(t)^{p}\Bigr{)}^{2}\Bigr{]}^{\frac{1}{2}}$
$\displaystyle\hphantom{\leq\
}\times\bbE\Bigl{[}\sum_{i_{1},\ldots,i_{k}=1}^{n}\lvert\kappa(Y_{i_{1}},\ldots,Y_{i_{k}})\rvert\Bigl{(}\Bigl{(}\prod_{j\in\\{1,\ldots,n\\}\setminus
S}\partial_{\bA_{i_{j}}}\Bigr{)}\operatorname{tr}\bS(t)^{p}\Bigr{)}^{2}\Bigr{]}^{\frac{1}{2}}.$

Let us denote $k_{1}\vcentcolon=\\#S$ and pick a bijection
$\mathfrak{j}:\\{1,\ldots,k_{1}\\}\to S$. For any $\bM\in\bbC^{d\times d}$ it
follows from [22, 7.4.1.3.(b)] and a polar decomposition that
$\lvert\operatorname{tr}\bM\rvert\leq\operatorname{tr}\lvert\bM\rvert$. Hence,
by Lemma 5.3 and Jensen’s inequality

$\displaystyle\Bigl{(}\Bigl{(}\prod_{j\in
S}\partial_{\bA_{i_{j}}}\Bigr{)}\operatorname{tr}\bS(t)^{p}\Bigr{)}^{2}$ (A.7)
$\displaystyle=\Bigl{(}\sum_{\rho\in\cS_{k_{1}}}\sum_{\begin{subarray}{c}r_{1},\ldots,r_{k_{1}+1}\geq
0\\\
r_{1}+\ldots+r_{k_{1}+1}=p-k_{1}\end{subarray}}\operatorname{tr}[\bS(t)^{r_{1}}\bA_{i_{\mathfrak{j}(\rho(1))}}\cdots\bS(t)^{r_{k}}\bA_{i_{\mathfrak{j}(\rho(k_{1}))}}\bS(t)^{r_{k_{1}+1}}]\Bigr{)}^{2}$
$\displaystyle\leq
k_{1}!\binom{p}{k_{1}}\sum_{\rho\in\cS_{k_{1}}}\sum_{\begin{subarray}{c}r_{1},\ldots,r_{k_{1}+1}\geq
0\\\
r_{1}+\ldots+r_{k_{1}+1}=p-k_{1}\end{subarray}}\operatorname{tr}[\lvert\bS(t)^{r_{1}}\bA_{i_{\mathfrak{j}(\rho(1))}}\cdots\bS(t)^{r_{k}}\bA_{i_{\mathfrak{j}(\rho(k_{1}))}}\bS(t)^{r_{k_{1}+1}}\rvert]^{2}.$

It was here used that $\\#\cS_{k_{1}}=k_{1}!$ and that the number of
$(k_{1}+1)$-tuples $(r_{1},\ldots,r_{k_{1}+1})$ satisfying $r_{j}\geq 0$ and
$\sum_{j=1}^{k_{1}+1}r_{j}=p-k_{1}$ is equal to $\binom{p}{k_{1}}$. It should
further be understood that $\binom{p}{k_{1}}=0$ if $k_{1}>p$. Due to Jensen’s
inequality we can here further estimate

$\displaystyle\operatorname{tr}[\lvert\bS(t)^{r_{1}}\bA_{i_{\mathfrak{j}(\rho(1))}}\cdots\bS(t)^{r_{k}}\bA_{i_{\mathfrak{j}(\rho(k_{1}))}}\bS(t)^{r_{k_{1}+1}}\rvert]^{2}$
(A.8)
$\displaystyle\leq\operatorname{tr}[\lvert\bS(t)^{r_{1}}\bA_{i_{\mathfrak{j}(\rho(1))}}\cdots\bS(t)^{r_{k}}\bA_{i_{\mathfrak{j}(\rho(k_{1}))}}\bS(t)^{r_{k_{1}+1}}\rvert^{2}]$
$\displaystyle=\operatorname{tr}[\bS(t)^{r_{1}}\bA_{i_{\mathfrak{j}(\rho(1))}}\cdots\bS(t)^{r_{k}}\bA_{i_{\mathfrak{j}(\rho(k_{1}))}}\bS(t)^{2r_{k_{1}+1}}\bA_{i_{\mathfrak{j}(\rho(k_{1}))}}\bS(t)^{r_{k}}\cdots\bA_{i_{\mathfrak{j}(\rho(1))}}\bS(t)^{r_{1}}].$

As we assumed that $\\#S\neq 0$ it holds that $2k_{1}\geq 2$. This ensures
that Lemma 5.4 is applicable:

$\displaystyle\sum_{i_{1},\ldots,i_{k}=1}^{n}\bbE\Bigl{[}\lvert\kappa(Y_{i_{1}},\ldots,Y_{i_{k}})\rvert$
$\displaystyle\operatorname{tr}[\lvert\bS(t)^{r_{1}}\bA_{i_{\mathfrak{j}(\rho(1))}}\cdots\bS(t)^{r_{k}}\bA_{i_{\mathfrak{j}(\rho(k_{1}))}}\bS(t)^{r_{k_{1}+1}}\rvert]^{2}\Bigr{]}$
(A.9) $\displaystyle\leq
R(\bA)^{2k_{1}-2}\Bigl{\|}\sum_{i_{1},\ldots,i_{k}=1}^{n}\lvert\kappa(Y_{i_{1}},\ldots,Y_{i_{k}})\rvert\bA_{i_{1}}^{2}\Bigr{\|}\bbE[\operatorname{tr}\bS(t)^{2p-2k_{1}}].$

Now combine eq. A.6–eq. A.9 and the upper bound $k_{1}!\binom{p}{k_{1}}\leq
p^{k_{1}}$ as well as the upper bound from eq. 5.19 to find that

$\displaystyle\bbE\Bigl{[}$
$\displaystyle\sum_{i_{1},\ldots,i_{k}=1}^{n}\lvert\kappa(Y_{i_{1}},\ldots,Y_{i_{k}})\rvert\Bigl{(}\Bigl{(}\prod_{j\in
S}\partial_{\bA_{i_{j}}}\Bigr{)}\operatorname{tr}\bS(t)^{p}\Bigr{)}^{2}\Bigr{]}$
(A.10)
$\displaystyle\leq\Bigl{(}k_{1}!\binom{p}{k_{1}}\Bigr{)}^{2}R(\bA)^{2k_{1}-2}\Bigl{\|}\sum_{i_{1},\ldots,i_{k}=1}^{n}\lvert\kappa(Y_{i_{1}},\ldots,Y_{i_{k}})\rvert\bA_{i_{1}}^{2}\Bigr{\|}\bbE[\operatorname{tr}\bS(t)^{2p-2k_{1}}]$
$\displaystyle\leq\mathbbm{1}\\{k_{1}\leq p\\}p^{2k_{1}}\eta
R(\bA)^{2k_{1}-2}(k!)^{1+\gamma}D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{2p}(Y)^{k}\varsigma(\bA)^{2}\bbE[\operatorname{tr}\bS(t)^{2p-2k_{1}}].$

A similar estimate applies to the other factor in Equation A.6 except that the
role of $k_{1}$ is replaced by $k-k_{1}$. Combine eq. A.6–eq. A.10 with the
estimate
$\bbE[\operatorname{tr}\bS(t)^{2p-2k_{i}}]\leq\bbE[\operatorname{tr}\bS(t)^{2p}]^{(2p-2k_{i})/(2p)}$
to conclude that whenever $\\#S\not\in\\{0,k\\}$

$\displaystyle\bbE\Bigl{[}$
$\displaystyle\sum_{i_{1},\ldots,i_{k}=1}^{n}\kappa(Y_{i_{1}},\ldots,Y_{i_{k}})\Bigl{(}\Bigl{(}\prod_{j\in
S}\partial_{\bA_{i_{j}}}\Bigr{)}\operatorname{tr}\bS(t)^{p}\Bigr{)}\Bigl{(}\Bigl{(}\prod_{j\in\\{1,\ldots,k\\}\setminus
S}\partial_{\bA_{i_{j}}}\Bigr{)}\operatorname{tr}\bS(t)^{p}\Bigr{)}\Bigr{]}$
$\displaystyle\leq p^{k}\eta
R(\bA)^{k-2}(k!)^{1+\gamma}D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{2p}(Y)^{k}\varsigma(\bA)^{2}\bbE[\operatorname{tr}\bS(t)^{2p}]^{\frac{2p-k}{2p}}.$
(A.11)

We claim that eq. A.11 remains true if $\\#S\in\\{0,k\\}$. Let us consider the
case where $\\#S=0$ and note that Lemma 5.3 then implies that

$\displaystyle\Bigl{(}\prod_{j\in\\{1,\ldots,k\\}}$
$\displaystyle\partial_{\bA_{i_{j}}}\Bigr{)}\operatorname{tr}\bS(t)^{p}$
(A.12)
$\displaystyle=\sum_{\rho\in\cS_{k_{1}}}\sum_{\begin{subarray}{c}r_{1},\ldots,r_{k+1}\geq
0\\\
r_{1}+\ldots+r_{k+1}=p-k\end{subarray}}\operatorname{tr}[\bS(t)^{r_{1}}\bA_{i_{\mathfrak{j}(\rho(1))}}\cdots\bS(t)^{r_{k}}\bA_{i_{\mathfrak{j}(\rho(k))}}\bS(t)^{r_{k+1}}].$

Now apply Lemma 5.4 with
$\bM_{j}=\lvert\operatorname{tr}\bS(t)^{p}\rvert^{r_{j+1}/(p-k)}\bS(t)^{r_{j+1}}$
and $p_{j}=(p-k)/r_{j+1}$ for $j<k$ and
$\bM_{k}=\operatorname{sign}(\operatorname{tr}\bS(t)^{p})\lvert\operatorname{tr}\bS(t)^{p}\rvert^{(r_{k+1}+r_{1})/(p-k)}\bS(t)^{r_{k+1}+r_{1}}$
and $p_{k}=(p-k)/(r_{k+1}+r_{1})$ for $j=k$ to find that

$\displaystyle\bbE\Bigl{[}$
$\displaystyle\sum_{i_{1},\ldots,i_{k}=1}^{n}\kappa(Y_{i_{1}},\ldots,Y_{i_{k}})\Bigl{(}\operatorname{tr}\bS(t)^{p}\Bigr{)}\Bigl{(}\Bigl{(}\prod_{j\in\\{1,\ldots,k\\}}\partial_{\bA_{i_{j}}}\Bigr{)}\operatorname{tr}\bS(t)^{p}\Bigr{)}\Bigr{]}$
(A.13) $\displaystyle\leq
k!\binom{p}{k}R(\bA)^{k-2}\Bigl{\|}\sum_{i_{1},\ldots,i_{k}=1}^{n}\lvert\kappa(Y_{i_{1}},\ldots,Y_{i_{k}})\rvert\bA_{i_{1}}^{2}\Bigr{\|}\bbE[\lvert\operatorname{tr}\bS(t)^{p}\rvert\operatorname{tr}\lvert\bS(t)\rvert^{p-k}].$

Recall that $\binom{p}{k}=0$ if $k>p$ so that this identity is also sensible
in this case. By the Cauchy–Schwarz inequality and Jensen’s inequality it here
holds that
$\bbE[\lvert\operatorname{tr}\bS(t)^{p}\rvert\operatorname{tr}\lvert\bS(t)\rvert^{p-k}]\leq\bbE[\operatorname{tr}\bS^{2p}]^{(2p-k)/2p}$.
The remainder of the proof proceeds exactly as eq. A.10–eq. A.11.

We conclude that eq. A.11 holds for any $S\subseteq\\{1,\ldots,k\\}$. Hence,
by eq. A.5

$\displaystyle\frac{\rm{d}}{{\rm{d}}t}\bbE[(\operatorname{tr}\bS(t)^{p})^{2}]\leq\frac{1}{2}$
$\displaystyle\sum_{k=3}^{2p}\sum_{S\subseteq\\{1,\ldots,k\\}}\frac{t^{\frac{k}{2}-1}}{(k-1)!}\times$
(A.14) $\displaystyle\ p^{k}\eta
R(\bA)^{k-2}(k!)^{1+\gamma}D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{2p}(Y)^{k}\varsigma(\bA)^{2}\bbE[\operatorname{tr}\bS(t)^{2p}]^{\frac{2p-k}{2p}}.$

Note that there are $2^{k}$ subsets $S\subseteq\\{1,\ldots,k\\}$. Using that
$k\leq(3/2)^{k}$, $k!\leq(2p)^{k}$, and $t^{\frac{k}{2}-1}\leq 1$ we conclude
that

$\displaystyle\frac{\rm{d}}{{\rm{d}}t}$
$\displaystyle\bbE[(\operatorname{tr}\bS(t)^{p})^{2}]\leq\frac{1}{2}\sum_{k=3}^{2p}(3p)^{(1+\gamma)k}\eta
R(\bA)^{k-2}D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{2p}(Y)^{k}\varsigma(\bA)^{2}\bbE[\operatorname{tr}\bS(t)^{2p}]^{\frac{2p-k}{2p}}.$
(A.15)

We now proceed precisely as in eq. A.2–eq. A.3:

$\displaystyle\frac{\rm{d}}{{\rm{d}}t}$
$\displaystyle\bbE[(\operatorname{tr}\bS(t)^{p})^{2}]$ (A.16)
$\displaystyle\leq\frac{1}{2}\sum_{k=3}^{2p}\Bigl{(}\frac{3}{4}\Bigr{)}^{k}(4p)^{(1+\gamma)k}\eta
R(\bA)^{k-2}D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{2p}(Y)^{k}\varsigma(\bA)^{2}\bbE[\operatorname{tr}\bS(t)^{2p}]^{\frac{2p-k}{2p}}$
$\displaystyle\leq\max_{k=3,\ldots,p}(4p^{1+\gamma})^{k}\eta
R(\bA)^{k-2}D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{p}(Y)^{k}\varsigma(\bA)^{2}\bbE[\operatorname{tr}\bS(t)^{2p}]^{\frac{2p-k}{2p}}$
$\displaystyle\leq(4p^{1+\gamma})^{3}\eta
R(\bA)D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{p}(Y)^{3}\varsigma(\bA)^{2}\Bigl{(}\bbE[\operatorname{tr}\bG^{2p}]^{\frac{1}{2p}}$
$\displaystyle+4^{1+\gamma}\eta^{\frac{1}{3}}R(\bA)^{\frac{1}{3}}D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{2p}(Y)\varsigma(\bA)^{\frac{2}{3}}p^{\frac{2+3\gamma}{3}}+4^{1+\gamma}R(\bA)D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{2p}(Y)p^{1+\gamma}.\Bigr{)}^{\frac{2p-3}{2p}}.$

Apply the fundamental theorem of calculus and use eq. A.4 together with the
fact that $4^{2}=16$ to conclude the proof. ∎

###### Proof of Theorem 4.3.

When $p=2$ it holds that
$\bbE[\operatorname{tr}\bS^{2}]=\bbE[\operatorname{tr}\bG^{2}]$ by definition
of a Gaussian model and the desired result is immediate from Proposition A.2.
Now assume that $p\geq 3$. Then, Theorem 4.2 together with the fact that
$\lvert(x\pm\varepsilon)^{2}-x^{2}\rvert\leq 2x\varepsilon+\varepsilon^{2}$
for any $x,\varepsilon\geq 0$ yields that

$\displaystyle\lvert\bbE[\operatorname{tr}\bS^{p}]^{2}-\bbE[\operatorname{tr}\bG^{p}]^{2}\rvert\leq
4^{(1+\gamma)p}p^{3(1+\gamma)}\eta
R(\bA)D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{2p}(Y)^{3}\varsigma(\bA)^{2}H^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{p}(\bA,Y)^{p-3}$
$\displaystyle\times(2\lvert\bbE[\operatorname{tr}\bG^{p}]\rvert+4^{(1+\gamma)p}p^{3(1+\gamma)}\eta
R(\bA)D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{2p}(Y)^{3}\varsigma(\bA)^{2}H^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{p}(\bA,Y)^{p-3}).$
(A.17)

Due to Jensen’s inequality, eq. A.4, and the definition of
$H^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{p}(\bA,Y)$ in Theorem 4.2 it further
holds that
$\lvert\bbE[\operatorname{tr}\bG^{p}]\rvert\leq\bbE[\operatorname{tr}\bG^{2p}]^{\frac{1}{2}}\leq
2^{p}H^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{p}(\bA,Y)^{p}$. The combination
of eq. A.17 with Proposition A.2 now implies that

$\displaystyle\lvert\operatorname{Var}[\operatorname{tr}\bS^{p}]-\operatorname{Var}\bbE[\operatorname{tr}\bG^{p}]\rvert$
(A.18) $\displaystyle\ \leq 4^{(1+\gamma)p}p^{3(1+\gamma)}\eta
R(\bA)D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{2p}(Y)^{3}\varsigma(\bA)^{2}H^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{p}(\bA,Y)^{2p-3}$
$\displaystyle\
\times\bigl{(}(2^{p+1}+4^{(1+\gamma)p})H^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{p}(\bA,Y)^{3}+4^{(1+\gamma)p}p^{3(1+\gamma)}\eta
R(\bA)D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{2p}(Y)^{3}\varsigma(\bA)^{2}\bigr{)}.$

This implies the desired result since $2^{p+1}+4^{(1+\gamma)p}\leq
5^{(1+\gamma)p}$ for $p\geq 3$. ∎

##  Appendix B Properties of the $\psi$-dependence coefficient

In this section, we prove some basic properties of the $\psi$-dependence
coefficient. First, we prove a bound on $\Psi(Z)$ in terms of the total
variation mixing time of the Markov chain in Section B.1. Second, in Section
B.2, we prove the properties of the $\psi$-dependence coefficient which were
stated in Section 6.1.

###  B.1 Bound on $\Psi(Z)$ in terms of total variation mixing time

Another common way to quantify the decay of dependence in a Markov chain is
the _total variation mixing time_ [27, Section 4.5]. In this section, we prove
a bound on $\Psi(Z)$ in terms of the mixing time; see Proposition B.3.

######  Lemma B.1.

Let $X$ and $Y$ be random variables which are supported on finite sets $\sX$
and $\sY$ respectively. Then,

$\displaystyle\psi(X\mid Y)=\max_{x\in\sX,y\in\sY}\
\Bigl{\lvert}\frac{\bbP(X=x,Y=y)-\bbP(X=x)\bbP(Y=y)}{\bbP(X=x)\bbP(Y=y)}\Bigr{\rvert}.$
(B.1)

###### Proof.

Observe that for any nonempty subsets $\cA,\cA_{1},\cA_{2}\subseteq\sX$ and
$\cB\subseteq\sY$ with $\cA=\cA_{1}\cup\cA_{2}$ and
$\cA_{1}\cap\cA_{2}=\emptyset$ it holds that

$\displaystyle\Bigl{\lvert}\frac{\bbP(X\in\cA,Y\in\cB)-\bbP(X\in\cA)\bbP(Y\in\cB)}{\bbP(X\in\cA)\bbP(Y\in\cB)}\Bigr{\rvert}$
(B.2)
$\displaystyle\qquad=\Bigl{\lvert}\frac{\bbP(X\in\cA_{1},Y\in\cB)+\bbP(X\in\cA_{2},Y\in\cB)-\bbP(X\in\cA)\bbP(Y\in\cB)}{\bbP(X\in\cA)\bbP(Y\in\cB)}\Bigr{\rvert}$
$\displaystyle\qquad\leq\frac{\bbP(X\in\cA_{1})}{\bbP(X\in\cA_{1})+\bbP(X\in\cA_{2})}\Bigl{\lvert}\frac{\bbP(X\in\cA_{1},Y\in\cB)-\bbP(X\in\cA_{1})\bbP(Y\in\cB)}{\bbP(X\in\cA_{1})\bbP(Y\in\cB)}\Bigr{\rvert}$
$\displaystyle\qquad\quad+\frac{\bbP(X\in\cA_{2})}{\bbP(X\in\cA_{1})+\bbP(X\in\cA_{2})}\Bigl{\lvert}\frac{\bbP(X\in\cA_{2},Y\in\cB)-\bbP(X\in\cA_{2})\bbP(Y\in\cB)}{\bbP(X\in\cA_{2})\bbP(Y\in\cB)}\Bigr{\rvert}.$

The final inequality used the triangle inequality together with the fact that
$\bbP(X\in\cA)=\bbP(X\in\cA_{1})+\bbP(X\in\cA_{2})$. By Jensen’s inequality it
follows that

$\displaystyle\Bigl{\lvert}\frac{\bbP(X\in\cA,Y\in\cB)-\bbP(X\in\cA)\bbP(Y\in\cB)}{\bbP(X\in\cA)\bbP(Y\in\cB)}\Bigr{\rvert}$
(B.3) $\displaystyle\qquad\leq\max_{i=1,2}\
\Bigl{\lvert}\frac{\bbP(X\in\cA_{i},Y\in\cB)-\bbP(X\in\cA_{i})\bbP(Y\in\cB)}{\bbP(X\in\cA_{i})\bbP(Y\in\cB)}\Bigr{\rvert}.$

The desired result now follows by repeatedly applying eq. B.3 until $\cA$ and
$\cB$ have been reduced to singletons. ∎

######  Lemma B.2.

Let $Z=(Z_{i})_{i=1}^{n}$ be an ergodic stationary Markov chain on a finite
state space $\sS$. Denote $\bP\in[0,1]^{\sS\times\sS}$ and $\pi\in[0,1]^{\sS}$
for the transition matrix and equilibrium distribution of $Z$. Then,

$\displaystyle\Psi(Z)=\min\Bigl{\\{}n,\,\min\Bigl{\\{}t\geq
1:\max_{i,j\in\sS}\Bigl{\lvert}\,\frac{(\bP^{t})_{i,j}-\pi_{j}}{\pi_{j}}\,\Bigr{\rvert}\leq\frac{1}{4}\Bigr{\\}}\Bigr{\\}}.$
(B.4)

###### Proof.

This is immediate by substitution of Lemma B.1 in the definition of $\Psi(Z)$;
recall eq. 3.4. ∎

The _total variation distance_ between two probability measures $\mu,\nu$ on a
finite set $\sS$ is defined by

$\displaystyle
d_{{\rm{TV}}}(\mu,\nu):=\max_{\cA\subseteq\sS}\,\lvert\mu(A)-\nu(A)\rvert.$
(B.5)

For any $\varepsilon>0$ the _$\varepsilon$ -mixing time_ of an ergodic Markov
chain $Z$ on a finite state space is defined as
$t_{\rm{mix}}(\varepsilon):=\min\\{t\geq 1:d(t)\leq\varepsilon\\}$ where

$\displaystyle d(t):=\sup_{i\in\sS}d_{\mathrm{TV}}(\mathbb{P}(Z_{t}=\cdot\mid
Z_{0}=i),\pi).$ (B.6)

We refer to $t_{\rm{mix}}:=t_{\rm{mix}}(1/4)$ as the _total variation mixing
time_ of $Z$.

######  Proposition B.3.

Let $Z$ and $\pi\in[0,1]^{\sS}$ be as in Lemma B.2 and denote
$\pi_{\min}\vcentcolon=\min\\{\pi_{x}:x\in\sS\\}$. Then,

$\displaystyle\Psi(Z)\leq\Bigl{(}\log_{2}\bigl{(}\frac{1}{\pi_{\min}}\bigr{)}+3\Bigl{)}t_{\rm{mix}}$
(B.7)

###### Proof.

By taking $\cA=\\{j\\}$ in eq. B.5 it follows that for every $t\geq 1$

$\displaystyle\max_{i,j\in\sS}\lvert\bP^{t}_{i,j}-\pi_{j}\rvert\leq d(t).$
(B.8)

Denote $\ell\vcentcolon=\lceil\log_{2}(1/\pi_{\min})+2\rceil$ and note that
$\ell\geq\log_{2}(1/\pi_{\min})+2$. It consequently follows from [27, (4.35)]
that

$\displaystyle d(\ell t_{\rm{mix}})\leq 2^{-\ell}\leq 4^{-1}\pi_{\min}.$ (B.9)

Combine eq. B.8 and eq. B.9 to find that

$\displaystyle\max_{i,j\in\sS}\ \Bigl{\lvert}\frac{\bP^{\ell
t_{\rm{mix}}}_{i,j}-\pi_{j}}{\pi_{j}}\Bigr{\rvert}\leq\frac{1}{4}.$ (B.10)

The desired result now follows from Lemma B.2 and the fact that
$\ell\leq\log_{2}(1/\pi_{\min})\allowbreak+3$. ∎

###  B.2 Proofs for Propositions 6.1 and 6.2

We here provide the proofs for properties of the $\psi$-dependence coefficient
which were stated in Propositions 6.1 and 6.2.

######  Lemma B.4.

Let $V,W$ be random variables taking values in measurable spaces
$\Omega_{V},\Omega_{W}$, respectively. Then, for any measurable
$E\subseteq\Omega_{V}\times\Omega_{W}$ it holds that

$\displaystyle\bigl{(}1-\psi(V\mid
W)\bigr{)}\bigl{(}\bbP_{V}\otimes\bbP_{W}\bigr{)}(E)\leq\bbP_{V,W}(E)\leq\bigl{(}1+\psi(V\mid
W)\bigr{)}\bigl{(}\bbP_{V}\otimes\bbP_{W}\bigr{)}(E).$ (B.11)

###### Proof.

First consider the case where $E=A\times B$ for measurable sets
$A\subseteq\Omega_{V}$ and $B\subseteq\Omega_{W}$. If $\bbP_{V}(A)=0$ or
$\bbP_{W}(B)=0$ then the claim is immediate as $\bbP_{V,W}(A\times
B)\leq\min\\{\bbP_{V}(A),\bbP_{W}(B)\\}$. If instead $\bbP_{V}(A)>0$ and
$\bbP_{W}(B)>0$ then the claim follows from the definition eq. 3.4 of the
$\psi$-dependence coefficient.

Denote $\cC$ for the collection of all subsets of $\Omega_{V}\times\Omega_{W}$
which can be expressed as finite disjoint unions of products of measurable
sets and let $\cG$ denote the collection of all measurable $E$ which satisfy
eq. B.11. Then, $\cC$ is a field of sets and $\cG$ is a monotone class
containing $\cC$. The monotone class theorem [9, Theorem 3.4] now implies that
$\sigma(\cC)$, the $\sigma$-algebra generated by $\cC$, is contained in $\cG$.
This proves the desired result since $\sigma(\cC)$ is the $\sigma$-algebra on
$\Omega_{V}\times\Omega_{W}$. ∎

###### Proof of Proposition 6.1.

The absolute continuity claim is immediate by Lemma B.4. We next consider the
upper bound in Proposition 6.1. Let us define a measurable set $E\subseteq
B_{V}\times B_{W}$ by

$\displaystyle E\vcentcolon=\Bigl{\\{}(v,w)\in B_{V}\times B_{W}:\frac{{\rm
d}\bbP_{V,W}}{{\rm d}(\bbP_{V}\otimes\bbP_{W})}(v,w)>1+\psi(V\mid
W)\Bigr{\\}}.$ (B.12)

Then, if $(\bbP_{V}\otimes\bbP_{W})(E)>0$ it holds that

$\displaystyle(\bbP_{V}\otimes\bbP_{W})(E)$
$\displaystyle=\int_{E}\frac{1+\psi(V\mid W)}{1+\psi(V\mid W)}{\rm
d}(\bbP_{V}\otimes\bbP_{W})(v,w)$ (B.13) $\displaystyle<\frac{1}{1+\psi(V\mid
W)}\int_{E}\frac{{\rm d}\bbP_{V,W}}{{\rm d}(\bbP_{V}\otimes\bbP_{W})}(v,w){\rm
d}(\bbP_{V}\otimes\bbP_{W})(v,w)$ $\displaystyle=\frac{1}{1+\psi(V\mid
W)}\bbP_{V,W}(E)$

which contradicts Lemma B.4. This establishes the upper bound in Proposition
6.1.

The lower bound is immediate if $\psi(V\mid W)\geq 1$ as the Radon–Nikodym
derivative of two measures is almost everywhere nonnegative. If $\psi(V\mid
W)<1$ then Lemma B.4 implies that $\bbP_{V}\otimes\bbP_{W}$ is absolutely
continuous with respect to $\bbP_{V,W}$ so it is sufficient to see that
$\bbP_{V,W}(E^{\prime})=0$ with

$\displaystyle E^{\prime}\vcentcolon=\Bigl{\\{}(v,w)\in B_{V}\times
B_{W}:\frac{{\rm d}\bbP_{V,W}}{{\rm
d}(\bbP_{V}\otimes\bbP_{W})}(v,w)<1-\psi(V\mid W)\Bigr{\\}}.$ (B.14)

Indeed, note that by the chain rule for Radon–Nikodym derivatives it holds
that ${\rm d}\bbP_{V,W}/{\rm d}(\bbP_{V}\otimes\bbP_{W})=1/({\rm
d}(\bbP_{V}\otimes\bbP_{W})/{\rm d}\bbP_{V,W})$. Hence, if
$\bbP_{V,W}(E^{\prime})>0$

$\displaystyle\bbP_{V,W}(E^{\prime})$
$\displaystyle=\int_{E^{\prime}}\frac{1-\psi(V\mid W)}{1-\psi(V\mid W)}{\rm
d}\bbP_{V,W}(v,w)$ (B.15) $\displaystyle<\bigl{(}1-\psi(V\mid
W)\bigr{)}\int_{E^{\prime}}\frac{{\rm d}(\bbP_{V}\otimes\bbP_{W})}{{\rm
d}\bbP_{V,W}}(v,w){\rm d}\bbP_{V,W}(v,w)$ $\displaystyle=\bigl{(}1-\psi(V\mid
W)\bigr{)}(\bbP_{V}\otimes\bbP_{W})(E^{\prime}).$

which contradicts Lemma B.4. This establishes the lower bound in Proposition
6.1. ∎

######  Lemma B.5.

Let $(V_{1},V_{2},V_{3})$ be a Markovian sequence of random variables with
values in standard Borel spaces $B_{1},B_{2}$, and $B_{3}$ respectively. Then,
if $\psi(V_{2}\mid V_{1})<\infty$ and $\psi(V_{3}\mid V_{2})<\infty$,

$\displaystyle\psi(V_{3}\mid V_{1})\leq\psi(V_{3}\mid V_{2})\psi(V_{2}\mid
V_{1}).$

###### Proof.

Let $E_{3}\in\sigma(V_{3})$ and $E_{1}\in\sigma(V_{1})$. Then, by the Markov
property, we can write

$\displaystyle\bbP(E_{1}\cap E_{3})-$
$\displaystyle\bbP(E_{1})\bbP(E_{3})=\int_{E_{1}\times B_{2}}\bbP(E_{3}\mid
V_{2}=y){\rm d}(\bbP_{V_{1},V_{2}}-\bbP_{V_{1}}\otimes\bbP_{V_{2}})(x,y).$
(B.16)

Note moreover that

$\displaystyle\int_{E_{1}\times B_{2}}\bbP(E_{3}){\rm
d}(\bbP_{V_{1},V_{2}}-\bbP_{V_{1}}\otimes\bbP_{V_{2}})(x,y)$
$\displaystyle=\bbP(E_{3})\bbP(E_{1})-\bbP(E_{3})\bbP(E_{1})$ (B.17)
$\displaystyle=0.$

Now denote $g(y)\vcentcolon=\bbP(E_{3}\mid V_{2}=y)-\bbP(E_{3})$ and combine
eq. B.17 and eq. B.16 to find that

$\displaystyle\bbP(E_{1}\cap E_{3})-\bbP(E_{1})$
$\displaystyle\bbP(E_{3})=\int_{E_{1}\times B_{2}}g(y)\,{\rm
d}(\bbP_{V_{1},V_{2}}-\bbP_{V_{1}}\otimes\bbP_{V_{2}})(x,y)$ (B.18)
$\displaystyle=\int_{E_{1}\times B_{2}}g(y)\Bigl{(}\frac{{\rm
d}\bbP_{V_{1},V_{2}}}{{\rm
d}(\bbP_{V_{1}}\otimes\bbP_{V_{2}})}(x,y)-1\Bigr{)}{\rm
d}(\bbP_{V_{1}}\otimes\bbP_{V_{2}})(x,y).$

Define a measurable function $\delta:B_{2}\to\bbR$ by

$\displaystyle\delta(y)\vcentcolon=\int_{E_{1}}\Bigl{(}\frac{{\rm
d}\bbP_{V_{1},V_{2}}}{{\rm
d}(\bbP_{V_{1}}\otimes\bbP_{V_{2}})}(x,y)-1\Bigr{)}{\rm d}\bbP_{V_{1}}(x).$
(B.19)

Then, considering the definition of $g$, eq. B.18 can be rewritten as

$\displaystyle\bbP(E_{1}\cap E_{3})-\bbP(E_{1})\bbP(E_{3})=\int_{B_{2}\times
E_{3}}\delta(y){\rm
d}(\bbP_{V_{2},V_{3}}-\bbP_{V_{2}}\otimes\bbP_{V_{3}})(y,z)$ (B.20)
$\displaystyle=\int_{B_{2}\times E_{3}}\delta(y)\Bigl{(}\frac{{\rm
d}\bbP_{V_{2},V_{3}}}{{\rm
d}(\bbP_{V_{2}}\otimes\bbP_{V_{3}})}(y,z)-1\Bigr{)}{\rm
d}(\bbP_{V_{2}}\otimes\bbP_{V_{3}})(y,z).$

Substitute the definition of $\delta(y)$ and use Proposition 6.1 to find that

$\displaystyle\lvert\bbP(E_{1}\cap
E_{3})-\bbP(E_{1})\bbP(E_{3})\rvert\leq\psi(V_{3}\mid V_{2})\psi(V_{2}\mid
V_{1})\bbP(E_{1})\bbP(E_{3}).$ (B.21)

Since $E_{1}\in\sigma(V_{1})$ and $E_{3}\in\sigma(V_{3})$ were arbitrary, this
concludes the proof. ∎

###### Proof of Proposition 6.2.

We proceed by induction on $\lfloor j/\Psi(Z)\rfloor$. In the base case, where
$\lfloor j/\Psi(Z)\rfloor=1$, the desired result is immediate from the
definition Equation 3.5 of $\Psi(Z)$.

Now suppose that $\lfloor j/\Psi(Z)\rfloor\geq 2$. Then, by Lemma B.5 and the
induction hypothesis applied to $j-\Psi(Z)$

$\displaystyle\psi(Z_{i+j}\mid Z_{i})$ $\displaystyle\leq\psi(Z_{i+j}\mid
Z_{i+j-\Psi(Z)})\psi(Z_{i+j-\Psi(Z)}\mid
Z_{i})\leq\frac{1}{4}\Bigl{(}\frac{1}{4}\Bigr{)}^{\lfloor(j-\Psi(Z))/\Psi(Z)\rfloor}.$
(B.22)

Remark that $\lfloor(j-\Psi(Z))/\Psi(Z)\rfloor=\lfloor(j/\Psi(Z)\rfloor-1$ to
conclude the proof. ∎

##  Appendix C Proofs for the Markovian model

We here provide the details for the proofs of the universality of tracial
moments and the variance thereof in the Markovian model. The proofs are
closely related to those of the matrix series model.

###  C.1 Universality for all tracial moments

The goal of this section is to prove Theorem 3.2.

######  Proposition C.1.

In the Markovian model it holds that for any integer $p\geq 3$

$\displaystyle\lvert\bbE[\operatorname{tr}\bS^{p}]-\bbE[\operatorname{tr}\bG^{p}]\rvert\leq$
$\displaystyle(40p)^{3}\Psi(Z)^{2}R(\bX)\varsigma(\bX)^{2}\bigl{(}\bbE[\operatorname{tr}\bG^{2p}]^{\frac{1}{2p}}$
$\displaystyle\
+60R(\bX)^{\frac{1}{3}}\Psi(Z)^{\frac{2}{3}}\varsigma(\bX)^{\frac{2}{3}}p^{\frac{2}{3}}+60R(\bX)\Psi(Z)p\bigr{)}^{p-3}.$

###### Proof.

Precisely as in steps eq. 6.68–eq. 6.75 in the proof of Lemma 6.12 it can be
deduced that for any $t\in[0,1]$

$\displaystyle\Bigl{\lvert}\frac{\rm{d}}{{\rm{d}}t}$
$\displaystyle\bbE[\operatorname{tr}\bS(t)^{p}]\Bigr{\rvert}\leq\sum_{k=3}^{p}(27p)^{k}R(\bX)^{k-2}\Psi(Z)^{k-1}\varsigma(\bX)^{2}\bbE[\operatorname{tr}\lvert\bS(t)\rvert^{p-k}].$
(C.1)

It was here used that $({\rm{e}}^{2+1/12}/2)/36\leq 1$ and
$t^{\frac{1}{2}}\leq 1$. By Jensen’s inequality it here holds that
$\bbE[\operatorname{tr}\lvert\bS(t)\rvert^{p-k}]\leq\bbE[\operatorname{tr}\bS(t)^{2p}]^{\frac{p-k}{2p}}$.
We now proceed as in eq. 6.76 using that $\sum_{k=3}^{p}(27/40)^{k}\leq 1$

$\displaystyle\Bigl{\lvert}\frac{\rm{d}}{{\rm{d}}t}\bbE[\operatorname{tr}\bS(t)^{p}]\Bigr{\rvert}$
$\displaystyle\leq\sum_{k=3}^{p}(27p)^{k}R(\bX)^{k-2}\Psi(Z)^{k-1}\varsigma(\bX)^{2}\bbE[\operatorname{tr}\bS(t)^{2p}]^{\frac{p-k}{2p}}$
(C.2)
$\displaystyle\leq\sum_{k=3}^{p}\Bigl{(}\frac{27}{40}\Bigr{)}^{k}(40p)^{k}R(\bX)^{k-2}\Psi(Z)^{k-1}\varsigma(\bX)^{2}\bbE[\operatorname{tr}\bS(t)^{2p}]^{\frac{p-k}{2p}}$
$\displaystyle\leq\max_{k=3,\ldots,p}(40p)^{k}R(\bX)^{k-2}\Psi(Z)^{k-1}\varsigma(\bX)^{2}\bbE[\operatorname{tr}\bS(t)^{2p}]^{\frac{p-k}{2p}}.$

By Lemma 6.13 it holds that

$\displaystyle\bbE[\operatorname{tr}\bS(t)^{2p}]^{\frac{1}{2p}}\leq\bbE[\operatorname{tr}\bG^{2p}]^{\frac{1}{2p}}+60R(\bX)^{\frac{1}{3}}\varsigma(\bX)^{\frac{2}{3}}\Psi(Z)^{\frac{2}{3}}p^{\frac{2}{3}}+60R(\bX)\Psi(Z)p.$
(C.3)

Note that, since $60p\geq 40p$ and all terms in eq. C.3 are nonnegative, the
maximum in Equation C.2 after substitution of eq. C.3 is achieved at $k=3$:

$\displaystyle\Bigl{\lvert}\frac{\rm{d}}{{\rm{d}}t}\bbE[\operatorname{tr}\bS(t)^{p}]\Bigr{\rvert}\leq(40p$
$\displaystyle)^{3}R(\bX)\Psi(Z)^{2}\varsigma(\bX)^{2}(\bbE[\operatorname{tr}\bG^{2p}]^{\frac{1}{2p}}$
(C.4)
$\displaystyle+60R(\bX)^{\frac{1}{3}}\Psi(Z)^{\frac{2}{3}}\varsigma(\bX)^{\frac{2}{3}}p^{\frac{2}{3}}+60R(\bX)\Psi(Z)p).$

The desired result now follows from the fundamental theorem of calculus and
the fact that $\bS(0)=\bG$ and $\bS(1)=\bS$. ∎

###### Proof of Theorem 3.2.

This follows identically to the proof of Theorem 4.2: combine eq. A.4 with
Proposition C.1. ∎

###  C.2 Universality for the variance of tracial moments

The goal of this section is to prove Theorem 3.3.

######  Proposition C.2.

In the Markovian model, it holds that for any integer $p\geq 2$

$\displaystyle\lvert\bbE[(\operatorname{tr}\bS^{p}$
$\displaystyle)^{2}]-\bbE[(\operatorname{tr}\bG^{p})^{2}]\rvert\leq
60^{2p}p^{3}R(\bX)\Psi(Z)^{2}\varsigma(\bX)^{2}H_{p}(\bX,Z)^{2p-3}$

where $H_{p}(\bX,Z)$ is as in Theorem 3.2.

###### Proof.

By Proposition 6.6 and the product rule

$\displaystyle\frac{\rm{d}}{{\rm{d}}t}$
$\displaystyle\bbE[(\operatorname{tr}\bS(t)^{p})^{2}]=\frac{1}{2}\sum_{k=3}^{2p}\sum_{S\subseteq\\{1,\ldots,k\\}}\frac{t^{\frac{k}{2}-1}}{(k-1)!}\times$
(C.5)
$\displaystyle\bbE\Bigl{[}\sum_{(\rho,\alpha,i)\in\cI_{k,n}}\Delta^{{\text{{$($}{}$\rho,\alpha,i${$)$}}}}\Bigl{(}\Bigl{(}\prod_{j\in
S}\partial_{\bXci_{i,j}}\Bigr{)}\operatorname{tr}\bS(t)^{p}\Bigr{)}\Bigl{(}\Bigl{(}\prod_{j\in\\{1,\ldots,k\\}\setminus
S}\partial_{\bXci_{i,j}}\Bigr{)}\operatorname{tr}\bS(t)^{p}\Bigr{)}\Bigr{]}.$

As in eq. A.5–eq. A.15 in the proof of Proposition A.2 one can now derive that

$\displaystyle\frac{\rm{d}}{{\rm{d}}t}$
$\displaystyle\bbE[(\operatorname{tr}\bS(t)^{p})^{2}]\leq
ct^{\frac{1}{2}}\sum_{k=3}^{2p}(54p)^{k}R(\bX)^{k-2}\Psi(Z)^{k-1}\varsigma(\bX)^{2}\bbE[\operatorname{tr}\bS(t)^{2p}]^{\frac{2p-k}{2p}}$
(C.6)

where $c\vcentcolon=({\rm{e}}^{2+1/12}/36)/2$. The right-hand side of this
inequality occurs in the left-hand side of eq. 6.76. Proceed to the right-hand
side of eq. 6.76 and use eq. C.3, eq. A.4, and the fundamental theorem of
calculus to conclude the proof. ∎

###### Proof of Theorem 3.3.

Precisely as in the proof of Theorem 4.3 this follows by combination of
Theorem 3.2 and Proposition C.2 and the fact that $2^{p+1}+60^{p}\leq 61^{p}$
for $p\geq 3$. ∎

##  Appendix D Proofs concerning block Markov chains

The proofs for Section 7.3 are given before the proofs of Section 7.1 and
Section 7.2 as it will be possible to reuse some tools. We adopt the notation
that was used in Section 7.3. That is,
$\bM=\sqrt{d/n}(\hat{\bN}-\bbE[\hat{\bN}])$, and $\bS$ is the self-adjoint
dilation defined in eq. 7.6.

This section is split in the following main parts. In Section D.1, we estimate
the entries of $\operatorname{Cov}(\bM)$ and use these to provide precise the
estimates on the parameters of $\bS$. We prove Proposition 7.6 in Section D.2.
Finally, the proof of Theorem 7.5 is given in Section D.3 where we also
establish a nonasymptotic concentration inequality in Theorem D.14.

###  D.1 Estimates on the parameters of block Markovian random matrices

For any fixed $d,n\geq 1$, we introduce the following abbreviations

$\displaystyle\mathfrak{c}_{1}$
$\displaystyle\vcentcolon=d\max\Bigl{\\{}\frac{\pi_{v}}{\\#\cV_{v}}:v\in\\{1,\ldots,K\\}\Bigr{\\}},$
(D.1) $\displaystyle\mathfrak{c}_{2}$
$\displaystyle\vcentcolon=d^{2}\max\Bigl{\\{}\frac{\pi_{v}}{\\#\cV_{v}}\frac{\mathbf{p}_{v,w}}{\\#\cV_{w}}:v,w\in\\{1,\ldots,K\\}\Bigr{\\}},$
(D.2) $\displaystyle\mathfrak{c}_{3}$
$\displaystyle\vcentcolon=d^{3}\max\Bigl{\\{}\frac{\pi_{u}}{\\#\cV_{u}}\frac{\mathbf{p}_{u,v}}{\\#\cV_{v}}\frac{\mathbf{p}_{v,w}}{\\#\cV_{w}}:u,v,w\in\\{1,\ldots,K\\}\Bigr{\\}},$
(D.3) $\displaystyle\mathfrak{d}$
$\displaystyle\vcentcolon=d^{2}\max\Bigl{\\{}\Bigl{\lvert}\frac{1}{n}\sum_{t=1}^{n-3}(n-2-t)\frac{(\mathbf{p}^{t})_{u,v}-\pi_{v}}{\\#\cV_{v}}\Bigr{\rvert}\frac{\mathbf{p}_{v,w}}{\\#\cV_{w}}:u,v,w\in\\{1,\ldots,K\\}\Bigr{\\}}.$
(D.4)

It should here be understood that $\mathfrak{d}=0$ if $n-3<1$. An estimate and
an alternative expression for $\mathfrak{d}$ may be found in Lemmas D.5 and
D.6.

######  Lemma D.1.

For any $i,j,k,m\in\\{1,\ldots,d\\}$ it holds that

$\displaystyle\lvert\operatorname{Cov}(\bM)_{ij,km}\rvert$ (D.5)
$\displaystyle\leq\begin{cases}\frac{1}{d}(\mathfrak{c}_{2}+\frac{2}{d^{2}}\mathfrak{c}_{2}^{2}+\frac{2}{d}\mathfrak{c}_{3}+\frac{2}{d^{2}}\mathfrak{c}_{2}\mathfrak{d})&\quad\text{
if }(i,j)=(k,m),\\\
\frac{1}{d^{2}}(\frac{3}{d}\mathfrak{c}_{2}^{2}+2\mathfrak{c}_{3}+\frac{2}{d}\mathfrak{c}_{2}\mathfrak{d})&\quad\text{
if }(i,j)\neq(k,m)\text{ and }(i=m\text{ or }j=k),\\\
\frac{1}{d^{3}}(3\mathfrak{c}_{2}^{2}+2\mathfrak{c}_{2}\mathfrak{d})&\quad\text{
else}.\end{cases}$

Furthermore, if $i\in\cV_{a}$ and $j\in\cV_{b}$ for $a,b\in\\{1,\ldots,K\\}$,
then

$\displaystyle\Bigl{\lvert}\operatorname{Cov}(\bM)_{ij,ij}-d\frac{\pi_{a}\mathbf{p}_{a,b}}{\\#\cV_{a}\\#\cV_{b}}\Bigr{\rvert}\leq\frac{1}{d^{2}}\Bigl{(}\frac{d}{n}\mathfrak{c}_{2}+\frac{2}{d}\mathfrak{c}_{2}^{2}+\mathfrak{c}_{3}+\frac{2}{d}\mathfrak{c}_{2}\mathfrak{d}\Bigr{)}.$
(D.6)

###### Proof.

Recall that the Markov chain of transitions $E=(E_{t})_{t=1}^{n-1}$ is defined
by $E_{t}=(Z_{t},Z_{t+1})$ where $(Z_{t})_{t=1}^{n}$ is the sample path of the
block Markov chain. For any $i,j,k,m\in\\{1,\ldots,n\\}$ we can write

$\displaystyle\operatorname{Cov}(\bM)_{ij,km}=\frac{d}{n}\bbE\Bigl{[}(\hat{\bN}-\bbE[\hat{\bN}])_{i,j}(\hat{\bN}-\bbE[\hat{\bN}])_{k,m}\Bigr{]}$
(D.7) $\displaystyle\
=\frac{d}{n}\sum_{t_{1},t_{2}=1}^{n-1}\bbE\Bigl{[}\mathbbm{1}\\{E_{t_{1}}=(i,j)\\}\mathbbm{1}\\{E_{t_{2}}=(k,m)\\}-\bbP(E_{t_{1}}=(i,j))\bbP(E_{t_{2}}=(k,m))\Bigr{]}$
$\displaystyle\
=\vcentcolon\frac{d}{n}\sum_{t_{1},t_{2}=1}^{n-1}\cE_{t_{1},t_{2}}(i,j,k,m).$

Let us separately consider the case where $t_{1}=t_{2}$, $\lvert
t_{1}-t_{2}\rvert=1$, and $\lvert t_{1}-t_{2}\rvert>1$. If $t_{1}=t_{2}$, then
since the block Markov chain starts from equilibrium it holds for any
$i,j,k,m\in\\{1,\ldots,d\\}$ that

$\displaystyle\frac{d}{n}$
$\displaystyle\sum_{t_{1}=1}^{n-1}\cE_{t_{1},t_{1}}(i,j,k,m)$ (D.8)
$\displaystyle=\begin{cases}-\frac{d(n-1)}{n}\bbP(E_{1}=(i,j))\bbP(E_{1}=(k,m))&\quad\text{
if }(i,j)\neq(k,m),\\\
\frac{d(n-1)}{n}\bigl{(}\bbP(E_{1}=(i,j))-\bbP(E_{1}=(i,j))^{2}\bigr{)}&\quad\text{
if }(i,j)=(k,m),\end{cases}$

It here holds for $i\in\cV_{a}$ and $j\in\cV_{b}$ that

$\displaystyle\bbP(E_{1}=(i,j))=\bbP(Z_{1}=i)\bbP(Z_{2}=j\mid
Z_{1}=i)=\frac{\pi_{a}\mathbf{p}_{a,b}}{\\#\cV_{a}\\#\cV_{b}}\leq\frac{\mathfrak{c}_{2}}{d^{2}}.$
(D.9)

Substitute this bound in eq. D.8 and use that
$\bbP(E_{1}=(i,j))-\bbP(E_{1}=(i,j))^{2}\leq\bbP(E_{1}=(i,j))$ and
$(n-1)/n\leq 1$ to conclude that

$\displaystyle\Bigl{\lvert}\frac{d}{n}$
$\displaystyle\sum_{t_{1}=1}^{n-1}\cE_{t_{1},t_{1}}(i,j,k,m)\Bigr{\rvert}\leq\begin{cases}\frac{1}{d^{3}}\mathfrak{c}_{2}^{2},&\quad\text{
if }(i,j)\neq(k,m),\\\ \frac{1}{d}\mathfrak{c}_{2}&\quad\text{ if
}(i,j)=(k,m).\end{cases}$ (D.10)

Furthermore, for $i\in\cV_{a}$ and $j\in\cV_{b}$,

$\displaystyle\Bigl{\lvert}\frac{d}{n}\sum_{t_{1}=1}^{n-1}\cE_{t_{1},t_{1}}(i,j$
$\displaystyle,i,j)-d\frac{\pi_{a}\mathbf{p}_{a,b}}{\\#\cV_{a}\\#\cV_{b}}\Bigr{\rvert}$
(D.11)
$\displaystyle\leq\Bigl{(}\frac{dn}{n}-\frac{d(n-1)}{n}\Bigr{)}\bbP(E_{1}=(i,j))+\frac{d(n-1)}{n}\bbP(E_{1}=(i,j))^{2}$
$\displaystyle\leq\frac{\mathfrak{c}_{2}}{dn}+\frac{\mathfrak{c}_{2}^{2}}{d^{3}}.$

Now consider the case where $\lvert t_{1}-t_{2}\rvert=1$. Due to symmetry, it
is sufficient to consider the case with $t_{2}=t_{1}+1$. In this case,

$\displaystyle\Bigl{\lvert}\frac{d}{n}\sum_{t_{1}=1}^{n-2}\cE_{t_{1},t_{1}+1}(i,j,k,m)\Bigr{\rvert}$
(D.12)
$\displaystyle=\begin{cases}\frac{d(n-2)}{n}\bbP(E_{1}=(i,j))\bbP(E_{2}=(k,m))&\text{
if }j\neq k,\\\
\frac{d(n-2)}{n}\bigl{\lvert}\bbP(E_{1}=(i,j),E_{2}=(j,m))-\bbP(E_{1}=(i,j))\bbP(E_{2}=(j,m))\bigr{\rvert}&\text{
if }j=k,\end{cases}$
$\displaystyle\leq\begin{cases}\frac{1}{d^{3}}\mathfrak{c}_{2}^{2},&\quad\text{
if }j\neq k,\\\
\frac{1}{d^{2}}(\mathfrak{c}_{3}+\frac{1}{d}\mathfrak{c}_{2}^{2})&\quad\text{
if }j=k.\end{cases}$

Consequently, using a similar estimate for the case $t_{1}=t_{2}+1$,

$\displaystyle\Bigl{\lvert}\frac{d}{n}\sum_{\lvert
t_{1}-t_{2}\rvert=1}\cE_{t_{1},t_{2}}(i,j,k,m)\Bigr{\rvert}\leq\begin{cases}\frac{2}{d^{3}}\mathfrak{c}_{2}^{2},&\
\text{ if }j\neq k\text{ and }i\neq m,\\\
\frac{2}{d^{2}}(\mathfrak{c}_{3}+\frac{1}{d}\mathfrak{c}_{2}^{2})&\ \text{ if
}j=k\text{ or }i=m.\end{cases}$ (D.13)

Finally, consider the case where $\lvert t_{1}-t_{2}\rvert>1$. Then, if
$t_{2}>t_{1}+1$

$\displaystyle\Bigl{\lvert}\frac{d}{n}\sum_{t_{1}=1}^{n-3}\sum_{t_{2}>t_{1}+1}\cE_{t_{1},t_{2}}(i,j,k,m)\Bigr{\rvert}=\Bigl{\lvert}\frac{d}{n}\sum_{s=2}^{n-2}(n-1-s)\cE_{1,1+s}(i,j,k,m)\Bigr{\rvert}$
(D.14)
$\displaystyle=d\bbP(E_{1}=(i,j))\Bigl{\lvert}\sum_{s=2}^{n-2}\frac{n-1-s}{n}\bigl{(}\bbP(E_{1+s}=(k,m)\mid
Z_{2}=j)-\bbP(E_{1+s}=(k,m))\bigr{)}\Bigr{\rvert}$
$\displaystyle=d\bbP(E_{1}=(i,j))\bbP(Z_{2+s}=m\mid Z_{1+s}=k)$
$\displaystyle\qquad\qquad\times\Bigl{\lvert}\sum_{s=2}^{n-2}\frac{n-1-s}{n}\bigl{(}\bbP(Z_{1+s}=k\mid
Z_{2}=j)-\bbP(Z_{1+s}=k)\bigr{)}\Bigr{\rvert}.$

Recall eq. D.4 and note that $\bbP(Z_{1+s}=k\mid
Z_{2}=j)=(\mathbf{p}^{s-1})_{a,b}/\\#\cV_{b}$ for any $j\in\cV_{a}$ and
$k\in\cV_{b}$. A substitution $t=s-1$ hence yields that

$\displaystyle\Bigl{\lvert}\frac{d}{n}\sum_{t_{1}=1}^{n-3}\sum_{t_{2}>t_{1}+1}\cE_{t_{1},t_{2}}(i,j,k,m)\Bigr{\rvert}\leq\frac{1}{d^{3}}\mathfrak{c}_{2}\mathfrak{d}.$
(D.15)

By using a similar estimate for the case $t_{1}>t_{2}+1$ we conclude that

$\displaystyle\Bigl{\lvert}\frac{d}{n}$ $\displaystyle\sum_{\lvert
t_{1}-t_{2}\rvert>1}\cE_{t_{1},t_{2}}(i,j,k,m)\Bigr{\rvert}\leq\frac{2}{d^{3}}\mathfrak{c}_{2}\mathfrak{d}.$
(D.16)

We can now complete the proof by combining the foregoing estimates. Due to eq.
D.7 it holds that

$\displaystyle\lvert\operatorname{Cov}(\bM)_{ij,km}\rvert\leq$
$\displaystyle\Bigl{\lvert}\frac{d}{n}\sum_{t_{1}=1}^{n-1}\cE_{t_{1},t_{1}}(i,j,k,m)\Bigr{\rvert}+\Bigl{\lvert}\frac{d}{n}\sum_{\lvert
t_{1}-t_{2}\rvert=1}\cE_{t_{1},t_{2}}(i,j,k,m)\Bigr{\rvert}$
$\displaystyle+\Bigl{\lvert}\frac{d}{n}\sum_{\lvert
t_{1}-t_{2}\rvert>1}\cE_{t_{1},t_{1}+1}(i,j,k,m)\Bigr{\rvert}.$ (D.17)

Estimate the terms in the right-hand side of eq. D.17 using eq. D.10, eq.
D.13, and eq. D.16 to complete the proof of eq. D.5. Similarly, the proof of
eq. D.6 can be completed by combining eq. D.11, eq. D.13, and eq. D.16
together with the fact that

$\displaystyle\lvert\operatorname{Cov}(\bM)_{ij,ij}-\frac{1}{d}$
$\displaystyle\frac{\pi_{a}\mathbf{p}_{a,b}}{\\#\cV_{a}\\#\cV_{b}}\rvert\leq\Bigl{\lvert}\frac{d}{n}\sum_{t_{1}=1}^{n-1}\cE_{t_{1},t_{1}}(i,j,k,m)-\frac{1}{d}\frac{\pi_{a}\mathbf{p}_{a,b}}{\\#\cV_{a}\\#\cV_{b}}\Bigr{\rvert}$
(D.18) $\displaystyle+\Bigl{\lvert}\frac{d}{n}\sum_{\lvert
t_{1}-t_{2}\rvert=1}\cE_{t_{1},t_{2}}(i,j,i,j)\Bigr{\rvert}+\Bigl{\lvert}\frac{d}{n}\sum_{\lvert
t_{1}-t_{2}\rvert>1}\cE_{t_{1},t_{1}+1}(i,j,i,j)\Bigr{\rvert}.$

This concludes the proof. ∎

Let $C\vcentcolon=(C_{t})_{t=1}^{n}$ denote the sequence of clusters
associated with $(Z_{t})_{t=1}^{n}$, i.e., the Markov chain with state space
$\\{1,\ldots,K\\}$ for which $C_{t}=k$ if and only if $Z_{t}\in\cV_{k}$. By
Lemma B.2, one can express $\Psi(C)$ more explicitly as

$\displaystyle\Psi(C)\vcentcolon=\min\Bigl{\\{}n,\,\min\Bigl{\\{}t\geq
1:\max_{i,j\in\\{1,\ldots,K\\}}\Bigl{\lvert}\,\frac{(\mathbf{p}^{t})_{i,j}-\pi_{j}}{\pi_{j}}\,\Bigr{\rvert}\leq\frac{1}{4}\Bigr{\\}}\Bigr{\\}}.$
(D.19)

We next show that one can estimate $\Psi(E)$ in terms of $\Psi(C)$.

######  Lemma D.2.

It holds that $\Psi(Z)=\Psi(C).$

###### Proof.

For any $i\in\cV_{a}$ and $j\in\cV_{b}$ it holds that $\bbP(Z_{1+t}=j\mid
Z_{1}=i)=(\mathbf{p}^{t})_{a,b}/\\#\cV_{b}$. Consequently, due to Lemma B.2

$\displaystyle\Psi(Z)$ $\displaystyle=\min\Bigl{\\{}n,\,\min\Bigl{\\{}t\geq
1:\max_{a,b\in\\{1,\ldots,K\\}}\Bigl{\lvert}\,\frac{\mathbf{p}^{t}_{a,b}/\\#\cV_{b}-\pi_{b}/\\#\cV_{b}}{\pi_{b}/\\#\cV_{b}}\,\Bigr{\rvert}\leq\frac{1}{4}\Bigr{\\}}\Bigr{\\}}$
(D.20) $\displaystyle=\Psi(C).$

∎

######  Lemma D.3.

It holds that $\Psi(E)\leq\Psi(Z)+1$.

###### Proof.

Note that for any $t>1$ and $i,j,k,m\in\\{1,\ldots,d\\}$, since $Z$ is
stationary

$\displaystyle\bbP\bigl{(}E_{1+t}=(i,j)$ $\displaystyle\mid
E_{1}=(k,m)\bigr{)}$ (D.21) $\displaystyle=\bbP(Z_{1+t}=i\mid
Z_{2}=m)\bbP(Z_{t+2}=j\mid Z_{t+1}=i)$ $\displaystyle=\bbP(Z_{1+t-1}=i\mid
Z_{1}=m)\bbP(Z_{t+2}=j\mid Z_{t+1}=i).$

Furthermore, since $Z$ starts in equilibrium the same holds for $E$ and the
equilibrium distribution of $E$ is given by

$\displaystyle\bbP(E_{1}=(i,j))$ $\displaystyle=\bbP(Z_{1}=i)\bbP(Z_{2}=j\mid
Z_{1}=i)$ (D.22) $\displaystyle=\bbP(Z_{t+1}=i)\bbP(Z_{t+2}=j\mid Z_{t+1}=i).$

Hence, for any $t>1$, it holds that

$\displaystyle\max_{i,j,k,m\in\\{1,\ldots,d\\}}\Bigl{\lvert}\,\frac{\bbP(E_{1+t}=(i,j)\mid
E_{1}=(k,m))-\bbP(E_{1+t}=(i,j))}{\bbP(E_{1+t}=(i,j))}\,\Bigr{\rvert}\leq\frac{1}{4}\Bigr{\\}}$
(D.23)
$\displaystyle=\max_{i,m\in\\{1,\ldots,d\\}}\Bigl{\lvert}\,\frac{\bbP(Z_{1+t-1}=i\mid
Z_{1}=m)-\bbP(Z_{1+t-1}=i)}{\bbP(Z_{t+1}=i)}\,\Bigr{\rvert}\leq\frac{1}{4}\Bigr{\\}}.$

The desired result now follows from Lemma B.2. ∎

######  Lemma D.4.

With $\bS$, $\bX$, and $E$ as in eq. 7.6–eq. 7.7 it holds that

$\displaystyle R(\bX)\leq 2\sqrt{d/n},\qquad\Psi(E)\leq\Psi$
$\displaystyle(C)+1,\qquad\varsigma(\bX)^{2}\leq\mathfrak{c}_{1},$
$\displaystyle\sigma(\bS)^{2}\leq\mathfrak{g},\qquad$ $\displaystyle\qquad
v(\bS)^{2}\leq d^{-1}\mathfrak{v}.$

where $\mathfrak{g}$ and $\mathfrak{v}$ satisfy

$\displaystyle\mathfrak{g}$
$\displaystyle\leq\mathfrak{c}_{1}+\frac{1}{d}\bigl{(}11\mathfrak{c}_{2}^{2}+6\mathfrak{c}_{3}+8\mathfrak{c}_{2}\mathfrak{d}\bigr{)},$
(D.24) $\displaystyle\mathfrak{v}$ $\displaystyle\leq
2\Bigl{(}(\mathfrak{c}_{2}+3\mathfrak{c}_{2}^{2}+4\mathfrak{c}_{3}+2\mathfrak{c}_{2}\mathfrak{d})+\frac{1}{d}(2\mathfrak{c}_{3}+8\mathfrak{c}_{2}^{2}+6\mathfrak{c}_{2}\mathfrak{d})\Bigr{)}.$
(D.25)

###### Proof.

The estimate $R(\bX)\leq 2\sqrt{d/n}$ is immediate from the definition eq. 7.7
of the matrices $\bX_{t}$. Similarly, the estimate on $\Psi(E)$ is immediate
from the combination of Lemmas D.2 and D.3.

We next consider the estimation of $\varsigma(\bX)$. Note that the random
matrices $\bX_{t}$ are identically distributed due to the assumption that the
block Markov chain starts in equilibrium. Hence, also using that for any self-
adjoint random matrix $\bA$ one has
$\bbE[(\bA-\bbE[\bA])^{2}]=\bbE[\bA^{2}]-\bbE[\bA]^{2}\preceq\bbE[\bA^{2}]$
where $\preceq$ denotes the positive semidefinite order,

$\displaystyle\sum_{t=1}^{n-1}\bbE[\bX_{t}^{2}]$
$\displaystyle=(n-1)\bbE[\bX_{1}^{2}]$ (D.26) $\displaystyle\preceq
d\sum_{i,j=1}^{d}\bbP(E_{1}=(i,j))\begin{pmatrix}0&e_{i}e_{j}^{\rm T}\\\
e_{j}e_{i}^{\rm T}&0\end{pmatrix}^{2}$
$\displaystyle=d\sum_{i=1}^{d}\bbP(Z_{1}=i)\begin{pmatrix}e_{i}e_{i}^{\rm
T}&0\\\ 0&0\end{pmatrix}+d\sum_{j=1}^{d}\bbP(Z_{2}=j)\begin{pmatrix}0&0\\\
0&e_{j}e_{j}^{\rm T}\end{pmatrix}.$

Since the operator norm of a positive diagonal matrix is its maximal element,
it follows that

$\displaystyle\varsigma(\bX)^{2}$
$\displaystyle\leq\max\Bigl{\\{}\pi_{k}\frac{d}{\\#\cV_{k}}:k=1,\ldots,K\Bigr{\\}}=\mathfrak{c}_{1}.$
(D.27)

This proves the claimed estimate on $\varsigma(\bX)^{2}$.

We next consider the estimate on $v(\bS)^{2}$. By [7, Lemma 4.10] one has that

$\displaystyle v(\bS)^{2}\leq 2\|\operatorname{Cov}(\bM)\|.$ (D.28)

Let $\operatorname{Cov}(\bM)^{+}$ denote the matrix which is found by
replacing all entries of $\operatorname{Cov}(\bM)$ by their absolute values
and note that
$\|\operatorname{Cov}(\bM)\|\leq\|\operatorname{Cov}(\bM)^{+}\|$. The spectral
radius of $\operatorname{Cov}(\bM)^{+}$ is equal to its operator norm since
this matrix is self-adjoint. Hence, by the upper bound in the Perron–Frobenius
theorem [17, Equation (37), Page 63]

$\displaystyle\|\operatorname{Cov}(\bM)\|$
$\displaystyle\leq\max_{i,j=1,\ldots,d}\sum_{k,m=1}^{d}\lvert\operatorname{Cov}(\bM)_{ij,km}\rvert.$
(D.29)

For any fixed $i,j$ there is precisely one term in eq. D.29 with
$(k,m)=(i,j)$; at most $2d$ terms with $(k,m)\neq(i,j)$ but $i=m$ or $j=k$;
and at most $d^{2}$ remaining terms. The combination of eq. D.29 and eq. D.5
yields that $v(\bS)^{2}\leq d^{-1}\mathfrak{v}$ with

$\displaystyle\mathfrak{v}\vcentcolon=2\Bigl{(}$
$\displaystyle\Bigl{(}\mathfrak{c}_{2}+\frac{2}{d^{2}}\mathfrak{c}_{2}^{2}+\frac{2}{d}\mathfrak{c}_{3}+\frac{2}{d^{2}}\mathfrak{c}_{2}\mathfrak{d}\Bigr{)}$
(D.30)
$\displaystyle\qquad+2\Bigl{(}\frac{3}{d}\mathfrak{c}_{2}^{2}+2\mathfrak{c}_{3}+\frac{2}{d}\mathfrak{c}_{2}\mathfrak{d}\Bigr{)}+\Bigl{(}3\mathfrak{c}_{2}^{2}+2\mathfrak{c}_{2}\mathfrak{d}\Bigr{)}\Bigr{)}.$

Reorder the terms and use that $1/d^{2}\leq 1/d$ to conclude the proof of the
estimate on $v(\bS)^{2}$.

We next consider the estimate on $\sigma(\bS)^{2}$. By a direct computation,

$\displaystyle\bS^{2}=\begin{pmatrix}\bM\bM^{{\rm T}}&0\\\ 0&\bM^{{\rm
T}}\bM\end{pmatrix}.$ (D.31)

Consequently, taking expectations and the operator norm on both sides,
$\sigma(\bS)^{2}=\max\\{\|\bA\|,\allowbreak\|\bB\|\\}$ where $\bA$ and $\bB$
are the self-adjoint $d\times d$ matrices whose entries are given by

$\displaystyle\bA_{i,j}=\sum_{\ell=1}^{d}\operatorname{Cov}(\bM)_{i\ell,j\ell},\qquad\bB_{i,j}=\sum_{\ell=1}^{d}\operatorname{Cov}(\bM)_{\ell
i,\ell j}.$ (D.32)

We consider the diagonal and the off-diagonal terms of these matrices
separately. First, consider the case where $i\neq j$. Then,
$(i,\ell)\neq(j,\ell)$ and $(\ell,i)\neq(\ell,j)$ for all
$\ell\in\\{1,\ldots,d\\}$. Hence, using eq. D.5 with separate consideration of
the case where $i=\ell$ or $j=\ell$

$\displaystyle\lvert\bA_{i,j}\rvert$
$\displaystyle\leq\frac{2}{d^{2}}\Bigl{(}\frac{3}{d}\mathfrak{c}_{2}^{2}+2\mathfrak{c}_{3}+\frac{2}{d}\mathfrak{c}_{2}\mathfrak{d}\Bigr{)}+\frac{d}{d^{3}}(3\mathfrak{c}_{2}^{2}+2\mathfrak{c}_{2}\mathfrak{d}),$
(D.33) $\displaystyle\lvert\bB_{i,j}\rvert$
$\displaystyle\leq\frac{2}{d^{2}}\Bigl{(}\frac{3}{d}\mathfrak{c}_{2}^{2}+2\mathfrak{c}_{3}+\frac{2}{d}\mathfrak{c}_{2}\mathfrak{d}\Bigr{)}+\frac{d}{d^{3}}(3\mathfrak{c}_{2}^{2}+2\mathfrak{c}_{2}\mathfrak{d}).$
(D.34)

For the case with $i=j$ we can get a slightly refined leading-order term if we
replace eq. D.10 by the following estimate:

$\displaystyle\Bigl{\lvert}\frac{d}{n}\sum_{\ell=1}^{d}\sum_{t_{1}=1}^{n-1}\cE_{t_{1},t_{1}}(i,\ell,i,\ell)\Bigr{\rvert}$
$\displaystyle=\frac{d(n-1)}{n}\sum_{\ell=1}^{d}\bigl{(}\bbP(E_{1}=(i,\ell))-\bbP(E_{1}=(i,\ell))^{2}\bigr{)}$
(D.35) $\displaystyle\leq d\bbP(Z_{1}=i)\leq\mathfrak{c}_{1}.$

It was here used that $\bbP(E_{1}=(i,\ell))\geq\bbP(E_{1}=(i,\ell))^{2}$. Now
observe that by eq. D.7,

$\displaystyle\Bigl{\lvert}\sum_{\ell=1}^{d}\operatorname{Cov}(\bM)_{i\ell,i\ell}\Bigr{\rvert}\leq$
$\displaystyle\Bigl{\lvert}\frac{d}{n}\sum_{\ell=1}^{d}\sum_{t_{1}=1}^{n-1}\cE_{t_{1},t_{1}}(i,\ell,i,\ell)\Bigr{\rvert}+\Bigl{\lvert}\frac{d}{n}\sum_{\ell=1}^{d}\sum_{\lvert
t_{1}-t_{2}\rvert=1}\cE_{t_{1},t_{2}}(i,\ell,i,\ell)\Bigr{\rvert}$
$\displaystyle+\Bigl{\lvert}\frac{d}{n}\sum_{\ell=1}^{d}\sum_{\lvert
t_{1}-t_{2}\rvert>1}\cE_{t_{1},t_{1}+1}(i,\ell,i,\ell)\Bigr{\rvert}.$ (D.36)

Hence, by using eq. D.13, eq. D.16, and eq. D.35 in eq. D.36

$\displaystyle\lvert\bA_{i,i}\rvert\leq\mathfrak{c}_{1}+\frac{1}{d}\Bigl{(}\frac{2}{d}\mathfrak{c}_{2}^{2}+2\mathfrak{c}_{3}+\frac{2}{d}\mathfrak{c}_{2}\mathfrak{d}\Bigr{)}$
(D.37)

Exactly the same estimate applies to $\lvert\bB_{i,i}\rvert$. Now reduce to an
application of the Perron-Frobenius theorem as in eq. D.29 to conclude that
$\sigma(\bS)^{2}\leq\mathfrak{g}$ with

$\displaystyle\mathfrak{g}=\mathfrak{c}_{1}$
$\displaystyle+\frac{1}{d}\Bigl{(}\frac{2}{d}\mathfrak{c}_{2}^{2}+2\mathfrak{c}_{3}+\frac{2}{d}\mathfrak{c}_{2}\mathfrak{d}\Bigr{)}$
(D.38)
$\displaystyle+\frac{1}{d}\Bigl{(}2\Bigl{(}\frac{3}{d}\mathfrak{c}_{2}^{2}+2\mathfrak{c}_{3}+\frac{2}{d}\mathfrak{c}_{2}\mathfrak{d}\Bigr{)}+(3\mathfrak{c}_{2}^{2}+2\mathfrak{c}_{2}\mathfrak{d})\Bigr{)}.$

Finally, reorder the terms and use that $1/d\leq 1$ to conclude the proof. ∎

We next prove estimates on the parameters in eq. D.1–eq. D.4. Define a
parameter by

$\displaystyle\hat{\alpha}_{\min}\vcentcolon=\min\Bigl{\\{}\frac{\\#\cV_{k}}{d}:k\in\\{1,\ldots,K\\}\Bigr{\\}}.$
(D.39)

######  Lemma D.5.

For any $i\in\\{1,2,3\\}$ it holds that
$\mathfrak{c}_{i}\leq\hat{\alpha}_{\min}^{-i}$ and
$\mathfrak{d}\leq\frac{4}{3}\Psi(C)\hat{\alpha}_{\min}^{-2}$.

###### Proof.

The estimate $\mathfrak{c}_{i}\leq\hat{\alpha}_{\min}^{-i}$ is immediate from
the definitions eq. D.1–eq. D.3 and the fact that $\pi_{v}\leq 1$ and
$\mathbf{p}_{v,w}\leq 1$ for all $v,w\in\\{1,\ldots,K\\}$. We proceed to the
estimate on $\mathfrak{d}$.

For any $u,v,w\in\\{1,\ldots,K\\}$ it follows from the triangle inequality
together the estimates $\\#\cV_{v}/d\geq\hat{\alpha}_{\min}$ and
$\mathbf{p}_{v,w}\leq 1$ that

$\displaystyle\Bigl{\lvert}\frac{1}{n}\sum_{t=1}^{n-2}(n-2-t)$
$\displaystyle\frac{(\mathbf{p}^{t})_{u,v}-\pi_{v}}{\\#\cV_{v}}\Bigr{\rvert}\frac{\mathbf{p}_{v,w}}{\\#\cV_{w}}\leq\sum_{t=1}^{n-2}\Bigl{\lvert}\frac{(\mathbf{p}^{t})_{u,v}-\pi_{v}}{\\#\cV_{v}}\Bigr{\rvert}\frac{\mathbf{p}_{v,w}}{\\#\cV_{w}}$
(D.40) $\displaystyle\leq
d^{-2}\hat{\alpha}_{\min}^{-2}\Bigl{(}(\Psi(C)-1)+\sum_{t=\Psi(C)}^{\infty}\bigl{\lvert}(\mathbf{p}^{t})_{u,v}-\pi_{v}\bigr{\rvert}\Bigr{)}.$

Due to Lemma B.1, and the fact that $\pi_{v}\leq 1$, one can relate the right-
hand side of eq. D.40 to the $\psi$-dependence coefficient:

$\displaystyle\max\Bigl{\\{}\lvert(\mathbf{p}^{t})_{u,v}-\pi_{v}\rvert:u,v\in\\{1,\ldots,K\\}\Bigr{\\}}$
$\displaystyle\leq\max\Bigl{\\{}\frac{\lvert(\mathbf{p}^{t})_{u,v}-\pi_{v}\rvert}{\pi_{v}}:u,v\in\\{1,\ldots,K\\}\Bigr{\\}}$
$\displaystyle=\psi(C_{1+t}\mid C_{1}).$ (D.41)

Due to Proposition 6.2 it hence follows that

$\displaystyle\mathfrak{d}$
$\displaystyle\leq\hat{\alpha}_{\min}^{-2}\Bigl{(}(\Psi(C)-1)+\sum_{t=\Psi(C)}^{\infty}\Bigl{(}\frac{1}{4}\Bigr{)}^{\lfloor
t/\Psi(C)\rfloor}\Bigr{)}$ (D.42)
$\displaystyle=\hat{\alpha}_{\min}^{-2}\Bigl{(}(\Psi(C)-1)+\Psi(C)\sum_{s=1}^{\infty}\Bigl{(}\frac{1}{4}\Bigr{)}^{s}\Bigr{)}.$

Use that $\sum_{t=1}^{\infty}(1/4)^{t}=1/3$ to conclude the proof. ∎

Evaluation of the definition of $\mathfrak{d}$ may appear daunting as it
involves a large sum; recall eq. D.4. The following lemma provides an
alternative exact expression.

######  Lemma D.6.

Let $\Pi$ denote the $K\times K$ matrix whose entries are given by
$\Pi_{i,j}=\pi_{j}$, assume that $n\geq 4$, and consider the $K\times K$
matrix given by

$\displaystyle\mathbf{q}\vcentcolon=\frac{1}{n}(\mathbf{p}-\Pi-\mathbf{1})^{-2}\Bigl{(}(\mathbf{p}-\Pi)^{n-1}-(n-2)(\mathbf{p}-\Pi)^{2}+(n-3)(\mathbf{p}-\Pi)\Bigr{)}.$

Then, it holds that

$\displaystyle\mathfrak{d}$
$\displaystyle=d^{2}\max\Bigl{\\{}\frac{\lvert\mathbf{q}_{u,v}\rvert}{\\#\cV_{v}}\frac{\mathbf{p}_{v,w}}{\\#\cV_{w}}:u,v,w\in\\{1,\ldots,K\\}\Bigr{\\}}.$

###### Proof.

For any scalar $x\neq 1$ it holds that
$\sum_{t=0}^{n}x^{t}=(x^{n+1}-1)/(x-1)$. By taking the derivative of this
identity, one further finds that
$\sum_{t=0}^{n-1}(t+1)x^{t}=(nx^{n+1}-(n+1)x^{n}+1)/(x-1)^{2}$. Consequently,
for any $x\neq 1$,

$\displaystyle\sum_{t=1}^{n-3}(n-2-t)x^{t}$
$\displaystyle=(n-2)\sum_{t=1}^{n-3}x^{t}-\sum_{t=1}^{n-3}tx^{t}$ (D.43)
$\displaystyle=(n-2)x\sum_{t=0}^{n-4}x^{t}-x\sum_{t=0}^{n-4}(t+1)x^{t}$
$\displaystyle=(n-2)\frac{x^{n-2}-x}{x-1}-\frac{(n-3)x^{n-1}-(n-2)x^{n-2}+x}{(x-1)^{2}}$
$\displaystyle=\frac{x^{n-1}-(n-2)x^{2}+(n-3)x}{(x-1)^{2}}.$

The assumption that $\mathbf{p}$ defines an ergodic Markov chain implies that
all eigenvalues of $\mathbf{p}-\Pi$ differ from one. It hence follows from eq.
D.43 that

$\displaystyle\frac{1}{n}\sum_{t=1}^{n-3}(n-2-t)(\mathbf{p}-\Pi)^{t}=\mathbf{q}.$
(D.44)

Next remark that $\Pi=j\pi^{{\rm T}}$ where $j=(1,\ldots,1)^{{\rm T}}$ is the
all-ones vector. In particular, $\Pi^{2}=\Pi$. Further, $\mathbf{p}\Pi=\Pi$
and $\Pi\mathbf{p}=\Pi$ since $\pi$ and $j$ are respectively left and right
eigenvectors of $\mathbf{p}$ with eigenvalue $1$. It follows that

$\displaystyle(\mathbf{p}-\Pi)^{2}=\mathbf{p}^{2}-\Pi\mathbf{p}-\mathbf{p}\Pi+\Pi^{2}=\mathbf{p}^{2}-\Pi.$
(D.45)

Proceed similarly, using induction on $t$, to conclude that
$(\mathbf{p}-\Pi)^{t}=\mathbf{p}^{t}-\Pi$ for all $t\geq 1$. The desired
result now follows by comparing eq. D.44 and eq. D.4. ∎

###  D.2 Convergence of singular value distributions

Recall the definition of the empirical singular value and eigenvalue
distributions from eq. 7.9 and eq. 7.2, respectively. Further, recall that
$\bS$ was defined by a self-adjoint dilation in eq. 7.6. It follows that
$\mu_{\bS}=\operatorname{sym}(\nu_{\bM})$. We subsequently rely on the well
known moment method to establish the limiting law of $\mu_{\bS}$. We state the
moment method as a lemma for the sake of clarity.

######  Lemma D.7.

Consider a sequence of self-adjoint random matrices $(\bS_{i})_{i=1}^{\infty}$
and let $\mu$ be a deterministic compactly supported probability measure on
$\bbR$. If for every positive integer $p\geq 1$

$\displaystyle\lim_{i\to\infty}\bbE[\operatorname{tr}\bS_{i}^{p}]=\int
x^{p}{\rm d}\mu(x)\qquad\text{ and
}\qquad\lim_{i\to\infty}\operatorname{Var}[\operatorname{tr}\bS_{i}^{p}]=0,$

then $\mu_{\bS_{i}}$ converges weakly in probability to $\mu$ as $i$ tends to
infinity.

###### Proof.

The proof of this lemma is implicit in the usual proof of the Wigner
semicircle law; see [2, Section 2.1.2]. ∎

######  Lemma D.8.

If $\lim_{d\to\infty}d/n=0$, then for every positive integer $p\geq 1$

$\displaystyle\lim_{d\to\infty}\lvert\bbE[\operatorname{tr}\bS^{p}]-\bbE[\operatorname{tr}\bG^{p}]\rvert=0\quad\text{
and
}\quad\lim_{d\to\infty}\lvert\operatorname{Var}[\operatorname{tr}\bS^{p}]-\operatorname{Var}[\operatorname{tr}\bG^{p}]\rvert=0.$

###### Proof.

Using that $\liminf_{d\to\infty}\min\\{\\#\cV_{k}/d:k=1,\ldots,K\\}>0$ in the
considered limiting regime as well as the assumption that
$\lim_{d\to\infty}d/n=0$ it follows from Lemmas D.4 and D.5 that

$\displaystyle\limsup_{d\to\infty}R(\bX)=0,\qquad$
$\displaystyle\qquad\limsup_{d\to\infty}\Psi(E)<\infty,$ (D.46)
$\displaystyle\limsup_{d\to\infty}\varsigma(\bX)^{2}<\infty,\qquad\limsup_{d\to\infty}\sigma$
$\displaystyle(\bS)^{2}<\infty,\qquad\limsup_{d\to\infty}v(\bS)^{2}=0.$

Consequently, since $\bX_{0}=\bbE[\bS]=0$, the parameter $H_{p}(\bX,E)$ from
Theorem 3.2 satisfies

$\displaystyle\limsup_{d\to\infty}H_{p}(\bX,E)=\limsup_{d\to\infty}\sigma(\bS)<\infty.$
(D.47)

The desired result now follows from Theorems 3.2 and 3.3 together with the
fact that, by definition of a Gaussian model,
$\operatorname{Var}[\operatorname{tr}\bS]=\operatorname{Var}[\operatorname{tr}\bG]$
and $\bbE[\operatorname{tr}\bS^{p}]=\bbE[\operatorname{tr}\bG^{p}]$ for $p\leq
2$. ∎

In order to prove Proposition 7.6 it is now sufficient to consider the
empirical eigenvalue distribution of the Gaussian model. To this end, we apply
a universality principle from [40, Theorem 4.2]. Let us note that this
universality principle is not directly applicable to $\bS$ because the
sparsity causes heavy-tailed entries when $n\ll d^{2}$.

For any positive semidefinite $D\times D$ matrix $\Sigma\succcurlyeq 0$ we
define the following parameter measuring the size of the off-diagonal terms:

$\displaystyle\epsilon(\Sigma)\vcentcolon=\max\bigl{\\{}\lvert\Sigma_{i,j}\rvert:i\neq
j,\ i,j\in\\{1,\ldots,D\\}\bigr{\\}}.$ (D.48)

The following lemma is used to verify a condition in [40].

######  Lemma D.9.

Fix a positive integer $D\geq 1$ and positive scalars $\ell,u>0$ and define a
set of positive semidefinite matrices by

$\displaystyle\fS_{D}(\ell,u)\vcentcolon=\Bigl{\\{}\Sigma\in\bbR^{D\times
D}:\Sigma\succcurlyeq 0\text{ and }\ell\leq\Sigma_{i,i}\leq u\text{ for all
}i\in\\{1,\ldots,D\\}\Bigr{\\}}.$

Then, for any nonnegative integers $0\leq r\leq D$ and $p_{1},\ldots,p_{D}\geq
0$ with $p_{i}=1$ for $i\in\\{1,\ldots,r\\}$ there exists a $C>0$ such that
for any mean-zero Gaussian vector $g$ with covariance matrix
$\Sigma\in\fS_{D}(\ell,u)$

$\displaystyle\bigl{\lvert}\bbE\bigl{[}g_{1}^{p_{1}}g_{2}^{p_{2}}\cdots
g_{D}^{p_{D}}\bigr{]}\bigr{\rvert}\leq C\epsilon(\Sigma)^{\frac{r}{2}}$ (D.49)

and

$\displaystyle\lvert\bbE[g_{1}^{2}\cdots
g_{D}^{2}]-\bbE[g_{1}^{2}]\cdots\bbE[g_{D}^{2}]\rvert\leq
C\epsilon(\Sigma)^{2}.$ (D.50)

###### Proof.

We proceed by induction on $D$. The base case $D=1$ is immediate from the
assumption that $\bbE[g_{1}]=0$. Now let $D>1$ and assume that the result is
known to hold true for all strictly smaller values of $D$. The general idea in
the inductive step is to exploit that the conditional distribution of $g_{1}$
given $g_{2},\ldots,g_{D}$ is explicit; see [15, Proposition 3.13]. We start
with some preliminary reductions and estimates.

First, we claim that it is sufficient to show that there exists some
$0<\varepsilon<1$ such that eq. D.49 and eq. D.50 hold on the subset
$\fS_{D}(\ell,u,\varepsilon)\subseteq\fS_{D}(\ell,u)$ defined by

$\displaystyle\fS_{D}(\ell,u,\varepsilon)\vcentcolon=\Bigl{\\{}\Sigma\in\fS_{D}(\ell,u):\epsilon(\Sigma)\leq\varepsilon\Bigr{\\}}.$
(D.51)

Indeed, due to Hölder’s inequality and the inequality
$\bbE[g_{i}^{2p}]=(\prod_{i=0}^{p-1}(2p-2i-1))\operatorname{Var}[g_{i}]^{p}\leq(2p)^{2p}u^{p}$
which holds due to $g_{i}$ being Gaussian, one can find a constant $\tilde{C}$
depending only on $p_{1},\ldots,p_{D}$ and $u$ such that
$\bigl{\lvert}\bbE\bigl{[}g_{1}^{p_{1}}g_{2}^{p_{2}}\cdots
g_{D}^{p_{D}}\bigr{]}\bigr{\rvert}\leq\tilde{C}$, $\bbE[g_{1}^{2}\cdots
g_{D}^{2}]\leq\tilde{C}$ and
$\bbE[g_{1}^{2}]\cdots\bbE[g_{D}^{2}]\leq\tilde{C}$. By taking $C$ to be
sufficiently large it can be ensured that
$C\max\\{\varepsilon^{D/2},\varepsilon^{2}\\}\geq 2\tilde{C}$ from which it
follows that eq. D.49 and eq. D.50 hold on
$\fS_{D}(\ell,u)\setminus\fS_{D}(\ell,u,\varepsilon)$. Note that the case
where $r=0$ in eq. D.49 is now also ensured to be true.

Second, we consider the partition of $\Sigma$ defined by

$\displaystyle\Sigma=\begin{pmatrix}\Sigma_{1,1}&V\\\ V^{{\rm
T}}&\Xi\end{pmatrix}$ (D.52)

with $V=(\Sigma_{1,2},\ldots,\Sigma_{1,D})$ and
$\Xi\in\bbR^{(D-1)\times(D-1)}$. Then, we claim that there exists some
$\varepsilon>0$ such that, for every $\Sigma\in\fS_{D}(\ell,u,\varepsilon)$,
it holds that $\Xi$ is invertible and that we have the following estimates:

$\displaystyle\|V\|\leq\epsilon(\Sigma)D\qquad\text{ and
}\qquad\|\Xi^{-1}\|\leq 2\ell^{-1}.$ (D.53)

Indeed, the estimate on $\|V\|$ is immediate from the triangle inequality for
the $L^{2}$-norm on $\bbR^{D-1}$ where we used that $D-1\leq D$. The bound
regarding $\Xi^{-1}$ are immediate in the special case where $\Sigma$ is
diagonal due to the assumption that $\Sigma_{i,i}\geq\ell$. The general case
follows from the continuity of matrix inversion in the neighborhood of an
invertible matrix together with the compactness of the set
$\\{\bM\in\bbR^{D\times D}:\ell\leq\bM_{i,i}\leq u,\ \bM_{i,j}=0\text{ for
}i\neq j\\}$. From here on, we fix such a value of $\varepsilon$ and assume
that $\Sigma\in\fS_{D}(\ell,u,\varepsilon)$.

Finally, let us observe that if we define a row vector
$W=(W_{2},\ldots,W_{D})$ by $W\vcentcolon=V\Xi^{-1}$ and a scalar by
$Z=V\Xi^{-1}V^{{\rm T}}$ then the following estimates hold

$\displaystyle\lvert W_{j}\rvert$ $\displaystyle\leq\|V\|\|\Xi^{-1}\|\leq
2D\ell^{-1}\epsilon(\Sigma)$ (D.54) $\displaystyle\lvert Z\rvert$
$\displaystyle\leq\|V\|^{2}\|\Xi^{-1}\|\leq
2D^{2}\ell^{-1}\epsilon(\Sigma)^{2}$ (D.55)

for any $j\in\\{2,\ldots,D\\}$ and any $\Sigma\in\fS_{D}(\ell,u,\varepsilon)$.
This concludes the preliminary estimates.

We now proceed to the proof of eq. D.49. Recall that the case with $r=0$ is
covered by the first preliminary reduction. It is hence sufficient to prove
eq. D.49 in the case where $r>0$ meaning that $p_{1}=1$. By the explicit
expression for the conditional expectation of a Gaussian from [15, Proposition
3.13] it holds that

$\displaystyle\bbE[g_{1}\mid g_{2},\ldots,g_{D}]$
$\displaystyle=\sum_{j=2}^{D}W_{j}g_{j}.$ (D.56)

Hence, by the law of total expectation and the triangle inequality it follows
that

$\displaystyle\bigl{\lvert}\bbE\bigl{[}g_{1}g_{2}^{p_{2}}\cdots
g_{D}^{p_{D}}\bigr{]}\bigr{\rvert}$
$\displaystyle=\Bigl{\lvert}\bbE\Bigl{[}\bbE[g_{1}\mid
g_{2},\ldots,g_{D}]g_{2}^{p_{2}}\cdots
g_{D}^{p_{D}}\Bigr{]}\Bigr{\rvert}\leq\sum_{j=2}^{D}\lvert
W_{j}\bbE[g_{j}g_{2}^{p_{2}}\cdots g_{D}^{p_{D}}]\rvert.$ (D.57)

Note that, since $j\geq 2$, the expression $g_{j}g_{2}^{p_{2}}\cdots
g_{D}^{p_{D}}$ does not depend on $g_{1}$. Hence, by applying the induction
hypothesis on the $(D-1)$-dimensional vector $(g_{2},g_{3},\ldots,g_{D})$,
there exists a constant $C^{\prime}>0$ such that for any
$j\in\\{2,\ldots,D\\}$

$\displaystyle\lvert\bbE[g_{j}g_{2}^{p_{2}}\cdots g_{D}^{p_{D}}]\rvert\leq
C^{\prime}\epsilon(\Sigma)^{\frac{r-1-\mathbbm{1}\\{j\leq r\\}}{2}}\leq
C^{\prime}\epsilon(\Sigma)^{\frac{r}{2}-1}.$ (D.58)

Combine eq. D.54, eq. D.57, and eq. D.58 to conclude that eq. D.49 holds true.

It remains to prove eq. D.50. By the decomposition
$\bbE[X^{2}]=\operatorname{Var}[X]+\bbE[X]^{2}$ together with the explicit
expression for the conditional variance and expectation of a Gaussian from
[15, Proposition 3.13]

$\displaystyle\bbE[g_{1}^{2}\mid g_{2},\ldots,g_{D}]-\bbE[g_{1}^{2}]$
$\displaystyle=\operatorname{Var}[g_{1}\mid
g_{2},\ldots,g_{D}]-\operatorname{Var}[g_{1}]+\bbE[g_{1}\mid
g_{2},\ldots,g_{D}]^{2}$
$\displaystyle=-Z+\sum_{j_{1},j_{2}=2}^{D}W_{j_{1}}W_{j_{2}}g_{j_{1}}g_{j_{2}}.$
(D.59)

Consequently, by the law of total expectation and the triangle inequality

$\displaystyle\lvert\bbE[g_{1}^{2}g_{2}^{2}\cdots g_{D}^{2}]-\bbE[$
$\displaystyle g_{1}^{2}]\bbE[g_{2}^{2}\cdots
g_{D}^{2}]\rvert=\lvert\bbE[(\bbE[g_{1}^{2}\mid
g_{2},\ldots,g_{2}]-\bbE[g_{1}^{2}])g_{2}^{2}\cdots g_{D}^{2}]\rvert$
$\displaystyle\leq\lvert Z\bbE[g_{2}^{2}\cdots
g_{D}^{2}]\rvert+\sum_{j_{1},j_{2}=2}^{D}\lvert
W_{j_{1}}W_{j_{2}}\bbE[g_{j_{1}}g_{j_{2}}g_{2}^{2}\cdots g_{D}^{2}]\rvert.$
(D.60)

We here used eq. D.59 in the computation of $\bbE[g_{1}^{2}\mid
g_{2},\ldots,g_{2}]-\bbE[g_{1}^{2}]$. As in the first preliminary reduction
one can use Hölder’s inequality to find a constant $C^{\prime}$, depending on
$D$ and $u$, such that

$\displaystyle\lvert\bbE[g_{2}^{2}\cdots g_{D}^{2}]\rvert\leq
C^{\prime}\qquad\text{ and }\qquad\lvert\bbE[g_{j_{1}}g_{j_{2}}g_{2}^{2}\cdots
g_{D}^{2}]\rvert\leq C^{\prime}.$ (D.61)

The combination of eq. D.54, eq. D.55, eq. D.60 and eq. D.61 shows that there
exists a constant $C^{\prime\prime}$ such that

$\displaystyle\lvert\bbE[g_{1}^{2}g_{2}^{2}\cdots g_{D}^{2}]-\bbE[$
$\displaystyle g_{1}^{2}]\bbE[g_{2}^{2}\cdots g_{D}^{2}]\rvert\leq
C^{\prime\prime}\epsilon(\Sigma)^{2}.$ (D.62)

Finally, due to the induction hypothesis applied on $(g_{2},\ldots,g_{D})$ and
the fact that $\bbE[g_{1}^{2}]\leq u$, there exists some constant
$C^{\prime\prime\prime}$ such that

$\displaystyle\lvert\bbE[g_{1}^{2}]\bbE[g_{2}^{2}\cdots
g_{D}^{2}]-\bbE[g_{1}^{2}]\bbE[g_{2}^{2}]\cdots\bbE[g_{D}^{2}]\rvert\leq
C^{\prime\prime\prime}\epsilon(\Sigma)^{2}.$ (D.63)

Combine eq. D.62 and eq. D.63 to conclude that eq. D.50 holds true. This
completes the proof. ∎

###### Proof of Proposition 7.6.

For any $d\geq 1$ let $\bA_{d}\vcentcolon=\sqrt{d}\bG$ denote a rescaled
version of the corresponding $2d\times 2d$ Gaussian model $\bG$ for $\bS$. We
claim that the sequence of random matrices $(\bA_{d})_{d=K}^{\infty}$ is
_approximately uncorrelated with variance profile_ as defined in [40,
Definition 4.1]. More precisely, this means that we have to show that for any
fixed non-negative integers $0\leq r\leq D$ and $p_{1},\ldots,p_{D}\geq 0$
with $p_{i}=1$ for $i=1,\ldots,r$

$\displaystyle\limsup_{d\to\infty}\max_{\forall k\neq
l:\\{i_{k},j_{k}\\}\neq\\{i_{l},j_{l}\\}}d^{\frac{r}{2}}\lvert\bbE[\bA_{d,i_{1}j_{1}}^{p_{1}}\bA_{d,i_{2}j_{2}}^{p_{2}}\cdots\bA_{d,i_{D}j_{D}}^{p_{D}}]\rvert<\infty$
(D.64)

and

$\displaystyle\limsup_{d\to\infty}\max_{\forall k\neq
l:\\{i_{k},j_{k}\\}\neq\\{i_{l},j_{l}\\}}\lvert\bbE[\bA_{d,i_{1}j_{1}}^{2}\cdots\bA_{d,i_{D}j_{D}}^{2}]-\bbE[\bA_{d,i_{1}j_{1}}^{2}]\cdots\bbE[\bA_{d,i_{D}j_{D}}^{2}]\rvert=0$
(D.65)

where the maxima run over all values of
$(i_{1},j_{1}),\ldots,(i_{D},j_{D})\in\\{1,\ldots,2d\\}^{2}$ with
$\\{i_{k},j_{k}\\}\neq\\{i_{l},j_{l}\\}$ for all $k\neq l$.

By definition of a Gaussian model, it holds that $\bbE[\bG]=\bbE[\bS]=0$ and
$\operatorname{Cov}(\bG)=\operatorname{Cov}(\bS)$. In the case where
$\bA_{d,i_{k},j_{k}}=0$ almost surely and there is nothing to prove so let us
assume that $i_{k}$ and $j_{k}$ are such that
$\operatorname{Var}[\bA_{i_{k},j_{k}}]\neq 0$. Recall that $\bG$ is a Gaussian
model of $\bS$ and that $\bS$ is defined by a self-adjoint dilation of $\bM$
in eq. 7.6. The covariance of the entries of $\bA$ is hence a function of the
covariance of the entries of $\bM$. Hence, an application of Lemma D.9 to the
Gaussian vector $g\vcentcolon=(\bA_{d,i_{1}j_{1}},\ldots,\bA_{d,i_{D}j_{D}})$
implies that eq. D.64 and eq. D.65 follow if we prove that there exist
constants $\ell,u,c>0$ such that $\ell\leq
d\operatorname{Cov}(\bM)_{ij,ij}\leq u$ and $\lvert
d\operatorname{Cov}(\bM)_{ij,km}\rvert\leq c/d$ for all $(i,j)\neq(k,m)$.
Indeed, the bound $\ell\leq d\operatorname{Cov}(\bM)_{ij,ij}\leq u$ shows that
the assumption of Lemma D.9 is satisfied while the bound $\lvert
d\operatorname{Cov}(\bM)_{ij,km}\rvert\leq c/d$ yields that
$\epsilon(\operatorname{Cov}(g))\leq c/d$ with $\epsilon$ as in eq. D.48 which
ensures that Lemma D.9 provides a sufficiently strong conclusion.

The required upper bounds on $\lvert d\operatorname{Cov}(\bM)_{ij,km}\rvert$
and $d\operatorname{Cov}(\bM)_{ij,ij}$ can be found in eq. D.5. For the lower
bound on $\operatorname{Cov}(\bM)_{ij,ij}$ we may note that eq. D.6 implies
that for any $a,b\in\\{1,\ldots,K\\}$

$\displaystyle\lim_{d\to\infty}\max_{i\in\cV_{a},j\in\cV_{b}}\Bigl{\lvert}d\operatorname{Cov}(\bM)_{ij,ij}-\frac{\pi_{a}\mathbf{p}_{a,b}}{\alpha_{a}\alpha_{b}}\Bigr{\rvert}=0.$
(D.66)

In particular, since $\frac{\pi_{a}\mathbf{p}_{a,b}}{\alpha_{a}\alpha_{b}}\neq
0$ due to the preliminary reduction to the case where
$\operatorname{Var}[A_{d,i_{k},j_{k}}]\neq 0$, there exists a constant
$\ell>0$ such that $\ell\leq d\operatorname{Cov}(\bM)_{ij,ij}$ for all $d$.

We may note that eq. D.66 is exactly the same limiting variance profile as
occurs in the dense regime with $n=d^{2}$ in [40, Equation (23)].
Consequently, since the universal limiting eigenvalue distribution in [40,
Theorem 4.2] only depends on the limiting variance profile, the empirical
eigenvalue distribution of $\bG=\bA_{d}/\sqrt{d}$ has the same universal limit
as is predicted by [40, Theorem 1.1]. More precisely, it follows from [40,
Lemma 6.5 and Lemma 6.6] that

$\displaystyle\lim_{d\to\infty}\bbE[\operatorname{tr}\bG^{p}]=\int x^{p}\ {\rm
d}\operatorname{sym}(\nu_{\infty})(x)\quad\text{ and
}\quad\lim_{i\to\infty}\operatorname{Var}[\operatorname{tr}\bG^{p}]=0$ (D.67)

where $\nu_{\infty}$ is as in Proposition 7.6. The desired result now follows
from Lemma D.7, Lemma D.8, and the fact that
$\mu_{\bS}=\operatorname{sym}(\nu_{\bM})$. ∎

###### Proof of Corollary 7.7.

Note that $\operatorname{rank}\bbE[\hat{\bN}]\leq K$. The desired result hence
follows from Proposition 7.6 together with the fact that low-rank
perturbations do not affect limiting singular value distributions. More
precisely, one can combine [5, Theorem A.43] with a self-adjoint dilation. ∎

######  Proposition D.10.

Adopt the notation and assumptions of Proposition 7.6. Then, for any
$\varepsilon>0$ there exists some constant $c>0$ such that

$\displaystyle\lim_{d\to\infty}\bbP\bigl{(}\\#\\{i\in\\{1,\ldots,d\\}:s_{i}(\bM)\in(\mathfrak{m}-\varepsilon,\mathfrak{m}+\varepsilon)\\}<cd\bigr{)}=0.$
(D.68)

In particular,

$\displaystyle\lim_{d\to\infty}\bbP(\|\bM\|<\mathfrak{m}-\varepsilon)=0.$
(D.69)

###### Proof.

The lower bound eq. D.69 is an immediate consequence of eq. D.68 since
$s_{1}(\bM)=\|\bM\|$ is the greatest singular value. Pick some continuous
function $f:\bbR\to[0,1]$ with support given by
$[\mathfrak{m}-\varepsilon,\mathfrak{m}+\varepsilon]$ and observe that $\int
f(x){\rm
d}\nu_{\bM}(x)\leq\frac{1}{d}\\#\\{i\in\\{1,\ldots,d\\}:s_{i}(\bM)\in(\mathfrak{m}-\varepsilon,\mathfrak{m}+\varepsilon)\\}$.
Proposition 7.6 ensures that $\operatorname{Var}[\int f(x){\rm
d}\nu_{\bM}(x)]$ converges to zero as $d$ tends to infinity. Consequently, it
is sufficient to argue that the limit $\lim_{d\to\infty}\bbE[\int f(x){\rm
d}\nu_{\bM}(x)]$, which is already known to exist, is nonzero.

Let $\bG^{\prime}$ denote a $2d\times 2d$ self-adjoint random matrix such that
the upper-triangle $(\bG_{i,j})_{i\leq j}$ consists of _independent_ Gaussian
random variables with

$\displaystyle\operatorname{Var}[\bG_{i,j}^{\prime}]=0\qquad\text{ and
}\qquad\operatorname{Var}[\bG_{i,j+K}^{\prime}]=\frac{1}{d}\frac{\pi_{a}\mathbf{p}_{a,b}}{\alpha_{a}\alpha_{b}}$
(D.70)

for all $i\in\cV_{a}$ and $j\in\cV_{b}$. Then, as is evident from the proof of
Proposition 7.6, the empirical eigenvalue distribution of $\bG^{\prime}$ has
the same limit as the empirical eigenvalue distribution of $\bS$; see eq.
D.66. In particular, $\lim_{d\to\infty}\bbE[\int f(x){\rm
d}\nu_{\bM}(x)]=\lim_{d\to\infty}\bbE[\int f(x){\rm d}\mu_{\bG^{\prime}}(x)]$.

Recall from Section 7.3 that $\alpha_{1},\ldots,\alpha_{K}$ are assumed to be
rational. Let us denote $A_{1},\ldots,A_{K},R\geq 1$ for the positive integers
with $\alpha_{i}=A_{i}/R$ for every $i\in\\{1,\ldots,K\\}$. By passing to a
subsequence of the sequence of block Markov chain models, it may be assumed
that $d$ is a multiple of $R$. We can further assume that
$\\#\cV_{a}=d\alpha_{a}$ for all $a\in\\{1,\ldots,K\\}$.

Denote $\bH$ for the $2R\times 2R$ version of $G^{\prime}$ which occurs when
$d=R$. Then, by [7, Lemma 3.2] and the foregoing preliminary reductions, it
holds that

$\displaystyle\|\bH_{\operatorname{free}}\|$
$\displaystyle=\mathop{\mathrm{inf}\vphantom{\mathrm{sup}}}_{x\in\bbR_{>0}^{2R}}\max_{i=1,\ldots,2R}\Bigl{\\{}\frac{1}{x_{i}}+\sum_{j=1}^{2R}\operatorname{Var}[\bH_{i,j}]x_{j}\Bigr{\\}}.$
(D.71)

Here, due to eq. D.70 and the fact that $\bH=\bH^{{\rm T}}$, it holds that

$\displaystyle\sum_{j=1}^{2R}\operatorname{Var}[\bH_{i,j}]x_{j}$
$\displaystyle=\begin{cases}\sum_{b=1}^{K}\bigl{(}\frac{1}{R}\frac{\pi_{a}\mathbf{p}_{a,b}}{\alpha_{a}\alpha_{b}}\bigr{)}\bigl{(}\sum_{j\in\cV_{b}}x_{j+R}\bigr{)}&\text{
if }i\in\cV_{a},\\\
\sum_{b=1}^{K}\bigl{(}\frac{1}{R}\frac{\pi_{b}\mathbf{p}_{b,a}}{\alpha_{a}\alpha_{b}}\bigr{)}\bigl{(}\sum_{j\in\cV_{b}}x_{j}\bigr{)}&\text{
if }i-R\in\cV_{a}.\end{cases}$ (D.72)

Note that $x_{i}\mapsto 1/x_{i}$ is a decreasing function when $x_{i}>0$. The
infimum in eq. D.71 can consequently be restricted to vectors which are
constant on every cluster $\cV_{a}$. That is, we may assume that $x_{j}=x_{k}$
and $x_{j+R}=x_{j+R}$ whenever $j,k\in\cV_{a}$ for $a\in\\{1,\ldots,K\\}$. We
find that

$\displaystyle\|\bH_{\operatorname{free}}\|$ (D.73)
$\displaystyle=\mathop{\mathrm{inf}\vphantom{\mathrm{sup}}}_{y\in\bbR_{>0}^{2K}}\max_{i=1,\ldots,K}\max\biggl{\\{}\frac{1}{y_{i}}+\sum_{j=1}^{K}\alpha_{i}^{-1}\pi_{i}\mathbf{p}_{i,j}y_{j+K},\
\frac{1}{y_{i+K}}+\sum_{j=1}^{K}\alpha_{i}^{-1}\pi_{j}\mathbf{p}_{j,i}y_{j}\biggr{\\}}.$

In other words, $\|\bH_{\operatorname{free}}\|=\mathfrak{m}$ with
$\mathfrak{m}$ as in Theorem 7.5.

Recall that we restricted ourselves to the subsequence where $d$ is a multiple
of $R$. Along this subsequence, [7, Corollary 4.4] yields that

$\displaystyle\lim_{d\to\infty}\bbE\Bigl{[}\int f(x){\rm
d}\mu_{\bG^{\prime}}(x)\Bigr{]}=\lim_{d\to\infty}\bbE[\operatorname{tr}f(\bG^{\prime})]=(\operatorname{tr}\otimes\tau)(f(\bH_{\operatorname{free}})).$
(D.74)

Naturally, the same limiting value occurs outside of the chosen subsequence
since we already know that the limit exists. Due to [32, Proposition 3.13.(2)]
there exists a measure $\mu_{\bH_{\operatorname{free}}}$ such that
$(\operatorname{tr}\otimes\tau)(f(\bH_{\operatorname{free}})=\int
f(x)\mu_{\bH_{\operatorname{free}}}(x)$ and by [32, (3.26)] it holds that
$\|\bH_{\operatorname{free}}\|=\mathfrak{m}$ is in the support of this measure
$\mu_{\bH_{\operatorname{free}}}$. In particular, it has to hold that
$(\operatorname{tr}\otimes\tau)(f(\bH_{\operatorname{free}})\neq 0$ since we
chose $f$ to be a nonnegative function with support given by
$[\mathfrak{m}-\varepsilon,\mathfrak{m}+\varepsilon]$. This proves that
$\lim_{d\to\infty}\bbE[\int f(x){\rm d}\nu_{\bM}(x)]\neq 0$ and concludes the
proof. ∎

######  Remark D.11.

The proof of Proposition D.10 is the only time we use the assumption that the
$\alpha_{i}$ are rational. The assumption can be removed using a perturbative
argument but we omit this generalization for the sake of brevity.

###  D.3 Sharp upper bounds on $\|\bM\|$

The main technical result in this section concerns a nonasymptotic upper bound
on $\|\bS_{\operatorname{free}}\|$; see Lemma D.13. We further provide the
proof of Theorem 7.5 and prove a nonasymptotic concentration inequality with
explicit constants in Theorem D.14.

For any finite $d$, let us denote $\hat{\alpha}_{i}\vcentcolon=\\#\cV_{i}/d$
and define a scalar $\hat{\mathfrak{m}}$ analogously to Theorem 7.5 by

$\displaystyle\hat{\mathfrak{m}}$
$\displaystyle\vcentcolon=\mathop{\mathrm{inf}\vphantom{\mathrm{sup}}}_{x\in\bbR_{>0}^{2K}}\max_{i=1,\ldots,2K}\Bigl{\\{}\frac{1}{x_{i}}+\sum_{j=1}^{2K}\hat{c}_{i,j}x_{j}\Bigr{\\}}$
(D.75)

where the infimum runs over all vectors $x$ with strictly positive coordinates
and the coefficients $(\hat{c}_{i,j})_{i,j=1}^{2K}$ are defined by

$\displaystyle\hat{c}_{i,j}=\begin{cases}0&\text{ if }i\leq K\text{ and }j\leq
K,\\\ \hat{\alpha}_{i}^{-1}\pi_{i}\mathbf{p}_{i,j-K}&\text{ if }i\leq K\text{
and }j>K,\\\ 0&\text{ if }i>K\text{ and }j>K,\\\
\hat{\alpha}_{i-K}^{-1}\pi_{j}\mathbf{p}_{j,i-K}&\text{ if }i>K\text{ and
}j\leq K.\end{cases}.$ (D.76)

Let us further introduce the following parameter:

$\displaystyle\mathfrak{u}\vcentcolon=\max_{i\in\\{1,\ldots,2K\\}}\min\Bigl{\\{}\frac{2\sqrt{\mathfrak{c}_{1}}}{\hat{c}_{i,j}}:j\in\\{1,\ldots,2K\\}\Bigr{\\}}.$
(D.77)

######  Lemma D.12.

There exists a vector $x^{*}\in\bbR^{2K}_{>0}$ which realizes the infimum in
eq. D.75 and this vector satisfies that $\frac{1}{2\mathfrak{c}_{1}}\leq
x_{i}^{*}\leq\mathfrak{u}$ for every $i\in\\{1,\ldots,2K\\}$.

###### Proof.

Exactly as in eq. D.70–eq. D.73 it follows from [7, Lemma 3.2] that
$\hat{\mathfrak{m}}=\|\hat{\bH}_{\operatorname{free}}\|$ where $\hat{\bH}$ is
the self-adjoint $2d\times 2d$ matrix for which the upper triangle
$(\hat{\bH}_{i,j})_{i\leq j}$ consists of independent Gaussian random
variables satisfying that

$\displaystyle\operatorname{Var}[\hat{\bH}_{i,j}]=0\qquad\text{ and
}\qquad\operatorname{Var}[\hat{\bH}_{i,j+K}]=\frac{1}{d}\frac{\pi_{a}\mathbf{p}_{a,b}}{\hat{\alpha}_{a}\hat{\alpha}_{b}}$
(D.78)

for any $i\in\cV_{a}$ and $j\in\cV_{b}$. Due to eq. 1.4 it consequently holds
that

$\displaystyle\hat{\mathfrak{m}}\leq
2\sigma(\hat{\bH})=2\|\bbE[\hat{\bH}^{2}]\|^{\frac{1}{2}}=2\sqrt{\max\Bigl{\\{}\frac{\pi_{a}}{\hat{\alpha}_{a}}:a\in\\{1,\ldots,K\\}\Bigr{\\}}}=2\sqrt{\mathfrak{c}_{1}}.$
(D.79)

It was here used that the operator norm of the diagonal matrix
$\bbE[\hat{\bH}^{2}]$ is equal to its maximal element.

Let us now define a subset of $\bbR^{2K}$ by

$\displaystyle\fX\vcentcolon=\Bigl{\\{}x\in\bbR^{2K}_{>0}:\frac{1}{2\sqrt{\mathfrak{c}_{1}}}\leq
x_{i}\leq\mathfrak{u}\text{ for all }i\in\\{1,\ldots,2K\\}\Bigr{\\}}.$ (D.80)

Then, due to eq. D.79, the infimum in eq. D.75 may be restricted to $\fX$.
Further recall that $\mathbf{p}$ is assumed to define an ergodic Markov chain.
It follows that for every $j$ there exists some $i$ with $\hat{c}_{i,j}\neq
0$. In particular, the parameter $\mathfrak{u}$ is finite and the set
$\mathfrak{X}$ is compact. Consequently, there exists some
$x^{*}\in\mathfrak{X}$ such that

$\displaystyle\hat{\mathfrak{m}}$
$\displaystyle=\mathop{\mathrm{inf}\vphantom{\mathrm{sup}}}_{x\in\fX}\max_{i=1,\ldots,2K}\Bigl{\\{}\frac{1}{x_{i}}+\sum_{j=1}^{2K}\hat{c}_{i,j}x_{j}\Bigr{\\}}=\max_{i=1,\ldots,2K}\Bigl{\\{}\frac{1}{x_{i}^{*}}+\sum_{j=1}^{2K}\hat{c}_{i,j}x_{j}^{*}\Bigr{\\}}.$
(D.81)

This concludes the proof. ∎

######  Lemma D.13.

With $\bS$ as in eq. 7.6 it holds that

$\displaystyle\|\bS_{\operatorname{free}}\|\leq\hat{\mathfrak{m}}+\frac{1}{d}\mathfrak{E}$

where the parameter $\mathfrak{E}>0$ is defined by

$\displaystyle\mathfrak{E}\vcentcolon=\mathfrak{u}\bigl{(}\frac{d}{n}\mathfrak{c}_{2}+3\mathfrak{c}_{2}^{2}+5\mathfrak{c}_{3}+2\mathfrak{c}_{2}\mathfrak{d}\bigr{)}+\frac{\mathfrak{u}}{d}\bigl{(}8\mathfrak{c}_{2}^{2}+6\mathfrak{c}_{2}\mathfrak{d}\bigr{)}.$
(D.82)

###### Proof.

Let $x^{*}\in\bbR^{2K}$ be the vector which is provided by Lemma D.12 and
define $\bW$ to be the $2d\times 2d$ diagonal matrix with
$\bW_{i,i}=x_{a}^{*}$ and $\bW_{i+d,i+d}=x_{a+K}^{*}$ for any $i\in\cV_{a}$
and $a\in\\{1,\ldots,K\\}$.

Then, due to eq. 1.2 and the fact that eigenvalues are dominated by the
operator norm

$\displaystyle\|\bS_{\operatorname{free}}\|\leq\lambda_{\max}\Bigl{(}\bW^{-1}+\bbE[\bS\bW\bS]\Bigr{)}\leq\|\bW^{-1}+\bbE[\bS\bW\bS]\|.$
(D.83)

For any $i,j\in\\{1,\ldots,2d\\}$ the $(i,j)$th entry of $\bbE[\bS\bW\bS]$ is
given by

$\displaystyle\bbE[\bS\bW\bS]_{i,j}=\sum_{k=1}^{2d}\bW_{k}\bbE[\bS_{i,k}\bS_{k,j}]$
(D.84) $\displaystyle=\begin{cases}0&\text{ if }(i\leq d\text{ and }j>d)\text{
or }(i>d\text{ and }j\leq d),\\\
\sum_{k=1}^{d}\bW_{k+d,k+d}\operatorname{Cov}(\bM)_{ik,jk}&\text{ if }i\leq
d\text{ and }j\leq d,\\\
\sum_{k=1}^{d}\bW_{k,k}\operatorname{Cov}(\bM)_{k(i-d),k(j-d)}&\text{ if
}i>d\text{ and }j>d.\end{cases}$

We next study the diagonal and off-diagonal entries separately.

We first consider the diagonal entries. Recall the estimate eq. D.6 on
$\operatorname{Cov}(\bM)_{ik,ik}$ and note that, since
$\hat{\alpha}_{a}=\\#\cV_{a}/d$, we can equivalently write

$\displaystyle\Bigl{\lvert}\operatorname{Cov}(\bM)_{ik,ik}-\frac{1}{d}\frac{\pi_{a}\mathbf{p}_{a,b}}{\hat{\alpha}_{a}\hat{\alpha_{b}}}\Bigr{\rvert}\leq\frac{1}{d^{2}}\bigl{(}\frac{d}{n}\mathfrak{c}_{2}+\frac{2}{d}\mathfrak{c}_{2}^{2}+\mathfrak{c}_{3}+\frac{2}{d}\mathfrak{c}_{2}\mathfrak{d}\bigr{)}$
(D.85)

for every $i\in\cV_{a}$ and $k\in\cV_{b}$. Recall from eq. D.76 and that
$\hat{c}_{a,b}=0$ if $\max\\{a,b\\}\leq K$ or if $\min\\{a,b\\}>K$. Further,
note that
$\max_{i=1,\ldots,d}\bW_{i,i}=\max_{b=1,\ldots,2K}x_{b}^{*}\leq\mathfrak{u}$
due to Lemma D.12. Hence, grouping terms along the clusters in eq. D.84 and
substituting eq. D.85 yields that

$\displaystyle\Bigl{\lvert}\bbE[\bS\bW\bS]_{i,i}-\sum_{b=1}^{2K}\hat{c}_{a,b}x_{b}^{*}\Bigr{\rvert}\leq\frac{\mathfrak{u}}{d}\bigl{(}\frac{d}{n}\mathfrak{c}_{2}+\frac{2}{d}\mathfrak{c}_{2}^{2}+\mathfrak{c}_{3}+\frac{2}{d}\mathfrak{c}_{2}\mathfrak{d}\bigr{)}$
(D.86)

for every $i,a$ with $i\in\cV_{a}$ and $a\leq K$ or $i\in\cV_{a-K}$ and $a>K$.

Now consider the off-diagonal entries where $i\neq j$. Then, using the
estimate eq. D.5 in eq. D.84 together with the fact that there are precisely
$2$ values of $k$ with $k\in\\{i,j\\}$ and $d-2\leq d$ remaining values,

$\displaystyle\lvert\bbE[\bS\bW\bS]_{i,j}\rvert$
$\displaystyle\leq\frac{2\mathfrak{u}}{d^{2}}(\frac{3}{d}\mathfrak{c}_{2}^{2}+2\mathfrak{c}_{3}+\frac{2}{d}\mathfrak{c}_{2}\mathfrak{d})+\frac{\mathfrak{u}}{d^{2}}(3\mathfrak{c}_{2}^{2}+2\mathfrak{c}_{2}\mathfrak{d})$
(D.87)
$\displaystyle=\frac{\mathfrak{u}}{d^{2}}\Bigl{(}(3\mathfrak{c}_{2}+4\mathfrak{c}_{3}+2\mathfrak{c}_{2}^{2}\mathfrak{d})+\frac{1}{d}(6\mathfrak{c}_{2}^{2}++4\mathfrak{c}_{2}\mathfrak{d})\Bigr{)}.$

Let us now split $\bW^{-1}+\bbE[\bS\bW\bS]=\bD+\bR$ where $\bD$ is the matrix
containing all diagonal entries and $\bR$ is the matrix containing all off-
diagonal entries. Then, since the operator norm of a diagonal matrix is the
greatest absolute value of its elements it follows from eq. D.86 that

$\displaystyle\|\bD\|\leq\hat{\mathfrak{m}}+\frac{\mathfrak{u}}{d}\bigl{(}\frac{d}{n}\mathfrak{c}_{2}+\frac{2}{d}\mathfrak{c}_{2}^{2}+\mathfrak{c}_{3}+\frac{2}{d}\mathfrak{c}_{2}\mathfrak{d}\bigr{)}.$
(D.88)

Further, using that the operator norm of a block diagonal matrix is the
maximum of the operator norms of the blocks as well as the fact that the
operator norm is dominated by the Frobenius norm, it follows from eq. D.87
that

$\displaystyle\|\bR\|$ $\displaystyle=\Bigl{\|}\begin{pmatrix}\bR_{1}&0\\\
0&\bR_{2}\end{pmatrix}\Bigr{\|}$ (D.89)
$\displaystyle=\max\\{\|\bR_{1}\|,\|\bR_{2}\|\\}$
$\displaystyle\leq\frac{\mathfrak{u}}{d}(3\mathfrak{c}_{2}^{2}+4\mathfrak{c}_{3}+2\mathfrak{c}_{2}\mathfrak{d})+\frac{\mathfrak{u}}{d^{2}}(6\mathfrak{c}_{2}^{2}+4\mathfrak{c}_{2}\mathfrak{d}).$

Hence, since $\|\bW^{-1}+\bbE[\bS\bW\bS]\|\leq\|\bD\|+\|\bR\|$, the
combination of eq. D.83, eq. D.88, and eq. D.89 yields the desired result. ∎

The combination of Lemmas D.4 and D.13 provides close–to–optimal estimates on
the parameters of $\bS$ in the block Markov chain model. We next state the
resulting sharp concentration inequality with explicit constants.

######  Theorem D.14.

The matrix $\bM\vcentcolon=\sqrt{d/n}(\hat{\bN}-\bbE[\hat{\bN}])$ satisfies
that for every integer $p\geq 1$ and any scalar $x>0$

$\displaystyle\bbP\Bigl{(}\|\bM\|\geq\Bigl{(}\hat{\mathfrak{m}}+\frac{\mathfrak{E}}{d}+2\Bigl{(}\frac{\mathfrak{v}\mathfrak{g}}{d}\Bigr{)}^{\frac{1}{4}}p^{\frac{3}{4}}+60\Bigl{(}\frac{4d}{n}\Psi(E)^{4}\mathfrak{c}_{1}^{2}\Bigr{)}^{\frac{1}{6}}p^{\frac{2}{3}}$
$\displaystyle+120\Bigl{(}\frac{d}{n}\Bigr{)}^{\frac{1}{2}}\Psi(E)p\Bigr{)}x\Bigr{)}$
$\displaystyle\leq dx^{-2p}.$

where $\hat{\mathfrak{m}},\mathfrak{E},\mathfrak{g},\mathfrak{v}$, and
$\mathfrak{c}_{1}$ are as in eq. D.75, eq. D.82, eq. D.24, eq. D.25, and eq.
D.1 respectively.

###### Proof.

Note that $\|\bM\|=\|\bS\|$. The result is hence immediate by substitution of
the estimates from Lemmas D.4 and D.13 in Proposition 6.14. ∎

######  Lemma D.15.

Adopt the notation and assumptions of Theorem 7.5. Then, for any
$\varepsilon>0$

$\displaystyle\lim_{d\to\infty}\bbP(\|\bM\|>\mathfrak{m}+\varepsilon)=0.$
(D.90)

###### Proof.

A comparison of eq. 7.8 and eq. D.75 shows that
$\lim_{d\to\infty}\hat{\mathfrak{m}}=\mathfrak{m}$; recall that we assume that
$\lim_{d\to\infty}\\#\cV_{a}/d=\alpha_{a}$ and that $\mathbf{p}$ is kept
fixed. Further, the parameter $\mathfrak{E}$ defined in eq. D.82 remains
bounded as $d$ tends to infinity. Due to Lemma D.13, we can consequently
assume that
$\|\bS_{\operatorname{free}}\|\leq\hat{\mathfrak{m}}+\mathfrak{E}/d\leq\mathfrak{m}+\varepsilon/2$
for all large $d$.

Fix some sufficiently small $0<\delta<1$ such that
$(1+\delta)(\mathfrak{m}+\frac{1}{2}\varepsilon)\leq\mathfrak{m}+\frac{2}{3}\varepsilon$.
Then, substitution of $x=2\log_{(1+\delta)}(d+1)$ in Theorem 3.1 yields that

$\displaystyle\bbP\Bigl{(}\|\bM\|\geq\mathfrak{m}+\frac{2}{3}\varepsilon+\varepsilon_{\delta,r}\Bigr{)}\leq\frac{1}{d+1}$
(D.91)

where, due to the estimates in Lemmas D.4 and D.5, there exist constants
$c_{1},c_{2},c_{3}$ depending only on $\hat{\alpha}_{\min}$ and $\Psi(C)$ such
that

$\displaystyle\varepsilon_{\delta,r}$ (D.92) $\displaystyle\leq
c_{1}\Bigl{(}\frac{\log_{(1+\delta)}(d+1)^{3}}{d}\Bigl{)}^{\frac{1}{4}}+c_{2}\Bigl{(}\frac{d\log_{(1+\delta)}(d+1)^{4}}{n}\Bigr{)}^{\frac{1}{6}}+c_{3}\Bigl{(}\frac{d\log_{(1+\delta)}(d+1)^{2}}{n}\Bigr{)}^{\frac{1}{2}}.$

The assumption that $\lim_{d\to\infty}d\ln(d)^{4}/n=0$, together with the fact
that we consider $\delta$ to be fixed, here ensures that
$\lim_{d\to\infty}\varepsilon_{\delta,r}=0$. In particular,
$\varepsilon_{\delta,r}<\varepsilon/3$ for all large $d$. The desired result
now follows from eq. D.91. ∎

###### Proof of Theorem 7.5.

This is immediate by combination of the lower bound in Proposition D.10 with
the upper bound in Lemma D.15. ∎

##  Appendix E Proof for Wigner matrices with independent heavy-tailed entries

We here prove Proposition 7.3 and adopt the notation which was introduced
there.

###### Proof.

Let us write $\bS\vcentcolon=d^{-\frac{1}{2}}\bW$, $\eta=1$, and
$\gamma\vcentcolon=\theta-1$. Denote $n\vcentcolon=\binom{d}{2}$ and pick some
bijective function $e:\\{1,\ldots,n\\}\to\\{(i,j):1\leq i\leq j\leq d\\}$.
Then, we can represent $\bS=\sum_{t=1}^{n}Y_{t}\bA_{t}$ where

$\displaystyle
Y_{t}\vcentcolon=\bW_{e(t)},\qquad(\bA_{t})_{i,j}\vcentcolon=d^{-\frac{1}{2}}\mathbbm{1}\\{(i,j)=e(t)\text{
or }(j,i)=e(t)\\}$ (E.1)

for every $i,j\in\\{1,\ldots,d\\}$. Recall the parameters of the matrix series
model from Section 4.1. The following estimates are immediate:

$\displaystyle
R(\bA)=d^{-\frac{1}{2}},\quad\varsigma(\bA)^{2}=1=\sigma(\bS)^{2},\quad
v(\bS)^{2}\leq 2d^{-1}.$ (E.2)

It remains to estimate the parameter
$D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{\infty}(Y)$.

Classical joint cumulants vanish whenever the random variables involved can be
partitioned in two subsets which are jointly independent; see [42, Proposition
4.1]. Consequently, since the random variables $Y_{t}$ are independent and
identically distributed,

$\displaystyle
K_{k}(Y)=\max_{t_{1}=1,\ldots,n}\lvert\kappa(Y_{t_{1}},Y_{t_{1}},\ldots,Y_{t_{1}})\rvert=\lvert\kappa(Y_{1},\ldots,Y_{1})\rvert=\lvert\kappa^{{\text{{$($}{}$k${$)$}}}}(\bW_{1,1})\rvert.$
(E.3)

It should here be understood that
$\kappa^{{\text{{$($}{}$k${$)$}}}}(\bW_{1,1})\vcentcolon=\kappa(\bW_{1,1},\ldots,\bW_{1,1})$
where the argument $\bW_{1,1}$ occurs $k$ times.

Due to [49, Theorem 1, items 1 and 4], the assumption that $\bW_{1,1}$ is sub-
Weibull is equivalent to the existence of some $L^{\prime}>0$ such that
$\bbE[\exp((\lvert\bW_{1,1}\rvert/L^{\prime})^{1/\theta})]\leq 2$. The latter
inequality is known as _Linnik’s condition_ and it is shown in [1, Page 2033]
that this is equivalent to the _Statulevičius condition_ : there exists some
$\Delta>0$ such that

$\displaystyle\kappa^{{\text{{$($}{}$k${$)$}}}}(\bW_{1,1})\leq\Delta^{k-2}(k!)^{\theta}$
(E.4)

for all $k\geq 3$. Let us further note that an inspection of the proofs
reveals that the constant $L^{\prime}$ from [49] only depends on $L$ and
$\theta$ and the constant $\Delta$ from [1, Page 2033] only depends on
$L^{\prime}$ and $\theta$. Recall that
$D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{\infty}(Y)$ was defined in eq. 4.4
and recall that $\theta=\gamma+1$ and $\eta=1$. The combination of eq. E.3 and
eq. E.4 consequently yields that

$\displaystyle D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{\infty}(Y)=\sup_{k\geq
3}\Bigl{(}\frac{K_{k}(Y)}{(k!)^{1+\gamma}}\Bigr{)}^{\frac{1}{k}}\leq\sup_{k\geq
3}(\Delta^{k-2})^{\frac{1}{k}}=\max\\{\Delta,\Delta^{\frac{1}{3}}\\}.$ (E.5)

We next substitute eq. E.2 and eq. E.5 in Theorem 4.1. Further, we use that
$\|\bS_{\operatorname{free}}\|\leq 2\sigma(\bS)$ by the case with
$\bbE[\bS]=0$ in eq. 1.4 and the fact that $\bbE[\bS]=0$. This yields that

$\displaystyle\bbP(\|\bS\|\geq
2+2\delta+c^{1+\gamma}\varepsilon^{{\text{{$($}{}$\eta,\gamma${$)$}}}}(x))\leq(d+1)(1+\delta)^{-x}$
(E.6)

where $c\leq 8$ and

$\displaystyle\varepsilon^{{\text{{$($}{}$\eta,\gamma${$)$}}}}(x)=2^{\frac{1}{2}}d^{-\frac{1}{4}}x^{\frac{3}{4}}+\max\\{\Delta,\Delta^{\frac{1}{3}}\\}d^{-\frac{1}{6}}x^{\frac{2+3\gamma}{3}}+\max\\{\Delta,\Delta^{\frac{1}{3}}\\}d^{-\frac{1}{2}}x^{1+\gamma}.$
(E.7)

Let
$c^{\prime}\vcentcolon=c^{1+\gamma}\max\\{2^{\frac{1}{2}},\Delta,\Delta^{\frac{1}{3}}\\}$
and recall that $\theta=\gamma+1$ to conclude the proof. ∎

##  Appendix F Proofs concerning random graphs

The goal of this section is to prove Proposition 7.2 concerning the empirical
eigenvalue distribution of adjacency matrices in the $\cG(d,m)$-model. This
proof proceeds similarly to the proof of Proposition 7.6: we estimate the
covariance profile, deduce estimates on the parameters, and use a general-
purpose result from [40] whose conditions are verified using Lemma D.9.

###  F.1 Preliminary reductions

Let us abbreviate $n\vcentcolon=\binom{d}{2}$. Denote $J$ for the $d\times d$
all-ones matrix, let $\mathbf{1}$ denote the $d\times d$ identity matrix, and
let $\cA$ denote the adjacency matrix of a $\cG(d,m)$-distributed random graph
$G$.

######  Lemma F.1.

The random matrix $J-\cA-\mathbf{1}$ has the same distribution as the
adjacency matrix of a $\cG(d,n-m)$-distributed graph.

###### Proof.

It holds that $J-\cA-\mathbf{1}$ is the adjacency matrix of the complement
graph of $G$, i.e., the graph $G^{c}=(V,E^{c})$ with $e\in E^{c}$ if and only
if $e\not\in E$. The result is hence immediate since the complement of a
$\cG(d,n-m)$-distributed graph is a $\cG(d,m)$-distributed graph. ∎

Note also that $p(1-p)$ is conserved by the transformation $\cA\mapsto
J-\cA-\mathbf{1}$ since $p=m/\binom{d}{2}$. The shift on the spectrum caused
by the subtraction of $\mathbf{1}$ is asymptotically negligible after we
rescale by $1/\sqrt{p(1-p)d}$. Consequently, since $\operatorname{rank}J=1$
and low-rank perturbations do not affect limiting eigenvalue distributions by
[5, Theorem A.43], it is sufficient to prove Proposition 7.2 in the special
case where $m\leq n/2$. We make this assumption from here on out.

Let us write $\bS\vcentcolon=(\cA-\bbE[\cA])/\sqrt{p(1-p)d}$. The following
result implies that it is sufficient to establish the limiting law of the
eigenvalue distribution of $\bS$.

######  Lemma F.2.

Assume that $\mu_{\bS}$ converges weakly in probability to
$\mu_{\operatorname{sc}}$ as $d$ tends to infinity. Then, the same holds for
$\mu_{\cA/\sqrt{p(1-p)d}}$.

###### Proof.

Note that $\operatorname{rank}\bbE[\cA]=1$. The desired result hence follows
from [5, Theorem A.43]. ∎

###  F.2 Bounds on the parameters

Analogously to eq. E.1, we can represent $\bS$ in terms of the matrix series
model as $\bS=\sum_{t=1}^{n}W_{t}\bB_{t}$ where

$\displaystyle
W_{t}=Y_{t}-\bbE[Y_{t}]\quad\text{and}\quad(\bB_{t})_{i,j}\vcentcolon=\sqrt{p(1-p)d}\mathbbm{1}\\{(i,j)=e(t)\text{
or }(j,i)=e(t)\\}$ (F.1)

with $Y_{t}$ and $e:\\{1,\ldots,n\\}\to\\{(i,j):1\leq i\leq j\leq d\\}$ as in
Section 7.1. The goal of the current section is to establish estimates on the
parameters of $\bS$. Recall that $m=m_{d}$ is implicitly a function of $d$,
that we denote $p=m/n$, and recall the definition of
$D^{{\text{{$($}{}$\eta,\gamma${$)$}}}}_{k}$ from eq. 4.4.

######  Lemma F.3.

Assume that $\lim_{d\to\infty}m=\infty$. Then, for any $k\geq 3$ there exists
a constant $C_{k}^{\prime}$ such that for all $d\geq 1$

$\displaystyle D^{{\text{{$($}{}$p,0${$)$}}}}_{k}(W)\leq C_{k}^{\prime}.$

###### Proof.

We estimate $K_{r}(W)$ for every $r\in\\{3,\ldots,k\\}$ where we recall that
$K_{r}(W)$ was defined in eq. 4.3. It is immediate from eq. 4.2 that classical
cumulants are multilinear. Further, note that classical joint cumulants vanish
whenever the random variables involved can be partitioned in two subsets which
are jointly independent [42, Proposition 4.1] and note that a scalar is
independent of any other random variable. Consequently, recentering does not
matter for the cumulants, and thus

$\displaystyle\kappa(W_{t_{1}},\ldots,W_{t_{r}})=\kappa(Y_{t_{1}},\ldots,Y_{t_{r}}).$
(F.2)

For any integer $1\leq L\leq r$ and any fixed $t_{1}\in\\{1,\ldots,n\\}$ there
are at most $L^{r-1}\binom{n-1}{L-1}\leq k^{k-1}n^{L-1}$ possible values for
the tuple $(t_{2},\ldots,t_{r})$ such that
$\\#\\{t_{1},\ldots,t_{r}\\}\allowbreak=L$. Hence, by Proposition 7.1,

$\displaystyle K_{r}(W)$
$\displaystyle=\max_{t_{1}\in\\{1,\ldots,n\\}}\sum_{t_{2},\ldots,t_{r}=1}^{n}\lvert\kappa(Y_{t_{1}},\ldots,Y_{t_{r}})\rvert$
(F.3) $\displaystyle\leq r\max_{1\leq L\leq
r}\max_{t_{1}\in\\{1,\ldots,n\\}}\sum_{t_{2},\ldots,t_{r}:\\#\\{t_{1},\ldots,t_{r}\\}=L}\lvert\kappa(Y_{t_{1}},\ldots,Y_{t_{r}})\rvert$
$\displaystyle\leq k^{k}p^{r}C_{r}\max_{1\leq L\leq r}m^{1-L}n^{L-1}.$

Consequently, by eq. F.2 and the fact that $n/m=p^{-1}$,

$\displaystyle K_{r}(W)\leq k^{k}pC_{r}.$ (F.4)

The desired result is now immediate from the definition eq. 4.4 of
$D^{{\text{{$($}{}$p,0${$)$}}}}_{k}(W)$. ∎

######  Lemma F.4.

It holds that

$\displaystyle R(\bB)\leq\sqrt{\frac{2}{dp}}\quad\text{ and
}\quad\varsigma(\bB)^{2}\leq\frac{2}{p}.$

###### Proof.

Recall the definitions of $R$ and $\varsigma$ from eq. 4.1. Both estimates are
immediate from the definition of $\bB_{t}$ in eq. F.1 and the fact that
$p(1-p)\geq p/2$ by the preliminary reduction to $m\leq n/2$. ∎

######  Lemma F.5.

Suppose that $d\geq 3$. Then, for any $i,j,k,r\in\\{1,\ldots,d\\}$ with
$\\{i,j\\}=\\{k,r\\}$ it holds that

$\displaystyle\operatorname{Cov}(\bS)_{ij,kr}=\frac{1}{d}$

and if $\\{i,j\\}\neq\\{k,r\\}$ it holds that

$\displaystyle\lvert\operatorname{Cov}(\bS)_{ij,kr}\rvert\leq\frac{1}{d}\frac{6}{n}.$

###### Proof.

Note that $\cA_{ij}$ is a Bernoulli distributed random variable with
$\bbP(\cA_{i,j}=1)=p$. Consequently,

$\displaystyle\operatorname{Cov}(\bS)_{ij,ij}=\frac{1}{p(1-p)d}\operatorname{Var}[\cA_{ij}]=\frac{1}{d}.$
(F.5)

Considering that
$\operatorname{Cov}(\bS)_{ij,ji}=\operatorname{Cov}(\bS)_{ij,ij}$ by the
matrix being symmetric, this proves the case with $\\{i,j\\}=\\{k,r\\}$.

Further, for $\\{i,j\\}\neq\\{k,r\\}$ it holds that

$\displaystyle\operatorname{Cov}(\bS)_{ij,kr}=\frac{1}{p(1-p)d}\operatorname{Cov}(\cA)_{ij,kr}$
(F.6) $\displaystyle\quad=\frac{1}{p(1-p)d}\bigl{(}\bbE[\mathbbm{1}\\{(i,j)\in
E\\}\mathbbm{1}\\{(k,r)\in E\\}]-\bbE[\mathbbm{1}\\{(i,j)\in
E\\}]\bbE[\mathbbm{1}\\{(k,r)\in E\\}]\bigr{)}$
$\displaystyle\quad=\frac{1}{p(1-p)d}\frac{m}{n}\Bigl{(}\frac{m-1}{n-1}-\frac{m}{n}\Bigr{)}$
$\displaystyle\quad\leq\frac{2}{d}\Bigl{\lvert}\frac{m-1}{n-1}-\frac{m}{n}\Bigr{\rvert}$

where the final inequality used that $(m/n)/(p(1-p))\leq 2$ since $p(1-p)\geq
p/2$ by the preliminary reduction to $m\leq n/2$. Recall that we assume that
$d\geq 3$. It follows that $n=\binom{d}{2}\geq 3$ and hence $\lvert
n/(n-1)-1\rvert\leq 2/n$. Consequently, by the triangle inequality

$\displaystyle\Bigl{\lvert}\frac{m-1}{n-1}-\frac{m}{n}\Bigr{\rvert}$
$\displaystyle\leq\Bigl{\lvert}\frac{m}{n-1}-\frac{m}{n}\Bigr{\rvert}+\Bigl{\lvert}\frac{1}{n-1}\Bigr{\rvert}=\frac{m}{n}\Bigl{\lvert}\frac{n}{n-1}-1\Bigr{\rvert}+\Bigl{\lvert}\frac{1}{n-1}\Bigr{\rvert}\leq\frac{2m}{n^{2}}+\frac{2}{n}$
(F.7)

where the final inequality used that $1/(n-1)\leq 2/n$ since $n\geq 3$. Use
that $2m/n^{2}\leq 1/n$ to conclude the proof. ∎

######  Corollary F.6.

Assume that $d\geq 3$. Then, it holds that

$\displaystyle v(\bS)^{2}\leq\frac{19}{d}\quad\text{ and
}\quad\sigma(\bS)^{2}\leq 7.$

###### Proof.

Let $\bD$ denote the matrix containing the diagonal entries of
$\operatorname{Cov}(\bS)$ and $\bR$ the matrix containing all off-diagonal
terms. By Lemma F.5, and the fact that the operator norm of a diagonal matrix
is determined by the maximal size of a diagonal element, it holds that
$\|\bD\|\leq 1/d$. Further, since the operator norm can be bounded by the
Frobenius norm, $\|\bR\|\leq 6d^{2}/(dn)$. Hence, since $n=\binom{d}{2}\geq
d^{2}/3$ for $d\geq 3$, the triangle inequality yields that

$\displaystyle
v(\bS)^{2}=\|\operatorname{Cov}(\bS)\|\leq\|\bD\|+\|\bR\|\leq\frac{1}{d}+\frac{18}{d}\leq\frac{19}{d}$
(F.8)

where the final step used that $d\geq 3$.

For $i,j\in\\{1,\ldots,d\\}$ it holds that

$\displaystyle\bbE[\bS^{2}]_{i,j}=\sum_{k=1}^{d}\operatorname{Cov}(\bS)_{ik,jk}.$
(F.9)

Consequently, splitting into diagonal and off-diagonal parts and proceeding
exactly as above, Lemma F.5 yields that

$\displaystyle\sigma(\bS)^{2}=\|\bbE[\bS^{2}]\|=1+d^{2}\frac{6}{dn}\leq
1+\frac{6d}{n}\leq 7.$ (F.10)

It was here used that $d/n\leq 1$. This concludes the proof. ∎

###  F.3 Proof of Proposition 7.2

We finally complete the proof using the moment method.

######  Lemma F.7.

If $\lim_{d\to\infty}d/m=0$ and $\bG$ is the Gaussian model of $\bS$, then for
every $k\geq 1$

$\displaystyle\lim_{d\to\infty}\lvert\bbE[\operatorname{tr}\bS^{k}]-\bbE[\operatorname{tr}\bG^{k}]\rvert=0\quad\text{
and
}\quad\lim_{d\to\infty}\lvert\operatorname{Var}[\operatorname{tr}\bS^{k}]-\operatorname{Var}[\operatorname{tr}\bG^{k}]\rvert=0.$

###### Proof.

By Corollary F.6

$\displaystyle\limsup_{d\to\infty}\sigma(\bS)<\infty\quad\text{ and
}\quad\limsup_{d\to\infty}v(\bS)=0.$ (F.11)

Furthermore, by Lemmas F.3 and F.4

$\displaystyle\limsup_{d\to\infty}D^{{\text{{$($}{}$p,0${$)$}}}}_{2k}(W)R(\bB)$
$\displaystyle\leq C_{2k}^{\prime}\limsup_{d\to\infty}\sqrt{\frac{2}{dp}}=0,$
(F.12)
$\displaystyle\limsup_{d\to\infty}pD^{{\text{{$($}{}$p,0${$)$}}}}_{2k}(W)^{3}R(\bB)\varsigma(\bB)^{2}$
$\displaystyle\leq(C_{2k}^{\prime})^{3}\limsup_{d\to\infty}p\sqrt{\frac{2}{dp}}\frac{2}{p}=0$
(F.13)

where it was used that $\lim_{d\to\infty}1/(dp)=0$ due to the assumption that
$\lim_{d\to\infty}d/m=0$ and the fact that $p=m/n=m/\binom{d}{2}$. It follows
that the quantity $H^{{\text{{$($}{}$p,0${$)$}}}}_{k}(W,\bB)$ defined in
Theorem 4.2 satisfies
$\limsup_{d\to\infty}H^{{\text{{$($}{}$p,0${$)$}}}}_{k}(W,\bB)<\infty$. The
desired result now follows from Theorems 4.2 and 4.3 together with the fact
that, by definition of a Gaussian model,
$\operatorname{Var}[\operatorname{tr}\bS]=\operatorname{Var}[\operatorname{tr}\bG]$
and $\bbE[\operatorname{tr}\bS^{k}]=\bbE[\operatorname{tr}\bG^{k}]$ for $k\leq
2$. ∎

###### Proof of Proposition 7.2.

Identically to the proof of Proposition 7.6 one can use Lemma F.5 to conclude
that the matrix $\sqrt{d}\bG$ is approximately uncorrelated with a variance
profile; see eq. D.64–eq. D.67. In fact, the variance profile is constant in
this case. The result now follows from Lemma D.7, Lemma F.7, and [40, Theorem
4.2] together with the fact that the moments of the semicircular law are given
by the Catalan numbers. That is, $\int x^{k}{\rm
d}\mu_{\operatorname{sc}}=\\#\cT_{k}$ where $\cT_{k}$ is the set consisting of
all ordered trees on $m+1$ vertices. ∎