On High Moments and the Spectral Norm of Large Dilute Wigner Random Matrices
Saved in:
| Published in: | Журнал математической физики, анализа, геометрии |
|---|---|
| Date: | 2014 |
| Main Author: | |
| Format: | Article |
| Language: | English |
| Published: |
Фізико-технічний інститут низьких температур ім. Б.І. Вєркіна НАН України
2014
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/106786 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | On High Moments and the Spectral Norm of Large Dilute Wigner Random Matrices / O. Khorunzhiy // Журнал математической физики, анализа, геометрии. — 2014. — Т. 10, № 1. — С. 64-125. — Бібліогр.: 27 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860202771681116160 |
|---|---|
| author | Khorunzhiy, O. |
| author_facet | Khorunzhiy, O. |
| citation_txt | On High Moments and the Spectral Norm of Large Dilute Wigner Random Matrices / O. Khorunzhiy // Журнал математической физики, анализа, геометрии. — 2014. — Т. 10, № 1. — С. 64-125. — Бібліогр.: 27 назв. — англ. |
| collection | DSpace DC |
| container_title | Журнал математической физики, анализа, геометрии |
| first_indexed | 2025-12-07T18:11:23Z |
| format | Article |
| fulltext |
Journal of Mathematical Physics, Analysis, Geometry
2014, vol. 10, No. 1, pp. 64–125
On High Moments and the Spectral Norm of Large
Dilute Wigner Random Matrices
O. Khorunzhiy
Laboratoire de Mathématiques Université de Versailles-Saint-Quentin
45, Avenue des Etats-Unis 78035 Versailles, France
E-mail: oleksiy.khorunzhiy@uvsq.fr
Received August 8, 2011, revised July 17, 2013
We consider a dilute version of the Wigner ensemble of n×n random real
symmetric matrices H(n,ρ), where ρ denotes an average number of non-zero
elements per row. We study the asymptotic properties of the spectral norm
‖H(n,ρn)‖ in the limit of infinite n with ρn = n2/3(1+ε), ε > 0. Our main
result is that the probability P
{‖H(n,ρn)‖ > 1 + xn−2/3
}
, x > 0 is bounded
for any ε ∈ (ε0, 1/2], ε0 > 0 by an expression that does not depend on
the particular values of the first several moments V2l, 2 ≤ l ≤ 6 and V12+2φ0 ,
φ0 = φ(ε0) of the matrix elements of H(n,ρ) provided they exist and the
probability distribution of the matrix elements is symmetric. The proof is
based on the study of the upper bound of the averaged moments of random
matrices with truncated random variables E{Tr(Ĥ(n,ρn))2sn}, sn = bχn2/3c
with χ > 0, in the limit n →∞.
We also consider the lower bound of E{Tr(H(n,ρn))2sn} and show that
in the complementary asymptotic regime, when ρn = nε with ε ∈ (0, 2/3]
and n → ∞, the fourth moment V4 enters the estimates from below and
the scaling variable n−2/3 at the border of the limiting spectrum is to be
replaced by a variable related with ρ−1
n .
Key words: random matrices, Wigner ensemble, dilute random matrices,
spectral norm.
Mathematics Subject Classification 2010: 15B52.
1. Introduction
The spectral theory of random matrices of high dimensions was started by
E. Wigner in the middle of the fifties, when the eigenvalue distribution of the
The financial support of the research grant ANR-08-BLAN-0311-11 ”Grandes Matrices
Aléatoires” (France) is gratefully acknowledged
c© O. Khorunzhiy, 2014
High Moments of Large Dilute Wigner Matrices
ensemble {A(n)} of real symmetric matrices of the form
(
A(n)
)
ij
=
1√
n
aij , 1 ≤ i ≤ j ≤ n, (1.1)
where {aij , i ≤ j} are jointly independent random variables with zero mean value
and the variance v2, was studied [27]. It was proved by E. Wigner that the
normalized eigenvalue counting function of An converges in the limit n → ∞ to
a non-random limiting distribution that has the density of the semicircle form.
It is common to refer to (1.1) as to the Wigner ensemble of random matrices.
The limiting eigenvalue distribution of An is often referred to as the semicircle
(or Wigner) law.
The semicircle law was then improved and generalized in various aspects,
in particular, by relaxing the Wigner conditions on the probability distribution
of the matrix elements aij [6, 18], by the studies of different random matrix
ensembles generalizing the form of (1.1) [15], by the studies of the extremal
eigenvalues of A(n) and related ensembles [2, 4, 5], and others.
Later on, being motivated by the universality conjecture of the level repulsion
in the spectra of heavy atomic nuclei [19], a strong interest to the local properties
of the eigenvalue distribution of A(n) at the bulk and at the border of the limiting
spectrum has led to a number of powerful and deep results (see monographs [1]
and [16] and references therein). These results were mostly related with the
ensembles of the form (1.1) with the probability distribution of A(n) that belong
to a certain class of laws.
In the general situation of the Wigner ensemble (1.1), the breakthrough results
in the studies of the local properties of the eigenvalue distribution at the border of
the limiting spectrum of random matrices were obtained in [22, 23] and [25], where
the eigenvalue distribution of random matrices (1.1) was studied for the first time
on the local scale, i.e., when the mean distance between the eigenvalues is of the
order n−2/3. These results were obtained with the help of a deep improvement
of the moment method initially proposed by E. Wigner. The local asymptotic
regime at the border of the spectrum is attained in the limit n → ∞ when the
order of the moments is proportional to n2/3.
One of the generalizations of the Wigner ensemble (1.1) is given by an en-
semble of n × n real random matrices such that each row contains a random
number of non-zero elements and the mean value of this number ρn is a function
of n. Following statistical mechanics terminology, where this kind of models was
first considered, it is natural to refer to this class of random matrices as to the
sparse or dilute random matrices [17, 20]. The limiting eigenvalue distribution
of dilute random matrices or related ensembles is studied in a number of publi-
cations, where, in particular, the semicircle law is proved to be valid in the limit
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 65
O. Khorunzhiy
n, ρn → ∞ [10, 20]. The spectral properties at the edge of the limiting spec-
tra was studied in papers [7, 11], however the local asymptotic regime was not
reached there.
In the present paper, we consider the dilute version of Wigner random ma-
trices and study its spectral properties on the local regime at the border of the
limiting spectra. The paper is organized as follows. In Section 2, we describe
the random matrix ensemble we study and formulate our main theorems. The
main technical result on the upper bound of high moments of dilute Wigner ran-
dom matrices is given and the general technique of the proof of this bound is
described. In Section 3, we introduce the necessary definitions and formulate the
basic principles of the estimates obtained. Section 4 is devoted to the proof of
our main technical result and the proofs of the main theorems as well.
In Sections 5 and 6, we prove the auxiliary statements used in Sections 3 and 4.
In Section 7, we obtain the estimates from below for the high moments of dilute
Wigner random matrices; these estimates are related with certain generalizations
of Catalan numbers. In Section 8, we discuss the results obtained.
2. Main Results
Let us consider a family of the real symmetric random matrices {H(n,ρ)}
whose elements are determined by the equality
(
H(n,ρ)
)
ij
= aij b
(n,ρ)
ij , 1 ≤ i ≤ j ≤ n, (2.1)
where A = {aij , 1 ≤ i ≤ j} is an infinite family of jointly independent identically
distributed random variables, and Bn = {b(n,ρ)
ij , 1 ≤ i ≤ j ≤ n} is a family
of jointly independent random variables that are also independent from A. We
denote by E = En the mathematical expectation with respect to the measure
P = Pn generated by the random variables {A, Bn}.
We assume that the probability distribution of the random variables aij is
symmetric and denote their even moments by V2l = E(aij)2l, l ≥ 1 with V2 =
v2 = 1/4.
The random variables b
(n,ρ)
ij are proportional to the Bernoulli ones,
b
(n,ρ)
ij =
1√
ρ
{
1− δij , with probability ρ/n,
0, with probability 1− ρ/n,
(2.2)
where δij is the Kronecker δ-symbol.
Our main result is related with the asymptotic behavior of the maximal in
the absolute value eigenvalue of H(n,ρ),
λ(n,ρ)
max = ‖H(n,ρ)‖ = max
1≤k≤n
|λk(H(n,ρ))|,
66 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
in the limit when n and ρ tend to infinity.
Theorem 2.1. Let the probability distribution of aij be such that the moment
V12+2φ = E|aij |12+2φ exists with some φ > 0. If ρn = n2/3(1+ε) with any given
ε > 3
6+φ , then the limiting probability
lim sup
n→∞
P
{
λ(n,ρn)
max ≥
(
1 +
x
n2/3
)}
≤ P(x), x > 0, (2.3)
admits the universal upper bound in the sense that P(x) does not depend on the
values of V2l with 2 ≤ l ≤ 6 and V12+2φ.
Assuming more about the probability distributions of aij , one can relax the
restriction on ε of Theorem 2.1. The following statement is true.
Theorem 2.2. Let ãij , 1 ≤ i ≤ j be independent identically distributed
bounded random variables, |ãij | ≤ U, such that their probability distribution is
symmetric. Then the maximal eigenvalue λ̃
(n,ρ)
max = λmax(H̃(n,ρ)) of the random
matrix with elements H̃
(n,ρ)
ij = ãijb
(n,ρ)
ij admits the same asymptotic bound as
(2.3),
lim sup
n→∞
P
{
λ̃(n,ρn)
max ≥
(
1 +
x
n2/3
)}
≤ P(x), x > 0, (2.4)
in the limit n →∞, ρn = n2/3(1+ε̃) with any given ε̃ ∈ (0, 1/2].
R e m a r k 1. Theorems 2.1 and 2.2 remain true in the case when the random
matrices H(n,ρn) (2.1) are hermitian, where aij are complex jointly independent
random variables and b
(n,ρn)
ij are still determined by (2.2). In this case the upper
bound P(x) can be slightly diminished. This difference should disappear in the
asymptotic regime of the infinite n and ρn such that ρn ¿ n2/3. We discuss this
topic in more details in Section 8.
R e m a r k 2. Theorem 2.1 is in agreement with the statements of [8], where
the existence of the moment V12+2φ with any positive φ > 0 is proved to be
sufficient for the upper bound (2.3) to hold for ρn = n when the dilute random
matrices coincide with those of the Wigner ensemble (1.1). Moreover, the proofs
of the theorems given in the present paper hold in the case of ρn = n without
any change. Thus, by using the technique developed here, we obtain once more
the results of [8].
The proofs of Theorems 2.1 and 2.2 are related with the detailed study of the
averaged moments M(n,ρ)
2s = EL(n,ρ)
2s ,
L(n,ρ)
2s = Tr
(
H(n,ρ)
)2s
=
n∑
i0,i1,i2,...,i2s−1=1
H
(n,ρ)
i0i1
H
(n,ρ)
i1i2
. . .H
(n,ρ)
i2s−1i0
, (2.5)
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 67
O. Khorunzhiy
in the limit of the infinite n, ρ and s. To study the case described by Theorem
2.1, we consider the random matrices with truncated random variables aij . This
makes the proofs of Theorems 2.1 and 2.2 almost identical up to the final stages.
Given a sequence Un > 0, n ≥ 1, we introduce the truncated random variables
âij = â
(n)
ij =
{
aij , if |aij | ≤ Un,
0, otherwise.
Theorems 2.1 and 2.2 will follow from our main technical result related with
moments (2.5) of the random matrices Ĥ
(n,ρ)
ij = â
(n)
ij b
(n,ρ)
ij .
Theorem 2.3. Under conditions of Theorem 2.1, there holds the inequality
lim sup
n→∞
ETr
(
Ĥ(n,ρn)
)2sn ≤ M(χ) < ∞, (2.6)
where sn = bχn2/3c with χ > 0, ρn = n2/3(1+ε) and Un = nδ with a proper choice
of δ > 0. The upper bound does not depend on the values of V2l, 2 ≤ l ≤ 6 and
V12+2φ.
Theorem 2.3 is proved in Section 4.
Following the original E. Wigner’s idea, it is natural to consider the right-
hand side of (2.5) as the weighted sum over paths of 2s steps. In particular, we
can write that
M̂(n,ρ)
2s = ETr
(
Ĥ(n,ρ)
)2s
=
∑
I2s∈I2s(n)
Π̂a(I2s)Πb(I2s), (2.7)
where the sequence I2s = (i0, i1, . . . , i2s−1, i0), ik ∈ {1, 2, . . . , n} is regarded as a
closed path of 2s steps (it−1, it) with the discrete time t ∈ [0, 2s]. We will also
say that I2s is a trajectory of 2s steps. The set of all possible trajectories of 2s
steps over {1, . . . , n} is denoted by I2s(n).
The weights Π̂a(I2s) and Πb(I2s) are naturally determined as the mathemat-
ical expectations of the products of the corresponding random variables,
Π̂a(I2s) = E
(
âi0i1 . . . âi2s−1i0
)
, Πb(I2s) = E
(
bi0i1 . . . bi2s−1i0
)
. (2.8)
Here and below, we omit the superscripts in b
(n,ρ)
ij when no confusion can arise.
In a series of papers by Ya. Sinai and A. Soshnikov [22, 23, 25], a powerful
and deep approach was developed to study the moments M(n)
2s of Wigner random
matrices in the limit n, s → ∞. It is based on the classification of the family
of trajectories I2s(n) according to the number of their self-intersections. Corre-
sponding classes of equivalence depend also on the types of these self-intersections
(simple self-intersections, simple open self-intersections, simple self-intersections
68 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
with multiple edges). In [14], this approach was completed by the notions of the
instants of broken tree structure and proper and imported cells that are impor-
tant in the studies of the trajectories I2s that have many steps with common
starting point. The complete version of the Sinai–Soshnikov description was fur-
ther developed in paper [8] where the results of [25] were generalized to the case
of Wigner random matrices whose elements have a finite number of moments.
In the present paper, we propose an improvement of the approach described
in [8] which enables us to study the high moments of dilute random matrices
in the asymptotic regime that describes the local properties of their spectra at
the border of the limiting eigenvalue distribution. The method proposed here,
when applied to the ensemble of Wigner random matrices, essentially simplifies
the technique used in [8].
3. Even Walks and Classes of Equivalence
Given a trajectory I2s, we write that I2s(t) = it, t ∈ [0, . . . , 2s] and consider
a subset U(I2s; t) = {I2s(t′), 0 ≤ t′ ≤ t} ⊆ {1, 2, . . . , n}. We denote by |U(I2s; t)|
its cardinality. Each I2s generates a walk W2s = W(I2s)
2s = {W(t), 0 ≤ t ≤ 2s}
that we determine as a sequence of 2s+1 symbols (or, equivalently, letters) from
an ordered alphabet, say, A = {α1, α2, . . . }. The walk W(I2s)
2s is constructed with
the help of the following recurrence rules [13]:
1) W2s(0) = α1;
2) if I2s(t + 1) /∈ U(I2s; t), then W2s(t + 1) = α|U(I2s;t)|+1;
if there exists t′ ≤ t such that I2s(t+1) = I2s(t′), thenW2s(t+1) = W2s(t′).
For example, I16 = (5, 2, 7, 9, 7, 1, 2, 7, 9, 7, 2, 7, 2, 1, 7, 2, 5) produces the walk
W16 = (α1, α2, α3, α4, α3, α5, α2, α3, α4, α3, α2, α3, α2, α5, α3, α2, α1).
One can say that the pair (W2s(t−1),W2s(t)) represents the t-th step of the walk
W2s and that α1 represents the root of the walk W2s.
Given two trajectories I ′2s and I ′′2s, we say that they are equivalent, I ′2s ∼
I ′′2s, if W(I′2s)
2s = W(I′′2s)
2s , and denote by CW = CW2s the corresponding class of
equivalence. It is clear that
|CW | = n(n− 1) · · · (n− |U(I2s; 2s)|+ 1). (3.1)
Given W2s, one can draw a graphical representation g(W2s) = (Vg,Eg) that
can be considered as a kind of multigraph with the set Vg of vertices labelled
by α1, . . . , α|U(I2s;2s)|, and the set Eg of 2s oriented edges (or, equivalently, arcs)
labelled by t ∈ [1, . . . , 2s]; the edge et = (αi, αj) is in Eg in the case when
W2s(t−1) = αi and W2s(t) = αj . To describe the properties of g(W2s) in general
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 69
O. Khorunzhiy
situations, we will use Greek letters α, β, γ, . . . instead of the symbols from the
ordered alphabet A. In this case the root of the walk will be denoted by %. Given
vertex β such that W2s(t) = β, we will say that β is seen in W2s at the instant
of time t. By an abuse of terminology, we refer to g(W2s) as to the graph of the
walk W2s.
Let us define the current multiplicity of the couple of vertices {β, γ}, β, γ ∈ Vg
up to the instant t by the variable
m
({β,γ})
W (t) = #{t′ ∈ [1, t] : (W(t′ − 1),W(t′)) = (β, γ) or
(W(t′ − 1),W(t′)) = (γ, β)}
and say that m
({β,γ})
W (2s) represents the total multiplicity of the couple {β, γ}.
The probability law of âij being symmetric, the weight of I2s (2.8) is non-zero,
Π̂a(I2s) 6= 0 only in the case when I2s is such that in the corresponding graph
of the walk W(I2s)
2s each couple {α, β} has an even multiplicity m
({α,β})
W (2s) =
0(mod 2). We refer to the walks of these trajectories as to the even closed walks
[22] and denote by W2s the set of all possible even closed walks of 2s steps. In
what follows, we consider the even closed walks only and consider them simply
as the walks.
3.1. Marked Steps and Self-Intersections
Regarding an instant of time t, we say that the couple (t− 1, t) represents the
step of time number t. It is natural to say that the pair (W2s(t− 1),W2s(t)) = st
represents the step of the walk number t. Given W2s ∈ W2s, we say that the
instant of time t is marked [22] if the couple {α, β} = {W2s(t−1),W2s(t)} has an
odd current multiplicity at the instant t, m
({α,β})
W (t) = 1(mod 2). We also say that
the step of the walk st and the corresponding edge et of g(W2s) are marked. All
other steps and edges are called the non-marked ones. Regarding the collection
of marked edges Ēs of g(W2s), we can consider the multigraph ḡs = (V̄s, Ēs).
Clearly, V̄s = Vs and |Ēs| = s. It is useful to keep the time labels of the edges
Ēs as they are in Es.
Any even closed walk W2s ∈ W2s generates a sequence θ2s of s marked and
s non-marked instants that can be regarded as a binary sequence of 0’s and 1’s.
The sequence θ2s is known to encode a Dyck path of 2s steps. We denote by
θ2s = θ(W2s) the Dyck path of W2s and say that θ(W2s) represents the Dyck
structure of W2s.
Let us denote by Θ2s the set of all Dyck paths of 2s steps. It is known that
Θ2s is in one-by-one correspondence with the set of all half-plane rooted trees
Ts ∈ Ts constructed with the help of s edges. Sometimes we will also use the
denotation T2s = Ts. The correspondence between Θ2s and Ts can be established
70 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
with the help of the chronological run R over the edges of Ts. The cardinality of
Ts being given by the Catalan number that we denote by
ts =
(2s)!
s! (s + 1)!
, (3.2)
we refer to the elements of Ts as to the Catalan trees. We consider the edges of
the tree Ts as the oriented ones in the direction away from its root.
Given a Catalan tree Ts ∈ Ts, one can label its vertices with the help of letters
of A according to RT . The root vertex gets the label α1 and each new vertex that
has no label is labelled by the next in turn letter. We denote the walk obtained
by
◦
W2s[Ts], and the corresponding Dyck path θ2s = θ(
◦
W2s) will be denoted also
as θ2s = θ(Ts).
Given W2s, we denote by θ∗(W2s) the height of the corresponding Dyck path,
θ∗(W2s) = max
0≤t≤2s
θ2s(t), θ2s = θ(W2s).
This is also the height of the tree Ts, θ∗(Ts) = max0≤t≤2s θ2s(t), θ2s = θ(Ts).
3
5
812
α
α
α
α
α1
4
3
5
T16
e
e
3
8
2
1
2
3
4 5
6
7
β
8 β
2
β5
1
β4
β3
10
6
1
2
Fig. 1. Graph ḡ(W16), tree T16 = T8 = T (W16) and a part of the chronological
run over T8
Any Dyck path θ2s generates a sequence (ξ1, ξ2, . . . , ξs), ξi ∈ [1, 2s − 1] such
that each step of the walk sξi , 1 ≤ i ≤ s, of
◦
W2s[θ2s] is marked. We denote this
sequence by Ξs = Ξ(θ2s). Given Ξs and τ ∈ [1, s], one can uniquely reconstruct
θ2s and find the corresponding instant of time ξτ ∈ [1, 2s− 1]. We will say that τ
represents the τ -marked instants or instants of marked time that varies from 1 to
s; sometimes we will simply say that τ is the marked instant when no confusion
with the term ”marked instant of time” can arise.
In Figure 1, we present the graph ḡ(W16) = (V8, Ē8) of the walk W16 as well
as its Catalan tree T16 = T8 = T (W16) and a part of the chronological run over
T8 on the time interval [0, 8] = [0, ξ6]. We have θ∗(W16) = 4. The set of five
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 71
O. Khorunzhiy
vertices {β1, . . . , β5} represents the descending part of the tree T6, that is a part
of T8.
Given a walk W2s and a letter β such that β ∈ Vg(W2s), we say that the
instant of time t′ such that W2s(t′) = β represents an arrival a at β and that
t′ is the arrival instant of time. If t′ is marked, we will say that a is the marked
arrival at β. In W2s, there can be several marked arrival instants of time at β
that we denote by 1 ≤ t
(β)
1 < · · · < t
(β)
N . For any non-root vertex β, we have
N = Nβ ≥ 1. The first arrival instant of time β is always the marked one. We
can say that β is created at this instant of time. To unify the description, we
assume that the root vertex % is created at the zero instant of time t
(ρ)
1 = 0
and add the corresponding zero marked instant to the list of the marked arrival
instants at %.
If Nβ ≥ 2, then we say that the N -plet (t(β)
1 , . . . , t
(β)
N ) of marked arrival
instants of time represents the self-intersection of W2s, β is the vertex of self-
intersection, and this self-intersection is of the degree N [22]. We say that the
self-intersection degree of β is equal to N and denote it by κ(β) = Nβ. Clearly,
if β 6= %, then the self-intersection degree κ(β) indicates the number of marked
edges of g(W2s) that have β as their tails.
If κ(β) = 2, then we say that β is the vertex of simple self-intersection [22]. If
the walk is such that κ(β) = 2 and at the second marked arrival instant t
(β)
2 there
is at least one couple {β, γ} with an odd current multiplicity, m
({β,γ})
W (t(β)
2 − 1) =
1(mod 2), then β is referred to as the vertex of open simple self-intersection and
t
(β)
2 is the instant of open simple self-intersection [23]. We will also say that the
vertex β is open at the instant of time t′ = t
(β)
2 − 1 or that β is a t′-open vertex.
3.2. Vertices and edges of g(W2s) and diagram G(W2s)
Given a walk W2s and an integer k0 ≥ 1, we consider all vertices β ∈ Vg such
that their self-intersection degree κ(β) ≤ k0 and say that they are the µ-vertices.
We will denote the collection of µ-vertices by V(k0,µ)
g = V(µ)
g . The vertices γ with
κ(γ) ≥ k0 + 1 are referred to as the ν-vertices, γ ∈ V(ν)
g .
Regarding a ν-vertex β, we say that all oriented marked edges of Ēg of the
form (γ, β) are the ν-edges. We color the ν-edges in black and denote by νk the
number of vertices β such that κ(β) = k, k ≥ k0 + 1. We denote by Ē(ν)
g the
collection of the ν-edges and determine the subset Ē(k0)
g = Ēg \ Ē(ν)
g .
The number of µ-vertices β such that κ(β) = 1 will be denoted by µ1. In this
case, all marked edges of the form (γ, β) will be referred to as the µ1-edges and
colored in grey.
Let us choose a µ-vertex β such that κ(β) ≥ 2 and consider the marked
72 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
arrivals āi at β. Let e2 = (γ, β) be the edge of Ēg that corresponds to the second
arrival ā2 at β. In our considerations, we do not assume that γ is different from
β. We denote by ξτ2 the marked instant of time of e2 and consider the sub-walk
W[0,t′] of W2s with t′ = ξτ2 − 1. We classify the µ-vertices and corresponding
edges according to the properties of the second and the third arrivals at them.
First, let us consider the edge e2 = (γ, β) of Ēg that corresponds to the second
arrival ā2 at β. We denote by ξτ2 the marked instant of time of e2 and consider
the the sub-walk W[0,t′] of W2s with t′ = ξτ2 − 1. We distinguish the following
properties with respect to ā2:
(a) the edge e2 = (γ, β) is such that there exists a marked edge e′ = (β, γ) such
that e′ ∈ Ē(k0)
g and e′ ∈ g(W[0,t′]); in this case we say that e2 is the q-edge;
(b) if the edge e2 does not verify condition (a) and there exists a marked edge
e′′ = (γ, β) such that e′′ ∈ g(W[0,t′]), then we say that e2 is the p-edge;
(c) if the edge e2 does not verify (a) and does not verify (b) and the vertex β is
t′-open, then we say that e2 is the o-edge.
We denote by M′
2 the collection of µ-vertices β such that the second arrival
ā2 at β verifies one of the three conditions listed above and denote its cardinality
by µ′2 = |M′
2|. We say that the first arrival a1 at β represents an f -edge of the
graph ḡs and color it in red. The o, p and q-edges are colored in blue color. All
edges that correspond to the arrivals ai, i ≥ 3 at µ′2-vertex β, if they exist, will
be referred to as the u-edges and colored in green color. We denote by u2 the
total number of these edges of ḡs.
If β is such that κ(β) = 2 and neither (a) nor (b) nor (c) is verified, we say
that e2 is the µ-edge at color it in blue color. The collection of vertices of this
kind will be denoted by M′′
2 with the cardinality |M′′
2| = µ′′2.
Let us take a µ-vertex β such that κ(β) ≥ 3 that does not belong to M′
2. If
the third arrival ā3 verifies at least one of the two conditions, either (a) or (b),
with τ2 and e2 replaced by τ3 and e3 = e(ξτ3) = (γ, β), respectively, we say that
β ∈ M′
3. In this case, assuming the same ordering of conditions (a) and (b) as
before, we attribute to the marked edge e3 of the third arrival at β one of two
labels, either q or p. All the edges that correspond to the arrivals āi, i ≥ 4 at β, if
they exist, will be referred to as the u-edges. We denote by u′′3 the total number
of these edges of ḡs. The cardinality of M′
3 will be denoted by µ′3 = |M′
3|.
If β ∈ M′
3, then we say that e3 is the µ-edge and color it in blue. We color
the edges of the first and the second arrivals at β in red and refer to them as to
the f -edges.
Finally, let us consider the vertices β such that κ(β) ≥ 3 and β /∈ M′
3 ∪M′
2.
The family of these vertices will be denoted by M′′
3 with |M′′
3| = µ′′3. In this case,
we say that all three arrival edges at β are the µ-edges and color them in blue.
The edges of all subsequent arrivals at β are referred to as the green u-edges.
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 73
O. Khorunzhiy
The total number of green edges will be denoted by u′3.
Summing up these considerations, we can see that a given walk W2s generates
a kind of graphical diagram G that describes the vertices of self-intersections of
W2s and the structure of the corresponding edges. More rigorously, we define
a diagram G as a collection of vertices vi ∈ V(G) |V(G)| = |Vg| and half-edges
ej ∈ E(G) attached to vi. The half-edges have heads but have no tails. Instead
of the tail, we attach to the corresponding end of e a circle that we refer to as
the window o. The windows can contain the numerical data; in this case we will
say that these numbers represent a realization of the windows. In general, we
will say that the numerical data in the windows that come from W2s represent a
realization of the diagram G given by W; we denote this realization by 〈G〉W . In
what follows, we will refer to the triplet (v, e, o) either as to the edge-window or
simply as to the edge of G. The edge-windows of G are colored according to the
colors of the corresponding edges of g(W2s). Then we can determine the same
classification of the elements of V(G) as it is done for those of Vg.
Regarding the example walk W16 from Fig. 1, we can see that the graph
g(W16) contains five vertices α1, . . . , α5. The vertices of self-intersections are
represented by two of them, α2, α4 ∈M′
2. Therefore the realization of the diagram
G(W16) contains two vertices, V(G) = {v1, v2}. There are four edge-windows at
v1 with 〈(o1, o2, o3, o4)〉W = (1, 6, 10, 12) and two at v2, 〈(o1, o2)〉W = (3, 8). We
order the vertices vi according to the values in the blue windows of the second
arrivals. If k0 ≥ 4, then v1 has one red, one blue and two green edges attached,
the vertex v2 has one red edge and one blue edge.
The vertices of V(G) are not ordered, but those of 〈G〉 are. In the general
situation, we order the vertices of 〈G〉 according either to the instants of the
second arrivals, if the vertices are from M′
2 ∪M′′
2, or to the instants of the third
arrivals, if they are from M′
3 ∪M′′
3, or to the instants of the last arrivals, if the
corresponding vertices of g(W2s) are the ν-vertices.
3.3. Classes of walks and trajectories
Given θ2s, an even closed walk W2s is determined by its values at the marked
and non-marked instants of time. The general estimation principle used in papers
[22, 23] and [25] is based on the observation that the knowledge of the instants
of self-intersections determines all values of W2s at the marked instants of time;
this knowledge being added by a rule Υ of the non-marked passages determines
completely the walk W2s (see Section 5 for the rigorous definition of Υ).
The vertices of self-intersections and the properties of the corresponding edges
are described by diagrams G. Any diagram is characterized by the following set
of variables:
S = (r, p, q, µ′′2, u2; µ′3, µ
′′
3, u3, ν̄),
74 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
where ν̄ = ν̄(k0+1) = (νk0+1, . . . , νs), and νk denotes the number of vertices v such
that κ(v) = k. Let us denote the set of the diagrams by G(S). The elements of
G(S) differ by the positions of green edges attached to the µ-vertices.
We say that W2s belongs to the class W2s(G), G = G(S) if the graph gs =
g(W2s) has a collection of µ-vertices M′
2,M′′
2,M′
3,M′′
3 with corresponding cardi-
nalities, where r+p+q = µ′2, and r is the number of self-intersections determined
by o-edges, p is the number of self-intersections with p-edges, and q is the number
of self-intersections with q-edges. Then obviously,
|V(G)| = µ1 + µ2 + µ3 +
s∑
k=k0+1
νk,
where µ2 = µ′2 + µ′′2 and µ3 = µ′3 + µ′′3, and
|E(G)| = µ1 + 2µ2 + 3µ3 + u2 + u3 +
∑
k=k0+1
kνk = s. (3.3)
Let us recall that |V(G)| = |Vg| and |E(G)| = |Ēg| and denote ‖ν̄‖ =
∑s
k=k0+1 kνk.
Lemma 3.1. If I2s is such that W(I2s) ∈W2s(G) with G ∈ G(S), then
Π̂a(I2s)Πb(I2s) ≤
(
V2
n
)µ1+µ′2+r+2µ′′2+2µ′3+3µ′′3
(
U2
n
ρ
)p+q+µ′3+u2+u3+‖ν̄‖
. (3.4)
P r o o f of Lemma 3.1. Regarding the factor Π̂a(I2s) of (2.8) determined
by a given diagram G, we replace by Un all random variables âij that correspond
to the ν-edges, u-edges, p-edges and q-edges together with all their non-marked
counterparts. When doing this, only one case needs a special attention, namely
the case when the vertices γ and β are joined by two q-edges of the form (β, γ) and
(γ, β). However, it is easy to consider all possible configurations of the marked
edges with heads γ and β and to show that (3.4) is valid for this class of diagrams.
Given a walk W2s, we determine the enter cluster of β of its graph g(W2s) as
the set of all marked edges of the form (αi, β), Λ(β) = Λ(β;W2s) =
{
(αj , β) ∈ Ēg
}
.
Similarly, we determine the exit cluster of a vertex β as the set of all edges (β, γi),
∆(β) = ∆(β;W2s) =
{
(β, γi) ∈ Ēg
}
. Sometimes, when no confusion can arise,
we will use the same denotations, Λ and ∆, for the collections of vertices that are
the heads (or tails, respectively) of the corresponding edges.
Regarding W2s, we find the exit cluster of maximal cardinality and say that
it determines the maximal exit degree of the walk,
D(W2s) = max
β∈Vg
|∆(β;W2s)|.
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 75
O. Khorunzhiy
Given θ = θ2s, let us consider a sub-class W[θ]
2s(D;G) ⊂ W2s(G) of walks W2s
of Dyck structure θ such that the maximal exit degree of W2s is equal to D,
D(W2s) = D. Given G, let us denote by G♦ the collection of its blue, green and
black edge-windows and by G◦ the collection of its red edge-windows.
Let 〈G♦〉s be a realization of the corresponding edge-windows filled with the
values from (1, . . . , s). Given such a realization, we perform a run of the walk
W2s with the self-intersections prescribed. If such a walk exists, we denote by
〈G◦〉 = 〈G◦〉W the realization of values in the red edge-windows of G recorded
during the run of W2s.
Lemma 3.2. Given a rule Υ, denote by W[θ]
2s(D;G,Υ) the family of walks
W2s such that W2s ∈W[θ]
2s(D;G,Υ), G ∈ G(S). Then
|W[θ]
2s(D;G, Υ)| =
∑
〈G◦〉
∑
〈G♦〉s
1,
where
∑
〈G♦〉s
1 ≤ sr+p+q+u2
r! p! q!
1
µ′′2!
(
s2
2
)µ′′2 sµ′3+u3
µ′3!
1
µ′′3!
(
s3
6
)µ′′3 s∏
k=k0+1
1
νk!
(
sk
k!
)νk
(3.5a)
and ∑
〈G◦〉
1 ≤ (2θ∗2s)
r Dp kq
0 (s(D + k0))µ′3 , (3.5b)
and therefore
|W[θ]
2s(D;G, Υ)| ≤ (2sθ∗2s)
r
r!
(sD)p
p!
(sk0)q
q!
1
µ′′2!
(
s2
2
)µ′′2
su2+u3
× (s2(D + k0))µ′3
µ′3!
1
µ′′3!
(
s3
6
)µ′′3 s∏
k=k0+1
1
νk!
(
sk
k!
)νk
,
where θ∗2s is the height of the Dyck path θ2s.
We will prove Lemma 3.2 in Section 5.
Corollary of Lemma 3.2. Let us consider the family of walks
W[θ]
2s(D;S) =
⊔
G∈G(S)
⊔
Υ∈Y
W[θ]
2s(D;G, Υ).
Then
|W[θ]
2s(D;S)| ≤ (6sθ∗2s)
r
r!
(3sD)p
p!
(3sk0)q
q!
1
µ′′2!
(
s2
2
)µ′′2 (8k4
0sµ
′
2)
u2
u2!
76 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
× (s2(D + k0))µ′3
µ′3!
1
µ′′3!
(
s3
6
)µ′′3 (16k5
0sµ3)u3
u3!
s∏
k=k0+1
1
νk!
(
(2ks)k
k!
)νk
. (3.6)
Let us introduce a class of walks W(u)
2s (D;S) such that the height of their
Dyck paths is equal to u. Combining the results of Lemma 3.1 and Corollary of
Lemma 3.2, it is not difficult to prove the following statement.
Lemma 3.3. Let us denote by C(W(u)
2s (D;S)) the family of trajectories I2s
such that their walks belong to W(u)
2s (D;S). Then
∑
I2s∈C(W(u)
2s (D;S))
Π̂a(I2s) Πb(I2s) ≤ V s
2 |Θ(u)
2s | exp
{
−(s− σ)2
2n
}
× 1
µ′′2!
(
s2
2n
)µ′′2
H(u,D,k0)
(S;2) (1)H(D,k0)
(S;3) (1)H(k0+1)
(S;ν̄) (1) , (3.7)
where Θ(u)
2s = {θ2s ∈ Θs, θ∗2s = u}, σ = µ2 + µ3 + u2 + u3 + |ν̄|1 with
|ν̄|1 =
s∑
k=k0+1
(k − 1)νk,
and
H(u,D,k0)
(S;2) (h) =
1
r!
(
6hsu
n
)r 1
p!
(
3hsDÛ2
n
ρ
)p
× 1
q!
(
3hsk0Û
2
n
ρ
)q
1
u2!
(
8hk4
0sµ
′
2Û
2
n
ρ
)u2
, (3.8a)
H(D,k0)
(S;3) (h) =
1
µ′3!
(
9h(D + k0)s2Û2
n
nρ
)µ′3 1
µ′′3!
(
3hs3
2n2
)µ′′3 1
u3!
(
16hk5
0sµ3Û
2
n
ρ
)u3
,
(3.8b)
and
H(k0+1)
(S;ν̄) (h) =
s∏
k=k0+1
1
νk!
(
n(2hks)k Û2k
n
k! ρk
)νk
(3.8c)
with h ≥ 1 and Û2
n = U2
n/V2.
The upper bound (3.7) represents a natural generalization of the estimates
obtained for the first time in [22, 23, 25] and [21]. Further modifications of these
estimates were presented in [8]. The form of (3.6) together with expressions (3.7),
(3.8), (3.9) and (3.10) is based on a new description related with the form and
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 77
O. Khorunzhiy
the structure of diagrams G. It gives a considerable simplification and powerful
improvement of the general approach used in [8]. The rigorous proof of Lemma
3.3 answers a number of questions that arise when reading papers [21, 25]. Notice,
we will prove Lemma 3.3 in Section 5.
The results of Lemma 3.3 are sufficient to get the upper bound of the leading
term of (2.5) and to show that the contribution of the walks that have multiple
edges and that have bounded maximal exit degree D(W2s) ≤ nε with certain
ε vanishes in the limit n → ∞ (see Section 4). To study the family of walks
such that D(W2s) > nε, we need to consider the properties of the corresponding
graphs in more details.
3.4. Vertex of maximal exit degree
Let us consider a walk W2s and find the first letter αi = β̆ such that |∆(β̆)| =
maxβ∈V(W2s) |∆(β)|. We will refer to β̆ as to the vertex of maximal exit degree
and denote D(β̆) = |∆(β̆)|. In this section we study the properties of even closed
walks related with the vertex of maximal exit degree β̆. To classify the arrival
edges at β̆, we need to determine the reduction procedures related with β̆. These
procedures are similar to those considered in [14].
3.4.1. Reduction procedures and reduced sub-walks. Any walk W2s
can be considered as an ordered set of its steps st, 1 ≤ t ≤ 2s, where st =
(W2s(t− 1),W2s(t)). Inversely, each pair of letters α, β such that W2s(t− 1) = α
and W2s(t) = β with some t represents an element of the ordered set of the steps
of W2s that we denote by S = S(W2s). To each element si ∈ S we attribute
the label i which is simply the number of the step in W2s. These labels order
in natural way the elements of S. We do not change these labels during the
reduction procedures considered below.
Given W2s, let t′ be the minimal instant of time such that
i) the step st′ is the marked step of W2s;
ii) the consecutive to st′ step st′+1 is non-marked;
iii) W2s(t′ − 1) = W2s(t′ + 1).
If this t′ exists, we can apply to S a reduction procedure R̂ that removes from
S two consecutive elements st′ and st′+1; we denote R̂(S) = S′. The ordering
labels of the elements of S′ are inherited from those of S.
It is clear that the ordered set S′ can be considered as a new walk W ′
2s−2 that
is again an even closed walk. We denote W ′
2s−2 = R̂(W2s) and say that R̂ is the
strong reduction procedure of the walk W2s. Then we can apply R̂ to W ′
2s−2 and
get an even closed walk W ′′
2s−4 = R̂(W2s−2). Repeating this action maximally
78 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
possible number of times m, we get the walk
Ŵ2ŝ = (R̂)m(W2s), ŝ = s−m,
which we refer to as the strongly reduced walk. We denote Ŝ = (R̂)m(S).
We introduce a weak reduction procedure R̆ of S that removes from W2s the
pair of consecutive steps, st′ , st′+1, such that the conditions (i)-(iii) are verified
and
iv) W2s(t′) 6= β̆.
We denote by
W̆2s̆ = (R̆)l(W2s), s̆ = s− l, (3.9)
the result of the action of maximally possible number of consecutive weak re-
ductions R̆ and denote S̆ = (R̆)l(S). In what follows, we sometimes omit the
subscripts 2ŝ and 2s̆.
Let us consider the example walk W16 (3.1). It is seen that D(W2s) = 5 and
the vertex of maximal exit degree is α3. The strongly reduced walk (R̂)3(W16) =
Ŵ10 is as follows:
Ŵ10 = (α1, α2, α3, α5, α2, α3, α2, α5, α3, α2, α1),
and the corresponding reduced set of the steps Ŝ = Ŝ(Ŵ10) is
Ŝ = {s1, s2, s5, s6, s7, s12, s13, s14, s15, s16}.
For this example walk, we have W̆10 = Ŵ10.
Regarding the difference S̆\Ŝ = Š, one can see that it represents a collection
of sub-walks, W̌ = ∪jW̌(j). Each sub-walk W̌(j) can be reduced by a sequence
of the strong reduction procedures R̂ to an empty walk. We say that W̌(j) is of
the tree-type structure, or that W̌(j) is a tree-type sub-walk. It is easy to see that
any W̌(j) starts by a marked step and ends by a non-marked steps and there is
no steps of Ŵ between these two steps of W̌(j). We say that W̌(j) is non-split.
It is not hard to see that the remaining part S̃ = S\S̆ is given by a collection
of the subsets S̃ = ∪kS̃
(k), each of S(k) represents a non-split tree-type sub-walk
W̃(k),
W̃ = ∪kW̃(k). (3.10)
In this definition we assume that each sub-walk W̃(k) is maximal by its length.
3.4.2. Tree-type sub-walks attached to β̆. Given W2s, let us consider the
instants of time 0 ≤ t1 < t2 < . . . tL ≤ 2s such that for all i = 1, . . . , L the walk
arrives at β̆ by the steps of W̆2s̆,
W2s(ti) = β̆ and sti ∈ W̆2s̆. (3.11)
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 79
O. Khorunzhiy
We say that ti are the t̆-arrival instants of time of W2s. Let us consider a sub-
walk that corresponds to the subset S[ti+1,ti+1] = {st, ti + 1 ≤ t ≤ ti+1} ⊆ S; we
denote this sub-walk by W[ti,ti+1]. In general situation, we also denote by W[t′,t′′]
a sub-walk which is not necessarily even and/or closed.
Let us consider the interval of time [ti + 1, ti+1 − 1] between two consecutive
t̆-arrivals at β̆. It can happen that W2s arrives at β̆ at some instants of time
t′ ∈ [ti + 1, ti+1 − 1], W2s(t′) = β̆. We denote by t̃(i) the maximal value of t′.
Lemma 3.4. The sub-walk W[ti,t̃(i)]
is of the tree structure and coincides with
one of the maximal tree-type sub-walks W̃(k′) of (3.10).
This statement means that the walk W2s is such that after an arrival at β̆ by
a step of W̆ it creates a tree-type sub-walk W(k′), which is not interrupted by the
steps of W̆, and that all steps performed after W(k′) belong again to W̆,
{st, ti + 1 ≤ t ≤ t̃(i)} ⊆ S̃, {st, t̃(i) + 1 ≤ t ≤ ti+1} ⊆ S̆.
P r o o f of Lemma 3.4. It is clear that the step st̃(i)
does not belong to S̆ and
it is non-marked. Then this step makes a part of a non-split tree-type sub-walk
W̃(k′) = W[t′′,t̃(i)] such that W̃(k′)(t′′) = β̆. Then the previous step st′′ ∈ S̆ is
such that W2s(t′′) = β̆. Then t′′ = ti. The lemma is proved.
As a consequence of Lemma 3.4, the sub-walk W[ti,t̃(i)]
= W̃(k′) is of the tree-
type structure that ends at β̆ by a non-marked step and therefore starts at β̆
by the marked step. Let us consider the family of all marked exit edges from β̆
performed by the marked steps on the interval of time [ti, t̃(i)] and denote these
edges of Ē = Ē(W2s) by ∆̃i. Regarding the non-empty subsets ∆̃j , we say that ∆̃j
represents the exit sub-clusters of tree type attached to β̆ and denote by dj = |∆̃j |
its cardinality, dj ≥ 1, j = 1, . . . , L′. These tree-type sub-clusters are numerated
in natural chronological order. Clearly, any non-empty tree-type sub-cluster is
attributed to a uniquely determined t̆-arrival instant at β̆.
Regarding the even walk W̆2s̆, we can determine the corresponding Dyck path
θ̆2s̆ = θ(W̆2s̆) and the tree T̆s̆ = T (θ̆). It is clear that T̆s̆ can be considered as a
subtree of Ts = T (θ(W2s)). One can determine the difference T̃ = Ts�T̆s̆ such
that it is represented by a collection of sub-trees T̃ (j). Not to overload the paper,
we do not present rigorous definitions here.
Regarding the Catalan tree T (θ2s), we say that the chronological run RT is
represented by 2s directed arcs $i, 1 ≤ i ≤ 2s drawn over Ts (see Fig. 1). This
chronological run uniquely determines L arcs $̆l, 1 ≤ l ≤ L that correspond to
the arrival instants of time t̆l at β̆. The corresponding vertices υl of the tree Ts
are also determined. It is clear that υl are not necessarily different for different l.
80 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
The sub-trees T̃ (l) are attached at υl and the chronological run over T̃ (l) starts
immediately after the arc $̆l is drawn. We will say that these arcs $̆l represent
the nest cells from where the sub-trees T̃ (l), 1 ≤ l ≤ L grow. It is clear that
the sub-tree Tl has dl ≥ 0 edges attached to its root ρl represented by the vertex
υl. Returning to W2s, we will say that the arrival instants of time t̆l represent
the arrival cells at β̆. In the next sub-section, we will give a classification of the
arrival cells at β̆ which is a natural improvement of the approach proposed in [14].
3.4.3. Classification of arrival cells at β̆ and BTS-instants. Let us consider
a t̆-arrival cell ti (3.11). If the step sti of W2s is marked, then we say that ti is
a proper cell at β̆. If the step sti is non-marked and sti ∈ W̌ = W̆ \ Ŵ, then we
say that ti is a mirror cell at β̆. If the step sti ∈ Ŵ is non-marked, then we say
that ti is an imported cell at β̆.
Let us consider I proper cells ťi such that the corresponding step sťi belongs to
Š. We denote by xi the corresponding to ťi marked instants, xi = ξťi , 1 ≤ i ≤ I,
and write that x̄I = (x1, . . . , xI). Each proper cell xi is associated with a number
of corresponding mirror cells. We denote this number by mi ≥ 0 and write that
M =
∑I
i=1 mi and m̄I = (m1, . . . , mI).
Regarding the strongly reduced walk Ŵ2ŝ, we denote by t̂k the proper cells
such that the steps st̂k
∈ Ŝ. The corresponding to t̂k marked instants will be
denoted by zk, 1 ≤ k ≤ K. Then z̄K = (z1, . . . , zK) and, clearly, κ(β̆) = I + K.
Regarding any walk W2s, we observe that if the set Ŝ is non-empty, then
there exists at least one pair of the elements of Ŝ, (s′, s′′) such that s′ is a marked
step of Ŵ2ŝ, s′′ is a non-marked one and s′′ follows immediately after s′ in Ŝ.
We refer to each pair of this kind as to the pair of broken tree structure of W2s
or in abbreviated form, the BTS-pair of W2s. If τ ′ is the marked instant that
corresponds to s′, we will simply say that τ ′ is the BTS-instant of W2s [14]. We
will refer to the vertex γ = W2s(ξτ ′) as to the BTS-vertex of the walk.
Regarding the strongly reduced walk Ŵ, let us consider a non-marked arrival
step at β̆ that we denote by s̄ = st̄. Then one can uniquely determine the marked
instant τ ′ such that all steps st ∈ Ŝ with ξτ ′ +1 ≤ t ≤ t̄ are the non-marked ones.
Let us denote by t′′ the instant of time of the first non-marked step st̄′′ ∈ Ŝ of
this series of non-marked steps. Then (st′ , st′′) with t′ = ξτ ′ is the BTS-pair of
W2s which corresponds to t̄. We will say that t̄ is attributed to the corresponding
BTS-instant τ ′. Several arrival instants t̄i can be attributed to the same BTS-
instant τ ′. We will also say that the BTS-instant τ ′ generates the imported cells
that are attributed to it.
Let us consider a BTS-instant τ such that W2s(ξτ ) = β̆. As it is said above,
we denote these marked instants by zk, 1 ≤ k ≤ K. Assuming that a marked
BTS-instant zk generates f ′k ≥ 0 imported cells, we denote by ϕ
(k)
1 , . . . , ϕ
(k)
f ′k
the
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 81
O. Khorunzhiy
positive numbers such that
W2s(ξzk
+
l∑
j=1
ϕ
(k)
j ) = β̆ for all 1 ≤ l ≤ f ′k. (3.12)
If for some k̃ we have f ′
k̃
= 0, then we will say that zk̃ does not generate any
imported cell at β̆. We denote ϕ̄(k) = (ϕ(k)
1 , . . . , ϕ
(k)
f ′k
).
Let us consider a BTS-instant τ that generates imported cells at β̆ and such
that W2s(ξτ ) 6= β̆. We denote these BTS-instants by yj , 1 ≤ j ≤ J . Assuming
that a marked BTS-instant yj generates f ′′j +1 imported cells, f ′′j ≥ 0, we denote
by `j , ψ
(j)
1 , . . . , ψ
(j)
f ′′j
the positive numbers such that W2s(ξyj + `j) = β̆ and
W2s
(
ξyj + `j +
k∑
l=1
ψ
(j)
l
)
= β̆ for all 1 ≤ k ≤ f ′′j . (3.13)
In this case we will say that the first arrival at β̆ given by the instant of time ξyj +`j
represents the principal imported cell at β̆. All subsequent arrivals at β̆ given
by (3.13) represent the secondary imported cells at β̆. We will say that yj is the
remote BTS-instant with respect to β̆ and will use denotations ȳJ = (y1, . . . , yJ)
and ¯̀
J = (`1, . . . , `J). We also denote ψ̄(j) = (ψ(j)
1 , . . . , ψ
(j)
f ′′j
).
All arrivals determined by (3.12) will also be referred to as the secondary
imported cells at β̆. We will say that the corresponding BTS-instant zk is the
local one with respect to β̆.
For a given walk W2s, the proper, mirror and imported cells at its vertex of
maximal exit degree are characterized by a set of parameters, (x̄, m̄)I , (z̄, Φ, f̄ ′)K ,
where ΦK = (ϕ̄(1), . . . ϕ̄(K)), f̄ ′K = (f ′1, . . . , f
′
K) and (ȳ, ¯̀,Ψ, f̄ ′′)J , where ΨJ =
(ψ̄(1), . . . , ψ̄(J)), f̄ ′′J = (f ′′1 , . . . , f ′′J ). We also denote F ′ =
∑K
k=1 f ′k and F ′′ =∑J
j=1 f ′′j .
Summing up, we observe that the vertex β̆ with κ(β̆) = I + K has the total
number of cells given by R = I + M + K + 2J + F , where F = F ′ + F ′′. In what
follows, we will use the following denotation for the set of parameters described
above:
{
(x̄, m̄)I , (z̄, Φ, f̄ ′)K , (ȳ, ¯̀,Ψ, f̄ ′′)J
}
= 〈PR〉. It would be an instructive
exercise to consider the example walkW16 from Fig. 1 and to determine its 〈PR〉.
82 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
4. Proof of Main Results
Remembering that ε > 3
6 + φ
= ε0, let us choose
k0 = b 3
ε− ε0
c+ 2 , δ =
ε0 + ε
6
, and Un = nδ. (4.1)
We assume k0 to be an even number.
Our aim is to show that the averaged trace L̂(n,ρ)
2sn
(2.7) admits an upper bound
in the limit n, sn → ∞, sn = bχn2/3c, χ > 0 that we denote by (n, s)χ → ∞.
We also prove that the trajectories I2s such that the graphs of their walks have
multiple edges vanish in this limit. Then Theorem 2.3 will follow.
In the spirit of [21, 25], we consider the following partition of the sum (2.7):
M̂(n,ρ)
2s = ETr
(
Ĥ(n,ρn)
)2sn
= Z
(1)
2s + Z
(2)
2s + Z
(3)
2s , (4.2)
where
• Z
(1)
2s is the sum over the trajectories I2s ∈ C(W2s) such that the graph
g(W2s) has neither p-edges nor µ′3-vertices;
• Z
(2)
2s is the sum over the trajectories I2s ∈ C(W2s) such that the graph
g(W2s) has at least one p-edge or one µ′3-vertex and the maximal exit degree
g(W2s) is bounded, D(W2s) ≤ nε, and
• Z
(3)
2s is the sum over the trajectories I2s such that the graph g(W2s) has
the maximal exit degree D(W2s) > nε.
As we will see further, the choice of ε = (ε− ε0)/12 is sufficient for our
purposes. The sub-sum Z
(1)
2s will also be represented as a sum of two parts in
dependence of the presence of q-edges, or u-edges, or ν-vertices.
4.1. Estimate of Z
(1)
2s
Following the definitions of Section 3, we can write that
Z
(1)
2s =
s∑
u=1
∑
〈S(1)〉
∑
G∈G(〈S(1)〉)
∑
〈G♦〉s
∑
W2s∈W(u)
2s (〈G♦〉s)
∑
I2s∈C(W2s)
Π̂a(I2s)Πb(I2s),
(4.3)
where S(1) = (r, 0, q, µ′′2, u2; 0, µ′′3, u3; ν̄) represents a particular case of the set
of variables S (see sub-section 3.3) and the sum over 〈S(1)〉 runs over all non-
negative integer values of its parameters such that condition (3.3) is verified. Let
us represent Z
(1)
2s as a sum of two terms,
Z
(1)
2s = Z
(1,1)
2s + Z
(1,2)
2s ,
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 83
O. Khorunzhiy
where Z
(1,1)
2s is the sum over the realizations of S(1,1) = (r, 0, 0, µ′′2, 0; 0, µ′′3, 0; 0).
Then the corresponding walks have neither q-edges, nor u-edges, nor ν-vertices.
To estimate the right-hand side of (4.3) from above, we use Lemma 3.3 of
Section 3 with p = q = u2 = µ′3 = u3 = |ν̄|1 = 0. Then σ = r + µ′′2 + µ′′3, and we
can write that
exp
{
−(s− σ)2
2n
}
≤ exp
{
− s2
2n
} (
e
s
n
)µ′′2+r+µ′′3
. (4.4)
Applying the upper bound (3.7) to the right-hand side of (4.3), replacing the sum
over 〈S(1)〉 by the sum over all possible values of the variables r, µ′′2, and µ′′3 and
using (4.4), we can write the inequality
Z
(1;1)
2s ≤ nV s
2 exp
{
− s2
2n
} s∑
u=1
|Θ(u)
2s |
s∑
r=0
1
r!
(
6su
n
es/n
)r
×
s∑
µ′′2=0
1
µ′′2!
(
s2
2n
es/n
)µ′′2 s∑
µ′′3=0
1
µ′′3!
(
3s3
2n2
es/n
)µ′′3
.
Taking into account that es/n ≤ 2 for large values of n, we get the bound
Z
(1,1)
2s ≤ nV s
2 ts Bs(12χ3/2) exp
{
s2
2n
(
es/n − 1
)
+ 3χ3
}
,
where we denoted
Bs(x) =
1
ts
s∑
u=1
|Θ(u)
2s | exp
{
xu√
s
}
= Es
(
exp{xθ∗/
√
s}) . (4.5)
In (4.5), Es(·) denotes the mathematical expectation with respect to the uniform
measure on the set of Catalan trees Ts. It is proved in [12] that Bs(x) in the
limit of infinite s is given by the exponential moment of the maximum of the
normalized Brownian excursion. Using the convergence B(x) = lims→∞Bs(x)
[12] and elementary relation
ntsn
4sn
=
n (2sn)!
4sn sn! (sn + 1)!
=
1√
πχ3
(1 + o(1)), sn = χn2/3,
that follows from the Stirling formula, we conclude that
lim sup
n→∞
Z(1,1)
2sn
≤ 1√
πχ3
B(12χ3/2) e4χ3
.
Let us consider the sub-sum Z
(1,2)
2s . Applying the upper bound (3.7) to the
right-hand side of (4.3), using the analog of (4.4) and replacing the sum over
84 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
〈S(1,2)〉 by the sum over all possible values of its variables, we can write the
inequality
Z
(1,2)
2s ≤ nV s
2
s∑
u=1
|Θ(u)
2s |
s∑
r=0
1
r!
(
12su
n
)r s∑
µ′′2=0
exp
{
− s2
2n
}
1
µ′′2!
(
s2
2n
es/n
)µ′′2
×
s∑
µ′′3=0
1
µ′′3!
(
3s3
n2
)µ′′3 ∑
u2+u3+|ν̄|1≥1
1
u2!
(
16k4
0srÛ
2
n
ρ
)u2
× 1
u3!
(
32k5
0sµ
′′
3Û
2
n
ρ
)u3 s∏
k=k0+1
1
νk!
n
(
C1sÛ
2
n
ρ
)k
νk
, (4.6)
where we denoted C1 = supk≥2
2k
(k!)1/k and used the relation es/n ≤ 2.
Regarding the last product of (4.6), we can write that
n
(
C1sÛ
2
n
ρ
)k
= A(k0)
n
(
C1sÛ
2
n
ρ
)k−k0
, A(k0)
n = n
(
C1sÛ
2
n
ρ
)k0
.
It follows from (4.1) that A
(k0)
n ≤
(
C1χ
V2
)k0
n−2ε with ε = (ε− ε0)/12 and there-
fore
n
(
C1sÛ
2
n
ρ
)k
≤
(
C1χ
V2
)k0
n−2ε
(
C1χ
V2
n−4ε
)k−k0
(4.7)
where we have taken into account that n2/3U2
n/ρ ≤ n−4ε. Then the following
relation is true:
s∑
|ν̄|1=1
s∏
k′=1
1
νk0+k′ !
A(k0)
n
(
C1sÛ
2
n
ρ
)k′
νk0+k′
≤ exp
{(
C1χ
V2
)k0
n−2ε
∞∑
k′=1
(
C1χ
V2
n−4ε
)k′
}
− 1 ≤ exp
{(
C1χ
V2
)k0
n−2ε
}
− 1,
where 1 takes the values 0 or 1. Denoting C2 = 64k5
0χ/V2, we can also write
that
s∑
u3=2
1
u3!
(
32k5
0sµ
′′
3Û
2
n
ρ
)u3
≤
{
exp{C2 µ′′3 n−4ε}, if 2 = 0,
C2 n−4ε eµ′′3 , if 2 = 1
for sufficiently large values of n. A similar computation shows that
s∑
u2=3
1
u2!
(
16k4
0srÛ
2
n
ρ
)u2
≤
{
exp{C2 r n−4ε}, if 3 = 0,
C2 n−4ε er, if 3 = 1.
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 85
O. Khorunzhiy
Using the elementary inequality
∑
1+2+3≥1
{·} ≤
∑
1≥1,2≥0,3≥0
{·}+
∑
1≥0,2≥1,3≥0
{·}+
∑
1≥0,2≥0,3≥1
{·}
and accepting that n is such that exp{s/n+C2n
−4ε} ≤ 2, we can see that relation
(4.6) implies the following inequality:
Z
(1,2)
2s ≤ nV s
2
s∑
u=1
|Θ(u)
2s | exp
{
12eχ3/2 u√
s
}
× exp
{
s2
2n
(
es/n − 1
)
+ 3eχ3 + 2C3n
−2ε
} (
2C2n
−4ε + 2C3n
−2ε
)
,
where C3 = 2C1χ/V2. Now it is clear that Z
(1,2)
2s = o(1), (n, s)χ → ∞, and
therefore
lim sup
(n,s)χ→∞
Z
(1)
2s ≤ 1√
πχ3
B(12χ3/2) e4χ3
. (4.8)
4.2. Estimate of Z
(2)
2s
Rewriting relation (4.3) with S(1) replaced by S(2) = (r, p, q, µ′′2, u2;µ′3, µ
′′
3, u3; ν̄)
and using the result of Lemma 3.3 together with (4.4), we can write that
Z
(2)
2s ≤ nV s
2
nε∑
D=1
s∑
u=1
|Θ(u)
2s |
s∑
µ′′2=0
exp
{
− s2
2n
}
1
µ′′2!
(
s2
2n
es/n
)µ′′2 s∑
r=0
1
r!
(
12su
n
)r
×
∑
p,µ′3:
p+µ′3≥1
1
p!
(
6sDÛ2
n
ρ
)p
1
µ′3!
(
9(D + k0)s2Û2
n
nρ
)µ′3 s∑
u2=0
1
u2!
(
32k4
0srÛ
2
n
ρ
)u2
×
s∑
q=0
1
q!
(
6sk0Û
2
n
ρ
)q s∑
µ′′3=0
1
µ3!
(
3s3
n2
)µ′′3 s∑
u3=0
1
u3!
(
64k5
0sµ3Û
2
n
ρ
)u3
×
∑
|ν̄|≥0
s∏
k′=1
1
νk!
A(k0)
n
(
C1sÛ
2
n
ρ
)k′
νk
. (4.9)
Taking into account that
sDU2
n
V2ρ
≤ χ
V2
n−3ε and
Ds2U2
n
V2nρ
≤ χ2
V2
n−3ε6χ2n−1/3 ≤ χ2
V2
n−3ε, (4.10)
86 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
and repeating the computations of the previous subsection, we deduce from (4.9)
the following estimate:
Z
(2)
2s ≤ 48χ
V2
n−2ε nV s
2
s∑
u=1
|Θ(u)
2s | exp
{
24χ3/2 u√
s
+ 8χ3 + 2A(k0)
n
}
.
Then
Z
(2)
2s = o(1), as (n, s)χ →∞. (4.11)
4.3. Estimate of Z(3)
In this subsection we estimate the sub-sum of (2.5) corresponding to the walks
that have a vertex β̆ of large exit degree D. In previous works (see, e.g., [7, 8, 25]),
it is observed that in the case of L arrival cells at β̆, the underlying Dyck path and
the corresponding tree Ts have to have at least one vertex υ whose exit degree is
not less than D/L. Then the collection of these trees has an exponentially small
cardinality with respect to the total number of trees, with the exponential factor
determined by a value proportional to D/L.
In the case of dilute random matrices, this observation is not sufficient for
getting the needed estimates of the cardinality of the set of such walks. Roughly
speaking, our aim is to get the upper bound related with the exponential factor
determined by the values proportional to D. Let us briefly outline the main idea
of the proof of corresponding bounds.
We consider the families of walks such that their vertex of maximal exit
degree β̆ is characterized by a collection of certain parameters P. This set of
parameters described in Section 3 involves the marked BTS-instants τi and the
corresponding descending lengths `, ϕ, ψ. Given P, the positions of the nest cells
in the tree Ts with given exit sub-clusters are uniquely determined. This implies
a fairly strong exponential estimate for the number of corresponding trees (see
D-lemma of Section 6). On the other hand, it appears that the collection of
the parameters P can be naturally inserted into the diagrams G that we use to
estimate the number of walks in the corresponding classes.
4.3.1. Diagrams and classes of walks. Given u, D and S, we consider a family
W(u)
2s (D;S, 〈PR〉) given by the walks such that their vertex of maximal exit degree
β̆ is characterized by the following set of numerical data (see subsection 3.4):
〈PR〉 =
{
(x̄, m̄)I , (z̄, Φ, f̄ ′)K , (ȳ, ¯̀,Ψ, f̄ ′′)J
}
, R = I + M + K + 2J + F. (4.12)
It is convenient to write that 〈PR〉 = (〈QR〉, 〈HR〉) with 〈QR〉 = {x̄I , z̄K , ȳJ} and
〈HR〉 =
{
m̄I , (Φ, f̄ ′)K , (¯̀,Ψ, f̄ ′′)J
}
. In what follows, when no confusion can arise,
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 87
O. Khorunzhiy
we omit the angles in the denotations of PR (4.12), as well as in QR and HR,
that denote numerical realizations of the sets of the parameters PR, QN and HR,
respectively. In denotations QR and HR, we keep the subscript R to indicate
that these values are taken from one common set (4.12).
Let us describe the construction of the family W(u)
2s (D;S,PR). Given S, we
build a diagram G(S) as it is done in Lemma 3.2 (see Section 3). Regarding
the set of vertices V(G), we add to it a vertex v̆ of the self-intersection degree
κ(v̆) = N = I + K, i.e., a vertex with I + K edge-windows attached. We denote
the diagram obtained by G∗(S).
The next step is to distribute the J labels over the edge-windows of G that
will be filled by the values ȳJ . We refer to these labels as to the y-labels. The
windows with y-labels will represent the marked instants of the remote BTS-pairs.
Therefore one cannot use the first arrival edges attached to the vertices of G. The
edge-windows attached to the vertices of M′′
2 cannot also be used. Thus, we have
µ′2 + u2 + µ3 + u3 + |ν̄|1 windows of G in our disposition and then the number
of the ways to distribute J labels is bounded from above by
(µ′2+u2+µ3+u3+|ν̄|1
J
)
.
The following upper bound will be useful for us:
(
µ′2 + u2 + µ3 + u3 + |ν̄|1
J
)
≤ (µ′2 + u2 + µ3 + u3 + |ν̄|1)J
J !
≤ 1
hJ
exp{h(µ′2 + u2 + µ3 + u3 + |ν̄|1)}, h ≥ h0 > 1. (4.13)
We denote by G〈Q〉(S) = GQ(S) a diagram obtained from G(S) by insertion
of the marked instants 〈QR〉 into the chosen J edge-windows of G(S).
The collection of blue, green and black edge-windows of GQ(S) that remain
free will be denoted by
¦
GQ (S). We denote by
〈 ¦GQ (S)〉s = 〈G/〉s
a realization of the values in these blue, green and black windows of G〈Q〉(S).
This gives the realization of the diagram G∗(S) that we denote as follows:
〈G?〉s = 〈v̆〉 ] 〈G/〉s,
where 〈v̆〉 denotes the realization of the edge-windows attached to v̆ given by the
values (x̄I , z̄K). The red f -edges of GQ(S) are denoted by G◦ as before.
The maximal exit degree of a walk W2s ∈ W(u)
2s (D;S, β̆,PR) can be repre-
sented as follows: D = D̆ + D̃, where D̆ is the number of marked edges of the
form (β̆, γ) that belong to the reduced walk W̆ (3.9). It is known that the number
of marked exits from β̆ is equal to the number of non-marked arrival steps at β̆,
88 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
D̆ = M + F + J and that F ≤ K (see [14] and also Lemma 5.1 of [8]). It is not
hard to see that M ≤ I − 1. Then we can write that
D̃ = D−M − F − J ≥ D− I −K − J. (4.14)
We can see that in a particular W2s, D̃ edges are attributed to R proper and
imported cells at β̆ and R ≤ 2(I + J + K). Let us denote by d̄R = (d1, . . . , dR)
a particular distribution of D̃ balls over R ordered boxes,
∑d
i=1 di = D̃ = DR.
Then the total number of different sets d̄R is bounded by
(
DR + R− 1
R− 1
)
≤
(
DR + L− 1
L− 1
)
, L = 2(I + J + K). (4.15)
Having determined all of the values described above, we denote by
W(u)
2s (D, d̄R; 〈G?〉s, 〈HR〉, Υ) = W(u)
2s (d̄R; 〈G?〉s,HR,Υ) (4.16)
the family of walks W2s with θ∗(W2s) = u and such that W2s follow the given
rule Υ of non-marked continuations.
4.3.2. Exponential estimate and the upper bound. It is clear that the
number of ways to attribute F ′ imported cells to K marked instants and F ′′
imported cells to J marked instants are bounded by
(
F ′ + K − 1
K − 1
)
≤ 2F ′+K and
F ′′ + J − 1
J − 1
≤ 2F ′′+J ,
respectively,and the number of ways to distribute M ≤ I mirror cells over I
marked arrivals at β̆ is bounded by 22I . The sub-sum Z
(3)
2s can be bounded by
the following expression (cf. (4.3)):
Z
(3)
2s ≤
s∑
D=bnεc
s∑
u=1
∑
I,K: I+K≥1
I∑
M=0
s∑
J=0
∑
F ′,F ′′≥0
∑
x̄I ,ȳJ ,z̄K
2F ′+F ′′+K+J+2I
×
∑
〈S〉
∑
G(S)
∑
〈QR〉∈G(S)
∑
〈G/〉s
∑
d̄R
∑
Υ
∑
〈HR〉
Π(β̆) |Υβ̆|
×
∑
W2s∈W?
2s
∑
I2s∈C(W2s)
Π̂a(I2s)Πb(I2s), (4.17)
where Π(β̆) is the weight of the edges attached to β̆, and |Υβ̆| stands for the
estimate of the local rule of non-marked passages. In (4.17), we also introduce
a denotation W?
2s = W(u)
2s (d̄R; 〈G?〉s,HR, Υ). Assuming that G? is such that
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 89
O. Khorunzhiy
µ′2 = r + p + q, we use the following upper bound (see Lemma 6.3 of Section
6):
s∑
u=1
∑
HR
|W(u)
2s (D, d̄R; 〈G?〉s,HR, Υ)| ≤ sr/2 Br 2r Dp kq
0 (s(D + k0))µ′3
× 4R (DR + 1) e−ηDR ts, (4.18)
where Br = sups≥1 Es((θ∗/
√
s)r) (see (4.5)) and ∆R = D̃ =
∑R
r=1 dR. Let us
note that (4.14) implies that
4R (DR + 1) e−ηDR ≤ s 4L eη(I+J+K) e−ηD. (4.19)
It follows from (4.15) that
∑
d̄R
1 ≤ (
D+L−1
L−1
)
, and elementary analysis shows that
sup
L≥1
4L
hL
0
(D + L− 1)!
D! (L− 1)!
≤ exp
{
4eD
h0
}
. (4.20)
The product Π(β̆) |Υβ̆| can be bounded with the help of the following inequalities
that are true for h ≥ 1 and sufficiently large values of n (see Section 5):
eh(I+K) Π(β̆) |Υβ̆| ≤ eh(I+K) s
I+K(C1U
2)I+K
ρI+K−1
≤ 1
hI+K
{
(hseh)k0 , if I + K ≤ k0,
ehk0 n−ε(hehn−ε/2)I+K−k0 , if I + K ≥ k0 + 1.
(4.21)
Finally, it is not difficult to see that
∑
ȳJ
∑
〈G/〉
1 =
∑
〈G♦〉
1 , (4.22)
where the last sum is estimated by the right-hand side of inequality (3.5a).
Taking into account the upper bound (3.5a) and relations (4.4), (4.13), (4.18)–
(4.22) and accepting that nε ≥ ehk0 , we deduce from (4.17) the inequality
Z
(3)
2s ≤ (hseh)k0+3
s∑
D=bnεc
∑
I,K: I+K≥1
s∑
J=0
(8h0)2(I+J+K)
hI+J+K
exp
{
−ηD +
4eD
h0
}
× exp
{
s2
2n
(
es/n − 1
)} ∑
r,p,q≥0
Br ·H(
√
s,D,k0)
(S,2) (eh)
×
∑
µ′3,µ′′3 ,u3≥0
H(D,k0)
(S,3) (eh)
∑
|ν̄|1≥0
H(k0+1)
(S,ν̄) (eh), (4.23)
90 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
where denotations (3.7) are used.
Assuming that
lim
s→∞
s∑
r=0
(2χ3/2eh)r
r!
Br = B(2χ3/2eh), (4.24)
the choice of h = (8h0 + 1)2 + 1 and h0 = 8/η in the right-hand side of (4.23) is
sufficient for the relation
Z
(3)
2s = O
(
sk0+4 exp{−ηnε/2}
)
= o(1) (4.25)
to hold in the limit (n, s)χ →∞.
Relation (4.24) can be proved provided Br = sups≥1 B
(s)
r = lims→∞B
(s)
r . This
statement would follow from the monotonicity of B
(s)
r with respect to s. We did
not find any related reference in the literature but assume that this monotonicity
is true. We do not study this question in the present paper. In fact, the existence
of an upper bound of the left-hand side of (4.24) would be sufficient for us.
4.4. Proof of Theorem 2.1 and Theorem 2.2
Using the standard arguments of the probability theory, we can write that
P
({
ω : λ̂(n,ρn)
max > 2v
(
1 +
x
n2/3
)})
≤ ETr(Ĥ(n,ρn))2sn
(
2v(1 + xn−2/3)
)2sn
, (4.26)
where λ̂
(n,ρn)
max is the maximal in absolute value eigenvalue of Ĥ(n,ρn).
Relations (4.2), (4.8), (4.11) and (4.25) show that
lim sup
n→∞
ETr(Ĥ(n,ρn))2sn = lim sup
n→∞
(
Z
(1,1)
2sn
+ Z
(1,2)
2sn
+ Z
(2)
2sn
+ Z
(3)
2sn
)
≤ 1√
πχ3
e4χ3
B(6χ3/2) = M(χ). (4.27)
It follows from (4.26) and (4.27) that
lim sup
n→∞
P
{
λ̂(n)
max > 2v
(
1 +
x
n2/3
)}
≤ inf
χ>0
M(χ)e−xχ = P(x). (4.28)
Let us consider the subset Λn ⊆ Ω, Λn = ∩1≤i<j≤n {ω : |aij(ω)| ≤ Un}. Denoting
λ̂
(n,ρn)
max = λmax(Ĥ(n,ρn)), we can write that
P
({
ω : λ(n,ρn)
max > y
})
= P
({
ω : λ̂(n,ρn)
max > y
})
+ P
({
ω : λ(n,ρn)
max > y
}
∩ Λ̄n
)
,
(4.29)
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 91
O. Khorunzhiy
where Λ̄n = Ω \ Λn. Clearly,
P
{
Λ̄n
} ≤
∑
1≤i<j≤n
P {|aij | > Un} ≤ n2 E|aij |12+2φ
U12+2φ
n
. (4.30)
The choice of δ given by (4.1) is sufficient for the right-hand side of (4.30) to
vanish in the limit n → ∞. Then we can deduce from (4.28) and (4.29) the
following estimate, (cf. (2.3)),
lim sup
n→∞
P
{
λ(n,ρn)
max > 2v
(
1 +
x
n2/3
)}
≤ P(x). (4.31)
Theorem 2.1 is proved.
Returning to (4.27), we observe that Z
(1,2)
2sn
+ Z
(2)
2sn
+ Z
(3)
2sn
= o(1) as n → ∞.
This means that the upper bound M(χ) is the same as if one considers the mo-
ments of Wigner random matrices H(n,n) (2.1) provided V12+2φ < ∞. The same
is true for the random matrices An of Gaussian Orthogonal Ensemble [16]. The
limit of the corresponding sub-sum Z
(1,1)
2sn
(An) exists [25], limn→∞ Z
(1,1)
2sn
(An) =
MGOE(χ), and therefore we conclude about the existence of the limit
lim
n→∞ ETr(Ĥ(n,ρn))2sn = MGOE(χ). (4.32)
Let us prove Theorem 2.3. Regarding the moments of random matrices
H̃(n,ρn), we can use the same representation as before and write that
M̃(n,ρn)
2sn
= ETr
(
H̃(n,ρn)
)2sn
= Z̃
(1,1)
2sn
+ Z̃
(1,2)
2sn
+ Z̃
(2)
2sn
+ Z̃
(3)
2sn
, (4.33)
where Z̃2sn are determined in the same way as it is done in (4.2). It is easy to
see that the estimate of Z̃
(1,1)
2sn
is the same as that of Z
(1,1)
2sn
.
To get the estimate of Z̃(1,2)
2sn
, we repeat the computations used to estimate
Z
(1,2)
2sn
with the only difference that (4.7) is replaced by the expression
n
(C1U
2s)k
(v2ρ)k
=
(
C1U
2
v2
)k
n1−2εk0/3−2ε(k−k0)/3, k ≥ k0 + 1.
Then the choice of the technical value k0 = b 3
2εc + 1 (cf. (4.1)) is sufficient to
conclude that Z̃
(1,2)
2sn
= o(1) as n →∞. The same concerns the estimates of Z̃
(2)
2sn
and Z̃
(3)
2sn
.
These arguments show that
lim sup
n→∞
M̃(n,ρn)
2sn
≤ 1√
πχ3
B(6χ3/2) e4χ3
(4.34)
92 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
for any positive ε ∈ (0, 1/2]. It is easy to see that (4.34) implies (2.4). Theorem
2.2 is proved.
In conclusion, let us say that the upper bounds (4.27) and (4.34) obtained
are not optimal. Regarding the estimate of Z
(1,1)
2s (see Section 4), we observe
that the leading contribution to this sum comes from the walks with the simple
self-intersections (open and not open ones) and the triple self-intersections that
are not open. The last group of intersections gives the factor exp{χ3} instead of
exp{4χ3}.
The simple open self-intersections with no BTS-pairs should be included into
the term µ′′2 and their contribution is normalized by the term exp{−s2/(2n)}.
Thus the factor B of (4.27) and (4.3) should take into account two kinds of BTS-
pairs and is to be replaced by B(2χ3/2). Therefore one could expect the explicit
form of the relation like (4.32) to be as follows:
lim
n→∞ ETr(H̃(n,ρn))2sn = MGOE(χ) =
1√
πχ3
B(2χ3/2) se2χ3
. (4.35)
It is not hard to observe that in the case of hermitian random matrices, only
one type of BTS-pair is present in the simple open self-intersections. Therefore
we expect the limit
lim
n→∞ ETr(H̃(n,ρn))2sn = MGUE(χ) =
1√
πχ3
B(χ3/2) e2χ3
(4.36)
to hold.
Let us note that the limiting expressions MGOE(χ) and MGUE(χ) are well
known in the spectral theory of random matrices. They can be computed with
the help of orthogonal polynomial technique (see [25] and references therein). By
using the Laplace transform method, it can be shown that these values are related
with the Tracy-Widom distributions F (t) = P(λ(n)
max ≤ 1 + t/n2/3) of GOE and
GUE, respectively [1, 25, 26]. Then one may conclude also about the convergence
of the left-hand side of (2.3) to the Tracy-Widom law. The discussion of these
questions goes out of the range of the present paper.
5. Auxiliary Statements
5.1. Proof of Lemma 3.2
Let us introduce the following denotations. A self-intersection with the marked
instants τ1 < . . . < τk ≤ s will be denoted by i(k)(τ1, . . . , τk). We denote the
vertex of self-intersection i(k) by v = v(i(k)). A collection of self-intersections
{i(kj)}, j ≥ 1 with given marked instants τi ∈ [1, . . . , s] will be denoted by 〈I〉s.
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 93
O. Khorunzhiy
Given θ = θ2s, 〈I〉s and a rule of non-marked passages Υ, the corresponding walk
W2s, if it exists, is unique and completely determined by the chronological run
along θ.
We will also use the following denotation of the self-intersection with a number
of free instants: ĩ
(k)
l = ĩ(k)(Ol, τ
(l)
k ), where Ol = (o1, . . . , ol), τ
(l)
k = (τl+1, . . . τk)
and
ĩ(k)(o1, . . . , ol, τl+1, . . . , τk) = tx1<···<xl<τl+1
i(k)(x1, . . . , xl, τl+1, . . . , τk).
We say that oj are the windows of self-intersection. In what follows, we will omit
the tilde sign and the subscript l in ĩ
(k)
l (Ol, τ
(l)
k ) when no confusion can arise.
Let us denote by W[θ]
2s(〈I〉s, ĩ(k)
l ; Υ) a family of walks that have a Dyck struc-
ture θ, the set of given self-intersections 〈I〉s, follow the rule Υ, and have an
additional k-fold self-intersection ĩ
(k)
l . We consider all possible walks of this
kind with all possible values of the free instants of self-intersection ĩ(k). Given
(θ, 〈I〉s, Υ), we omit these variables and indicate their presence by an asterisk in
the denotation
∗
W2s. The next sub-section represents a rigorous formulation of
the observations used in [22] and [25]. The tools developed will give us means to
proceed in more complicated cases.
5.1.1. Walks with β ∈M′
2. Let us consider a family of walks
∗
W2s
(
i(2)(o1, τ2)
)
such that the instant of the second marked arrival ā2 = a2 at v = v(i(2)) is given
by τ2. The set
∗
W2s
(
i(2)(o1, τ2)
)
can be constructed as follows. Regarding a sub-
walkW[0,ξτ2−1] that is completely determined by (θ, 〈I〉s, Υ), we setW2s(ξτ2) = β,
β ∈ g(W[0,ξτ2−1]). Then, respecting the rules of θ, 〈I〉s and Υ, we continue W to
the time interval [ξτ2 + 1, 2s]. If such a walk exists, we add it to the list of the
elements of
∗
W2s
(
i(2)(o1, τ2)
)
. In this case, the value τ ′ that is the first arrival
instant at β fills the window o1. We say that the value τ1 = τ ′ of the simple
self-intersection is a realization of the window o1 given by the walk W2s. We
denote this realization by τ1 = 〈o1〉W2s .
In this construction, the only condition on τ ′ at the instant τ2 of the second
arrival a2 is such that there is no other marked arrivals at β than the first one, τ ′.
Let us say that this situation describes the unconstraint simple self-intersection,
when there is no other special condition imposed on a2.
Let us denote by i(2)
(
o1,
[
τ2
u2
])
a simple self-intersection i(2)(o1,τ2) with a cer-
tain condition u2 imposed on the second arrival instant a2 at v(i(2)).
We consider first the construction of walks W2s ∈
∗
W2s
(
i(2)
(
o1,
[
τ2
u2
]))
with
open simple self-intersection i(2) that corresponds to condition (c) of subsection
3.2 with denotation u2 = (o). Starting with a uniquely determined sub-walk
94 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
W[0,ξτ2−1] that follows the rules of θ, 〈I〉s and Υ, we can see that the vertex
v = γ of the open simple self-intersection i(2) can be chosen from the subset of
vertices V(o)
t′ ∈ V(g), g(W[0,ξτ2−1]) that are open at the instant of time t′ = ξτ2−1,
i.e., have at least one open non-oriented edge attached to γ. We will say that
V(o)
t′ is the set of t′-open vertices. Choosing one of the admissible vertices, we
continue the run of the walk according to the rules θ, 〈I〉s and Υ, if it is possible.
A simple but important observation is that for any instant of time ξτ2 , the
following upper bound holds: maxt |V(o)(W[0,t])| ≤ 2θ∗, where θ∗ is the height of
the Dyck path θ2s [23]. Therefore we can write that
#
{
τ1 : τ1 = 〈o1〉W2s , W2s ∈
∗
W2s
(
i(2)
(
o1,
[
τ2
u2
]))}
≤ 2θ∗, u2 = (o). (5.1)
Clearly,
∗
W2s
(
i(2)
(
o1,
[
τ2
u2
]))
⊆ ∗
W2s
(
i(2) (o1, τ2)
)
,
and we can say that the set
∗
W2s
(
i(2) (o1, τ2)
)
is filtered by the condition u2.
With a certain abuse of language, we can say that the possible values τ ′ at the
window o1 are restricted or filtered by the condition u2 imposed on the second
arrival a2. In a brief form, we will say that the first arrival a1 is filtered by the
property u2 of the second arrival a2.
The next case of the simple self-intersection with filtered first arrival is given
by condition (b) of subsection 3.2. The corresponding self-intersection produces
a p-edge of the form (γ, v), v = v(i(2)). In this case, it is necessary that v belong
to the exit cluster ∆(α) of g(W[0,ξτ2−1]) with α = W(ξτ2 − 1) that is uniquely
determined. We denote this condition by u2 = (∆).
The condition u2 = (∆) means that we can continue the sub-walk W[0,ξτ2−1]
to the instant of time ξτ2 with a letter (a vertex) that belongs to ∆(α). To choose
this letter is also to choose the marked instant of the first arrival at this vertex.
Therefore, if one considers the family of the walks
∗
W2s
(
D; i(2)
(
o1,
[
τ2
u2
]))
such
that |D(W2s)| = D, then
#
{
τ1 : τ1 = 〈o1〉W2s , W2s ∈
∗
W2s
(
D; i(2)
(
o1,
[
τ2
u2
]))}
≤ D, u2 = (∆). (5.2)
Thus,
∗
W2s (i(2) (o1, τ2)) is filtered by the condition u2 = (∆). We will say that
i(2) of this type produces a multiple edge in Ē(k0)
g .
The second type of filtering related with the multiple edges in Ē(k0)
g is given by
condition (a) of subsection 3.2. In this case, a necessary condition on 〈o1〉W2s = τ1
is that the marked edge (v(i(2)), α) = (W2s(ξτ1),W2s(ξτ2 − 1)) exists and belongs
to Ē(k0)
g . The latter condition implies that v(i(2)) ∈ Λ(α) and means that the
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 95
O. Khorunzhiy
vertex v(i(2)) is the µ-vertex. We denote this necessary condition by u2 = (Λ(k0)).
The number of vertices in Λ(α) bounded by k0, we can write that
#
{
τ1 : τ1 = 〈o1〉W2s , W2s ∈
∗
W2s
(
i(2)
(
o1,
[
τ2
u2
]))}
≤ k0, u2 = (Λ(k0)).
(5.3)
In this case, the values τ ′ at the window o1 are filtered by the Λ(k0)-condition.
It is obvious that the upper bounds (5.1), (5.2) and (5.3) are true in the case
when β ∈M′
2, i.e., when κ(β) = m ≥ 2. To prove this, it is sufficient to consider
the walks with the self-intersection ĩ
(m)
1 = ĩ(m)(o1, τ2, τ3, . . . , τm).
Let us note that in the reasonings above, we did not make any difference
between two procedures, the first one related with the continuation of the sub-
walk W[0,ξτ2−1] to the instant of time ξτ2 with some letter that verifies one or
another condition and the second one given by the filtration of the set of walks
∗
W2s (i(i)(o1, τ2)) with respect to one or another filtering condition. It is easy
to see that these two procedures are similar and lead to the same results, i. e.,
to the same estimates of the cardinalities of families of walks. We will use this
observation in the sub-sections that follow.
The last remark is that in the reasoning above the cases when v(i(2)) = α are
not excluded. This means that the estimates presented are valid in the cases of
loops. This is also true with respect to the proofs of estimates that follow.
5.1.2. Walks with β ∈M′
3. Using the tools of the previous subsection, we can
describe the properties of walks that belong to
∗
W2s (i(3)(o1, o2, τ3)), where the
vertex of self-intersection i(3) is such that β = v(i(3)) ∈M′
3. If the edge e3 = e(ξτ3)
of the third arrival ā3 = a3 is the p-edge, we will write that e(ξτ3) ∈ V(p)(g). If
e3 = e(ξτ3) is the q-edge, we will write that e(ξτ3) ∈ V(q)(g).
Lemma 5.1. Let us denote by
∗
W2s (D; i(3)) a family of walks with kj ≤ k0,
j ≥ 1 and such that D(W2s) = D. Then
#
{
(τ1, τ2) = 〈(o1, o2)〉W ,W ∈ ∗
W2s
(
D; i(3)
(
o1, o2,
[
τ3
u3
]))}
≤
{
sD, if u3 = (∆),
sk0, if u3 = (Λ(k0)).
(5.4)
The statement of Lemma 5.1 seems to be a simple generalization of relations
(5.2) and (5.3) of the previous sub-section. However, the proof of Lemma 5.1
crucially depends on the classification of vertices ofM′
2 andM′
3 we introduced and
therefore represents a key point in the general method of the proof of Lemmas 3.2
and 3.3. It should be emphasized that the estimates like (5.4) were not considered
in papers [22, 23] and [25].
96 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
P r o o f of Lemma 5.1. Let us start with the case e3 ∈ V(p)(g). Then the
edge e3 = (α, β) is such that the marked edge e′ = (α, β) exists in the graph of
the sub-walk W[0,ξτ3−1], and α = W(ξτ3 − 1). By the definition, β /∈ M′
2. This
means that the edge e′ represents either the first marked arrival at β, e′ = e(a1)
or the second one, e′ = e(a2), and that the situation when e(a1) = e(a2) = (α, β)
is excluded.
We are going to construct the walks of
∗
W2s (D; i(3)(o1, o2, τ3)) with v(i(3)) ∈M′
3
such that e3 = e(ξτ3) is a p-edge. We denote the exit cluster of α = W(ξτ3 − 1)
by ∆(α) = {β1, . . . βl} with l ≤ D. Let us assume for the moment that κ(βi) = 1
for all i ∈ [1, . . . , l]. We choose one of the vertices βi and take the marked instant
τ ′ such that W[0,ξτ3−1](ξτ ′) = βi. The sub-walk W[0,ξτ3−1] will be continued at
the instant of time ξτ3 with the letter βi.
Our aim is to construct a sub-walk W̄[0,ξτ3−1] that has a self-intersection (·, ·)1
with the participation of τ ′. The subscript 1 indicates the fact that this simple
self-intersection is not present in W[0,ξτ3−1]. We proceed as follows: we take any
marked instant of time τ ′′, not involved into the self-intersections already present,
and consider the letter γ′′ = W[0,ξτ3−1](ξτ ′′). If τ ′′ < τ ′, then we replace βi by γ′′.
The walk W̄[0,ξτ3−1] performs a self-intersection (τ ′′, τ ′), and in general situ-
ation this fact changes the run of the walk after ξτ ′ with respect to the run of
the initial sub-walk W[0,ξτ3−1]. Therefore the exit cluster ∆̃(α) can differ from
∆(α). Indeed, one can easily find the examples of sub-walks W̄ and W such that
∆̃(α) ∩∆(α) = ∅.
As a consequence, it may happen that e(τ ′) /∈ ∆̄(α). Moreover, if one
considers another value τ̃ ′ such that e(τ̃ ′) /∈ ∆(α), one cannot guarantee that
e(τ̃ ′) /∈ ∆̄′(α). Thus, without additional considerations, we cannot say that given
τ3 and τ ′′, the set of all possible values of τ ′ has a cardinality bounded by the
maximal exit degree D.
An important observation here is that the changes of the exit cluster of α are
possible only in the cases when the sub-walk performs a BTS-couple (ξτ ′ , ξτ ′ +1).
If it is not the case, all cells at α created up to the instant ξτ3 − 1 remain the
same and therefore the edges of ∆(α) are determined uniquely by θ2s. The key
point is that the relation β ∈ M′
3 implies that β /∈ M′
2. This means that the
second arrival a2 does not verify condition (c) mentioned above, and we cast off
those walks that arrive by a2 at an open vertex. Therefore a2 cannot represent
the BTS-pair, and the set ∆(α) is determined uniquely by the parameters θ, 〈I〉s
and Υ. The exit cluster ∆(α) does not change when the values τ ′′ and τ ′ vary.
Then the edge e(τ ′) = (α, βi) = (α, γ′′) always belongs to ∆(α).
If τ ′ < τ ′′, then we replace the letter γ′′ by βi. Again, the fact that (α, βi) ∈
Λ(α) remains true. The number of walks that verify the conditions imposed is
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 97
O. Khorunzhiy
bounded by (s− 1)D. Thus the following upper bound holds:
#
{
(τ1, τ2)1 =〈(o1, o2)〉W ,W ∈ ∗
W2s
(
D; i(3)
(
o1, o2,
[
τ3
u3
]))}
≤(s−1)D, u3 = (∆).
Let us consider the case when κ(βi) = 2 in the graph of the sub-walk W[0,ξτ3−1].
Then we can write that
#
{
(τ1, τ2)1 = 〈(o1, o2)〉W ,W ∈ ∗
W2s
(
D; i(3)
(
o1, o2,
[
τ3
u3
]))}
≤ D, u3 = (∆).
These two estimates give (5.4) with u3 = (∆).
Let us construct the walks of
∗
W2s (i(3)(o1, o2, τ3)) with v(i(3)) ∈ M′
3
such that e3 = e(ξτ3) ∈ V(q)(g). Given θ, 〈I〉s and Υ, the enter cluster of
α = W[0,ξτ3−1](ξτ3 − 1) that is Λ(α) = {β1, . . . βl}, l ≤ k0, is uniquely determined.
Let us assume for the moment that κ(βi) = 1 for all i ∈ [1, . . . , l]. We choose one
of the vertices βi and take the marked instant τ ′ such that W[0,ξτ3−1](ξτ ′) = βi.
The sub-walk will be continued at the instant of time ξτ3 with the letter βi.
We are going to construct a sub-walk W̃[0,ξτ3−1] which has a self-intersection
(·, ·)1 with the participation of τ ′. The subscript 1 indicates the fact that this
simple self-intersection is not present inW[0,ξτ3−1]. We proceed as follows: we take
any marked instant of time τ ′′ , not involved into the self-intersections already
present, and consider the letter γ′′ = W[0,ξτ3−1](ξτ ′′). If τ ′′ < τ ′, then we replace
βi by γ′′. The fact thatW[0,ξτ3−1] performs this additional self-intersection (τ ′′, τ ′)
does not change the set Λ(α) because we reject the walks such that the intersection
(τ ′′, τ ′) is the open self-intersection. Therefore the edge (βi, α) still belongs to
Λ(α). If τ ′ < τ ′′, then we replace the letter γ′′ by βi. Again, the fact that
(βi, α) ∈ Λ(α) remains true. The choice of βi is bounded by k0, we get not more
than (s− 1)k0 different walks of this kind,
#
{
(τ1, τ2)1 = 〈(o1, o2)〉W ,W ∈ ∗
W2s
(
D; i(3)
(
o1, o2,
[
τ3
u3
]))}
≤ (s− 1)k0, u3 = (Λ(k0)).
Let us consider the case when κ(βi) = 2 in the graph of the sub-walk
W[0,ξτ3−1]. Then we can write that
#
{
(τ1, τ2)1 = 〈(o1, o2)〉W ,W ∈ ∗
W2s
(
D; i(3)
(
o1, o2,
[
τ3
u3
]))}
≤ k0, u3 = (Λ(k0)).
Gathering these two bounds, we obtain the estimate (5.4) with u3 = (Λ(k0)).
Lemma 5.1 is proved.
It is not hard to generalize these considerations to the case of walks with the
self-intersection of the form ĩ
(k)
2 (o1, o2, τ3, . . . , τk) and obtain here the same upper
bounds (5.4).
98 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
5.1.3. General filtration procedure. The general filtration procedure is as
follows. Let us consider a diagram G and recall that 〈G♦〉s denotes a realization
of blue, green and black half-edges of G. This procedure will be considered in
more details in the next sub-section. Regarding the first vertex v of G that has at
least one red f -edge attached, we consider the value τ in the blue edge-window
attached at v as the value τ2 or τ3, in dependence whether κ(v) is equal to 2 or
3. Let us consider the edges of V(G) \ v such that the integers in their windows
lie to the left of τ . They form a family of self-intersections that we regard as the
family 〈I〉s introduced above.
Now we can use the filtration procedure of the previous sub-sections and
perform a chronological run RT (t) along Ts = T (θ2s). If the next in turn step
t′ = ξτ ′ is marked and τ ′ does not belong to 〈I〉s and to the realizations of the
red edges seen by W, the walk W creates a new, next in turn, letter from the
alphabet A. If τ ′ belongs to 〈I〉s, we follow the rules of 〈I〉s and Υ; we continue
these actions till the instant ξτ−1. Then we consider all possible continuations of
the sub-walk W[0,ξt−1] to the instant of time ξt, choose one of them and continue
the run of the sub-walk till it meets the second blue window of the vertex that
has red edges attached. Then the procedure is repeated.
It is clear that the set of walks W[θ]
2s(D;S, 〈G♦〉s) with given G(S) = G has a
cardinality equal to the number of realizations of all red edge-windows G◦ of G
and that
|G◦| ≤ (2θ∗)r Dp kq
0 · (s(D + k0))µ′3 . (5.5)
Relation (3.5b) follows from (5.5).
5.1.4. Values in blue, green and black edge-windows. Given G, let us
fill its blue edge-windows Eb first. We consider the set of integers [1, . . . , s] and
choose the values for r groups of one element, p groups of one element, q groups
of one element, µ′′2 groups of two elements, µ′3 groups of one element, µ′′3 groups
of three elements and νk groups of k elements, k0 + 1 ≤ k ≤ s.
The number of ways to choose these groups of subsets of [1, . . . , s] is given by
the expression
|〈Eb〉s| = s!
r! p! q! µ′3! µ′′2! (2!)µ′′2 (3!)µ′′3 µ′′3!
s∏
k=k0+1
1
νk! (k!)νk
· 1
(s−E)!
,
where E = r + p + q + 2µ′′2 + µ′3 + 3µ′′3 + ‖ν̄‖. Clearly,
|〈Eb〉s| ≤ sE
r! p! q! µ′3! µ′′2! (2!)µ′′2 (3!)µ′′3 µ′′3!
s∏
k=k0+1
1
νk! (k!)νk
. (5.6)
The values in the green edge-windows Eg are chosen from the set (1, . . . , s)\〈Eb〉s.
Thus,
|〈Eg〉s| ≤ su2+u3 . (5.7)
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 99
O. Khorunzhiy
The number of realizations 〈G♦〉s is bounded by the product of the right-hand
sides of (5.6) and (5.7). This gives (3.5a). Lemma 3.2 is proved.
5.2. Proof of Lemma 3.3
5.2.1. The number of diagrams G(S). As it is pointed out, given S =
(r, p, q, µ′′2, u2; µ′3, µ
′′
3, u3; ν̄), the diagrams G ∈ G(S) differ by the positions of the
green edges attached to the vertices of M′
2 = V ′2(G) and M3 = V3(G). According
to the last remark of the previous sub-section, we can consider the vertices of V ′2
and V3 as the ordered ones. By the construction, |V ′2| = µ′2 and |V3| = µ3. So,
we can consider G as a union of three parts, G = G2 ] G3 ] G(k0+1)
We take the u2 green edges and distribute them over the vertices V ′2. We
draw the green edges to the right of the blue edges.
Let us denote by u
(i)
2 , 1 ≤ i ≤ k0 − 2, the number of vertices that have
i green edges attached,
∑k0−2
i=1 iu
(i)
2 = u2. Given µ′2 = r + p + q and ū2 =
(u(1)
2 , . . . , u
(k0−2)
2 ), the number of all possible diagrams G2 is equal to
(
µ′2
u
(1)
2 , . . . , u
(k0−2)
2
)
=
µ′2!
u
(1)
2 ! · · · u
(k0−2)
2 ! (µ′2 − |ῡ2|)!
.
Therefore the cardinality of the set G2 = {G2} is bounded as follows:
|G2| ≤
k0−2∏
i=1
(µ′2)
u
(i)
2
u
(i)
2 !
. (5.8)
Here the elementary bound
(
a
b
) ≤ ab/b! is used.
The u3 green edges are distributed over the vertices of V3 and placed to the
right of the blue edges at each vertex. Assuming that the number of vertices that
have j green edges is given by u
(j)
3 , 1 ≤ j ≤ k0− 3 with
∑k0−3
j=1 ju
(j)
3 = u3, we can
see that for given values of the parameters µ3 and ū3 = (u(1)
3 , . . . , u
(k0−3)
3 ) one
obtains the following upper bound for the cardinality of the set G3 = {G3}:
|G3| ≤
k0−3∏
j=1
(µ3)u
(j)
3
u
(j)
3 !
. (5.9)
5.2.2. Sum over rules Υ and diagrams G(S). In this subsection we prove
Corollary of Lemma 3.2. Let us denote by Y = Y(S) the family of all possible
rules of continuation for the class of walks with the set of parameters S, Y(S) =
{Υ(S)}. To do this, we have to consider a contribution of each vertex β such
100 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
that the non-marked depart from β can be performed in a number of different
ways. We denote by Υβ this local rule of passage. Let ξτ be a marked instant
time of the i-th arrival at a vertex β of self-intersection, and the instant ξτ + 1
be a non-marked one. If the vertex β is closed at the instant of time ξτ − 1, then
there is only one possibility to continue the run of the walk at the non-marked
instant of time ξτ + 1.
Regarding a vertex of simple open self-intersection with the second arrival at
the marked instant ξτ , we can see that the number of ξτ -open edges attached to β
is bounded by 3. Then there are not more than 3 possible continuations of the run
of the walk at the non-marked instant of time. If there are r vertices of simple
open self-intersection, then the contribution of these vertices to Y is bounded
by 3r. The same concerns the vertices from M′
2 that have p-edges and q-edges
attached. They can produce the open self-intersections too. Thus, the total
contribution of o−, p− and q-arrivals at the vertices of M′
2 such that κ(β) = 2 is
bounded by 3r+p+q.
It is proved in [14] (see also [8]) that any vertex β of the self-intersection
degree k has k non-marked departures from β and that at any instant of time
there is not more than 2k open edges attached to β.
Using this simple but important observation, we conclude that for any vertex
β ∈M′
2 that has u ≥ 1 green edges attached, the upper bound for the number of
continuations is given by
(2(2 + u))2+u ≤ (2k0)2+u ≤ (2k0)3u.
Let us consider the vertex β ∈ M′′
3. If κ(β) = 3, then the number of non-
marked departures from β with the choice of edges to close is not greater than 1,
and the number of possible continuations is bounded by 3. This departure can
be performed after the third marked arrival at β.
Regarding the vertex β of M′
3 such that κ(β) = 3 + u with u ≥ 1, we get the
following upper bound for the total number of continuations at this vertex:
(2(3 + u))3+u ≤ (2k0)4u.
Any vertex β ∈ M′′
3 such that κ(β) = 3 produces not more than 9 possible
continuations.
Finally, any ν-vertex β such that κ(β) = k contributes to the number of
possible continuations with a factor bounded from above by (2k)k.
Combining the upper bounds obtained, we get the inequality
|Y(S)| ≤ 3r+p+q 9µ3 (2k0)3u2+4u3 ·
s∏
k=k0+1
(2k)kνk . (5.10)
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 101
O. Khorunzhiy
Gathering estimates (5.6)–(5.9) and (5.10) and combining them with the re-
sult of Lemma 3.2, we can estimate the number of walks for a class with given
diagram G(S) with S = (µ′′2, r, p, q, ū2; µ′3, µ
′′
3, ū3; ν̄) by the following expression:
1
µ′′2!
(
s2
2
)µ′′2 (6sθ∗)r
r!
(3sD)p
p!
· (3sk0)q
q!
1
µ′′3!
(
9s3
3!
)µ′′3
× (9s2(D + k0))µ′3
µ′3!
× ((2k0)3s)u2((2k0)4s)u3
k0−2∏
i=1
(µ′2)
u
(i)
2
u
(i)
2 !
k0−3∏
j=1
(µ3)u
(j)
3
u
(j)
3 !
. (5.11)
The sum of (5.11) over all possible values of ū2 gives the upper bound
((2k0)3s)u2
∑
u
(1)
2 +···+u
(k0−2)
2 =u2
k0−2∏
i=1
(µ′2)
u
(i)
2
u
(i)
2 !
=
((2k0)3sµ′2)
u2
u2!
∑
u
(1)
2 +···+u
(k0−2)
2 =u2
u2!
u
(1)
2 ! · · ·u(k0−2)
2 !
=
(
(2k0)3(k0 − 2)sµ′2
)u2
u2!
.
(5.12)
When deriving (5.12), we use the multinomial theorem.
The sum of (5.11) over all possible values of ū3 gives the following upper
bound:
((2k0)4s)u3
∑
u
(1)
3 +···+u
(k0−3)
3 =u3
k0−3∏
j=1
(µ3)u
(j)
3
u
(j)
3 !
≤
(
(2k0)4(k0 − 3)sµ3
)u3
u3!
. (5.13)
Combining relations (5.11), (5.12), (5.13) with the result of Lemma 3.2, we obtain
inequality (3.6). Corollary of Lemma 3.2 is proved.
To complete the proof of Lemma 3.3, it remains to estimate the number of
trajectories in the class of equivalence CW (3.1). It is easy to see that given W2s
of the class G = G(S), we have the equality
|U(I2s; 2s)| = |Vg| = s− σ + 1, (5.14)
where σ = µ2 + 2µ3 + u2 + u3 + |ν̄|1. Then [22]
|CW | =
s−σ∏
k=1
(
1− k
n
)
≤ exp
{
−(s− σ)2
2n
}
. (5.15)
This simple but important upper bound can be proved with the help of repre-
sentation 1− k/n = exp{ln(1− k/n)} and the use of the Taylor expansion. Now,
combining (5.15) with (3.6) and the result of Lemma 3.1, we get inequality (3.7).
Lemma 3.3 is proved.
102 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
5.3. Walks with imported cells
As we have seen in Section 3, the proper and imported cells at the vertex of
maximal exit degree β̆ are characterized by the set of parameters PR = (QR,HR)
(4.12). The aim of this sub-section is to describe the general principles of the
study of the family of walks W(u)
2s (D, d̄R; 〈G?〉s,HR; Υ) (4.16). In this subsection,
we assume that I = 0 and there is neither proper nor mirror cells at β̆.
Let us consider the walks that have only one imported cell generated by one
BTS-instant determined by a couple (τ1, φ), where the marked instant τ1 is either
z1 or y1 and denote it byW(u)
2s (D, d1, d2; 〈G?
τ1〉s, φ, Υ). We choose a tree of τ1 edges
Tτ1 and perform over it a partial chronological run R
(τ1)
T ,
R
(τ1)
T = {RT (t), 1 ≤ t ≤ ξτ1 − 1} . (5.16)
Going along R
(τ1)
T , we construct a sub-walk W[0,ξτ1−1] according to the self-
intersections of 〈G?〉s. During this run, we choose the realizations of the values
in red windows G◦ with the help of general filtration procedure described in the
proof of Lemma 3.2 (see subsections 5.1 and 5.2) and follow the rules Υ at the
non-marked steps. Then we can write that
W[0,t1] = W (Tτ1 , 〈G?
τ1〉s, 〈G◦〉[0,t1],Υ
)
, (5.17)
where 〈G◦〉[0,t1] indicates a realization of red edge-windows of G on the time in-
terval [0, t1] = [0, ξτ1 − 1].
5.3.1. Filtration of values `, ϕ and ψ. Let us assume that the instant τ1 = y1
fills the edge-window of the second arrival a2 = a2(i) of a simple self-intersection
i(2) = i(o1, y1). As we have pointed out (see subsection 4.3), this edge-window
can represent either o-edge or p-edge or q-edge of G.
To construct a continuation of the sub-walk W[0,t1] at the marked instant of
time ξτ1 , we have to choose one of the vertices γi of g(W[0,t1]) that verify the
condition that the chosen vertex γ is situated on the distance of φ non-marked
steps from β̆, where φ denotes either ` or ψ1.
Let us consider the case when the second arrival a2 has to verify the o-property.
Then the collection Γ = Γ(`,(o))
t1
(β̆) of admissible vertices γi is such that
u⊔
`=1
Γ(`,(o))
t1
(β̆) = V(o)
t1
,
where V(o)
t1
is the set of t1-open vertices. Clearly,
∑u
`=1 |Γ(`,(o))
t1
(β̆)| ≤ 2u.
Let us consider the case when a2 verifies the p-condition. Then the admissible
vertices γi belong to the sub-set ∆(`)(α) ⊆ ∆(α), α = W(ξτ1−1), of vertices that
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 103
O. Khorunzhiy
are situated on the distance of ` non-marked steps from β̆. Therefore,
u∑
`=1
|Γ(`,(∆))
t1
(β̆)| =
u∑
`=1
|∆(`)(α)| ≤ D. (5.18)
The same reasoning can be applied to the case of the q-condition imposed on a2.
Summing up, we can write that
u∑
`=1
|Γ(`,u2)
t1
(β̆)| ≤ |Γ(u2)| =
2u, if u2 = (o),
D, if u2 = (∆),
k0, if u2 = (Λ).
(5.19)
Let us consider the secondary imported cell generated by the remote BTS-
instant τ1 = y1. In the graph g(W[0,ξy1−1]), the way from β̆ to β̆ by ψ1 non-marked
steps is uniquely determined by the rule Υ. Therefore we can write that
u∑
ψ1=1
|Γ(ψ1)
t1
(β̆)| ≤ 1. (5.20)
The same is true for all subsequent secondary imported cells generated by y1,
and therefore (5.20) holds for all values of ψi with 1 ≤ i ≤ f ′′1 .
Now it is clear that in the case when the BTS-instant represented by τ1 = z1
is the local one, then for all imported cells generated by z1 the following equality
is valid:
u∑
ϕk=1
|Γ(ϕk)
t1
(β̆)| ≤ 1, 1 ≤ k ≤ f ′1. (5.21)
Let us consider the case when the y-label of (y1, `) is attributed to the edge-
window of the third arrival a3 at a vertex of M′
3 of G. Assume that a3 verifies
∆-condition. Repeating the proof of Lemma 5.1, attribute to W(ξy1) a vertex
γ that belongs to ∆(`)(α), α = W(ξy1 − 1) and take a marked instant τ ′ that
determines γ. Taking into account the last inequality of (5.18), we can see that
after the sum over `, the total number of admissible values τ ′ is bounded by D.
The remaining part of the reasoning is the same as before. The case when a3
verifies the Λ-condition can be studied by the similar argument. Then (cf. (5.4))
u∑
`=1
#
{
〈(o1, o2)〉W , W ∈ ∗
W2s
(
i(3)
(
o1, o2,
[
(y1,`)
u3
]))}
≤
{
sD, if u3 = (∆),
sk0, if u3 = (Λ).
(5.22)
It is clear that the sum over the values ψi attributed to y1 put into the edge-
window of a3 gives the upper bounds of the form (5.20). The same is true for the
sums over variables φi in the case of τ1 = z1.
104 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
Finally, let us consider the cases when the y-label is attributed to an edge-
window e of G that represents the third arrival a3 to the corresponding vertex v.
If v ∈ M′
2, then e is the u-edge. If v ∈ M′′
3, then e represents the blue µ-edge. If
v is a ν-vertex, then e is the black ν-edge. In all of these three cases, the vertex
γ = W(ξy1) is determined uniquely by the sub-walk W[0,t1] and therefore
u∑
φ=1
|Γ(φ)
t1
(β)| ≤ 1. (5.23)
The same is true in the cases when y1 is attributed to the edge-windows of the
k-th arrivals ak.
Summing up, we can say that after the summation over φ the number of
realizations of the values in red edge-windows is bounded by the same expres-
sions (5.19) and (5.22) as in the ordinary case without y-labels considered in the
previous sub-section.
Let us consider a walk constructed with the help of a diagram G? that has
two y-labels with the values to (y1, `1) and (y2, `2), respectively, belonging to the
same vertex v ∈ V(G?). We assume that y1 < y2. In this case the filtering of the
values of `1 is performed as before, and the sum over `1 gives one of the estimates
(5.19)–(5.23) for the number of admissible vertices. When arrived at the instant
of time ξy2 − 1, the vertex γ is determined by the construction of the sub-walk
W[0,ξy2−1], and y2 is attributed to the arrival αk at v with κ ≥ 3. Then the sum
over `2 gives us the upper bound
u∑
`2=1
|Γ(`2)
t2
(β̆)| ≤ 1. (5.24)
To get the final account on the sums over variables `, ψ and ϕ, let us assume
that the diagram GQ contains µ̆′2 y-labels attributed to r̆ o-edges, p̆ p-edges and
q̆ q-edges of G, and µ̆′3 y-labels attributed to the third arrivals at the vertices of
M′
3. Then
J∏
j=1
u∑
`j=1
f ′′j∏
i=1
u∑
ψi=1
K∏
k=1
f ′k∏
l=1
u∑
ϕl=1
|Γ(φ)(GQ)| ≤ (2u)r̆ Dp̆ kq̆
0 (2s(D + k0))µ̆′3 = F̆(G),
(5.25)
where we denoted by |Γ(φ)(GQ)| the product over all cardinalities of the sets of
admissible vertices presented.
5.3.2. Underlying Dyck paths and trees.
Regarding a walk W2s ∈ W(u)
2s (D, d1, d2; 〈G?
τ1〉s, φ, Υ), let us denote by t1 and
t2 the instants of time such that W2s(ti) = β̆, τ1 = ξτ1 , and t2 represents the
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 105
O. Khorunzhiy
arrival a′ at β̆ by the corresponding imported cell. According to the definition of
variables (τ1, φ), the sub-walk W[t1+1,t2−1] is such that it has φ non-marked steps
and after each of these steps it has tree-type sub-walks W̃(k) that are reduced by
R̂ to the empty walks. This means that the Dyck structure of W2s is such that
the nest cell $′ = $(τ1, φ) that corresponds to a′ is obtained after φ descending
steps are performed in Tτ1 from the vertex υ = RTτ1
(ξτ1). Then the vertex υ′ of
Ts of W2s is determined, where the exit sub-cluster of d2 edges is to be placed.
Therefore Ts is to be of the following structure: consider a tree T [l]
τ1 that
contains τ1 edges and has the descending part of the length l ≥ φ (see Fig. 1).
We will say that the vertex υ1 = RT (ξτ1) is on the distance l from the root of
the tree. On the l vertices of the descending part, construct a realization of l
sub-trees of the total number of s − τ1 edges such that at the nest cell $′ there
exists a tree with the root sub-cluster of d2 edges (see Section 6 for more details).
We denote such a family of trees by T {l}s−τ1(d2, τ1, φ).
The family of trees that corresponds to the Dyck paths generated by the
elements of W(u)
2s (d2, 〈G?〉s, φ, Υ) is given by the expression
τ1⊔
l=1
{
T [l]
τ1 ⊗ T
{l}
s−τ1(d2, τ1, φ)︸ ︷︷ ︸
}
= T∗s,
u-condition
where we denoted
T∗s = T(u)
s (d2, τ1, φ). (5.26)
The under-brace with u-condition means that we construct the sub-trees T [l]
τ1 and
T {l}s−τ1(d2, τ1, φ) in the way that the height of the common tree obtained Ts attains
u. In Section 6 we describe in details the set of these trees.
Ignoring the condition that the vertex β̆ = W2s(x1) has the first proper cell
x1 with d1 edges of the exit sub-cluster, we can write that
|W(u)
2s (d2, 〈G?〉s, φ, Υ)| =
τ1∑
l=1
∑
T [l]
τ1
∑
〈G◦〉[0,ξτ1−1]
|Γ(φ)
τ1 (β̆)|
×
∑
T {l}
s−τ1
(d2,τ1,φ)
∑
〈G◦〉(τ1,φ)
[ξτ1+1,2s]
1. (5.27)
In the last sum of (5.27), we have denoted by 〈G◦〉(τ1,φ)
[ξτ1+1,2s] a realization of the
values in the red edge-windows of G on the time interval [ξτ1 +1, 2s]; this realiza-
tion also depends on T [l]
τ1 and T {l}s−τ1(d2, τ1, φ). We denote by r1, p1, q1, 2µ′3(1) and
r2, p2, q2, 2µ′3(2) the number of red windows to be determined during the time
106 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
intervals [0, ξτ1 − 1] and [ξτ1 + 1, 2s], respectively. It is clear that r1 = r2 + 1 = r.
The same equalities are verified by other red edge-windows.
Let us forget for the moment that the walks of the left-hand side of (5.26) are
such that their Dyck paths have the height θ∗ = u. Then it is not hard to show
that the following upper bound holds for any given value of φ:
∑
T {l}
s−τ1
(d2,τ1,φ)
1 ≤ e−ηd2
∑
T {l}
s−τ1
1, (5.28)
where η = ln(4/3) (see Lemma 6.1 of the next section).
Taking into account that the upper bound (cf. (5.5))
|
{
〈G◦〉(τ1,φ)
[ξτ1+1,2s]
}
| ≤ |G(2)
◦ | = (2u)r2Dp2kq2
0 (s(D + k0))µ′3(2) (5.29)
is uniform with respect to φ, we use (5.19) and deduce from (5.27) that
u∑
φ=1
|W(u)
2s (d2, 〈G?〉s, φ, Υ)| ≤
τ1∑
l=1
∑
T [l]
τ1
∑
〈G◦〉[0,ξτ1−1]
∑
T {l}
s−τ1
e−ηd2 · |G(2)
◦ | ·
u∑
φ=1
|Γ(φ)
τ1 (β̆)| .
Taking into account that
τ1∑
l=1
∑
T [l]
τ1
∑
T {l}
s−τ1
1 = ts,
we finally get the upper bound
u∑
φ=1
|W(u)
2s (d2, 〈G?〉s, φ, Υ)| ≤ e−ηd2 ts |G◦|, (5.30)
where |G◦| is given by (5.5).
The u-condition of (5.26) makes the use of (5.28) more complicated. The
proof of the exponential estimates of the form of (5.30) is given in Section 6.
6. Catalan trees and D-lemma
6.1. Exponential bound for Catalan trees
The following statement slightly improves the corresponding results of [7] and [8].
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 107
O. Khorunzhiy
Lemma 6.1. Consider the family of Catalan trees constructed with the help
of s edges and such that the root vertex % has d edges attached to it and denote
by t̃s(d) its cardinality. Then the upper bound
t̃s(d) ≤ e−ηd ts, η = ln(4/3) (6.1)
is true for any given integers d and s such that 1 ≤ d ≤ s.
P r o o f. By the definition,
t̃s(d) =
∑
u1+···+ud−1+ud=s−d
tu1 · · · tud−1
tud
, (6.2)
where the sum runs over integers uj ≥ 0. We will say that (6.2) represents the
number of Catalan trees of s edges that have a sub-cluster attached to the root
% that contains d edges.
Using the fundamental recurrence relation
ts+1 =
s∑
j=0
tj tk−j , s ≥ 0, t0 = 1, (6.3)
we can rewrite (6.2) in the following form:
t̃s(d) =
s−d∑
v=0
∑
u1+···+ud−2+v=s−d
tu1 · · · tud−2
∑
ud−1+ud=v
tud−1
tud
=
∑
u1+···+ud−2+ud−1=s−d+1
tu1 · · · tud−2
tud−1
−
∑
u1+···+ud−2=s−d+1
tu1 · · · tud−2
.
(6.4)
Relation (6.4) implies that
t̃s(d) =
t̃s(d− 1)− t̃s−1(d− 2), for all 3 ≤ d ≤ s,
ts−1, for d = 2 and s ≥ 2,
ts−1, for d = 1 and s ≥ 1,
(6.5)
where the last two relations are easy to obtain directly. It follows from (6.5) that
t̃s(d) ≤ ts−1, for all 1 ≤ d ≤ s. (6.6)
Let us return to (6.4) and rewrite it in the form
t̃s(d) =
s−d∑
v=0
t̃s−v−1(d− 1) · tv, 2 ≤ d ≤ s. (6.7)
108 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
Assuming that d ≥ 3 and applying (6.6) to the right-hand side of (6.7), we get
the inequality
t̃s(d) ≤
s−d∑
v=0
ts−2−v tv ≤ ts−1 − ts−2. (6.8)
Using the explicit expression for the Catalan numbers (3.2), it is easy to show
that
2ts ≤ ts+1 ≤ 4ts, s ≥ 1. (6.9)
Then we deduce from (6.8) that
t̃s(d) ≤
(
3
4
)
ts−1, d ≥ 3. (6.10)
Relation (6.1) holds for d = 3, s ≥ 3. The standard reasoning by recurrence
based on (6.7) proves the bound
t̃s(d) ≤
(
3
4
)d−2
ts−1, 3 ≤ d ≤ s. (6.11)
Remembering (6.5), we get that (6.11) is also true in the case of d = 2, s ≥ 2.
Using the first inequality of (6.9), we deduce from (6.11) the upper bound (6.1).
Lemma 6.1 is proved.
6.2. Tree-type walks with multiple edges
Given a Catalan tree Ts, let us denote by N(2)(Ts) the number of choices of
two edges of Ts that have the same parent vertex. Clearly, the sum N(2)
s =∑
Ts∈Ts
N(2)(Ts) represents the number of even closed tree-type walks of 2s steps
whose graphs have exactly one p-edge passed four times and s − 2 grey edges
passed two times.
Lemma 6.2. For any given s ≥ 2, the following relations hold:
N(2)
s =
(2s)!
(s− 2)! (s + 2)!
=
(
s− 3s
s + 2
)
ts, (6.12)
and therefore N(2)
s ≤ sts; the lower bound N(2)
s ≥ (sts)/2 is true for all s ≥ 4.
P r o o f. It is easy to see that
N(2)
s =
∑
u+v1+v2+v3=s−2
(2u + 1) tutv1tv2tv3 , s ≥ 2, (6.13)
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 109
O. Khorunzhiy
where the sum runs over all integers u ≥ 0 and vi ≥ 0. Then the generating
function Φ(2)(ς) =
∑
k≥0 N(2)
k ςk with N(2)
0 = N(2)
1 = 0 is given by the relation
Φ(2)(ς) = 2ς3 f ′(ς) f3(ς) + ς2 f4(ς), (6.14)
where f(ς) =
∑∞
s=0 ts ςs is the generating function of the Catalan numbers. It
follows from (6.3) that f(ς) verifies the well-known equation
f(ς) = 1 + ς f2(ς), (6.15)
and then
f(ς) =
1−√1− 4ς
2ς
. (6.16)
It follows from (6.15) that
f ′(ς) = f2(ς) + 2ς f ′(ς) f(ς). (6.17)
Using (6.15) and (6.17) and taking into account that
f ′(ς) =
∞∑
k=0
(k + 1)tk+1 ςk, (6.18)
one can easily derive from (6.14) relation (6.12). Lemma 6.2 is proved.
Let us consider a general case of the tree-type walks such that their graphs
have exactly one edge passed 2l times and other s − l edges passed two times.
The number of these walks N(l)
s is given by the the total number of possibilities
to mark l edges that have the same parent vertex at the Catalan trees. Similarly
to (6.13), we can write that
N(l)
s =
∑
u+v1+···+v2l−1=s−l
(2u + 1) tutv1tv2 . . . tv2l−1
. (6.19)
The corresponding generating function Φ(l)(ς) is given by the relation
Φ(l)(ς) = 2ς l+1 f ′(ς) f2l−1(ς) + ς l f2l(ς), (6.20)
and therefore
Φ(l)(ς) = ς l f2l−1(ς)
(
2√
1− 4ς
− f(ς)
)
. (6.21)
Using (6.15) and (6.18), we can deduce from (6.20) that
N(l)
s ≤ 2ls ts, 2 ≤ l ≤ s. (6.22)
110 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
This inequality means that the constant η = ln(4/3) of the exponential estimate
(6.1) can be considerably increased for large values of s and d.
Similarly to (6.12), it is not hard to show that
N(3)
s =
(2s)!
(s− 3)! (s + 3)!
= ts
(
s− 8− 36s + 48
s2 + 5s + 6
)
, (6.23)
and therefore N(3)
s ≤ sts. Regarding N(1)
s as a number of trees with one marked
edge, we can see that
N(1)
s = sts =
(2s)!
(s− 1)! (s + 1)!
. (6.24)
Relation (6.24) indicates a natural connection among expressions (3.2), (6.12)
and (6.23). It is natural to assume that the equality
N(l)
s =
(2s)!
(s− l)! (s + l)!
(6.25)
is true for all values of l ∈ [1, . . . , s]. However, relation (6.21) seems to be not so
convenient for proving (6.25). It would be useful to find the representations of
N(l)
s different from (6.19) and (6.20). Let us note that (6.25) would imply a useful
upper bound N(l)
s ≤ sts for all s and l ≤ s that is stronger than (6.20). Clearly,
the last upper bound is in complete accordance with the Galton–Watson view of
Catalan trees.
6.3. D-lemma
Our aim is to prove the exponential-type estimate of the form (4.18). For
simplicity, we consider the case when the non-trivial tree-type sub-clusters with
di > 0 correspond either to the proper or to the imported cells at β̆. The case of
mirror cells will be considered at the end of the present subsection.
Lemma 6.3 Consider a family of walks W(u)
2s (D, d̄R; 〈G?
R〉s,HR, Υ) (4.16).
Then for any integer m ≥ 0,
s∑
u=1
um
∑
HR
|W(u)
2s (D, d̄R; 〈G?
R〉s,HR, Υ)| ≤ A(m)
s · 4R (DR + 1) e−ηDR ts, (6.26)
where we denoted
A(m)
s = A(m)
s (G,D, k0) = s(m+r)/2 Bm+r 2r Dp kq
0 (s(D + k0))µ′3 , (6.27)
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 111
O. Khorunzhiy
with
Bm+r = sup
s≥1
B
(s)
m+r, B(s)
r =
1
ts
s∑
u=1
(
u√
s
)r
· |T(u)
s | (6.28)
and
T(u)
s = {Ts : θ∗(Ts) = u} . (6.29)
We prove Lemma 6.3 by recurrence. Let us introduce the following denota-
tions related with (6.29). Given natural a and u, let us denote by Ṫ(u)
a = T(u)
a
a family of Catalan trees Ta of a edges such that for any such a tree the corre-
sponding Dyck path has the height u, θ∗(Ta) = u. In this case we simply say that
Ta has the height u. Let T̈(u)
a be a family of Catalan trees such that θ∗(Ta) ≤ u.
We denote the cardinalities of these sets of trees by Ṫ
(u)
a and T̈
(u)
a , respectively,
Ṫ
(u)
a = | {Ta ∈ Ta : θ∗(Ta) = u} | and T̈
(u)
a = | {Ta ∈ Ta : θ∗(Ta) ≤ u} | .
(6.30)
We assume that Ṫ
(u)
a = 0 when a < u, Ṫ
(0)
a = T̈
(0)
a = 0 for any a ≥ 1 and
Ṫ
(0)
0 = T̈
(0)
0 = 1.
We also denote by Ṫ(u,[l])
a the family of trees of the height u that have the
descending part of length l. The families Ṫ(u,{l})
a , T̈(u,[l])
a and T̈(u,{l})
a as well as
the families of trees that have a sub-cluster at one of the nest cell are determined
in obvious manner, (see (5.26)). This will be clarified in the computations that
follow.
6.3.1. The initial step of recurrence. In this subsection, we study a family
of walks W(u)
2s (d, 〈G?
τ1〉s, φ,Υ) given by (4.16) with R = 1 such that the first non-
trivial sub-cluster of the tree-type part W̃ with d edges is attached to the nest
cell $1 = (τ1, φ1) of the corresponding tree (see also (5.26)). The variable τ1
denotes one of the three possible values that are x1, y1 or z1, and φ1 = φ is equal
to 0, `1 or ϕ1, respectively. If τ1 = y1, then φ can also be equal to ψ1.
According to the definitions of (6.30), the subset of trees (5.26) can be repre-
sented as follows:
T(u)
s (d, τ1, φ) =
τ1⊔
l=1
{
Ṫ (u,[l])
τ1 ⊗ T̈ (u,{l})
s−τ1 (d, τ1, φ)
}
t
τ1⊔
l=1
{
T̈ (u−1,[l])
τ1 ⊗ Ṫ (u,{l})
s−τ1 (d, τ1, φ)
}
. (6.31)
The accurate version of (5.27) is given then by the two sums,
|W(u)
2s (d, 〈G∗〉s, φ,Υ)|
112 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
=
τ1∑
l=1
∑
Ṫ (u,[l])
τ1
∑
〈G◦〉[0,t1]
|Γ(φ,u)
t1
(β̆)|
∑
T̈ (u,{l})
s−τ1
(d,τ1,φ)
∑
〈G◦〉(τ1,φ)
[t1+2,2s]
1
+
τ1∑
l=1
∑
T̈ (u−1,[l])
τ1
∑
〈G◦〉[0,t1]
|Γ(φ,u)
t1
(β̆)|
∑
Ṫ (u,{l})
s−τ1
(d,τ1,φ)
∑
〈G◦〉(τ1,φ)
[t1+2,2s]
1, (6.32)
where we denoted t1 = ξτ1 − 1. It should be noted that the sum
∑
〈G◦〉(τ1,φ)
[t1+2,2s]
1
is bounded from above by |G(2)
◦ | (5.29) uniformly with respect to φ.
Let us estimate the cardinality of the family T̈(u,{l})
s−τ1 (d, τ1, φ),
|T̈(u,{l})
s−τ1 (d, τ1, φ)| =
∑
T̈ (u,{l})
s−τ1
(d,τ1,φ)
1 .
Using (6.30), we can write that
|T̈(u,{l})
s−τ1 (d, τ1, φ)| =
∑
b̄d,c̄l,
|b̄d|+|c̄l|=s−τ1
T̈
(u−l+φ−1)
{d,b̄d} T̈
(u)
[l+1,c̄l]
, (6.33)
where b̄d = (b1, . . . , bd), |b̄d| = b1 + · · · + bd, c̄l = (c0, c1, . . . , cl), |c̄l| = c0 + c1 +
· · ·+ cl,
T̈
(u−l+φ−1)
{d,β̄d} =
d∏
k=1
T̈
(u−l+φ−1)
bk
and
T̈
(u)
[l+1,c̄l]
=
l∏
i=0
T̈
(u−l+i)
ci
.
Regarding (6.34), we can use the obvious inequalities
T̈
(u−l+φ−1)
bk
≤ T̈
(u−l+φ)
bk
≤ tbk
(6.34)
and write that for a given b ≥ d, due to Lemma 6.1,
∑
b̄d: |b̄d|=b−d
T̈
(u−l+φ−1)
{d,b̄d} ≤
∑
b̄d: |b̄d|=b−d
d∏
k=1
tbk
= τb(d) ≤ e−ηd tb. (6.35)
Then
|T̈(u,{l})
s−τ1 (d, τ1, φ)| ≤
s−max{τ1,1}∑
b=d
e−ηd tb
∑
c̄l,
|c̄l|=s−τ1−b
T̈
(u)
[l+1,c̄l]
. (6.36)
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 113
O. Khorunzhiy
Now we can perform the sum over φ in the right-hand side of (6.32) and get with
the help of (5.19), the upper bound (cf. (5.5))
u∑
φ=1
∑
〈G◦〉[0,t1]
|Γ(φ,u)
t1
(β̆)| · |G(2)
◦ | ≤ (2u)r Dp kq
0 (s(D + k0))µ′3 = |G◦|.
The sum over φ being performed, the last expression of (6.36) can be inserted
into the first term of the right-hand side of (6.32). This gives the sum
τ1∑
l=1
∑
Ṫ (u,[l])
τ1
∑
c̄l,|c̄l|=s−τ1−b
T̈
(u)
[l+1,c̄l]
= |T̀(u,τ1)
s−b |, (6.37)
where we have denoted by T̀(u,τ1)
s−b the family of all trees Ts−b such that the height
θ∗(Ts−b) = u is attained for the first time during the time interval [0, t1] =
[0, ξτ1 − 1].
Let us consider the second term of the right-hand side of (6.32) and estimate
the cardinality
|Ṫ(u,{l})
s−τ1 (d, τ1, φ)| =
∑
Ṫ (u,{l})
s−τ1
(d,τ1,φ)
1.
Using the first inequality of (6.35), we can write that
|Ṫ(u,{l})
s−τ1 (d, τ1, φ)| ≤
∑
b̄d,c̄l,
|b̄d|+|c̄l|=s−τ1
(
T̈
(u−l+φ)
{d,b̄d} Ṫ
(u)
[l+1,c̄l]
+ Ṫ
(u−l+φ)
{d,b̄d} T̈
(u)
[l+1,c̄l]
)
,
(6.38)
where
Ṫ
(u−l+φ)
{d,b̄d} =
d∑
k=1
T̈
(u−l+φ−2)
b1 · · · T̈(u−l+φ−2)
bk−1
Ṫ
(u−l+φ−1)
bk
T̈
(u−l+φ−1)
bk+1
· · · T̈(u−l+φ−1)
bd
.
(6.39)
Let us consider the first term of the right-hand side of (6.38). The same
computation as before shows that for any given b ≥ d,
∑
b̄d: |b̄d|=b−d
T̈
(u−l+φ)
{d,b̄d} ≤ e−ηd tb. (6.39)
Similarly to (6.37), we observe that
τ1∑
l=1
∑
T̈ (u,[l])
τ1
∑
c̄l,|c̄l|=s−τ1−b
Ṫ
(u)
[l+1,c̄l]
= |T́(u,τ1)
s−b |, (6.40)
114 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
where we T́(u,τ1)
s−b denotes the family of trees Ts−b such that the height θ∗(Ts−b) = u
is attained for the first time during the time interval [ξτ1 , 2s].
Let us consider the second term of the right-hand side of (6.38). Applying
(6.34) to all the factors T̈ of (6.39), we can write that
Ṫ
(u−l+φ)
{d,b̄d} ≤
d∑
k=1
tb1 · · · tbk−1
Ṫ
(u−l+φ−1)
bk
tbk+1
· · · tbd
.
Then for any given b ≥ d,
∑
b̄d: |b̄d|=b−d
Ṫ
(u−l+φ)
{d,b̄d} ≤ d e−η(d−1)
b−d∑
b1=u−l+φ−1
Ṫ
(u−l+φ−1)
b1 tb−b1−1. (6.41)
It is useful to note that the factor Ṫ
(u−l+φ−1)
b1 T̈
(u)
[l+1,c̄l]
being substituted into the
second term of (6.32) produces an expression
τ1∑
l=1
∑
T̈ (u−1,[l])
τ1
Ṫ
(u−l+φ−1)
b1
∑
c̄l,
|c̄l|=s−τ1−(b−b1−1)
T̈
(u)
[l+1,c̄l]
= |Ť(u,τ1,φ,1)
s−(b−b1−1)|, (6.42)
where we denote by Ť(u,τ1,φ,1)
s−b′ , b′ = b− b1 − 1 the family of trees Ts−b′ such that
the height θ∗(Ts−b′) = u is attained for the first time during the chronological
run over a sub-tree attached by exactly one edge to the nest cell (τ1, φ) of Ts−b′ .
This definition is self-explained by the left-hand side of (6.42). It is clear that
|Ť(u,τ1,φ,1)
s−b′ | ≤ |Ṫ(u)
s−b′ | and |T̀(u,τ1)
s−b | + |T́(u,τ1)
s−b | = |Ṫ(u)
s−b|. (6.43)
Remembering that all of the upper bounds (6.36), (6.39) and (6.41) are valid
for any given values of φ, we turn back to (6.32) and get the upper bound
|W(u)
2s (d, 〈G∗〉s, φ, Υ)| ≤ |G◦| e−ηd
(
s−1∑
b=d
tb |Ṫ(u)
s−b|+
4d
3
s−1∑
b′=d−1
tb′ |Ṫ(u)
s−b′ |
)
.
(6.44)
Extracting the factor ur from |G◦| (5.5), we can write that
s−b∑
u=1
um+r |Ṫ(u)
s−b| = (
√
s)m+r
s−b∑
u=1
(
u√
s
)m+r
|Θ(u)
2s−2b| ≤ s(m+r)/2 ts−b Bm+r .
(6.45)
Taking into account that d ≥ 1 and using the elementary relations based on (3.2)
and (6.3),
s−1∑
b=1
tb ts−b = ts+1 − 2ts ≤ 2ts
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 115
O. Khorunzhiy
and
4
3
s−1∑
b′=0
tb′ ts−b′ =
4
3
(ts+1 − ts) ≤ 4ts,
we deduce from (6.44) and (6.45) that
s∑
u=1
um
u∑
φ=1
|W(u)
2s (d, 〈G∗〉s, φ, Υ)| ≤ (2 + 4d) e−ηd ts
× s(m+r)/2 Bm+r 2r Dp kq
0 (s(D + k0))µ′3 . (6.46)
This proves relations (6.26), (6.27) with R = 1.
6.3.2. Recurrent estimates. Let us denote by τR+1 the marked instant that
corresponds to the imported cell (τR+1, φR+1) and write down the expression
(cf. (6.32))
|W(u)
2s (D, d̄R+1; 〈G?
R+1〉s, (HR, φR+1), Υ)| = Σ(1)(φR+1) + Σ(2)(φR+1), (6.47)
where
Σ(1)(φR+1) =
τR+1∑
l=1
∑
Ṫ (u,[l])
τR+1
∑
〈G(1)
◦ 〉
|Γ(φR+1,u)
tR+1
(β̆)|
∑
T̈ (u,{l})
s−τR+1
(dR+1,τR+1,φR+1)
∑
〈G(2)
◦ 〉
1
and
Σ(2)(φR+1) =
τR+1∑
l=1
∑
T̈ (u,[l])
τR+1
∑
〈G(1)
◦ 〉
|Γ(φR+1,u)
tR+1
(β̆)|
∑
Ṫ (u,{l})
s−τR+1
(dR+1,τR+1,φR+1)
∑
〈G(2)
◦ 〉
1.
In these relations, by 〈G(1)
◦ 〉 are denoted the realizations of values of the red
edge-windows of 〈GQR
〉s such that the marked instants of the corresponding blue
edge-windows are strictly less than τR+1 and by 〈G(2)
◦ 〉 those that have marked
instants greater or equal to τR+1.
Taking into account the uniform with respect to φτR+1 estimate of 〈G(2)
◦ 〉
(5.29) and denoting τ ′ = τR+1, we can write with the help of (6.37) that the sum
Σ(1) =
∑u
φR+1=1 Σ(1)(φR+1) is bounded from above as follows:
Σ(1) ≤ e−ηdR+1
s−1−τ ′∑
b=dR+1
tb
∑
T ∈T̀(u,τ ′)
s−b
∑
〈G(1)
◦ 〉
1
· |G(2)
◦ | · |Γ(uR+1)|. (6.48)
116 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
It should be noted that the expression standing in the parenthesis of (6.48) rep-
resents the family of walks
Ẁ(u,τ ′)
2s−2b(D, d̄R; 〈G(?,1)
R 〉s−b,HR,Υ) =
∑
T ∈T̀(u,τ ′)
s−b
∑
〈G(1)
◦ 〉
1 (6.49)
such that the conditions of Lemma 6.3 are verified. Here we have denoted by
〈G(?,1)
R 〉s−b the part of the realization of the diagram 〈G?
R〉s that takes into account
the instants of self-intersections that are strictly less than τ ′ = τR+1.
Regarding the sum Σ(2) =
∑u
φR+1=1 Σ(2)(φR+1), we use representation (6.38)
and write that
Σ(2) ≤ Σ́(2) + Σ̇(2), (6.50)
where
Σ́(2) ≤ e−ηdR+1
s−1−τ ′∑
b=dR+1
tb
∑
T ∈T́(u,τ ′)
s−b
∑
〈G(1)
◦ 〉
1
|G(2)
◦ | |Γ(uR+1)| (6.51)
and
Σ̇(2)(φ′) ≤ dR+1 e−η(dR+1−1)
s−1∑
b=dR+1−1
tb |G(2)
◦ |
×
τ ′∑
l=1
∑
T̈ (u,[l])
τ ′
∑
〈G(1)
◦ 〉
∑
|c̄l|=s−τ ′−b
T̈
(u−1)
[l+1,c̄l]
Ṫ
(u−l+φ′−1)
b−1
|Γ(uR+1)|. (6.52)
It is easy to see that
Σ(1) + Σ́(2) ≤ Dp2 kq2
0 (2s(D + k0))µ′3(2) |Γ(uR+1)|
×e−ηdR+1
s−1∑
b=1
tb (2u)r2 · |W(u,τ ′)
2s−2b(D, d̄R; 〈G(?,1)
R 〉s−b,HR, Υ)|. (6.53)
Regarding the sum
Σ′R+1 =
s∑
u=1
um
∑
HR
(
Σ(1) + Σ́(2)
)
,
we apply to the right-hand side of (6.53) the main proposition of the lemma (6.27)
and get the inequality
Σ′R+1 ≤ 2 · 4R DR e−ηDR+1 ts ·Bm+r 2r Dp kq
0 (s(D + k0))2µ′3 . (6.54)
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 117
O. Khorunzhiy
Let us consider the right-hand side of (6.52). The expression standing in the
parenthesis of (6.52) is bounded from above by the number of walks W2s−2b that
on the time interval [0, ξτR+1 − 1] verify the conditions of Lemma 6.3 and such
that the height u of the corresponding Dyck path θ(W2s−2b) is attained for the
first time above the edge attached to the nest cell (τ ′, φ′). Let us denote this
set of walks by Ẇ(u,τ ′,φ′)
2s−2b (D, d̄R; 〈G(?,1)
R 〉s−b,HR, Υ) (cf. (6.49)). To simplify the
proof, it is useful to observe that
|Ẇ(u,τ ′,φ′)
2s−2b (D, d̄R; 〈G(?,1)
QR
〉s−b,HR,Υ)| ≤ | ...
W
(u,∆c
i )
2s−2b (D, d̄R; 〈G(?,1)
R 〉s−b,HR,Υ)|,
where
...
W
(u,∆c
i )
2s−2b (D, d̄R; 〈G(?,1)
R 〉s−b,HR,Υ) is the family of walks with the same
properties as before and the only difference that the height θ∗(W2s) = u is at-
tained somewhere excepting those parts of θ that lie over the exit sub-clusters
∆i, 1 ≤ i ≤ dR.
We are going to show that
s∑
u=1
um
∑
HR
| ...
W
(u,∆c
i )
2s−2b (D, d̄R; 〈G(?,1)
R 〉s−b,HR, Υ)|
≤ 2R e−ηDR ts−b Bm+r1 2r1 Dp1 kq1
0 (s(D + k0))µ′3(1) . (6.55)
One can prove (6.55) by recurrence. We consider here the initial case of R = 1
only. It is easy to see that
| ...
W
(u,∆c
i )
2s (D, d; 〈G?
τ1〉s, φ1, Υ)| =
τ1∑
l=1
∑
T̈ (u−1,[l])
τ1
∑
Ṫ (u,{l})
s−τ1−b
+
∑
Ṫ (u,[l])
τ1
∑
T̈ (u,{l})
s−τ1−b
∑
〈G◦〉[0,t1]
1
× |Γ(φ1,u1)
t1
(β̆)|
∑
T̈ (u−l+φ1−1)
b (d)
∑
〈G◦〉[t1+2,2s]
1, (6.56)
where t1 = ξτ1 − 1.
Using the upper bound (5.5) and inequality (6.35), we deduce from (6.56) the
following inequality:
s∑
u=1
um
u∑
φ1=1
| ...
W
(u,∆c
i )
2s (D, d; 〈G∗τ1〉s, φ1, Υ)|
≤
s−1∑
b=d1
s∑
u=1
um+r |Ṫ(u)
s−b| · e−ηd1 tb 2r Dp kq
0 (2s(D + k0))µ′3 . (6.57)
Standard computations show that (6.57) proves (6.55) in the case of R = 1.
118 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
With the help of (6.55), we can deduce from (6.52) the following inequality:
Σ′′R+1 =
s∑
u=1
um
∑
HR
u∑
φ′=1
Σ̇(2)(φ′) ≤ 4dR+1
3
2R+1 e−ηDR+1 ts
Bm+r 2r Dp kq
0 (s(D + k0))2µ′3 .
Remembering (6.54), we obtain that
Σ′R+1 + Σ′′R+1 ≤
(
2 · 4R DR +
4dR+1
3
2R+1
)
e−ηDR+1 ts
×Bm+r 2r Dp kq
0 (s(D + k0))2µ′3 .
It is clear that the last inequality implies (6.27) with R replaced by R+1. Lemma
6.3 is proved.
6.3.3. Walks with mirror cells at β̆. Let us consider a family of walks
W(u)
2s (D, d̄R; 〈G?
R〉s,HR, Υ) (4.16) with the given set (x̄, m̄)I and assume that x1
is attributed by a number m1 > 0. This means that the walk arrives at β̆ at the
marked instant x1 and then performs a tree-type sub-walk W̌ = tm1
i=1W̌(i) such
that during this sub-walk it arrives m1 times by non-marked steps at β̆. Moreover,
each of the m1 tree-type sub-walks W̌(i) has a number of marked instants x
(i)
j
such that W̌(i)(ξ
x
(i)
j
) = β̆. These marked instants being determined, let us denote
the maximal one by x′1 = max{x(i)
j }.
The construction of the sub-trees and the nest cell is as follows: we consider
a tree T [l1]
x1 such that the vertex υ1 is on the distance of l1 from the tree root %.
Then we add l2 edges to the vertex υ1 and get the vertex υ2. On l2 roots obtained,
we construct sub-trees with the help of x′1 − x1 edges and get the tree T [l1+l2]
x′1
.
The mirror cell we consider will correspond to the arrival at υ2 by λ2 steps from
υ2. Then the ordinary procedure of constructing the trees with u-condition like
(5.26) can be used.
In the proof of Lemma 6.3 by recurrence, we needed the construction of the
last proper imported cell only. Therefore it is clear that the construction of the
mirror cell presented above fits completely this scheme. We do not present the
detailed arguments here.
7. Estimates from Below
Let us consider the random matrices H(n,ρ) (2.1) with random variables aij
that have all moments finite. Then the following statement for the moments
M(n,ρ)
n (2.5) is true.
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 119
O. Khorunzhiy
Theorem 7.1. Let sn = χn2/3 and ρn = ζn2/3 with given χ, ζ > 0. Then
lim inf
n→∞ M(n,ρn)
2sn
≥ 4V4
ζ(πχ)1/2
e−eχ3
(1 + o(1)) , (7.1)
where V4 = E|aij |4 and E|aij |2 = v2 = 1/4.
P r o o f. Let us consider a Dyck path θ2s and the corresponding Catalan
tree Ts. Regarding the chronological run RT , let us determine the marked instants
τ1 and τ2 such that the corresponding vertices of Ts have the same parent. We
denote such a pair by (τ1, τ2)p. Regarding the example tree T8 from Figure 1, we
can take (τ1, τ2)p = (3, 4) or, say, (τ ′1, τ
′
2)p = (6, 8).
It is clear that the tree-type walk W2s = W [θ]
2s (τ1, τ2) that has the Dyck
structure θs = θ(Ts) and one simple self-intersection (τ1, τ2)p is a walk with one
p-edge. It is also clear that the family of all possible walks
W[1,p]
2s =
⊔
Ts
⊔
(τ1,τ2)p
W [θ]
2s (τ1, τ2)
has the cardinality |W[1,p]
2s | = N(2)
s (6.12).
Let us denote the elements of W[1,p]
2s by w = w2s. We are going to construct a
family of walks W2s(w; µ2) by introducing µ2 additional simple self-intersections
in it, 0 ≤ µ2 ≤ M . The graph of the walk w2s has s vertices and therefore the
cardinality of this family is bounded from below as follows:
|W2s(w;µ2)| = s!
2µ2 µ2!(s− 2µ2)!
≥ 1
µ2!
(
(s− 2M)2
2
)µ2
. (7.2)
It is clear that the weight of any trajectory I2s (2.8) such thatW(I2s) ∈W(w; µ2)
admits the lower bound
Πa(I2s)Πb(I2s) ≥ V s−1
2 V4
ns−2 ρ
. (7.3)
Remembering (3.1), we conclude that the number of trajectories in the class
C(W2s), W2s ∈W2s(w;µ2) is bounded as follows:
|C(W2s)| =
s−µ2−1∏
i=0
(n− i) = ns−µ2
s−µ2−1∏
k=1
(
1− k
n
)
≥ ns−µ2 exp
{
− s2
2n
}
. (7.4)
The last inequality is obtained by the same argument as the upper bound (5.15).
Taking M = bcn1/3c+1 with c > 0, we deduce from relations (7.2), (7.3) and
(7.4) that
M(n,ρ)
2s ≥
∑
w∈W[1,p]
2s
M∑
µ2=0
∑
I2s∈C(W)
∑
W∈W2s(w;µ2)
V s−1
2 V4
ns−1 ρ
120 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
≥ nN(2)
s exp
{
− s2
2n
} M∑
µ2=0
1
µ2!
(
(s−M)2
2n
)µ2 V s−2
2 V4
ρ
. (7.5)
Elementary use of the Stirling formula shows that
∞∑
µ2=M+1
1
µ2!
(
(s−M)2
2n
)µ2
≥ 1√
2πcn1/3
∞∑
µ2=M+1
(
eχ2
2c
)µ2
= o(1)
for c = eχ2, and therefore with this choice of c we have
exp
{
− s2
2n
} M∑
µ2=0
1
µ2!
(
(s−M)2
2n
)µ2
≥ 1
2
exp{−eχ3/2}.
Remembering the lower bound N(2)
s ≥ (sts)/2 (see Lemma 6.2), we deduce from
(7.5) the inequality
M(n,ρ)
2s ≥ nts V s
2
s V4
4V 2
2 ρ
exp{−eχ3}.
Then (7.1) follows. Theorem 7.1 is proved.
8. Discussion
We have studied the asymptotic properties of the probability distribution of
the spectral norm of large dilute random matrices. We have shown that the prob-
ability distribution of the maximal eigenvalue of dilute Wigner random matrices
H(n,ρn), when regarded at the scale n−2/3, admits a universal upper bound in the
limit of infinite n, ρn such that n2/3(1+ε) ≤ ρn ≤ n, ε > 0 and sn = χn2/3, χ > 0.
This result is a consequence of the existence of a universal upper bound L(χ)
of the moments M̃(n,ρn)
2sn
, sn = χn2/3 of H̃(n,ρn) (2.6) and, in more general situa-
tion, of the moments M̂(n,ρn)
2sn
of corresponding random matrices with truncated
elements.
According to the general scheme developed in papers [23, 25], in the case
of Wigner ensemble of random matrices, this kind of asymptotic behavior of the
moments M2sn = EL2sn can be regarded as the strong evidence of the universality
of the probability distribution of one maximal eigenvalue of H(n,ρn), or its several
consecutive neighbors (see also [3, 24]). Indeed, as it is described in [25], the study
of the correlation functions of L2s′n and L2s′′n can be reduced, in a major part, to
the study of the related moment M2s′n+2s′′n−2 whose behavior can be shown to be
universal (see, however, [9]).
Therefore one can expect that the dilute Wigner random matrices in the
limit of the weak dilution, i.e., for the values of ρn such that n2/3 ¿ ρn ≤ n, n →
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 121
O. Khorunzhiy
∞, belong to the class of universality determined by the Gaussian Orthogonal
Ensemble of random matrices (GOE) in the case of real symmetric H(n,ρn), or to
the class of GUE in the hermitian case [16].
Theorem 7.1 shows that in the asymptotic regime n, ρn →∞ such that ρn =
ζn2/3, the estimate from below of M(n,ρn)
2sn
involves the factor V4. Therefore the
upper bound lim supn→∞M(n,ρn)
2sn
≤ M(χ) (2.6) cannot be true in this asymptotic
regime. This means that in the asymptotic regimes of the moderate and strong
dilutions, when ρn = ζ2/3 or ρn = o(n2/3), respectively, the limiting probability
distribution of the maximal eigenvalue cannot be universal in the sense that the
limiting expressions should depend on the moments higher than V2 of the random
variables aij .
Moreover, inequality (7.1) shows that in the asymptotic regime n, ρn → ∞
when ρn = σnε with 0 < ε < 2/3, to get the finite upper bound for the moment
M(n,ρn)
2sn
of the order sn, one should restrict the growth of sn and consider the case
when sn is proportional to ρn but not to n2/3 as before. According to the general
considerations based on the inequalities of the form (4.26), one can conclude that
the scale at the border of the limiting spectrum of H(n,ρn) should also be changed
to be proportional to ρn and not to n2/3 as it is in the case of n2/3(1+ε) ≤ ρn.
Therefore we can put forward a conjecture that the rate ρn = n2/3 represents
the critical point where the eigenvalue distribution at the edge of the spectrum
changes its properties, such as the scale and the dependence on the probability
distribution of the matrix elements aij .
Another important observation concerns the subsequent terms of the estimate
from below given by (7.1). Repeating the computations of the proof of Theorem
7.1 and using (6.23), we observe that the moments M(n,ρ)
2s (2.5) admit the following
asymptotic expansion:
M(n,ρ)
2s ' nts
4s
c(1) +
∑
k≥1
c
(2)
k
(
s V4
ρ
)k
+
∑
l≥1
c
(3)
l
(
s V6
ρ2
)l
+ o(s/ρ2)
, (8.1)
where s = χn2/3, ρ = ζn2/3 and c(i) > 0 depend on χ and ζ but do not depend
on n. In this case, the terms with V4 are present in the asymptotic development
of M(n,ρ)
2s , but the higher moments V6, V8, . . . disappear from it. Therefore we can
formulate a conjecture that the regimes of moderate and strong dilutions exhibit a
new kind of universality, say, V4-universality at the border of the limiting spectra.
The next observation is that the asymptotic expansion of the form
4s
nts
M(n,ρ)
2s ' c(1) +
∑
k≥1
c
(2)
k
(
s V4
ρ
)k
, s = χn2/3, ρ = ζn2/3 (8.2)
122 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
is related with the corresponding limit of the moments of sparse random matrices
studied in [13]. The fact that the right-hand side of (8.2) depends on the terms
with V4 only could essentially simplify the recurrent relations obtained in [13].
Moreover, it is natural to assume that the coefficients c
(2)
k will be related with
the corresponding terms of lims/ρ=χ/ζ, s→∞m
(ρ)
s , where m
(ρ)
s are determined by
the following recurrent relation with obvious initial conditions:
m(ρ)
s = v2
∑
a1+a2=s−1
m(ρ)
a1
m(ρ)
a2
+
V4
ρ
∑
b1+···+b4=s−2
m
(ρ)
b1
m
(ρ)
b2
m
(ρ)
b3
m
(ρ)
b4
. (8.3)
One can show that the asymptotic expression of the numbers m
(ρ)
s (8.3) should
be related with the generating functions of the numbers of ternary trees. We
postpone the study of (8.3) to subsequent publications.
Our last remark is related with the difference between the ensembles of real
symmetric and hermitian matrices. As it is mentioned in Section 2, the upper
bounds MGOE(χ) and MGUE(χ) are slightly different (see also relations (4.35) and
(4.36)). This difference is due to the contribution of walks with simple open self-
intersections and the breaks of the tree structure performed by the walk at them.
The contribution of these walks should vanish in the asymptotic regime of the
strong dilution, when ρn ≤ n2/3−ε and sn ≤ n2/3−ε, and only the tree-type walks
give the non-vanishing contribution. This means that the difference between
the spectral properties of real symmetric random matrices and their hermitian
analogs could disappear in the asymptotic regime of the strong dilution. It would
be interesting to study this phenomenon in more details. It should be noted that
the moments M(n,ρ)
2s of random matrices H(n,ρ) (2.1) with ρ = O(1) as n → ∞
were studied in [13] in the case of s = O(1). The explicit expressions obtained
there as well as the technique developed in [7] could be useful in the studies of
more complicated asymptotic regime described above, when sn →∞ as n →∞.
Acknowledgement. The author is grateful to the anonymous referee for the
careful reading of the manuscript.
References
[1] G.W. Anderson, A. Guionnet, and O. Zeitouni, An Introduction to Random Ma-
trices. Cambridge Studies in Advanced Mathematics, 118. Cambridge University
Press, Cambridge, 2010.
[2] Z.D. Bai and Y.Q. Yin, Necessary and Sufficient Conditions for the Almost Sure
Convergence of the Largest Eigenvalue of Wigner Matrices. — Ann. Probab. 16
(1988), 1729–1741.
[3] O.N. Feldheim and S. Sodin, A Universality Result for the Smallest Eigenvalues of
Certain Sample Covariance Matrices. — Geom. Funct. Anal. 20 (2010), 88–123.
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 123
O. Khorunzhiy
[4] Z. Füredi and J. Komlós, The Eigenvalues of Random Symmetric Matrices. —
Combinatorica 1 (1981), 233–241.
[5] S. Geman, A Limit Theorem for the Norm of Random Matrices. — Ann. Probab.
8 (1980), 252–261.
[6] V.L. Girko, Spectral Properties of Random Matrices. Nauka, Moscow, 1988. (Rus-
sian)
[7] A. Khorunzhy, Sparse Random Matrices: Spectral Edge and Statistics of Rooted
Trees. — Adv. Appl. Probab. 33 (2001), 124–140.
[8] O. Khorunzhy, High Moments of Large Wigner Random Matrices and Asymptotic
Properties of the Spectral Norm. — Random Oper. Stoch. Eq. 20 (2012), 25–68.
[9] O. Khorunzhiy, On Correlation Function of High Moments of Wigner Random
Matrices. Preprint arXiv:1011.3965
[10] O. Khorunzhiy, B. Khoruzhenko, L. Pastur, and M. Shcherbina, The large-n Limit
in Statistical Mechanics and the Spectral Theory of Disordered Systems. In: Phase
Transitions and Critical Phenomena 15, 74–239, Academic Press, London, 1992.
[11] O. Khorunzhy, W. Kirsch, and P. Müller, Lifshitz Tails for Spectra of Erdős-Rényi
Random Graphs. — Ann. Appl. Probab. 16 (2006), 295–309.
[12] O. Khorunzhy and J.-F. Marckert, Uniform Bounds for Exponential Moment of
Maximum of a Dyck Path. — Electr. Commun. Probab. 14 (2009), 327–333.
[13] O. Khorunzhy, M. Shcherbina, and V. Vengerovsky, Eigenvalue Distribution of
Large Weighted Random Graphs. — J. Math. Phys. 45 (2004), 1648–1672.
[14] O. Khorunzhiy and V. Vengerovsky, Even Walks and Estimates of High Moments
of Large Wigner Random Matrices. Preprint arXiv:0806.0157
[15] V.A. Marchenko and L.A. Pastur, Distribution of Eigenvalues for Some Sets of
Random Matrices. — Math. USSR Sb. 1 (1967), No. 4, 457–483.
[16] M.L. Mehta, Random Matrices. Amsterdam: Elsevier/Academic Press, 2004.
[17] A.D. Mirlin and Ya.V. Fyodorov, Universality of Level Correlation Function of
Sparse Random Matrices. — J. Phys. A 24 (1991), 2273–2286.
[18] L. Pastur, On the Spectrum of Random Matrices. — Theor. Math. Phys. 10 (1972),
102–111.
[19] C. Porter (Ed.), Statistical Theories of Spectra: Fluctuations. Acad. Press, New-
York, 1965.
[20] G.J. Rodgers and A.J. Bray, Density of States of a Sparse Random Matrix. — Phys.
Rev. B 37 (1988), 3557–3562.
[21] A. Ruzmaikina, Universality of the Edge Distribution of the Eigenvalues of Wigner
Random Matrices with Polynomially Decaying Distributions of Entries. — Commun.
Math. Phys. 261 (2006), 277–296.
124 Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1
High Moments of Large Dilute Wigner Matrices
[22] Ya. Sinai and A. Soshnikov, Central LimitTtheorem for Traces of Large Symmetric
Matrices with Independent Matrix Elements. — Bol. Soc. Brazil. Mat. 29 (1998),
1–24.
[23] Ya. Sinai and A. Soshnikov, A Refinement of Wigner’s Semicircle Law in a Neigh-
borhood of the Spectrum Edge for Random Symmetric Matrices. — Func. Anal.
Appl. 32 (1998), 114–131.
[24] S. Sodin, The Tracy-Widom Law for Some Sparse Random Matrices. — J. Stat.
Phys. 136 (2009), 834–841.
[25] A. Soshnikov, Universality at the Edge of the Spectrum in Wigner Random Matrices.
— Commun. Math. Phys. 207 (1999), 697–733.
[26] C.A. Tracy and H. Widom, Level Spacing Distribution and the Airy Kernel. —
Commun. Math. Phys. 159 (1994), 151–174.
[27] E. Wigner, Characteristic Vectors of Bordered Matrices with Infinite Dimensions.
— Ann. Math. 62 (1955), 548–564.
Journal of Mathematical Physics, Analysis, Geometry, 2014, vol. 10, No. 1 125
|
| id | nasplib_isofts_kiev_ua-123456789-106786 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1812-9471 |
| language | English |
| last_indexed | 2025-12-07T18:11:23Z |
| publishDate | 2014 |
| publisher | Фізико-технічний інститут низьких температур ім. Б.І. Вєркіна НАН України |
| record_format | dspace |
| spelling | Khorunzhiy, O. 2016-10-05T18:56:23Z 2016-10-05T18:56:23Z 2014 On High Moments and the Spectral Norm of Large Dilute Wigner Random Matrices / O. Khorunzhiy // Журнал математической физики, анализа, геометрии. — 2014. — Т. 10, № 1. — С. 64-125. — Бібліогр.: 27 назв. — англ. 1812-9471 DOI: 10.15407/mag10.01.064 MSC2000: 15B52 https://nasplib.isofts.kiev.ua/handle/123456789/106786 The author is grateful to the anonymous referee for the careful reading of the manuscript. en Фізико-технічний інститут низьких температур ім. Б.І. Вєркіна НАН України Журнал математической физики, анализа, геометрии On High Moments and the Spectral Norm of Large Dilute Wigner Random Matrices Article published earlier |
| spellingShingle | On High Moments and the Spectral Norm of Large Dilute Wigner Random Matrices Khorunzhiy, O. |
| title | On High Moments and the Spectral Norm of Large Dilute Wigner Random Matrices |
| title_full | On High Moments and the Spectral Norm of Large Dilute Wigner Random Matrices |
| title_fullStr | On High Moments and the Spectral Norm of Large Dilute Wigner Random Matrices |
| title_full_unstemmed | On High Moments and the Spectral Norm of Large Dilute Wigner Random Matrices |
| title_short | On High Moments and the Spectral Norm of Large Dilute Wigner Random Matrices |
| title_sort | on high moments and the spectral norm of large dilute wigner random matrices |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/106786 |
| work_keys_str_mv | AT khorunzhiyo onhighmomentsandthespectralnormoflargedilutewignerrandommatrices |