The Spectral Distribution of Random Mixed Graphs

Abstract

In this work, we propose a random mixed graph model $G_n(p\left(n\right),q\left(n\right))$ that incorporates both the classical Erdős-Rényi’s random graph model and the random oriented graph model. We show that the empirical spectral distribution of $G_n(p\left(n\right),q\left(n\right))$ converges to the standard semicircle law under some mild condition, and the Monte Carlo simulation highly agrees with our result.

1. Introduction

A mixed graph $G=(V,E)$ is a graph with vertex set $V=\{v_1,v_2,\dots ,v_n\}$ and edge set $E=\{e_1,e_2,\dots ,e_m\}$, in which some edges may be undirected and some may be directed. In this paper, the Hermitian adjacency matrix is defined in such a way that the digons (i.e., a pair of arcs with the same end vertices but in opposite directions) may be thought of as undirected edges. From this point of view, digraphs are equivalent to the class of mixed graphs we consider here. The underlying graph of a mixed graph G, denoted by $\Gamma \left(G\right)$, is the undirected graph that keeps all vertices and edges of G and change every arc of G to an undirected edge.

The notion of a mixed graph generalizes the classical approach of orienting either all edges or none. Undirected graphs, oriented graphs and digraphs are special cases of mixed graphs. We denote an edge (no matter it is directed or not) joining two vertices u and v in G by $uv$. A subgraph of a mixed graph is called mixed walk, mixed path or mixed cycle if its underlying graph is a walk, path or cycle, respectively. However, by the terms of order, size, number of components, degree of a vertex, and distance, we mean that they are the same as in their underlying graphs. Let W be a mixed walk of a mixed graph G, its underlying graph $\Gamma \left(W\right)$ (the undirected graph spanned by W in G) may contain parallel edges since W may go through an edge or arcs (no matter in which direction) several of times and thus not necessarily simple. If we take the edge set of $\Gamma \left(W\right)$ without multiplicities, this edge set can span a simple undirected graph which we denote it by $\overline{\Gamma }\left(W\right)$. For undefined terminology and notation, we refer the reader to [1].

Let $G_n(p,q):=G_n(p\left(n\right),q\left(n\right))$ be a random mixed graph on the set of vertices $\{v_1,v_2,\dots ,v_n\}$ in which independently for each pair of vertices $v_k,v_{\ell }$ (with $k\ne \ell$), there is an undirected edge $v_k{v}_{\ell }$ with probability p; there is an arc $v_k{v}_{\ell }$ from $v_k$ to $v_{\ell }$ (and the reverse arc $v_{\ell }{v}_k$ does not occur) with probability q; there is an arc $v_{\ell }{v}_k$ from $v_{\ell }$ to $v_k$ (and the reverse directed edge does not occur) with probability q; and finally there is no any undirected edge or arc between $v_k$ and $v_{\ell }$ with probability $1-p-2q$ (with $p,q,p+2q\in [0,1]$). It is immediately to see that $G_n(p,q)$ is a mixed graph. Note that if we set $q=0$, then the model $G_n(p,0)$ is the classical Erdős and Rényi’s random graph model, see [2]; if we set $p=0$, then the model $G_n(0,q/2)$ is the random oriented graph model, see [3]; if we set $q=\sqrt{p}-p$, then $G_n(p,\sqrt{p}-p)$ is the random mixed graph model in [4]. Since the parameter $q=\sqrt{p}-p$, it is easy to see that the random mixed graph model in [4] is not a generalization of the classical Erdős and Rényi’s random graph model. Thus, it is natural for us to build a rather generalized random mixed graph model $G_n(p,q)$, which incorporates both classical Erdős and Rényi’s random graph model and the random oriented graph model.

Note that our model is different with the Łuczak and Cohen’s three-parameter random digraphs model [5], as their parameters are absolute constants, but the parameters in our model are functions on n, i.e., $p=p\left(n\right)$ and $q=q\left(n\right)$. What is more, they use their model for the study of phase transition of a giant strongly connected component. We will use our model for the study of empirical spectral distribution.

For a digraph G, its classical adjacency matrix is a $0-1$ matrix $A\left(G\right)$ with rows and columns indexed by the vertices of G, such that the $uv$-entry of $A\left(G\right)$ is equal to 1 if there is an arc from u to v and 0 otherwise. Thus, the classical adjacency matrix of a digraph is not necessary to be symmetric or Hermitian, and thus we cannot guarantee all its eigenvalues to be real. This fact makes the study of the spectrum of digraphs or mixed graphs more difficult than that of undirected graphs. Therefore, Liu and Li [6] and Guo and Mohar [7] independently introduced the Hermitian adjacency matrices of mixed graphs or digraphs. In this work, we will make use of this concept to study the spectral distribution of random mixed graphs.

For brevity, asymptotic notation is used under the assumption that $n\to \infty$. For functions f and g of parameter n, we use the notation: $f=\omega \left(g\right)$ if $\left|f\right|/\left|g\right|\to \infty$ as $n\to \infty$.

The Hermitian adjacency matrix of $G_n(p,q)$, denoted by $H\left(G_n(p,q)\right)={\left(h_{k\ell }\right)}_{n\times n}$ (or $H_n$, for brevity), satisfies that:

• $H_n$ is a Hermitian matrix with $h_{k\ell }={\overline{h}}_{\ell k}$ for $1\le k,\ell \le n$ and all diagonal entries $h_{kk}=0,1\le k\le n$;
• The upper-triangular entries $h_{k\ell }(1\le k<\ell \le n)$ are independently identically distributed (i.i.d.) copies of a random variable $\xi$, which takes value 1 with probability p, $\mathbf{i}$ with probability q, $-\mathbf{i}$ with probability q, and 0 with probability $1-p-2q$,

where $\mathbf{i}$ is the imaginary unit with $\mathbf{i}=\sqrt{-1}$. Note that $\mathbf{E}\left(\xi \right)=1·p+\mathbf{i}·q+(-\mathbf{i})q+0·(1-p-2q)=p$, and

$$\begin{array}{cc}\hfill {\sigma }^2:& =\mathbf{Var}\left(\xi \right)=\mathbf{E}\left[(\xi -\mathbf{E}\left(\xi \right))\overline{(\xi -\mathbf{E}(\xi \left)\right)}\right]={\mathbf{E}\left(\right|\xi |}^2{) - |\mathbf{E}\left(\xi \right)|}^2\hfill \\ \hfill & =1·[p+2q]+0·(1-p-2q)-p^2\hfill \\ \hfill & =p+2q-p^2.\hfill \end{array}$$

Let ${\left\{M_n\right\}}_{n=1}^{\infty }$ be a sequence of $n\times n$ random Hermitian matrices. Suppose that ${\lambda }_1\left(M_n\right),{\lambda }_2\left(M_n\right)$, $\dots ,{\lambda }_n\left(M_n\right)$ are the eigenvalues of $M_n$. The empirical spectral distribution (ESD) of $M_n$ is defined by

$$F^{M_n}\left(x\right)=\frac{1}{n}\#\left\{{\lambda }_k\left(M_n\right)\right|{\lambda }_k\left(M_n\right)\le x,k=1,2,\cdots ,n\},$$

where $\#\{·\}$ is the cardinality of the set.

The distribution to which the ESD of $M_n$ converges as $n\to \infty$ is called the limiting spectral distribution (LSD) of ${\left\{M_n\right\}}_{n=1}^{\infty }$.

Wigner matrix, denoted by $X_n$, is an $n\times n$ random Hermitian matrix satisfying:

• The upper-triangular entries $x_{k\ell }(1\le k<\ell \le n)$ are i.i.d. complex random variables with zero mean and unit variance;
• The diagonal entries $x_{kk}(1\le k\le n)$ are i.i.d. real random variables, independent of the upper-triangular entries, with zero mean;
• For each positive integer r, $max\left\{\mathbf{E}\left(\right|x_{11}{|}^r),\mathbf{E}(|x_{12}{|}^r)\right\} <\infty$.

