The Semicircle Law for Matrices with Dependent Entries

Abstract

We investigate the spectral distribution of random matrix ensembles with correlated entries. The matrices considered are symmetric, have real-valued entries and stochastically independent diagonals. Along the diagonals the entries may be correlated. We show that under sufficiently nice moment conditions and sufficiently strong decay of correlations the empirical eigenvalue distribution converges almost surely weakly to the semi-circle law. The present note improves an earlier result (see [Friesen and Löwe, J. Theor. Probab., 2011]) by the authors using similar techniques.

2010 Mathematics Subject Classification. 60F05.

1 Introduction

Large-dimensional random matrices were first considered in the context of application in statistics and in theoretical physics, among others, in particular they served as a model when studying the properties of atoms with heavy nuclei. However, nowadays the field of random matrices is considered to be interesting in its own rights, since it gave rise to many interesting results, such as Wigner’s semi-circle law for the limiting spectral distribution of a symmetric or Hermitian random matrix or the Tracy-Widom distribution as the limiting distribution of the (appropriately scaled) largest eigenvalue of a random Hermitian matrix. Moreover, there are connections to many questions in pure mathematics as well as applications in a multitude of areas outside of mathematics, e.g. telecommunications.

As indicated by the results mentioned above, one of the most interesting and best studied problems, has been to investigate the properties of the eigenvalues of random matrices. The most prominent example is Wigner’s semi-circle law. Wigner, in his seminal paper [17] showed that the spectral distribution of symmetric Bernoulli matrices under appropriate scaling converges to the semi-circle law. In [18] he remarked that this result may be generalized to the spectral distribution of a wide class of random matrices, among them symmetric or Hermitian random matrices with independent Gaussian entries, otherwise.

A result in this spirit was proved by Arnold [3] in the situation of symmetric or Hermitian random matrices filled with independent and identically distributed (i.i.d.) random variables with sufficiently many moments. Other generalizations of Wigner’s semi-circle law concern matrix ensembles with entries drawn according to weighted Haar measures on classical (e.g., orthogonal, unitary, symplectic) groups. Such results are particularly interesting, since such random matrices also play a major role in non-commutative probability (see e.g. [10]); other applications are in graph theory, combinatorics or algebra. For a broad overview the interested reader is referred to Mehta’s classical textbook [14] or to the rather recent work by Anderson et al. [2].

This note addresses a question that is much in the spirit of Arnold’s generalization of the semi-circle law. Even though a couple of random matrix models include situations with stochastically correlated entries (see especially [6], where the case of random Toeplitz and Hankel matrices is treated), the dependencies are not very natural from a stochastic point of view. A generic way to construct random matrices with dependent entries could be to consider a two dimensional (stationary) random field indexed by ${\mathbb{Z}}^{2}$ with correlations that decay with the distance of the indices and to take an n ×n block as entries for a random n ×n matrix.

This setup would, of course, be very general, and the present note is just a first step to study the asymptotic eigenvalue distribution of such matrix ensembles. Here we will deviate from the independence assumption by considering (real) random fields with entries that may be dependent on each diagonal, but with stochastically independent diagonals. For such matrices we will prove a semi-circle law under a sufficiently fast decay of correlations along the diagonals. It should be noted, that a similar result under an arbitrarily slow decay of correlations cannot be expected, since in such a situation one should already get into the realm of Toeplitz matrices as treated in [6].

The setup of the present note may look at first glance a bit more artificial than a situation where the matrices are filled with row- or columnwise independent random variables (e.g. with row- or columnwise independent Markov chains). Note, however, that in order to guarantee for real eigenvalues we will need to restrict ourselves to symmetric random matrices. This would imply that a matrix with rowwise independent entries above the diagonal has columnwise independent entries below it. Not only is this a rather strange setup, also can one see from simulations that their asymptotic eigenvalue distribution is probably not the semi-circle law.

It should also be remarked that the conditions in this note are weaker than those in earlier article (see [8]) and therefore the results are more general then our previous ones. Example 4.3 below shows that these weaker assumptions extend the validity of Theorem 2.2 to a set of rather natural examples that could not be treated by means of the main theorem in [8]. Moreover, we also find an indication that the rather strong moment conditions we impose (see (C1) below) may be relaxed. Theorem 2.4 below is a first step into this direction.

It also should be mentioned that a similar situation has been studied by Khorunzhy and Pastur in [12]. They consider the eigenvalue distribution of so called deformed Wigner ensembles that consist of matrices which can be written as a sum of Wigner matrix (a symmetric matrix with independent entries above the diagonal) and a deterministic matrix. It is proven that in this situation the empirical eigenvalue density converges in probability to a non-random limit. This setup, yet similar, is different from ours.

The question, whether stochastically dependent entries could be allowed in order for the semi-circle law to hold, is not new. For example, Bai [4] p. 626 raises the question of whether Wigner’s theorem is still holding true when the independence condition in the Wigner matrix is weakened. Also Götze and Tikhomirov [9], Hofmann-Credner and Stolz [11], and Schenker and Schulz-Baldes [16] consider a situation where the entries of a random matrix are in a natural way stochastically dependent. However, their conditions do not cover our situation.

On the other hand, some extra conditions apart from a weak dependence structure are necessary. Indeed, Anderson and Zeitouni [1] show that convergence to the semicircle law does not hold in general under finite range of dependence.

The rest of the note is organized as follows. In the second section we will formalize the situation we want to consider and state our main result. Section 3 is devoted to the proof, that is based on a moment method. These naturally lead to some combinatorial problems, that need to be solved. Section 4 contains some examples. In particular we consider Gaussian random fields as well as Markov chains on a finite state space.

2 The Main Result

In this section we will state our main theorem, a semi-circle law for symmetric random matrices with independent diagonals (for a precise formulation see Theorem 2.2 below). These random matrices are constructed as follows:

Let $\left \{a_{n}(p,q),1 \leq p \leq q < \infty \right \}$ be a real valued random field. For any $n \in \mathbb{N}$, define the symmetric random n ×n matrix X _n by

$$\mathbf{X}_{n}(q,p) = \mathbf{X}_{n}(p,q) = \frac{1} {\sqrt{n}}a_{n}(p,q),\qquad 1 \leq p \leq q \leq n,$$

We will have to impose the conditions on X _n . To be able to formulate them introduce

$$m_{k} :=\sup _{n\in \mathbb{N}}\max _{1\leq p\leq q\leq n}\mathbb{E}\left [{\left \vert a_{n}(p,q)\right \vert }^{k}\right ]\quad k \in \mathbb{N}.$$

(1)

We will assume the following.

• (C1) $\mathbb{E}\left [a_{n}(p,q)\right ] = 0$, $\mathbb{E}\left [a_{n}{(p,q)}^{2}\right ] = 1$ and

  $$m_{k} < \infty ,\quad \forall k \in \mathbb{N}.$$

  (2)

• (C2) The diagonals of X _n , i.e. the families $\left \{a_{n}(p,p + r),p \in \mathbb{N}\right \}$, $r \in \mathbb{N}_{0}$, are independent,

• (C3) The covariance of two entries on the same diagonal can be bounded by some constant depending only on their distance, i.e. for any $\tau \in \mathbb{N}_{0}$ there is a constant c(τ) ≥ 0 such that

  $$\vert \mathrm{Cov}(a_{n}(p,q),a_{n}(p+\tau ,q+\tau ))\vert \leq c(\tau ),\qquad p,q \in \mathbb{N},$$

• (C4) The entries on the diagonals have a quickly decaying dependency structure, which will be expressed in terms of the condition

  $$\lim _{\tau \rightarrow \infty }c{(\tau )\ \tau }^{\epsilon } = 0,$$

  for some $\epsilon > 0$.

Remarks 2.1.

• (i) The choice of the first two moments in (C1) is just for standardization, while (2) is a condition one might eventually want to relax. This, however, not that easy in general. We will see that for a weaker form of our main result the weaker condition

  • (C1’) $\mathbb{E}\left [a_{n}(p,q)\right ] = 0$, $\mathbb{E}\left [a_{n}{(p,q)}^{2}\right ] = 1$ and

    $$m_{2} < \infty $$

    (3)

    suffices.

• (ii) Note that condition (C4) implies that $\sum _{\tau =1}^{n}c(\tau ) = o(n)$ since

  $$\frac{1} {n}\displaystyle\sum _{\tau =1}^{n}c(\tau ) \leq \frac{1} {{n}^{\epsilon }}\displaystyle\sum _{\tau =1}^{n}\frac{c{(\tau )\ \tau }^{\epsilon }} {\tau } \rightarrow 0,\quad \text{as}\ n \rightarrow \infty.$$

• (iii) In particular (C4) is an improvement over the condition of summable correlations

  $$\displaystyle\sum _{\tau =0}^{\infty }\vert c(\tau )\vert < \infty $$

  we imposed in [8].

As noted, we will show that the empirical eigenvalue distribution of the (appropriately scaled) random matrices introduced above converges to a limit law μ, the so-called semi-circle distribution. We choose its density to be concentrated on the interval [ − 2, 2]. Then its density is given by