Let ${\left\{X_n\right\}}_{n=1}^{\infty }$ be a sequence of Wigner matrices. Then, Wigner’s Semicircle Law [8] says that, with probability 1, the ESD of $n^{-1/2}{X}_n$ converges to the standard semicircle distribution whose density is given by

$$\rho \left(x\right)=\left\{\begin{array}{cc}\frac{1}{2\pi }\sqrt{4-x^2},\hfill & \mathrm{for}\left|x\right|\le 2,\hfill \\ 0,\hfill & \mathrm{for}\left|x\right|>2.\hfill \end{array}\right.$$

Before we give our main results and their proofs, we need the following results.

Lemma 1

(See [9] Lemma 2.4). The number of closed mixed walks of length $2s$, which went through each of its edge $v_k{v}_{\ell }$ from vertex $v_k$ to vertex $v_{\ell }$ once and its reverse from vertex $v_{\ell }$ to vertex $v_k$ once and the underlying graph of the closed mixed walk of a tree is $\frac{1}{s + 1}\left(\genfrac{}{}{0pt}{}{2s}{s}\right)$.

Lemma 2

(See [9] Lemma 2.1). For a non-negative integer r, we have

$${\int }_{-2}^2{x}^r\rho \left(x\right)dx= \left\{\begin{array}{cc}0,\hfill & \mathrm{for}r=2s + 1,\hfill \\ \frac{1}{s+1}\left(\genfrac{}{}{0pt}{}{2s}{s}\right),\hfill & \mathrm{for}r=2s.\hfill \end{array}\right.$$

Lemma 3

(See [9] Theorem A.43). Let A and B be two $n\times n$ Hermitian matrices, then

$$\parallel F^A-F^B\parallel \le \frac{1}{n}\mathrm{rank}(A-B),$$

where $\parallel f\parallel :={sup}_x\left|f\left(x\right)\right|$ for a function $f\left(x\right)$, and $F^A$ means the ESD of A.

Lemma 4

(Dini’s theorem, see [10] p. 64). Suppose that the sequence of continuous functions $\left\{s_n\left(x\right)\right\}$ converges to continuous function $s\left(x\right)$ on $[a,b]$ pointwisely. If, for any $x\in [a,b]$, the sequence $\left\{s_n\left(x\right)\right\}$ is monotone, then $\left\{s_n\left(x\right)\right\}$ converges to $s\left(x\right)$ uniformly.

The following result is from [11] p. 264, and we give a proof of it in Appendix A.

Lemma 5.

For any distribution function H, if ${\int \left|x\right|}^{k}dH<\infty$, then

$$\underset{n\to \infty }{lim}\left(n^{(k-s)/2}{\int }_{\left|x\right|<\sqrt{n}}{\left|x\right|}^{s}dH\right)=0,\forall s\ge k+1.$$

Lemma 6

(Bernstein’s inequality, see [9] p. 21). If $X_1,X_2,\cdots ,X_n$ are independent random variables with mean zero and uniformly bounded by b, then for any $ϵ>0$,

$$\mathbf{P}\left(\right|S_n|\ge ϵ)\le 2exp(-\frac{{ϵ}^2}{2(B_n^2+bϵ)}),$$

where $S_n=X_1+X_2+\cdots +X_n$ and $B_n^2=\mathbf{E}\left(S_n^2\right)$.

Lemma 7

(Borel–Cantelli lemma, see [12] Theorem 3.18). Let $E_1,E_2,\cdots$ be a sequence of events in some probability space. If the sum of the probabilities of the $E_n$ is finite, that is ${\sum }_{n=1}^{\infty }\mathbf{P}\left(E_n\right)<\infty$, then the probability that infinitely many of them occur is 0, that is,

$$\mathbf{P}(\underset{n\to \infty }{lim\; sup}{E}_n)=0.$$

Remark 1.

As a result of Lemma 7, for any $ϵ>0$ and any sequence $\left\{X_n\right\}$ of random variables, we have

• If ${\sum }_{n=1}^{\infty }\mathbf{P}\left(\right|X_n|\ge ϵ)<\infty$, then $X_n\to 0a.s.$
• If ${\sum }_{n=1}^{\infty }\mathbf{E}{\left|X_n-X\right|}^k<\infty ,k>0$, then $X_n\to Xa.s$.

Define

$$M_n:=\frac{1}{\sigma }[H_n-p(J_n-I_n)]=\left({\eta }_{k\ell }\right),$$

where $p:=p\left(n\right)$ is the parameter from $G_n(p,q)$, $\sigma =\sqrt{p(1-p)+2q}$, $J_n$ is the all-ones matrix of order n and $I_n$ is the identity matrix of order n. It is easy to check that

• $M_n$ is Hermitian matrix;
• The diagonal entries ${\eta }_{kk}=0$ and the upper-triangular entries ${\eta }_{k\ell }(1\le k<\ell \le n)$ are i.i.d. copies of random variable $\eta$ which takes value $\frac{1 - p}{\sigma }$ with probability p, $\frac{\mathbf{i} - p}{\sigma }$ with probability q, $\frac{-\mathbf{i} - p}{\sigma }$ with probability q, and $\frac{-p}{\sigma }$ with probability $1-p-2q$.

Note that $\mathbf{E}\left(\eta \right)=\mathbf{E}\left(\frac{\xi - p}{\sigma }\right)=\frac{\mathbf{E}\left(\xi \right) - p}{\sigma }=0,\mathbf{Var}\left(\eta \right)=\mathbf{Var}\left(\frac{\xi - p}{\sigma }\right)=\frac{\mathbf{Var}\left(\xi \right)}{{\sigma }^2}=1$ and the expectation

$$\begin{array}{cc}\hfill \mathbf{E}\left(\right|\eta {|}^s)=& \mathbf{E}\left(\right|\frac{\xi -p}{\sigma }{|}^s)=\frac{\mathbf{E}\left(\right|\xi -p{|}^s)}{{\sigma }^s}\hfill \\ \hfill =& \frac{{\left|1-p\right|}^s·p+{\left|\mathbf{i}-p\right|}^s·q+{\left|-\mathbf{i}-p\right|}^s·q+{\left|0-p\right|}^s·(1-p-2q)}{{(p+2q-p^2)}^{s/2}}\hfill \\ \hfill =& \frac{p{(1-p)}^s+2q{(1+p^2)}^{s/2}+(1-p-2q)p^s}{{(p(1-p)+2q)}^{s/2}}.\hfill \end{array}$$

(1)

On one hand, since $0\le p:=p\left(n\right),q:=q\left(n\right),1-p-2q\le 1$, it can easily see from (1) that if ${\sigma }^2=p(1-p)+2q\nrightarrow 0$ as $n\to \infty$, then $\mathbf{E}\left(\right|\eta {|}^s)<\infty$ for every positive integer s as $n\to \infty$. Then ${\left\{M_n\right\}}_{n=1}^{\infty }$ is a sequence of Wigner matrices and hence LSD of ${\left\{M_n\right\}}_{n=1}^{\infty }$ is immediate by the Wigner’s Semicircle Law. On the other hands, if ${\sigma }^2\to 0$ as $n\to \infty$, then $\mathbf{E}\left(\right|\eta {|}^s)\to \infty$ for every positive integer $s\ge 3$ as $n\to \infty$. Then, ${\left\{M_n\right\}}_{n=1}^{\infty }$ is not a sequence of Wigner matrices. Thus, if ${\sigma }^2\to 0$ as $n\to \infty$, the LSD of $M_n$ cannot be directly derived by the Wigner’s Semicircle Law. In fact, if ${\sigma }^2\to 0$ as $n\to \infty$, then either $p\to 0,q\to 0$ or $p\to 1,q\to 0$.

For the case $p\to 0,q\to 0$, we have

$${\mathbf{E}\left(\right|\eta |}^s)\ge \frac{p{(1-p)}^s}{{(p(1-p)+2q)}^{s/2}}\ge \frac{p{(1-p)}^s}{p^{s/2}{(1-p)}^{s/2}}=\frac{{(1-p)}^{s/2}}{p^{s/2-1}}\to +\infty .$$

For the case $p\to 1,q\to 0$, we have

$${\mathbf{E}\left(\right|\eta |}^s)\ge \frac{(1-p-2q)p^s}{{(p(1-p)+2q)}^{s/2}}\ge \frac{(1-p)p^s}{p^{s/2}{(1-p)}^{s/2}}=\frac{p^{s/2}}{{(1-p)}^{s/2-1}}\to +\infty .$$

From the discussion above, we have:

Lemma 8.

The sequence of matrices ${\left\{M_n\right\}}_{n=1}^{\infty }$ are Wigner’s matrices if and only if ${\sigma }^2\nrightarrow 0$.

Now, we arrive at the main results in the following, which say that even when ${\sigma }^2\to 0$, we still can get the semicircle distribution of LCD of the corresponding sequences of matrices if $n{\sigma }^2\to \infty$ holds.

Theorem 1.

Let ${\left\{H_n\right\}}_{n=1}^{\infty }$ be a sequence of Hermitian adjacency matrices of random mixed graphs ${\left\{G_n(p,q)\right\}}_{n=1}^{\infty }$ with $p:=p\left(n\right),q:=q\left(n\right)$ and ${\sigma }^2=p(1-p)+2q$ $(0\le p,q,1-(p+2q)\le 1)$. If ${\sigma }^2=\omega \left(\frac{1}{n}\right)$, then with probability 1, the ESD of $\frac{1}{\sigma \sqrt{n}}{H}_n$ converges to the standard semicircle distribution with density $\rho \left(x\right)$.

Note that the above result considers an ensemble of random Hermitian matrices, to which the corresponding random mixed graphs are not necessarily connected. Before we proceed to the proof, we use the Monte Carlo method to demonstrate Theorem 1, and it is easy to see from Figure 1 that

(1)

As $n{\sigma }^2$ changes from a small value to relatively large value, the ESD becomes more and more close to the semicircle distribution.

(2)

In the first row of the Figure 1, we set $p=0, n=1000$ and changes q increasingly from $0.001$ to $0.1$ (from right to left), then $n{\sigma }^2$ is getting larger and larger, and the ESD is getting more and more close to the semicircle distribution.

(3)

In the second row, the similar things happen as the first line except that we fix $q=0,$ $n=1000$ and change p increasingly from $0.001$ to $0.1$ (from right to left).

(4)

In the third row, we fix $n=1000$ and increase the values of $p,q$ (from right to left). At this time, we find $n{\sigma }^2$ increases simultaneously with $p,q$ and the ESD is getting more and more close to the semicircle distribution.

(5)

In the fourth row, we fix $p=q=0.01$ and change n from $10,100$, 10,000 (from right to left) and at the meantime corresponding $n{\sigma }^2$ increases. Finally, we restore the semicircle law.

(6)

In the fifth row we fix $q=0.01,n=1000$ and increase the value of p and we find that $n{\sigma }^2$ changes from 110 to 270 (from right to left). All ESDs fit with the semicircle law very well.

Remark 2.

The result of the theorem means that if ${\sigma }^2=\omega \left(\frac{1}{n}\right)$, then for any bounded continuous function f, we have

$$\int f\left(x\right)d{F}^{\frac{1}{\sigma \sqrt{n}}{H}_n\left(\alpha \right)}\left(x\right)\to \int f\left(x\right)dF\left(x\right)a.s.$$

Clearly,

$$\frac{1}{n}\sum _{i=1}^{n}f\left({\lambda }_i\right)\to \int f\left(x\right)\rho \left(x\right)dxa.s.$$

Here, ${\lambda }_i:={\lambda }_i\left(\frac{1}{\sigma \sqrt{n}}{H}_n\left(\alpha \right)\right)$ is the eigenvalue of the matrix $\frac{1}{\sigma \sqrt{n}}{H}_n\left(\alpha \right)$. The proof is exactly the Theorem 1.15 in [13] and we omit it.

Remark 3.

If we set $q=0$, then our model $G_n(p,0)$ is the classical Erdős and Rényi’s random graph model. Since if $p=\omega \left(\frac{1}{n}\right)$, then ${\sigma }^2=\omega \left(\frac{1}{n}\right)$. Thus, we could get the result of Theorem 1.3 in [14] as a corollary. Note that the paper [14] is to deal with a much more difficult situation and the original proof of Wigner [8] may be extended without difficulty to derive Theorem 1.3.

Since ${\sigma }^2=\omega \left(\frac{1}{n}\right)$ is equivalent to $p=\omega \left(\frac{1}{n}\right)$ or $1-p=\omega \left(\frac{1}{n}\right)$. We could say more than that.

Corollary 1

([14]). Let ${\left\{H_n\right\}}_{n=1}^{\infty }$ be a sequence of adjacency matrices of random graphs ${\left\{G_n(p,0)\right\}}_{n=1}^{\infty }$ with $p:=p\left(n\right)$ and ${\sigma }^2=p(1-p)$ $(0\le p,1-p\le 1)$. If $p=\omega \left(\frac{1}{n}\right)$ or $1-p=\omega \left(\frac{1}{n}\right)$, then with probability 1, the ESD of $\frac{1}{\sigma \sqrt{n}}{H}_n$ converges to the standard semicircle distribution with density $\rho \left(x\right)$.

Remark 4.

If we set $p=0$, then our model $G_n(0,q/2)$ is essentially the random oriented graph model since the skew-adjacency matrix $S\left(G\right)=\mathbf{i}H\left(G\right)$ for an oriented graph G. Therefore, they share the same spectral distribution. Since if $q=\omega \left(\frac{1}{n}\right)$, then ${\sigma }^2=\omega \left(\frac{1}{n}\right)$. Thus, we could get the result of Theorem 3.1 in [3] as a corollary.

Corollary 2

([3]). Let ${\left\{H_n\right\}}_{n=1}^{\infty }$ be a sequence of Hermitian adjacency matrices of random oriented graphs ${\left\{G_n(0,q/2)\right\}}_{n=1}^{\infty }$ with $q:=q\left(n\right)$ and ${\sigma }^2=q$ $(0\le q\le 1)$. If $q=\omega \left(\frac{1}{n}\right)$, then with probability 1, the ESD of $\frac{1}{\sigma \sqrt{n}}{H}_n$ converges to the standard semicircle distribution with density $\rho \left(x\right)$.

The proof of Theorem 1 will be given in the sequel. We shall first prove the following result.

Theorem 2.

If ${\sigma }^2=\omega \left(\frac{1}{n}\right)$, then with probability 1, the ESD of $T_n:=n^{-1/2}{M}_n$ converges to the standard semicircle distribution.

Proof. 

Denote $T_{r,n}$ the r-th moment of the ESD of $T_n$. Since the standard semicirlular distribution F has finite support, it is uniquely characterized by its sequences of moments. Thus, to prove the weak convergence of $F^{T_n}$ to F, it is equivalent to prove the convergence of moments by the Moment Convergence Theorem (see, e.g., [9]), that is

$$T_{r,n}=\int x^{r}d{F}^{T_n}\left(x\right)\to \int x^r\rho \left(x\right)dxa.s.n\to \infty ,r=1,2,\dots$$

(2)

Since

$$\begin{array}{cc}\hfill T_{r,n}=& \int x^{r}d{F}^{T_n}\left(x\right)=\frac{1}{n}\sum _{k=1}^n{\lambda }_k^r\left(T_n\right)\hfill \\ \hfill =& \frac{1}{n}\mathrm{trace}\left(T_n^r\right)=\frac{1}{n}\mathrm{trace}[{(\frac{1}{\sqrt{n}}{M}_n)}^r]\hfill \\ \hfill =& \frac{1}{n^{1+r/2}}\mathrm{trace}\left(M_n^r\right)\hfill \\ \hfill =& \frac{1}{n^{1+r/2}}\sum _{1\le k_1,\dots ,k_r\le n}{\eta }_{k_1{k}_2}{\eta }_{k_2{k}_3}\cdots {\eta }_{k_r{k}_1},\hfill \end{array}$$

(3)

where $W:=v_{k_1}{v}_{k_2}\cdots v_{k_{r-1}}{v}_{k_r}{v}_{k_1}$ corresponds to a closed mixed walk of length r in the complete digraph $D{K}_n$ of order n, and $D{K}_n$ is formed by replacing every undirected edge with a pair of arcs in opposite directions in the complete undirected graph $K_n$ of order n. For each edge $v_k{v}_{\ell }\in E\left(\overline{\Gamma }\left(W\right)\right)$, let $q_{k\ell }^W$ be the number of times that the walk W goes from vertex $v_k$ to vertex $v_{\ell }$. Let $m_{k\ell }^W:=q_{k\ell }+q_{\ell k}$. If there is no ambiguity, we will omit the upper symbol for brevity.

Let

$$\eta \left(W\right):=\prod _{v_k{v}_{\ell }\in E(\overline{\Gamma }\left(W\right))}{\eta }_{k\ell }^{q_{k\ell }}{\eta }_{\ell k}^{q_{\ell k}}.$$

Then we rewrite (3) as

$$T_{r,n}=\frac{1}{n^{1+r/2}}\sum _W\eta \left(W\right)=\frac{1}{n^{1+r/2}}\sum _W\prod _{v_k{v}_{\ell }\in E(\overline{\Gamma }\left(W\right))}{\eta }_{k\ell }^{q_{k\ell }}{\eta }_{\ell k}^{q_{\ell k}}.$$

(4)

Here, the summation is taken over all closed mixed walks W of length r. Note that all different edges (with different pair of end vertices) of a mixed graph are mutually independent, we have

$$\mathbf{E}\left(T_{r,n}\right)=\frac{1}{n^{1+r/2}}\sum _W\mathbf{E}\left(\eta \left(W\right)\right)=\frac{1}{n^{1+r/2}}\sum _W\prod _{v_k{v}_{\ell }\in E(\overline{\Gamma }\left(W\right))}\mathbf{E}\left({\eta }_{k\ell }^{q_{k\ell }}{\eta }_{\ell k}^{q_{\ell k}}\right).$$

(5)

Define ${\tilde{M}}_n=\left({\eta }_{k\ell }^{\prime }\right)$, where

$${\eta }_{k\ell }^{\prime }=\left\{\begin{array}{cc}{\eta }_{k\ell },\hfill & \mathrm{if}|{\eta }_{k\ell }| <\sqrt{n},\hfill \\ 0,\hfill & \mathrm{if}|{\eta }_{k\ell }| \ge \sqrt{n}.\hfill \end{array}\right.$$

Let

$${\tilde{T}}_n=\frac{1}{\sqrt{n}}{\tilde{M}}_n=(\frac{{\eta }_{k\ell }^{\prime }}{\sqrt{n}}),$$

and $T_{r,n}^{\prime }$ be the r-th moment of the ESD of the matrix ${\tilde{T}}_n$. Similar to (3)–(5), we have

$$T_{r,n}^{\prime }=\frac{1}{n^{1+r/2}}\sum _W{\eta }^{\prime }\left(W\right)=\frac{1}{n^{1+r/2}}\sum _W\prod _{v_k{v}_{\ell }\in E(\overline{\Gamma }\left(W\right))}{{\eta }^{\prime }}_{k\ell }^{q_{k\ell }}{{\eta }^{\prime }}_{\ell k}^{q_{\ell k}},$$

(6)

and

$$\mathbf{E}\left(T_{r,n}^{\prime }\right)=\frac{1}{n^{1+r/2}}\sum _W\mathbf{E}\left({\eta }^{\prime }\left(W\right)\right)=\frac{1}{n^{1+r/2}}\sum _W\prod _{v_k{v}_{\ell }\in E(\overline{\Gamma }\left(W\right))}\mathbf{E}\left({{\eta }^{\prime }}_{k\ell }^{q_{k\ell }}{{\eta }^{\prime }}_{\ell k}^{q_{\ell k}}\right).$$

(7)

Next, we will prove that

Fact 1.

${lim}_{n\to \infty }\mathbf{E}\left(T_{r,n}^{\prime }\right)={\int }_{-2}^2{x}^r\rho \left(x\right)dx=\left\{\begin{array}{cc}0,\hfill & \mathrm{for}r=2s+1,\hfill \\ \frac{1}{s+1}\left(\genfrac{}{}{0pt}{}{2s}{s}\right),\hfill & \mathrm{for}r=2s.\hfill \end{array}\right.$.

Fact 2.

${lim}_{n\to \infty }{T}_{r,n}^{\prime }={lim}_{n\to \infty }\mathbf{E}\left(T_{r,n}^{\prime }\right)a.s.$

Fact 3.

${lim}_{n\to \infty }{T}_{r,n}={lim}_{n\to \infty }{T}_{r,n}^{\prime }a.s.$

Combining the above Facts 1–3, we show (2) and complete the proof. □

1.1. Proof of Fact 1

Proof. 

The second equality is just the Lemma 2. Now, we consider the remaining equality.

We decompose $\mathbf{E}\left(T_{r,n}^{\prime }\right)$ into parts ${\mathbf{E}}_{m,r,n},m=1,2,\dots ,r$, containing the m-fold sums,

$$\mathbf{E}\left(T_{r,n}^{\prime }\right)=\sum _{m=1}^r{\mathbf{E}}_{m,r,n},$$

(8)

where

$${\mathbf{E}}_{m,r,n}=\frac{1}{n^{1+r/2}}\sum _{W:|E(\overline{\Gamma }\left(W\right))|=m}\mathbf{E}\left({\eta }^{\prime }\left(W\right)\right):=\frac{1}{n^{1+r/2}}\sum _{W:|E(\overline{\Gamma }\left(W\right))|=m}\prod _{v_k{v}_{\ell }\in E(\overline{\Gamma }\left(W\right))}\mathbf{E}({\eta }_{k\ell }^{\prime q_{k\ell }}{\eta }_{\ell k}^{\prime q_{\ell k}}),$$

(9)

Here, the summation in (9) is taken over all closed mixed walks W of length r with $\left|E(\Gamma (W\left)\right)\right|=m$. Additionally, $|E\left(\overline{\Gamma }\left(W\right)\right)|=m$ means that the cardinality of the edge set of $\overline{\Gamma }\left(W\right)$ is m and thus $\left|V(\Gamma (W\left)\right)\right|\le m+1$.

For a closed mixed walk $W:=v_{k_1}{v}_{k_2}\cdots v_{k_{r-1}}{v}_{k_r}{v}_{k_1}$. Its underlying graph $\Gamma \left(W\right)$ is connected since there exists an edge between any two vertices $v_j$ and $v_{j+1},j=1,\dots ,r-1$. Note that $\Gamma \left(W\right)$ is a multigraph and $\overline{\Gamma }\left(W\right)$ is a simple graph. For a closed mixed walks W of length r with $|E\left(\overline{\Gamma }\left(W\right)\right)|=m$, if it goes through some edge only once, then $\mathbf{E}\left(W\right)=0$. Hence, if $m>\lfloor \frac{r}{2}\rfloor$, then there must be some edge that appears only once in W and thus $\mathbf{E}\left(W\right)=0$. In the following, we only consider closed mixed walks W of length r with $m\le \lfloor \frac{r}{2}\rfloor$ and $m_{k\ell }\ge 2$ for all edges $v_k{v}_{\ell }$ in $\overline{\Gamma }\left(W\right)$.

If $m_{k\ell }=2$ for an edge $v_k{v}_{\ell }$ in $\overline{\Gamma }\left(W\right)$. Then,

$$\mathbf{E}({\eta }_{k\ell }^{\prime q_{k\ell }}{\eta }_{\ell k}^{\prime q_{\ell k}})\le \mathbf{E}({|{\eta }^{\prime }|}^2)={\mathbf{E}\left(\right|\eta |}^2{I}_{\left|\eta \right|<\sqrt{n}}{) \le \mathbf{E}(\left|\eta \right|}^2) =1asn\to \infty$$

If $m_{k\ell }\ge 3$ for an edge $v_k{v}_{\ell }$ in $\overline{\Gamma }\left(W\right)$. Then, by Lemma 5 with $k=2$ and $\mathbf{E}\left(\right|{\eta }^{\prime }{|}^2{) \le \mathbf{E}(\left|\eta \right|}^2)=1$, we have

$$\mathbf{E}({\eta }_{k\ell }^{\prime q_{k\ell }}{\eta }_{\ell k}^{\prime q_{\ell k}})\le \mathbf{E}\left(\right|{\eta }_{k\ell }^{\prime }{|}^{q_{k\ell }}{|{\eta }_{\ell k}^{\prime }|}^{q_{\ell k}}) =\mathbf{E}(|{\eta }_{k\ell }^{\prime }{|}^{m_{k\ell }})=o(n^{m_{k\ell }/2-1})asn\to \infty$$

Moreover, we have

$$\mathbf{E}({\eta }_{k\ell }^{\prime q_{k\ell }}{\eta }_{\ell k}^{\prime q_{\ell k}})\le \mathbf{E}\left(\right|{\eta }_{k\ell }^{\prime }{|}^{m_{k\ell }})\le n^{m_{k\ell }/2-1}$$

(10)

for every edge $v_k{v}_{\ell }$ in $\overline{\Gamma }\left(W\right)$ with $m_{k\ell }\ge 2$.

Therefore, if we decompose the edge set of $\overline{\Gamma }\left(W\right)$ into the following set:

$$\begin{array}{cc}\hfill & E_2\left(W\right):=\left\{v_k{v}_{\ell }\right|m_{k\ell }=2in\Gamma \left(W\right)\},\hfill \\ \hfill & E_3\left(W\right):=\left\{v_k{v}_{\ell }\right|m_{k\ell }\ge 3in\Gamma \left(W\right)\},\hfill \end{array}$$

then ${\displaystyle \sum _{v_k{v}_{\ell }\in E_2\left(W\right)}}{m}_{k\ell }+{\displaystyle \sum _{v_k{v}_{\ell }\in E_3\left(W\right)}}{m}_{k\ell }=r$ and $|E_2\left(W\right)|+|E_3\left(W\right)|=m$ and we have

$$\begin{array}{cc}\hfill & \mathbf{E}\left({\eta }^{\prime }\left(W\right)\right)=\prod _{v_k{v}_{\ell }\in \overline{\Gamma }\left(W\right)}\mathbf{E}({\eta }_{k\ell }^{\prime q_{k\ell }}{\eta }_{\ell k}^{\prime q_{\ell k}})\le \prod _{v_k{v}_{\ell }\in \overline{\Gamma }\left(W\right)}\mathbf{E}\left(|{\eta }_{k\ell }^{\prime }{|}^{m_{k\ell }}\right)\hfill \\ \hfill & =\prod _{v_k{v}_{\ell }\in E_2\left(W\right)}\mathbf{E}\left(|{\eta }_{k\ell }^{\prime }{|}^{m_{k\ell }}\right)\prod _{v_k{v}_{\ell }\in E_3\left(W\right)}\mathbf{E}\left(|{\eta }_{k\ell }^{\prime }{|}^{m_{k\ell }}\right)\hfill \\ \hfill & \le \prod _{v_k{v}_{\ell }\in E_2\left(W\right)}{n}^{m_{k\ell }/2-1}\prod _{v_k{v}_{\ell }\in E_3\left(W\right)}o(n^{m_{k\ell }/2-1})\hfill \end{array}$$

Thus, if $|E_3\left(W\right)|=0$, we get $\mathbf{E}\left({\eta }^{\prime }\left(W\right)\right)\le 1$; for otherwise

$$\begin{array}{cc}\hfill \mathbf{E}\left({\eta }^{\prime }\left(W\right)\right)& \le \prod _{v_k{v}_{\ell }\in E_2\left(W\right)}{n}^{m_{k\ell }/2-1}·\prod _{v_k{v}_{\ell }\in E_3\left(W\right)}o(n^{m_{k\ell }/2-1})\hfill \\ \hfill & =n^{{\displaystyle \sum _{v_k{v}_{\ell }\in E_2\left(W\right)}}(m_{k\ell }/2-1)}·o\left(n^{{\displaystyle \sum _{v_k{v}_{\ell }\in E_3\left(W\right)}}(m_{k\ell }/2-1)}\right)\hfill \\ \hfill & =o(n^{r/2-m})\hfill \end{array}$$

Note that $|E\left(\overline{\Gamma }\left(W\right)\right)|=m,\left|V(\Gamma (W\left)\right)\right|\le m+1$, and then the number of such closed walks W of length r is at most $n^{m+1}·{(m+1)}^r$.

Now, we consider the following two cases.

Case 1. The closed walks W of length r with $E_3\left(W\right)\ne \varnothing$.

We have

$$\begin{array}{cc}\hfill {\mathbf{E}}_{m,r,n}& =\frac{1}{n^{1+r/2}}\sum _{W:|E(\overline{\Gamma }\left(W\right))|=m}\prod _{v_k{v}_{\ell }\in \overline{\Gamma }\left(W\right)}\mathbf{E}\left({{\eta }^{\prime }}_{k\ell }^{q_{k\ell }}{{\eta }^{\prime }}_{\ell k}^{q_{\ell k}}\right)\hfill \\ \hfill & \le \frac{1}{n^{1+r/2}}\sum _{W:|E(\overline{\Gamma }\left(W\right))|=m}\prod _{v_k{v}_{\ell }\in \overline{\Gamma }\left(W\right)}\mathbf{E}\left(\right|{{\eta }^{\prime }}_{k\ell }{|}^{m_{k\ell }})\hfill \\ \hfill & =\frac{1}{n^{1+r/2}}\sum _{W:|E(\overline{\Gamma }\left(W\right))|=m}\prod _{v_k{v}_{\ell }\in E_2\left(W\right)}\mathbf{E}\left(\right|{{\eta }^{\prime }}_{k\ell }{|}^{m_{k\ell }})\prod _{v_k{v}_{\ell }\in E_3\left(W\right)}\mathbf{E}\left(\right|{{\eta }^{\prime }}_{k\ell }{|}^{m_{k\ell }})\hfill \\ \hfill & \le \frac{1}{n^{1+r/2}}\sum _{W:|E(\overline{\Gamma }\left(W\right))|=m}\prod _{v_k{v}_{\ell }\in E_2\left(W\right)}(n^{m_{k\ell }/2-1})\prod _{v_k{v}_{\ell }\in E_3\left(W\right)}o(n^{m_{k\ell }/2-1})\hfill \\ \hfill & \le \frac{n^{m+1}{(m+1)}^r}{n^{1+r/2}}·o(n^{r/2-m})\hfill \\ \hfill & ={(m+1)}^r·o\left(1\right)\to 0asn\to \infty .\hfill \end{array}$$

Case 2. The closed walks W of length r with $E_3\left(W\right)=\varnothing$.

We then have $\mathbf{E}\left({\eta }^{\prime }\left(W\right)\right)\le 1$ by the above discussion. We divide this case into two subcases according to the cardinality of $V\left(\overline{\Gamma }\left(W\right)\right)$.

Subcase 2.1. The closed walks W of length r with $|V\left(\overline{\Gamma }\left(W\right)\right)|\le m$.

We have that the number of such closed walks W of length r is at most $n^m·m^r$ and

$$\begin{array}{cc}\hfill & \frac{1}{n^{1+r/2}}\sum _{\genfrac{}{}{0pt}{}{W:|E(\overline{\Gamma }\left(W\right))|=m,}{|V(\overline{\Gamma }\left(W\right))|\le m}}\mathbf{E}\left({\eta }^{\prime }\left(W\right)\right)\hfill \\ \hfill & \le \frac{1}{n^{1+r/2}}\sum _{\genfrac{}{}{0pt}{}{W:|E(\overline{\Gamma }\left(W\right))|=m,}{|V(\overline{\Gamma }\left(W\right))|\le m}}1\hfill \\ \hfill & \le \frac{n^m·m^r}{n^{1+r/2}}\hfill \\ \hfill & =\frac{m^r}{n^{1+r/2-m}}\hfill \\ \hfill & \le \frac{m^r}{n}\to 0asn\to \infty .\hfill \end{array}$$

Case 2.2. The closed walks W of length r with $|V\left(\overline{\Gamma }\left(W\right)\right)|=m+1$ and $E_3\left(W\right)=\varnothing$.

We have that $m_{k\ell }=2$ for each edge $v_k{v}_{\ell }\in E\left(\overline{\Gamma }\left(W\right)\right)$. Since $\overline{\Gamma }\left(W\right)$ is connected, $\overline{\Gamma }\left(W\right)$ is a tree with $m+1$ vertices and $q_{k\ell }=1,q_{\ell k}=1$ for every edge $v_k{v}_{\ell }\in \overline{\Gamma }\left(W\right)$. Then, $r=2m$ and W is a closed mixed walk of length $2m$, which satisfies the condition of Lemma 1. By Lemma 1, the number of such W is $\frac{1}{m+1}\left(\genfrac{}{}{0pt}{}{2m}{m}\right)$. The number of ways to choose $m+1$ vertices of W with the natural order of first appearance in W from n vertices is $n(n-1)\cdots (n-m)$. Note that $\mathbf{E}\left({\eta }^{\prime }\left(W\right)\right)\le 1$ and $\mathbf{E}\left({\eta }^{\prime }\left(W\right)\right)\to 1$, as $n\to \infty$. Thus,

$$\begin{array}{cc}\hfill & \frac{1}{n^{1+m}}\sum _{\genfrac{}{}{0pt}{}{W:\left|E(\Gamma (W\left)\right)\right|=m,}{|E(\overline{\Gamma }\left(W\right))|=m+1}}\mathbf{E}\left({\eta }^{\prime }\left(W\right)\right)\hfill \\ \hfill & \to \frac{1}{n^{1+m}}\sum _{\genfrac{}{}{0pt}{}{W:\left|E(\Gamma (W\left)\right)\right|=m,}{|V(\overline{\Gamma }\left(W\right))|\le m}}1=\frac{n(n-1)\cdots (n-m)}{n^{1+m}}\frac{1}{m+1}\left(\genfrac{}{}{0pt}{}{2m}{m}\right)\hfill \\ \hfill & =\frac{n^{1+m}(1+O\left(n^{-1}\right))}{n^{1+m}}·\frac{1}{m+1}\left(\genfrac{}{}{0pt}{}{2m}{m}\right)=(1+O\left(n^{-1}\right))·\frac{1}{m+1}\left(\genfrac{}{}{0pt}{}{2m}{m}\right)\hfill \\ \hfill & \to \frac{1}{m+1}\left(\genfrac{}{}{0pt}{}{2m}{m}\right)asn\to \infty .\hfill \end{array}$$

Therefore,

$$\underset{n\to \infty }{lim}{\mathbf{E}}_{m,2m,n}=\frac{1}{m+1}\left(\genfrac{}{}{0pt}{}{2m}{m}\right).$$

From the above discussion, we have

$$\underset{n\to \infty }{lim}\mathbf{E}\left(T_{r,n}^{\prime }\right)=\left\{\begin{array}{cc}\frac{1}{m+1}\left(\genfrac{}{}{0pt}{}{2m}{m}\right),\hfill & \mathrm{for}r=2m.\hfill \\ 0,\hfill & \mathrm{otherwise}\hfill \end{array}\right.$$

which completes the proof. □

1.2. Proof of Fact 2

Proof. 

Note that $T_{r,n}^{\prime }=\frac{1}{n^{1+r/2}}{\sum }_W{\eta }^{\prime }\left(W\right)$ and since $T_{r,n}^{\prime }$ is a real random variable and so is $\mathbf{E}\left(T_{r,n}^{\prime }\right)$, we have

$$\begin{array}{c}\hfill \mathbf{E}\left[\right|T_{r,n}^{\prime }-\mathbf{E}\left(T_{r,n}^{\prime }\right){|}^4]=\mathbf{E}\left[{(T_{r,n}^{\prime }-\mathbf{E}\left(T_{r,n}^{\prime }\right))}^4\right]=\frac{1}{n^{4+2r}}\sum _{W_1,\dots ,W_4}\mathbf{E}(\prod _{k=1}^4[{\eta }^{\prime }\left(W_k\right)-\mathbf{E}\left({\eta }^{\prime }\left(W_k\right)\right]),\end{array}$$

(11)

due to the symmetric of $W_k(k=1,2,3,4)$, where $W_k(k=1,\dots ,4)$ corresponds to a closed mixed walk of length r in the complete digraph of order $D{K}_n$. We aim to show the righthand side in Equation (11) is $O\left(n^{-2}\right)$. Let $k_0\in \{1,2,3,4\}$. If $\overline{\Gamma }\left(W_{k_0}\right)$ has no any common edge with $\Gamma (\overline{W}\setminus W_{k_0})$, where $\overline{W}:=W_1\cup W_2\cup W_3\cup W_4$, then the corresponding expectation of the summand in Equation (11) is zero. If there is an edge $v_{k_0}{v}_{{\ell }_0}$ whose number of occurrence in $\Gamma \left(\overline{W}\right)$ is 1, then the corresponding expectation of the summand in Equation (11) is also zero. Thus, we only have to consider the case when no edge $v_{k_0}{v}_{{\ell }_0}\in E(\Gamma \left(\overline{W}\right))$ with $m_{k_0{\ell }_0}^{\overline{W}}=1$ and each $\overline{\Gamma }\left(W_k\right)$ must share at least one edge with $\overline{\Gamma }(\overline{W}\setminus W_k)$ for $k=1,2,3,4$ below. Thus,

$$\begin{array}{cc}\hfill \mathbf{E}\left(\right|T_{r,n}^{\prime }-\mathbf{E}\left(T_{r,n}^{\prime }\right){|}^4)& =\frac{1}{n^{4+2r}}\sum _{W_1,\dots ,W_4}\mathbf{E}\left(\prod _{k=1}^4[{\eta }^{\prime }\left(W_k\right)-\mathbf{E}\left({\eta }^{\prime }\left(W_k\right)\right)]\right)\hfill \\ \hfill & =\frac{1}{n^{4+2r}}\sum _{W_1,\dots ,W_4}[\mathbf{E}(\prod _{\ell =1}^4{\eta }^{\prime }\left(W_{\ell }\right))-4\mathbf{E}({\eta }^{\prime }\left(W_1\right))\mathbf{E}(\prod _{\ell =2}^4{\eta }^{\prime }\left(W_{\ell }\right))\hfill \\ \hfill & +6\mathbf{E}({\eta }^{\prime }\left(W_1\right){\eta }^{\prime }\left(W_2\right))\mathbf{E}({\eta }^{\prime }\left(W_3\right){\eta }^{\prime }\left(W_4\right))-3\prod _{\ell =1}^4\mathbf{E}({\eta }^{\prime }\left(W_{\ell }\right))]\hfill \\ \hfill & \le \frac{1}{n^{4+2r}}\sum _{W_1,\dots ,W_4}\left[\right|\mathbf{E}(\prod _{\ell =1}^4{\eta }^{\prime }\left(W_{\ell }\right))|+4|\mathbf{E}({\eta }^{\prime }\left(W_1\right))\mathbf{E}(\prod _{\ell =2}^4{\eta }^{\prime }\left(W_{\ell }\right))|\hfill \\ \hfill & +6|\mathbf{E}\left({\eta }^{\prime }\left(W_1\right){\eta }^{\prime }\left(W_2\right)\right)\mathbf{E}\left({\eta }^{\prime }\left(W_3\right){\eta }^{\prime }\left(W_4\right)\right)|+3|\prod _{\ell =1}^4\mathbf{E}({\eta }^{\prime }\left(W_{\ell }\right))\left|\right].\hfill \end{array}$$

For closed mixed walks $W_k(k=1,\dots ,4)$ of length r, let $|E(\overline{\Gamma }\left(\overline{W}\right)|=x,|E\left(\overline{\Gamma }\left(W_1\right)\right)|=x_1,$ $|E(\overline{\Gamma }({\bigcup }_{j=2}^4{W}_j))|=x_2$, then $x\le x_1+x_2,x_1\le r/2,x_2\le 3r/2,x\le 2r$ and

$$\sum _{v_k{v}_{\ell }\in E(\overline{\Gamma }(\overline{W}))}{m}_{k\ell }^{\overline{W}}=4r,$$

which implies

$$|\mathbf{E}\left({\eta }^{\prime }\left(W_1\right)\right)|\le n^{r/2-x_1},|\mathbf{E}(\prod _{j=2}^4{\eta }^{\prime }\left(W_j\right))|\le n^{3r/2-x_2}.$$

Thus,

$$|\mathbf{E}\left({\eta }^{\prime }\left(W_1\right)\right)\mathbf{E}(\prod _{j=2}^4{\eta }^{\prime }\left(W_j\right))|\le n^{4r/2-x_1-x_2}\le n^{2r-x}.$$

Similarly, we have

$$|\mathbf{E}\left({\eta }^{\prime }\left(W_1\right)\right)\mathbf{E}\left({\eta }^{\prime }\left(W_2\right)\right)\mathbf{E}(\prod _{j=3}^4{\eta }^{\prime }\left(W_j\right))|\le n^{2r-x}$$

and

$$|\mathbf{E}\left({\eta }^{\prime }\left(W_1\right)\right)\mathbf{E}\left({\eta }^{\prime }\left(W_2\right)\right)\mathbf{E}\left({\eta }^{\prime }\left(W_3\right)\right)\mathbf{E}\left({\eta }^{\prime }\left(W_4\right)\right)|\le n^{2r-x}$$

Therefore,

$$\begin{array}{cc}\hfill \mathbf{E}\left(\right|T_{r,n}^{\prime }-\mathbf{E}\left(T_{r,n}^{\prime }\right){|}^4)& \le \frac{1}{n^{4+2r}}\sum _{W_1,\dots ,W_4}14n^{2r-x}=\frac{14}{n^4}\sum _{W_1,\dots ,W_4}{n}^{-x}.\hfill \end{array}$$

Since $W_j$ is a closed mixed walk of length r, $\Gamma \left(W_j\right)(j=1,2,3,4)$ is connected. Combining the previous discussions, the connected components of $\Gamma \left(\overline{W}\right)$ is at most 2. Then, there are at most $x+2$ vertices in $\Gamma \left(\overline{W}\right)$, which means that the number of such $\overline{W}$ is at most $n^{x+2}c(x,r)$ with $c(x,r)$ a constant only depending on x and r. Hence,

$$\frac{14}{n^4}\sum _{\genfrac{}{}{0pt}{}{W_1,\dots ,W_4}{|E(\overline{\Gamma }(\overline{W})|=x}}{n}^{-x}\le \frac{14}{n^4}\sum _{x=1}^{2r}{n}^2·c(x,r)=O\left(n^{-2}\right).$$

Thus, for every positive integer r

$$\sum _{n=1}^{\infty }\mathbf{E}\left({\left|T_{r,n}^{\prime }-\mathbf{E}\left(T_{r,n}^{\prime }\right)\right|}^4\right)=\sum _{n=1}^{\infty }O\left(n^{-2}\right)<\infty$$

By Lemma 7, we have ${lim}_{n\to \infty }{T}_{r,n}^{\prime }={lim}_{n\to \infty }\mathbf{E}\left(T_{r,n}^{\prime }\right)a.s.$ This finishes the proof of Fact 2. □

1.3. Proof of Fact 3

Proof. 

Note that

$$T_{r,n}=\int x^{r}d{F}^{T_n}\left(x\right)=\int x^{r}d{F}^{n^{-1/2}{M}_n}\left(x\right)$$

and

$$T_{r,n}^{\prime }=\int x^{r}d{F}^{{\tilde{T}}_n}\left(x\right)=\int x^{r}d{F}^{n^{-1/2}{\tilde{M}}_n}\left(x\right).$$

So we have

$$\parallel F^{T_n}-F^{{\tilde{T}}_n}\parallel =\parallel F^{n^{-1/2}{M}_n}-F^{n^{-1/2}{\tilde{M}}_n}\parallel \le \frac{1}{n}\mathrm{rank}(n^{-1/2}{M}_n-n^{-1/2}{\tilde{M}}_n)=\frac{1}{n}\mathrm{rank}(M_n-{\tilde{M}}_n).$$

Notice that $\mathrm{rank}(M_n-{\tilde{M}}_n)\le$ the number of nonzero entries in $M_n-{\tilde{M}}_n$, which is bounded by ${\sum }_{1\le j,k\le n}{I}_{|{\eta }_{jk}|\ge \sqrt{n}}$, where

$$I_{\left\{\right|{\eta }_{jk}|\ge \sqrt{n}\}}=\left\{\begin{array}{cc}1,\hfill & \mathrm{if}|{\eta }_{jk}| <\sqrt{n},\hfill \\ 0,\hfill & \mathrm{if}|{\eta }_{jk}| \ge \sqrt{n}.\hfill \end{array}\right.$$

Then

$$\parallel F^{T_n}-F^{{\tilde{T}}_n}\parallel \le \frac{1}{n}\sum _{1\le j\ne k\le n}{I}_{|{\eta }_{jk}|\ge \sqrt{n}}.$$

Note that ${\eta }_{jk}={\overline{\eta }}_{kj}$, we get

$$\parallel F^{T_n}-F^{{\tilde{T}}_n}\parallel \le \frac{2}{n}\sum _{1\le j<k\le n}{I}_{|{\eta }_{jk}|\ge \sqrt{n}}$$

Here, the summation occurs among $\frac{n^2-n}{2}$ terms. We can show the convergence to zero in the righthand side almost surely using Lemma 6. In fact, set ${\beta }_n=\mathbf{P}\left(\right|\eta |\ge \sqrt{n})$, and for any $ϵ>0$, we consider

$$\begin{array}{cc}\hfill \mathbf{P}(\frac{1}{n}\sum _{1\le j<k\le n}{I}_{|{\eta }_{jk}|\ge \sqrt{n}}\ge ϵ)=& \mathbf{P}(\sum _{1\le j<k\le n}(I_{|{\eta }_{jk}|\ge \sqrt{n}}-{\beta }_n)\ge ϵn-{\beta }_n·\frac{n^2-n}{2})\hfill \\ \hfill \le & 2exp(-\frac{{(ϵn-{\beta }_n·\frac{n^2-n}{2})}^2}{2[\frac{n^2-n}{2}({\beta }_n-{\beta }_n^2)+ϵn-{\beta }_n·\frac{n^2-n}{2}]})\hfill \\ \hfill =& 2exp(-\frac{{(ϵ-{\beta }_n·\frac{n-1}{2})}^2·n}{2(ϵ-\frac{n-1}{2}{\beta }_n^2)}).\hfill \end{array}$$

Here, we have used $\mathbf{E}(I_{|{\eta }_{jk}|\ge \sqrt{n}}-{\beta }_n)=0$ and $\mathbf{Var}(I_{|{\eta }_{jk}|\ge \sqrt{n}}-{\beta }_n)={\beta }_n-{\beta }_n^2$. Note that

$$\begin{array}{cc}\hfill \frac{{(ϵ-{\beta }_n·\frac{n-1}{2})}^2}{ϵ-\frac{n-1}{2}{\beta }_n^2}\ge & \frac{{(ϵ-{\beta }_n·\frac{n-1}{2})}^2}{ϵ-\frac{n-1}{2}{\beta }_n}=ϵ-\frac{{\beta }_n(n-1)}{2}\ge ϵ-\frac{n{\beta }_n}{2}\hfill \end{array}$$

Claim. If ${\sigma }^2=\omega \left(\frac{1}{n}\right)$, then ${\beta }_n=\omega \left(\frac{1}{n}\right).$

If s be any integer no less than 3, then by the Markov’s inequality

$$\begin{array}{cc}\hfill n{\beta }_n& =n\mathbf{P}\left(\right|\eta |\ge \sqrt{n})\le n\frac{\mathbf{E}\left(\right|\eta {|}^s)}{{\left(\sqrt{n}\right)}^s}\hfill \\ \hfill =& n\frac{p{(1-p)}^s+2q{(1+p^2)}^{s/2}+(1-p-2q)p^s}{{\left[n(p+2q-p^2)\right]}^{s/2}}\hfill \\ \hfill =& \frac{np{(1-p)}^s+2nq{(1+p^2)}^{s/2}+n(1-p-2q)p^s}{{[np(1-p)+2nq]}^{s/2}}\hfill \\ \hfill =& \frac{np{(1-p)}^s}{{[np(1-p)+2nq]}^{s/2}}+\frac{2nq{(1+p^2)}^{s/2}}{{[np(1-p)+2nq]}^{s/2}}+\frac{n(1-p-2q)p^s}{{[np(1-p)+2nq]}^{s/2}}.\hfill \end{array}$$

(12)

By direct calculation, we get that each of the last three summands in (12) tends to zero if ${\sigma }^2=\omega \left(\frac{1}{n}\right)$.

By the claim above $n{\beta }_n\to 0$ if ${\sigma }^2=\omega \left(\frac{1}{n}\right)$, we can limit it less than $ϵ$ and then we have

$$\mathbf{P}(\frac{1}{n}\sum _{1\le j<k\le n}{I}_{|{\eta }_{jk}|\ge \sqrt{n}}\ge ϵ)\le 2exp(-\frac{ϵ}{2}n).$$

Finally we get

$$\sum _{n=1}^{\infty }\mathbf{P}(\frac{1}{n}\sum _{1\le j<k\le n}{I}_{|{\eta }_{jk}|\ge \sqrt{n}}\ge ϵ)<\infty ,$$

which completes the proof by Lemma 7. □

2. Proof of Theorem 1

Proof. 

Recall that

$$T_n=n^{-1/2}{M}_n=\frac{1}{\sigma \sqrt{n}}[(H_n+p{I}_n)-p{J}_n],$$

and set

$$T_n^{*}=\frac{1}{\sigma \sqrt{n}}(H_n+p{I}_n).$$

Then

$$T_n^{*}-T_n=\frac{p}{\sigma \sqrt{n}}{J}_n.$$

By Lemma 3, we have

$$\parallel F^{T_n^{*}}-F^{T_n}\parallel \le \frac{1}{n}·\mathrm{rank}\left(\frac{p}{\sigma \sqrt{n}}{J}_n\right)=\frac{1}{n}.$$

This implies that $T_n^{*}$ and $T_n$ have the same LSD. By Theorem 2, we have

$$\underset{n\to \infty }{lim}{F}^{T_n^{*}}\left(x\right)=\underset{n\to \infty }{lim}{F}^{T_n}\left(x\right)=F\left(x\right):={\int }_{-\infty }^x\rho \left(x\right)dxa.s.$$

Set $T_n^{**}=\frac{1}{\sigma \sqrt{n}}{H}_n$. Note that

$$T_n^{*}-T_n^{**}=\frac{p}{\sigma \sqrt{n}}{I}_n=:{\Delta }_n{I}_n,$$

and

$$\underset{n\to \infty }{lim}{\Delta }_n^2=\underset{n\to \infty }{lim}\frac{p^2}{n{\sigma }^2}=0as{\sigma }^2=\omega \left(\frac{1}{n}\right).$$

Since $T_n^{*}=T_n^{**}+{\Delta }_n{I}_n$, we have that $\lambda$ is an eigenvalue of $T_n^{**}$ if and only if $\lambda +{\Delta }_n$ is an eigenvalue of $T_n^{*}$. By the definition of $F^{T_n^{*}},F^{T_n^{**}}$, we know

$$\begin{array}{cc}\hfill F^{T_n^{**}}\left(x\right)=& \frac{1}{n}\#\left\{\lambda \left(T_n^{**}\right)\right|\lambda \left(T_n^{**}\right)\le x,i=1,2,\dots ,n\}\hfill \\ \hfill =& \frac{1}{n}\#\left\{\lambda \left(T_n^{**}\right)\right|\lambda \left(T_n^{**}\right)+{\Delta }_n\le x+{\Delta }_n,i=1,2,\dots ,n\}\hfill \\ \hfill =& \frac{1}{n}\#\left\{\lambda \left(T_n^{*}\right)\right|\lambda \left(T_n^{*}\right)\le x+{\Delta }_n,i=1,2,\dots ,n\}\hfill \\ \hfill =& F^{T_n^{*}}(x+{\Delta }_n).\hfill \end{array}$$

Note that by Lemma 4 and the continuity of $F\left(x\right)$, we have

$$\begin{array}{cc}\hfill \underset{n\to \infty }{lim}{F}^{T_n^{*}}(x+{\Delta }_n)=& \underset{n\to \infty }{lim}[F^{T_n^{*}}(x+{\Delta }_n)-F(x+{\Delta }_n)+F(x+{\Delta }_n)]\hfill \\ \hfill =& \underset{n\to \infty }{lim}[F^{T_n^{*}}(x+{\Delta }_n)-F(x+{\Delta }_n)]+\underset{n\to \infty }{lim}F(x+{\Delta }_n)\hfill \\ \hfill =& F\left(x\right)a.s.\hfill \end{array}$$

Finally we get

$$\underset{n\to \infty }{lim}{F}^{T_n^{**}}\left(x\right)=\underset{n\to \infty }{lim}{F}^{T_n^{*}}(x+{\Delta }_n)=F\left(x\right)a.s.$$

This completes the proof. □

3. Conclusions

In this work, we propose a random mixed graph model $G_n(p\left(n\right),q\left(n\right))$. The model generalizes the classical Erdős-Rényi’s random graph model and the random oriented graph model. Furthermore, we give a sufficient condition, i.e., if ${\sigma }^2=\omega \left(\frac{1}{n}\right)$, then with probability 1, the ESD of $\frac{1}{\sigma \sqrt{n}}{H}_n$ converges to the standard semicircle distribution. The simulation result not only supports our theorem, but also indicates that the condition may be necessary. We would like to resolve this problem in future work.