$$\frac{d\mu } {dx} = \left \{\begin{array}{ll} \frac{1} {2\pi }\sqrt{4 - {x}^{2}} & \mbox{ if } - 2 \leq x \leq 2 \\ 0 &\mbox{ otherwise.} \end{array} \right.$$

To state our main theorems denote the ordered (real) eigenvalues of X _n by

$$\lambda _{1}^{(n)} \leq \lambda _{ 2}^{(n)} \leq \ldots \lambda _{ n}^{(n)}.$$

Let μ _n be the empirical eigenvalue distribution, i.e.

$$\mu _{n} = \frac{1} {n}\displaystyle\sum _{k=1}^{n}\delta _{ \lambda _{k}^{(n)}}.$$

With these notations we are able to formulate the central result of this note.

Theorem 2.2.

Assume that the symmetric random matrix X _n as defined above satisfies the conditions (C1), (C2), (C3), and (C4). Then, with probability 1, the empirical spectral distribution of X _n converges weakly to the standard semi-circle distribution, i.e.

$$\mu _{n} \Rightarrow \mu \qquad \mbox{ as }n \rightarrow \infty $$

both, in expectation and $\mathbb{P} -\mbox{ almost surely}$ . Here “ ⇒” denotes weak convergence.

Remark 2.3.

As stated in the introduction for the semi-circle law to hold, it is not possible to renounce condition (C4) without any replacement. To understand this, consider for example a Toeplitz matrix, that is a Hermitian matrix with identical entries on each diagonal. If the variance of the entries is positive, we clearly have

$$c(\tau ) = \mathcal{O}(1).$$

Indeed, it was shown in [6] that the empirical distribution of a sequence of Toeplitz matrices tends with probability 1 to a nonrandom probability measure with unbounded support.

If we assume (C1’) instead of (C1) we still obtain a convergence result.

Theorem 2.4.

Assume that the symmetric random matrix X _n as defined above satisfies the conditions (C1’), (C2), (C3), and (C4). Then, the empirical spectral distribution of X _n converges weakly in probability to the semi-circle distribution.

3 Proof of Theorems 2.2 and 2.4

The basic tool in our proofs will be the method of moments. Naively, one could expect an approach using Stieltjes transforms to work as well (and in this case one would probably be able to work with weaker moment conditions than those imposed in (C1)). This method is rather standard in random matrix theory (see e.g. Chap. 2.4 in [2]). However, if the entries of a random matrix are not independent, this method seems to have serious technical difficulties.

The method of moments, on the other hand, also is traditional in the proof of a semicircle law. Among others, Wigner used this method to derive the semicircle distribution as the limiting spectral distribution for scaled Bernoulli matrices, see [17]. Also Arnold’s generalization of the semicircle law [3] relies on the same technique. A recent example for matrices with dependent entries is [16]. Our proof is particularly inspired by the latter of these paper. An excellent reference to this method is also provided by Bose and Sen, cf. [5].

A key observation for the following is that the techniques in [8] suffice to prove Theorem 2.2 also under the weaker assumption (C4). For the reader’s convenience we will give this proof next (following the lines in [8], of course).

To this end, let Y be distributed according to the semi-circle distribution. For the proof of the theorem it will be important to notice that the moments of Y are given by

$$\mathbb{E}({Y }^{k}) = \left \{\begin{array}{@{}l@{\quad }l@{}} 0, \quad &\text{if}\ k\ \text{is odd},\\ C_{\frac{ k} {2} },\quad &\text{if}\ k\ \text{is even}, \end{array} \right.$$

(4)

where

$$C_{\frac{k} {2} } = \frac{k!} {\frac{k} {2} !\left (\frac{k} {2} + 1\right )!}$$

denote the Catalan numbers. Note that these moments determine the semicircle distribution uniquely.

This implies, that the weak convergence of the expected empirical distribution will follow from the convergence of the empirical moments, i.e. from the relation

$$\lim _{n\rightarrow \infty }\frac{1} {n}\mathbb{E}\left [\mathrm{tr}\left (\mathbf{X}_{n}^{k}\right )\right ] = \left \{\begin{array}{@{}l@{\quad }l@{}} 0, \quad &\text{if}\ k\ \text{is odd},\\ C_{\frac{ k} {2} },\quad &\text{if}\ k\ \text{is even,} \end{array} \right.$$

where tr( ⋅) denotes the trace operator. The first part of the proof is to verify this convergence.

To start with, consider the set $\mathcal{T}_{n}(k)$ of k-tuples of consistent pairs, that is elements of the form P ₁, …, P _k with $P_{j} = (p_{j},q_{j}) \in {\left \{1,\ldots ,n\right \}}^{2}$ satisfying q _j  = p _j + 1 for any j = 1, …, k, where k + 1 is identified with 1. Then, we have

$$\frac{1} {n}\mathbb{E}\left [\mathrm{tr}\left (\mathbf{X}_{n}^{k}\right )\right ] = \frac{1} {{n}^{1+\frac{k} {2} }} \displaystyle\sum _{\left (P_{1},\ldots ,P_{k}\right )\in \mathcal{T}_{n}(k)}\mathbb{E}\left [a_{n}(P_{1}) \cdot \ldots \cdot a_{n}(P_{k})\right ].$$

Further, define $\mathcal{P}(k)$ to be the set of all partitions π of 1, …, k. Any partition π induces an equivalence relation ∼  _π on 1, …, k by

$$i \sim _{\pi }j\quad : \Longleftrightarrow\quad i\ \text{and}\ j\ \text{belong to the same set of the partition}\ \pi.$$

We say that an element $\left (P_{1},\ldots ,P_{k}\right ) \in \mathcal{T}_{n}(k)$ is a π-consistent sequence if

$$\left \vert p_{i} - q_{i}\right \vert = \left \vert p_{j} - q_{j}\right \vert \quad \Longleftrightarrow\quad i \sim _{\pi }j.$$

At this stage, the independence of the diagonals enters crucially. Indeed, due to condition (C2), this implies that $a_{n}(P_{i_{1}}),\ldots ,a_{n}(P_{i_{l}})$ are stochastically independent if i ₁, …, i _l belong to l different blocks of π. The set of all π-consistent sequences $\left (P_{1},\ldots ,P_{k}\right ) \in \mathcal{T}_{n}(k)$ is denoted by S _n (π). Thus, we can write

$$\frac{1} {n}\mathbb{E}\left [\mathrm{tr}\left (\mathbf{X}_{n}^{k}\right )\right ] = \frac{1} {{n}^{1+\frac{k} {2} }} \displaystyle\sum _{\pi \in \mathcal{P}(k)}\displaystyle\sum _{\left (P_{1},\ldots ,P_{k}\right )\in S_{n}(\pi )}\mathbb{E}\left [a_{n}(P_{1}) \cdot \ldots \cdot a_{n}(P_{k})\right ].$$

Now fix a $k \in \mathbb{N}$. For any $\pi \in \mathcal{P}(k)$ let #π denote the number of equivalence classes of π.

We distinguish different cases. This will show that eventually only those π satisfying $\#\pi = \frac{k} {2}$ count.

First case: $\quad \#\pi > \frac{k} {2}$.

Since π is a partition of 1, …, k, there is at least one equivalence class with a single element l. Consequently, for any sequence $\left (P_{1},\ldots ,P_{k}\right ) \in S_{n}(\pi )$ we have

$$\mathbb{E}\left [a_{n}(P_{1}) \cdot \ldots \cdot a_{n}(P_{k})\right ] = \mathbb{E}\Big[\displaystyle\prod _{i\neq l}a_{n}(P_{i})\Big] \cdot \mathbb{E}\left [a_{n}(P_{l})\right ] = 0,$$

due to the independence of elements in different equivalence classes.

Hence, we obtain

$$\frac{1} {n}\mathbb{E}\left [\mathrm{tr}\left (\mathbf{X}_{n}^{k}\right )\right ] = \frac{1} {{n}^{1+\frac{k} {2} }} \displaystyle\sum _{\mathop{\pi \in \mathcal{P}(k),}\limits_{\#\pi \leq \frac{k} {2} }}\displaystyle\sum _{\left (P_{1},\ldots ,P_{k}\right )\in S_{n}(\pi )}\mathbb{E}\left [a_{n}(P_{1}) \cdot \ldots \cdot a_{n}(P_{k})\right ].$$

Second case: $\quad r := \#\pi < \frac{k} {2}$.

We need to calculate #S _n (π). To fix an element $\left (P_{1},\ldots ,P_{k}\right ) \in S_{n}(\pi )$, we first choose the pair P ₁ = (p ₁, q ₁). There are at most n possibilities to assign a value to p ₁ and another n possibilities for q ₁. To fix $P_{2} = (p_{2},q_{2})$, note that the consistency of the pairs implies p ₂ = q ₁. If now 1 ∼  _π 2, the condition $\left \vert p_{1} - q_{1}\right \vert = \left \vert p_{2} - q_{2}\right \vert$ allows at most two choices for q ₂. Otherwise, if $1\not\sim _{\pi }2$, we have at most n possibilities. We now proceed sequentially to determine the remaining pairs. When arriving at some index i, we check whether i is equivalent to any preceding index 1, …, i − 1. If this is the case, then we have at most two choices for P _i and otherwise, we have n. Since there are exactly r different equivalence classes, we can conclude that

$$\#S_{n}(\pi ) \leq {n}^{2} \cdot {n}^{r-1} \cdot {2}^{k-r} \leq C \cdot {n}^{r+1}$$

with a constant C = C(r, k) depending on r and k.

Now the uniform boundedness of the moments and the Hölder inequality together imply that for any sequence (P ₁, …, P _k ),

$$\left \vert \mathbb{E}\left [a_{n}(P_{1}) \cdot \ldots \cdot a_{n}(P_{k})\right ]\right \vert \leq {\left [\mathbb{E}{\left \vert a_{n}(P_{1})\right \vert }^{k}\right ]}^{\frac{1} {k} } \cdot \ldots \cdot {\left [\mathbb{E}{\left \vert a_{n}(P_{k})\right \vert }^{k}\right ]}^{\frac{1} {k} } \leq m_{k}.$$

(5)

Consequently, taking account of the relation $r < \frac{k} {2}$, we get

$$\frac{1} {{n}^{1+\frac{k} {2} }} \displaystyle\sum _{\mathop{\pi \in \mathcal{P}(k),}\limits_{\#\pi <\frac{k} {2} }}\displaystyle\sum _{\left (P_{1},\ldots ,P_{k}\right )\in S_{n}(\pi )}\left \vert \mathbb{E}\left [a_{n}(P_{1}) \cdot \ldots \cdot a_{n}(P_{k})\right ]\right \vert \leq C \cdot \frac{1} {{n}^{1+\frac{k} {2} }} \cdot {n}^{r+1} = o(1).$$

Combining the calculations in the first and the second case, we can conclude that

$$\displaystyle\begin{array}{rcl} & & \lim _{n\rightarrow \infty }\frac{1} {n}\mathbb{E}\left [\mathrm{tr}\left (\mathbf{X}_{n}^{k}\right )\right ] \\ & & =\lim _{n\rightarrow \infty } \frac{1} {{n}^{1+\frac{k} {2} }} \displaystyle\sum _{\mathop{\pi \in \mathcal{P}(k),}\limits_{\#\pi =\frac{k} {2} }}\displaystyle\sum _{\left (P_{1},\ldots ,P_{k}\right )\in S_{n}(\pi )}\mathbb{E}\left [a_{n}(P_{1}) \cdot \ldots \cdot a_{n}(P_{k})\right ], \\ \end{array}$$

if the limits exist.

Now consider the case where k is odd. Since then the condition $\#\pi = \frac{k} {2}$ cannot be satisfied, the considerations above immediately yield

$$\lim _{n\rightarrow \infty }\frac{1} {n}\mathbb{E}\left [\mathrm{tr}\left (\mathbf{X}_{n}^{k}\right )\right ] = 0.$$

It remains to cope with evenk. Denote by $\mathcal{P}\mathcal{P}(k) \subset \mathcal{P}(k)$ the set of all pair partitions of 1, …, k. In particular, $\#\pi = \frac{k} {2}$ for any $\pi \in \mathcal{P}\mathcal{P}(k)$. On the other hand, if $\#\pi = \frac{k} {2}$ but $\pi \notin \mathcal{P}\mathcal{P}(k)$, we can conclude that π has at least one equivalence class with a single element and hence, as in the first case, the expectation corresponding to the π-consistent sequences will become zero. Consequently,

$$\displaystyle\begin{array}{rcl} & & \lim _{n\rightarrow \infty }\frac{1} {n}\mathbb{E}\left [\mathrm{tr}\left (\mathbf{X}_{n}^{k}\right )\right ] \\ & & =\lim _{n\rightarrow \infty } \frac{1} {{n}^{1+\frac{k} {2} }} \displaystyle\sum _{\pi \in \mathcal{P}\mathcal{P}(k)}\displaystyle\sum _{\left (P_{1},\ldots ,P_{k}\right )\in S_{n}(\pi )}\mathbb{E}\left [a_{n}(P_{1}) \cdot \ldots \cdot a_{n}(P_{k})\right ], \\ \end{array}$$

if the limits exist. We have now reduced the original set $\mathcal{P}(k)$ to the subset $\mathcal{P}\mathcal{P}(k)$. Next we want to fix a $\pi \in \mathcal{P}\mathcal{P}(k)$ and cope with the set S _n (π).

Lemma 3.1 (cf. [6], Proposition 4.4.). 

Let $S_{n}^{{\ast}}(\pi ) \subseteq S_{n}(\pi )$ denote the set of π-consistent sequences (P₁,…,P_k) satisfying

$$i \sim _{\pi }j\quad \Longrightarrow\quad q_{i} - p_{i} = p_{j} - q_{j}$$

for all i≠j. Then, we have

$$\#\left (S_{n}(\pi )\setminus S_{n}^{{\ast}}(\pi )\right ) = o\left ({n}^{1+\frac{k} {2} }\right ).$$

Proof.

We call a pair (P _i , P _j ) with i ∼  _π j, i≠j, positive if $q_{i} - p_{i} = q_{j} - p_{j} > 0$ and negative if $q_{i} - p_{i} = q_{j} - p_{j} < 0$. Since $\sum _{i=1}^{k}q_{i} - p_{i} = 0$ by consistency, the existence of a negative pair implies the existence of a positive one. Thus, we can assume that any sequence $(P_{1},\ldots ,P_{k}) \in S_{n}(\pi )\setminus S_{n}^{{\ast}}(\pi )$ contains a positive pair (P _l , P _m ). To fix such a sequence, we first determine the positions of l and m and then, we fix the signs of the remaining differences q _i  − p _i . The number of possibilities to accomplish that depends only on k and not on n. Now we choose one of n possible values for p _l . In a next step, we fix the values of the differences q _i  − p _i for all P _i except for P _l and P _m . We have ${n}^{\frac{k} {2} -1}$ possibilities for that, since π is a pair partition and for any i ∼  _π j it holds that $\vert p_{i} - q_{i}\vert = \vert p_{j} - q_{j}\vert$ by definition. Then, $\sum _{i=1}^{k}q_{i} - p_{i} = 0$ implies that

$$0 < 2(q_{l} - p_{l}) = q_{l} - p_{l} + q_{m} - p_{m} =\displaystyle\sum _{ \mathop{i=1,}\limits_{i\neq l,m}}^{k}p_{ i} - q_{i}.$$

Since we have already chosen the signs of the differences as well as their absolute values, we know the value of the sum on the right hand side. Hence, the difference $q_{l} - p_{l} = q_{m} - p_{m}$ is fixed. We now have the index p _l , all differences $\left \vert q_{i} - p_{i}\right \vert ,i \in \left \{1,\ldots ,k\right \}$, and their signs. Thus, we can start at P _l and go systematically through the whole sequence (P ₁, …, P _k ) to see that it is uniquely determined. Consequently, our considerations lead to

$$\#\left (S_{n}(\pi )\setminus S_{n}^{{\ast}}(\pi )\right ) \leq C \cdot {n}^{\frac{k} {2} } = o\left ({n}^{1+\frac{k} {2} }\right ).$$

 □ 

As a consequence of Lemma 3.1 and relation (5), we obtain

$$\displaystyle\begin{array}{rcl} & & \lim _{n\rightarrow \infty }\frac{1} {n}\mathbb{E}\left [\mathrm{tr}\left (\mathbf{X}_{n}^{k}\right )\right ] \\ & & =\lim _{n\rightarrow \infty } \frac{1} {{n}^{1+\frac{k} {2} }} \displaystyle\sum _{\pi \in \mathcal{P}\mathcal{P}(k)}\displaystyle\sum _{\left (P_{1},\ldots ,P_{k}\right )\in S_{n}^{{\ast}}(\pi )}\mathbb{E}\left [a_{n}(P_{1}) \cdot \ldots \cdot a_{n}(P_{k})\right ], \\ \end{array}$$

if the limits exist.

We call a pair partition $\pi \in \mathcal{P}\mathcal{P}(k)$ crossing if there are indices i < j < l < m with i ∼  _π l and j ∼  _π m. Otherwise, we call πnon-crossing. The set of all non-crossing pair partitions is denoted by $\mathcal{N}\mathcal{P}\mathcal{P}(k)$.

Lemma 3.2.

For any crossing $\pi \in \mathcal{P}\mathcal{P}(k)\setminus \mathcal{N}\mathcal{P}\mathcal{P}(k)$ , we have

$$\displaystyle\sum _{\left (P_{1},\ldots ,P_{k}\right )\in S_{n}^{{\ast}}(\pi )}\mathbb{E}\left [a_{n}(P_{1}) \cdot \ldots \cdot a_{n}(P_{k})\right ] = o\left ({n}^{\frac{k} {2} +1}\right ).$$

Proof.

Let π be crossing and consider a sequence $\left (P_{1},\ldots ,P_{k}\right ) \in S_{n}^{{\ast}}(\pi )$. Note that if there is an l ∈ 1, …, k with l ∼  _π l + 1, where k + 1 is identified with 1, we immediately have

$$a_{n}(P_{l}) = a_{n}(P_{l+1}),$$

since q _l  = p _l + 1 by consistency and then p _l  = q _l + 1 by definition of S _n ^∗(π). In particular,

$$\mathbb{E}\left [a_{n}(P_{l}) \cdot a_{n}(P_{l+1})\right ] = 1.$$

The sequence $\left (P_{1},\ldots ,P_{l-1},P_{l+2},\ldots ,P_{k}\right )$ is still consistent because of the relation $q_{l-1} = p_{l} = q_{l+1} = p_{l+2}$. Since there are at most n choices for q _l  = p _l + 1, it follows

$$\#S_{n}^{{\ast}}(\pi ) \leq n \cdot \#S_{ n}^{{\ast}}{(\pi }^{(1)}),$$

where ${\pi }^{(1)} \in \mathcal{P}\mathcal{P}(k - 2)\setminus \mathcal{N}\mathcal{P}\mathcal{P}(k - 2)$ is the pair partition induced by π after eliminating the indices l and l + 1. Let r denote the maximum number of pairs of indices that can be eliminated in this way. Since π is crossing, there are at least two pairs left and hence, $r \leq \frac{k} {2} - 2$. By induction, we conclude that

$$\#S_{n}^{{\ast}}(\pi ) \leq {n}^{r} \cdot \#S_{ n}^{{\ast}}{(\pi }^{(r)}),$$

where now ${\pi }^{(r)} \in \mathcal{P}\mathcal{P}(k - 2r)\setminus \mathcal{N}\mathcal{P}\mathcal{P}(k - 2r)$ is the still crossing pair partition induced by π. Thus, we so far have

$$\displaystyle\begin{array}{rcl} & & \displaystyle\sum _{\left (P_{1},\ldots ,P_{k}\right )\in S_{n}^{{\ast}}(\pi )}\left \vert \mathbb{E}\left [a_{n}(P_{1}) \cdot \ldots \cdot a_{n}(P_{k})\right ]\right \vert \\ & &\qquad \qquad \qquad \qquad \leq {n}^{r}\displaystyle\sum _{ (P_{1}^{(r)},\ldots ,P_{k-2r}^{(r)})\in S_{n}^{{\ast}}{(\pi }^{(r)})}\left \vert \mathbb{E}\left [a_{n}(P_{1}^{(r)}) \cdot \ldots \cdot a_{ n}(P_{k}^{(r)})\right ]\right \vert.\end{array}$$

(6)

Choose $i \sim _{{\pi }^{(r)}}i + j$ such that j is minimal. We want to count the number of sequences $(P_{1}^{(r)},\ldots ,P_{k-2r}^{(r)}) \in S_{n}^{{\ast}}{(\pi }^{(r)})$ given that p _i ^(r) and q _i + j ^(r) are fixed. Therefore, we start with choosing one of n possible values for q _i ^(r). But then, we can also deduce the value of

$$p_{i+j}^{(r)} = q_{ i}^{(r)} - p_{ i}^{(r)} + q_{ i+j}^{(r)}.$$

Since j is minimal, any element in i + 1, …, i + j − 1 is equivalent to some element outside the set i, …, i + j. There are n possibilities to fix P _i + 1 ^(r) as $p_{i+1}^{(r)} = q_{i}^{(r)}$ is already fixed. Proceeding sequentially, we have n possibilities for the choice of any pair P _l ^(r) with $l \in \left \{i + 2,\ldots ,i + j - 2\right \}$ and there is only one choice for P _{i + j − 1} ^(r) since $q_{i+j-1}^{(r)} = p_{i+j}^{(r)}$ is already chosen. For any other pair that has not yet been fixed, there are at most n possibilities if it is not equivalent to one pair that has already been chosen. Otherwise, there is only one possibility. Hence, assuming that the elements p _i ^(r) and q _i + j ^(r) are fixed, we have at most

$$n \cdot {n}^{j-2} \cdot {n}^{\frac{k} {2} -r-j} = {n}^{\frac{k} {2} -r-1}$$

possibilities to choose the rest of the sequence $(P_{1}^{(r)},\ldots ,P_{k-2r}^{(r)}) \in S_{n}^{{\ast}}{(\pi }^{(r)})$. Consequently, estimating the term in (6) further, we obtain

$$\displaystyle\begin{array}{rcl} & & \displaystyle\sum _{\left (P_{1},\ldots ,P_{k}\right )\in S_{n}^{{\ast}}(\pi )}\left \vert \mathbb{E}\left [a_{n}(P_{1}) \cdot \ldots \cdot a_{n}(P_{k})\right ]\right \vert \\ & &\leq {n}^{r}\displaystyle\sum _{ (P_{1}^{(r)},\ldots ,P_{k-2r}^{(r)})\in S_{n}^{{\ast}}{(\pi }^{(r)})}\left \vert \mathbb{E}\left [a_{n}(P_{i}^{(r)})\ a_{ n}(P_{i+j}^{(r)})\right ]\right \vert \\ & &\leq {n}^{\frac{k} {2} -1}\displaystyle\sum _{p_{ i}^{(r)},q_{i+j}^{(r)}=1}^{n}c(\vert q_{ i+j}^{(r)} - p_{ i}^{(r)}\vert ) \\ & & \leq C \cdot {n}^{\frac{k} {2} }\displaystyle\sum _{\tau =0}^{n-1}c(\tau ) = o\left ({n}^{1+\frac{k} {2} }\right ), \\ \end{array}$$

since $\sum _{\tau =0}^{n-1}c(\tau ) = o(n)$ by condition (C4) and Remark 2.1 (ii). □ 

Lemma 3.2 now guarantees that we need to consider only non-crossing pair partitions, that is

$$\displaystyle\begin{array}{rcl} & & \lim _{n\rightarrow \infty }\frac{1} {n}\mathbb{E}\left [\mathrm{tr}\left (\mathbf{X}_{n}^{k}\right )\right ] \\ & & =\lim _{n\rightarrow \infty } \frac{1} {{n}^{1+\frac{k} {2} }} \displaystyle\sum _{\pi \in \mathcal{N}\mathcal{P}\mathcal{P}(k)}\displaystyle\sum _{\left (P_{1},\ldots ,P_{k}\right )\in S_{n}^{{\ast}}(\pi )}\mathbb{E}\left [a_{n}(P_{1}) \cdot \ldots \cdot a_{n}(P_{k})\right ], \\ \end{array}$$

if the limits exist.

Lemma 3.3.

Let $\pi \in \mathcal{N}\mathcal{P}\mathcal{P}(k)$ . For any $\left (P_{1},\ldots ,P_{k}\right ) \in S_{n}^{{\ast}}(\pi )$ , we have

$$\mathbb{E}\left [a_{n}(P_{1}) \cdot \ldots \cdot a_{n}(P_{k})\right ] = 1.$$

Proof.

Let l < m with m ∼  _π l. Since π is non-crossing, the number l − m − 1 of elements between l and m must be even. In particular, there is l ≤ i < j ≤ m with i ∼  _π j and j = i + 1. By the properties of S _n ^∗, we have $a_{n}(P_{i}) = a_{n}(P_{j})$, and the sequence $\left (P_{1},\ldots ,P_{l},\ldots ,P_{i-1},P_{i+2},\ldots ,P_{m},\ldots ,P_{k}\right )$ is still consistent. Applying this argument successively, all pairs between l and m vanish and we see that the sequence $\left (P_{1},\ldots ,P_{l},P_{m},\ldots ,P_{k}\right )$ is consistent, that is q _l  = p _m . Then, the identity p _l  = q _m also holds. In particular, $a_{n}(P_{l}) = a_{n}(P_{m})$. Since l, m have been chosen arbitrarily, we obtain

$$\mathbb{E}\left [a_{n}(P_{1}) \cdot \ldots \cdot a_{n}(P_{k})\right ] =\displaystyle\prod _{{ l<m \atop l\sim _{\pi }m} }\mathbb{E}\left [a_{n}(P_{l}) \cdot a_{n}(P_{m})\right ] = 1.$$

 □ 

It remains to verify

Lemma 3.4.

For any $\pi \in \mathcal{N}\mathcal{P}\mathcal{P}(k)$ , we have

$$\lim _{n\rightarrow \infty }\frac{\#S_{n}^{{\ast}}(\pi )} {{n}^{\frac{k} {2} +1}} = 1.$$

Proof.

To calculate the number of elements in S _n ^∗(π), first choose P ₁. There are n ² possibilities for that choice. If 1 ∼  _π 2, then P ₂ is uniquely determined since p ₂ = q ₁ and by definition of S _n ^∗(π), q ₂ = p ₁. If $1\not\sim _{\pi }2$, then there are n − 1 possibilities to fix P ₂. Proceeding in the same way, we see that if i ∈ 2, …, k is equivalent to some element in 1, …, i − 1, there is always only one value P _i can take. Otherwise there are asymptotically n choices. The latter case will occur exactly $\frac{k} {2} - 1$ times. In conclusion,

$$\#S_{n}^{{\ast}}(\pi ) \sim {n}^{2} \cdot {n}^{\frac{k} {2} -1} = {n}^{1+\frac{k} {2} }.$$

 □ 

Lemmas 3.3 and 3.4 now provide that

$$\displaystyle\begin{array}{rcl} & & \lim _{n\rightarrow \infty }\frac{1} {n}\mathbb{E}\left [\mathrm{tr}\left (\mathbf{X}_{n}^{k}\right )\right ] \\ & & =\lim _{n\rightarrow \infty } \frac{1} {{n}^{1+\frac{k} {2} }} \displaystyle\sum _{\pi \in \mathcal{N}\mathcal{P}\mathcal{P}(k)}\displaystyle\sum _{\left (P_{1},\ldots ,P_{k}\right )\in S_{n}^{{\ast}}(\pi )}\mathbb{E}\left [a_{n}(P_{1}) \cdot \ldots \cdot a_{n}(P_{k})\right ] \\ & & =\lim _{n\rightarrow \infty } \frac{1} {{n}^{1+\frac{k} {2} }} \displaystyle\sum _{\pi \in \mathcal{N}\mathcal{P}\mathcal{P}(k)}\#S_{n}^{{\ast}}(\pi ) = \#\mathcal{N}\mathcal{P}\mathcal{P}(k).\end{array}$$

Since the number of non-crossing pair partitions $\#\mathcal{N}\mathcal{P}\mathcal{P}(k)$ equals exactly the Catalan number $C_{\frac{k} {2} }$, we can conclude that the expected empirical spectral distribution of X _n tends to the semi-circle law. This is the asserted convergence in expectation.

It remains to deduce almost sure convergence. Therefore, we want to follow the ideas of [6]. To this end, we need

Lemma 3.5.

Suppose the conditions of Theorem 2.2 hold. Then, for any $k,n \in \mathbb{N}$,

$$\mathbb{E}\left [{\left (\mathrm{tr}\left (\mathbf{X}_{n}^{k}\right ) - \mathbb{E}\left [\mathrm{tr}\left (\mathbf{X}_{ n}^{k}\right )\right ]\right )}^{4}\right ] \leq C \cdot {n}^{2}.$$

Proof.

Fix $k,n \in \mathbb{N}$. Using the notation

$$P = (P_{1},\ldots ,P_{k}) = ((p_{1},q_{1}),\ldots ,(p_{k},q_{k})),\qquad a_{n}(P) = a_{n}(P_{1}) \cdot \ldots \cdot a_{n}(P_{k}),$$

we have that

$$\displaystyle\begin{array}{rcl} & & \mathbb{E}\left [{\left (\mathrm{tr}\left (\mathbf{X}_{n}^{k}\right ) - \mathbb{E}\left [\mathrm{tr}\left (\mathbf{X}_{ n}^{k}\right )\right ]\right )}^{4}\right ] \\ & & = \frac{1} {{n}^{2k}}\displaystyle\sum _{{\pi }^{(1)},\ldots {,\pi }^{(4)}\in \mathcal{P}(k)}\displaystyle\sum _{{P}^{(i)}\in S_{n}\left ({\pi }^{(i)}\right ),i=1,\ldots ,4}\mathbb{E}\Big[\displaystyle\prod _{j=1}^{4}\left (a_{ n}({P}^{(j)}) - \mathbb{E}\left [a_{ n}({P}^{(j)})\right ]\right )\Big].\end{array}$$

(7)

Now consider a partition $\boldsymbol{\pi }$ of 1, …, 4k. We say that a sequence (P ⁽¹⁾, …, P ⁽⁴⁾) is $\boldsymbol{\pi }$-consistent if each P ⁽ⁱ⁾, i = 1, …, 4, is a consistent sequence and

$$\big\vert q_{l}^{(i)} - p_{ l}^{(i)}\big\vert \ =\ \left \vert q_{ m}^{(j)} - p_{ m}^{(j)}\right \vert \quad \Longleftrightarrow\quad l + (i - 1)k\ \sim _{\boldsymbol{\pi }}\ m + (j - 1)k.$$

Let $\mathcal{S}_{n}(\boldsymbol{\pi })$ denote the set of $\boldsymbol{\pi }$-consistent sequences with entries in 1, …, n. Then, (7) becomes

$$\displaystyle\begin{array}{rcl} & & \mathbb{E}\left [{\left (\mathrm{tr}\mathbf{X}_{n}^{k} - \mathbb{E}\left [\mathrm{tr}\mathbf{X}_{ n}^{k}\right ]\right )}^{4}\right ] \\ & & = \frac{1} {{n}^{2k}}\displaystyle\sum _{\boldsymbol{\pi }\in \mathcal{P}(4k)}\displaystyle\sum _{({P}^{(1)},\ldots ,{P}^{(4)})\in \mathcal{S}_{n}\left (\boldsymbol{\pi }\right )}\mathbb{E}\Big[\displaystyle\prod _{j=1}^{4}\left (a_{ n}({P}^{(j)}) - \mathbb{E}\left [a_{ n}({P}^{(j)})\right ]\right )\Big].\end{array}$$

(8)

We want to analyze the expectation on the right hand side. Therefore, fix a $\boldsymbol{\pi }\in \mathcal{P}(4k)$. We call $\boldsymbol{\pi }$ a matched partition if

• (i) Any equivalence class of $\boldsymbol{\pi }$ contains at least two elements and

• (ii) For any i ∈ 1, …, 4 there is a j≠i and l, m ∈ 1, …, k with

  $$l + (i - 1)k\ \sim _{\boldsymbol{\pi }}\ m + (j - 1)k.$$

In case $\boldsymbol{\pi }$ is not matched, we can conclude that

$$\displaystyle\sum _{({P}^{(1)},\ldots ,{P}^{(4)})\in \mathcal{S}_{n}\left (\boldsymbol{\pi }\right )}\mathbb{E}\Big[\displaystyle\prod _{j=1}^{4}\left (a_{ n}({P}^{(j)}) - \mathbb{E}\left [a_{ n}({P}^{(j)})\right ]\right )\Big] = 0.$$

Thus, we only have to consider matched partitions to evaluate the sum in (8). Let $\boldsymbol{\pi }$ be such a partition and denote by $r = \#\boldsymbol{\pi }$ the number of equivalence classes of $\boldsymbol{\pi }$. Note that condition (i) implies r ≤ 2k. To count all $\boldsymbol{\pi }$-consistent sequences (P ⁽¹⁾, …, P ⁽⁴⁾), we first choose one of at most n ^r possibilities to fix the r different equivalence classes. Afterwards, we fix the elements $p_{1}^{(1)},\ldots ,p_{1}^{(4)}$, which can be done in n ⁴ ways. Since now the differences $\vert q_{l}^{(i)} - p_{l}^{(i)}\vert$ are uniquely determined by the choice of the corresponding equivalence classes, we can proceed sequentially to see that there are at most two choices left for any pair P _l ⁽ⁱ⁾. To sum up, we have at most

$${2}^{4k} \cdot {n}^{4} \cdot {n}^{r} = C \cdot {n}^{r+4}$$

possibilities to choose (P ⁽¹⁾, …, P ⁽⁴⁾). If now r ≤ 2k − 2, we can conclude that

$$\#\mathcal{S}_{n}(\boldsymbol{\pi }) \leq C \cdot {n}^{2k+2}.$$

(9)

Hence, it remains to consider the case where r = 2k − 1 and r = 2k, respectively.

To begin with, let r = 2k − 1. Then, we have either two equivalence classes with three elements or one equivalence class with four. Since $\boldsymbol{\pi }$ is matched, there must exist an i ∈ 1, …, 4 and an l ∈ 1, …, k such that P _l ⁽ⁱ⁾ is not equivalent to any other pair in the sequence P ⁽ⁱ⁾. Without loss of generality, we can assume that i = 1. In contrast to the construction of (P ⁽¹⁾, …, P ⁽⁴⁾) as above, we now alter our procedure as follows: We fix all equivalence classes except of that P _l ⁽¹⁾ belongs to. There are n ^r − 1 possibilities to accomplish that. Now we choose again one of n ⁴ possible values for $p_{1}^{(1)},\ldots ,p_{1}^{(4)}$. Hereafter, we fix q _m ⁽¹⁾, m = 1, …, l − 1, and then start from $q_{k}^{(1)} = p_{1}^{(1)}$ to go backwards and obtain the values of $p_{k}^{(1)},\ldots ,p_{l+1}^{(1)}$. Each of these steps leaves at most two choices to us, that is 2^k − 1 choices in total. But now, P _l ⁽¹⁾ is uniquely determined since $p_{l}^{(1)} = q_{l-1}^{(1)}$ and $q_{l}^{(1)} = p_{l+1}^{(1)}$ by consistency. Thus, we had to make one choice less than before, implying (9).

Now, let r = 2k. In this case, each equivalence class has exactly two elements. Since we consider a matched partition, we can find here as well an l ∈ 1, …, k such that P _l ⁽¹⁾ is not equivalent to any other pair in the sequence P ⁽¹⁾. But in addition to that, we also have an m ∈ 1, …, k such that, possibly after relabeling, P _m ⁽²⁾ is neither equivalent to any element in P ⁽¹⁾ nor to any other element in P ⁽²⁾. Thus, we can use the same argument as before to see that this time, we can reduce the number of choices to at most C ⋅n ^r + 2 = C ⋅n ^2k + 2. In conclusion, (9) holds for any matched partition $\boldsymbol{\pi }$. To sum up our results, we obtain that

$$\displaystyle\begin{array}{rcl} & & \mathbb{E}\left [{\left (\mathrm{tr}\mathbf{X}_{n}^{k} - \mathbb{E}\left [\mathrm{tr}\mathbf{X}_{ n}^{k}\right ]\right )}^{4}\right ] \\ & & \quad = \frac{1} {{n}^{2k}}\displaystyle\sum _{{ \boldsymbol{\pi }\in \mathcal{P}(4k), \atop \boldsymbol{\pi }\ \text{matched}} }\displaystyle\sum _{({P}^{(1)},\ldots ,{P}^{(4)})\in \mathcal{S}_{n}\left (\boldsymbol{\pi }\right )}\mathbb{E}\Big[\displaystyle\prod _{j=1}^{4}\left (a_{ n}({P}^{(j)}) - \mathbb{E}\left [a_{ n}({P}^{(j)})\right ]\right )\Big] \\ & & \quad \leq C \cdot {n}^{2}, \\ \end{array}$$

which is the statement of Lemma 3.5. □ 

From Lemma 3.5 and Chebyshev’s inequality, we can now conclude that for any $\epsilon > 0$ and any $k,n \in \mathbb{N}$,

$$\mathbb{P}\left (\left \vert \frac{1} {n}\mathrm{tr}\mathbf{X}_{n}^{k} - \mathbb{E}\left [ \frac{1} {n}\mathrm{tr}\mathbf{X}_{n}^{k}\right ]\right \vert > \epsilon \right ) \leq \frac{C} {{\epsilon }^{4}{n}^{2}}.$$

Hence, the convergence in expectation part of Theorem 2.2 together with the Borel-Cantelli lemma yield that

$$\lim _{n\rightarrow \infty }\frac{1} {n}\mathrm{tr}\mathbf{X}_{n}^{k} = \mathbb{E}\left [{Y }^{k}\right ]\qquad \text{almost surely},$$

where Y is distributed according to the standard semi-circle law. In particular, we have that, with probability 1, the empirical spectral distribution of X _n converges weakly to the semi-circle law. This finishes the proof of Theorem 2.2.

Theorem 2.4 can be proved along the lines of the proof of Theorem 2.1.21 in [2]. Indeed, by a result of Hoffman and Wielandt for any two symmetric n ×n matrices A and B and their ordered eigenvalues $\lambda _{1}^{\mathbf{A}} \leq \ldots \leq \lambda _{n}^{\mathbf{A}}$ and $\lambda _{1}^{\mathbf{B}} \leq \ldots \leq \lambda _{n}^{\mathbf{B}}$, respectively, it holds

$$\displaystyle\sum _{i=1}^{n}\vert \lambda _{ i}^{\mathbf{A}} -\lambda _{ i}^{\mathbf{B}}\vert \leq \mathrm{ tr}{(\mathbf{A} -\mathbf{B})}^{2}.$$

Since for random matrices the right hand side just depends on the second moments of the entries of A and B, this bound can be used to establish a truncation technique and first show a semicircle law in probability for the truncated matrices (as above) and then extend it to matrices satisfying (C1’). For details we refer to the proof of Theorem 2.1.21 in [2].

4 Examples

4.1 Gaussian Processes

Let $\left \{a(p,p + r),p \in \mathbb{N}\right \}$, $r \in \mathbb{N}_{0}$, be independent families of stationary Gaussian Markov processes with mean 0 and variance 1. In addition to this, we assume that the processes are non-degenerate in the sense that $\mathbb{E}\left [a(p,p + r)\vert a(q,q + r),q \leq p - 1\right ]\neq a(p,p + r)$. In this case, the conditions of Theorem 2.2 are satisfied. Indeed, for fixed $r \in \mathbb{N}_{0}$ and any $p \in \mathbb{N}$, we can represent a _p : = a(p, p + r) as

$$a_{p} = x_{p}\displaystyle\sum _{j=1}^{p}y_{ j}\xi _{j},$$

where ξ _j is a family of independent standard Gaussian variables and $x_{p},y_{1},\ldots ,y_{p} \in \mathbb{R}\setminus \left \{0\right \}$. Then, we obtain

$$c(\tau ) := \vert \mathrm{Cov}(a_{p},a_{p+\tau })\vert = \left \vert \frac{x_{p+\tau }} {x_{p}} \right \vert ,$$

implying c(τ) = c(1)^τ for any $\tau \in \mathbb{N}_{0}$. By calculating the second moment of a ₂ = x ₂ y ₂ ξ ₂ + Cov(a ₁, a ₂)a ₁, we can conclude that $c(1) < 1$. Thus, condition (C4) is satisfied for any $\epsilon > 0$.

4.2 Markov Chains with Finite State Space

We want to verify that condition (C4) holds for stationary N-state Markov chains which are aperiodic and irreducible. Let $\left \{X_{k},k \in \mathbb{N}\right \}$ be such a Markov chain on the state space S = { s ₁, …, s _N } with mean 0 and variance 1. Denote by π its stationary distribution. In [13], Theorem 4.9, it is stated that for some constant C > 0 and some α ∈ (0, 1),

$$\max _{i,j\in \{1,\ldots ,N\}}\vert \mathbb{P}(X_{k} = s_{i}\ \vert \ X_{1} = s_{j}) -\pi (i)\vert \leq {C\alpha }^{k-1},\quad k \in \mathbb{N}.$$

In particular, we obtain

$$\vert \mathrm{Cov}(X_{k},X_{1})\vert = \left \vert \displaystyle\sum _{i,j=1}^{N}s_{ i}s_{j}\left (\mathbb{P}(X_{k} = s_{i}\ \vert \ X_{1} = s_{j}) -\pi (i)\right )\pi (j)\right \vert \leq {C\alpha }^{k-1}.$$

Thus Cov(X _k , X ₁) decays exponentially to 0 as k → ∞ and condition (C4) is satisfied.

4.3 Fractional Brownian Motion

We want to consider a stochastic process that exhibits long-range dependence but satisfies condition (C4) nevertheless. To this end, consider fractional Brownian motion (B _t ^H) _t with Hurst parameter (or index) H. Recall that B _t ^H is a continuous stochastic process, starting in 0, obeying $\mathbb{E}B_{t}^{H} = 0$ for all t and

$$\mathrm{Cov}(B_{t}^{H},B_{ s}^{H}) = \frac{1} {2}({t}^{2H} + {s}^{2H} -\vert t - s{\vert }^{2H}).$$

In particular,

$$\mathbb{V}(B_{t}^{H}) = {t}^{2H}$$

implying that for Hurst parameter $H = \frac{1} {2}$ the process is a Brownian motion. A standard reference for fractional Brownian motion is the textbook by Samorodnitsky and Taqqu [15], Chap. 7.

Now for each diagonal, we take independent fractional Brownian motions with index H ∈ (0, 1) and for the entries $\{X_{k},k \in \mathbb{N}\}$ on a (fixed) diagonal, we take the integer times of fractional Gaussian noise, i.e. $X_{k} = B_{k}^{H} - B_{k-1}^{H}$. Thus the $\{X_{k},k \in \mathbb{N}\}$ are stationary with mean zero and variance one. Using the above covariance formula it can be further shown that for H≠1 ∕ 2,

$$\mathrm{Cov}(X_{k+1},X_{1}) = \frac{1} {2}\left ({(k + 1)}^{2H} - 2{k}^{2H} + {(k - 1)}^{2H}\right ) \sim H(2H - 1){k}^{2H-2},$$

as k → ∞ (cf. [7], Proposition 3.1). Hence, condition (C4) is satisfied. In particular, the sum $\sum _{k=0}^{\infty }\vert \mathrm{Cov}(X_{k+1},X_{1})\vert$ diverges if 1 ∕ 2 < H < 1 implying that we have a long-range dependence.