《贝叶斯学习与随机矩阵及在无线通信中的应用 BI-RM-AWC》课程教学资源（文献书籍）An Introduction to Random Matrices（Greg W. Anderson、Alice Guionnet）

2.1 TRACES,MOMENTS AND COMBINATORICS on R with density 1 6)=2元V4-k2 (2.1.3) The following theorem,contained in [Wig55],can be considered the starting point of Random Matrix Theory(RMT). Theorem 2.1.1 (Wigner)For a Wigner matrix,the empirical measure LN con- verges weakly,in probability,to the standard semicircle distribution. In greater detail,Theorem 2.1.1 asserts that for any fC(R),and any g >0, mPKw,)-(o,1>e)=0. Remark 2.1.2 The assumption(2.1.1)that rk<for all k is not really needed. See Theorem 2.1.21 in Section 2.1.5. We will see many proofs of Wigner's Theorem 2.1.1.In this section,we give a direct combinatorics-based proof,mimicking the original argument of Wigner. Before doing so,however,we need to discuss some properties of the semicircle distribution. 2.1.I The semicircle distribution,Catalan numbers,and Dyck paths Define the moments mg:=(o,x).Recall the Catalan numbers 2k k (2k)I Ck= k+1 (K+1)！k We now check that for all integers k. 2k=Ck,m2k+1=0. (2.1.4) Indeed,mk+1=0 by symmetry,while L()as=2. r/2 2k= πJ-2 sin2k(0)cos2(0)de 2·2/n sin2k(0)d0-(2k+1)m2k πJ-/2 Hence, 2.22k sin2(0)de=4(2k-1) rπ/2 12k= π(2k+2)J-π/2 2k+2m2k-2, (2.1.5)

2.1 TRACES, MOMENTS AND COMBINATORICS 7 on R with density σ(x) = 1 2π p 4−x 21|x|≤2 . (2.1.3) The following theorem, contained in [Wig55], can be considered the starting point of Random Matrix Theory (RMT). Theorem 2.1.1 (Wigner) For a Wigner matrix, the empirical measure LN con￾verges weakly, in probability, to the standard semicircle distribution. In greater detail, Theorem 2.1.1 asserts that for any f ∈ Cb(R), and any ε > 0, lim N→∞ P(|hLN, fi − hσ, fi| > ε) = 0. Remark 2.1.2 The assumption (2.1.1) that rk < ∞ for all k is not really needed. See Theorem 2.1.21 in Section 2.1.5. We will see many proofs of Wigner’s Theorem 2.1.1. In this section, we give a direct combinatorics-based proof, mimicking the original argument of Wigner. Before doing so, however, we need to discuss some properties of the semicircle distribution. 2.1.1 The semicircle distribution, Catalan numbers, and Dyck paths Define the moments mk := hσ,x k i. Recall the Catalan numbers Ck =  2k k  k +1 = (2k)! (k +1)!k! . We now check that for all integers k, m2k = Ck , m2k+1 = 0. (2.1.4) Indeed, m2k+1 = 0 by symmetry, while m2k = Z 2 −2 x 2kσ(x)dx = 2 · 2 2k π Z π/2 −π/2 sin2k (θ)cos2 (θ)dθ = 2 · 2 2k π Z π/2 −π/2 sin2k (θ)dθ −(2k +1)m2k . Hence, m2k = 2 · 2 2k π(2k +2) Z π/2 −π/2 sin2k (θ)dθ = 4(2k −1) 2k +2 m2k−2 , (2.1.5)

2.WIGNER MATRICES from which,together with mo =1,one concludes (2.1.4). The Catalan numbers possess many combinatorial interpretations.To introduce a first one,say that an integer-valued sequence [Snose is a Bernoulli walk of length e if So =0 and S+1-S =1 for t <e-1.Of particular relevance here is the fact that C&counts the number of Dyck paths of length 2k,that is,the number of nonnegative Bernoulli walks of length 2k that terminate at 0.Indeed,let B& denote the number of such paths.A classical exercise in combinatorics is Lemma2.1.3βk=Ck<4k.Further,the generating function B(e):=1+∑R=lβ satisfies,for <1/4. Be)=1--E (2.1.6) Proof of Lemma 2.1.3 Let Bk denote the number of Bernoulli walks {Sm}of length 2k that satisfy S24=0,and let B&denote the number of Bernoulli walks {S}of length 2k that satisfy S28 =0 and S<0 for some t<2k.Then,B& B&-B.By reflection at the first hitting of-1,one sees that B&equals the number of Bernoulli walks {Sn}of length 2k that satisfy S2x=-2.Hence, A=B队-a=（)-（2)=c Turning to the evaluation of B(),considering the first return time to 0 of the Bernoulli walk {Sn}gives the relation A=-B-1,k≥1， (2.1.7) with the convention that Bo=1.Because the number of Bernoulli walks of length 2k is bounded by 44,one has that B&<4k,and hence the function B(=)is well defined and analytic for<1/4.But,substituting(2.1.7), 阳-1含宫=2宫 while e-AA=三2Ra 9=0司 Combining the last two equations,one sees that B(e)=1+B(e2

8 2. WIGNER MATRICES from which, together with m0 = 1, one concludes (2.1.4). The Catalan numbers possess many combinatorial interpretations. To introduce a first one, say that an integer-valued sequence {Sn}0≤n≤ℓ is a Bernoulli walk of length ℓ if S0 = 0 and |St+1 −St | = 1 for t ≤ ℓ−1. Of particular relevance here is the fact that Ck counts the number of Dyck paths of length 2k, that is, the number of nonnegative Bernoulli walks of length 2k that terminate at 0. Indeed, let βk denote the number of such paths. A classical exercise in combinatorics is Lemma 2.1.3 βk =Ck < 4 k . Further, the generating function ˆβ(z):= 1+∑ ∞ k=1 z kβk satisfies, for |z| < 1/4, ˆβ(z) = 1− √ 1−4z 2z . (2.1.6) Proof of Lemma 2.1.3 Let Bk denote the number of Bernoulli walks {Sn} of length 2k that satisfy S2k = 0, and let B¯k denote the number of Bernoulli walks {Sn} of length 2k that satisfy S2k = 0 and St < 0 for some t < 2k. Then, βk = Bk −B¯k . By reflection at the first hitting of −1, one sees that B¯k equals the number of Bernoulli walks {Sn} of length 2k that satisfy S2k = −2. Hence, βk = Bk −B¯k =  2k k  −  2k k −1  = Ck . Turning to the evaluation of ˆβ(z), considering the first return time to 0 of the Bernoulli walk {Sn} gives the relation βk = k ∑ j=1 βk−jβ j−1 , k ≥ 1, (2.1.7) with the convention that β0 = 1. Because the number of Bernoulli walks of length 2k is bounded by 4k , one has that βk ≤ 4 k , and hence the function ˆβ(z) is well defined and analytic for |z| < 1/4. But, substituting (2.1.7), ˆβ(z)−1 = ∞ ∑ k=1 z k k ∑ j=1 βk−jβ j−1 = z ∞ ∑ k=0 z k k ∑ j=0 βk−jβ j , while ˆβ(z) 2 = ∞ ∑ k,k ′=0 z k+k ′ βkβk ′ = ∞ ∑ q=0 q ∑ ℓ=0 z qβq−ℓβℓ . Combining the last two equations, one sees that ˆβ(z) = 1+z ˆβ(z) 2

2.1 TRACES.MOMENTS AND COMBINATORICS from which(2.1.6)follows (using that B(0)=1 to choose the correct branch of the square-root). 0 We note in passing that expanding(2.1.6)in power series in=in a neighborhood of zero,one gets (for<1/4) (2k-2)川 B(e)= 2R=1-立 2 (+) which provides an alternative proof of the fact that B&=Ck Another useful interpretation of the Catalan numbers is that C&counts the num- ber of rooted planar trees with k edges.(A rooted planar tree is a planar graph with no cycles,with one distinguished vertex,and with a choice of ordering at each vertex;the ordering defines a way to"explore"the tree,starting at the root.) It is not hard to check that the Dyck paths of length 2k are in bijection with such rooted planar trees.See the proof of Lemma 2.1.6 in Section 2.1.3 for a formal construction of this bijection. We note in closing that a third interpretation of the Catalan numbers,particu- larly useful in the context of Chapter 5,is that they count the non-crossing parti- tions of the ordered set.={1,2,...,k Definition 2.1.4 A partition of the set.:={1,2,...,k is called crossing if there exists a quadruple (a,b,c,d)with I sa<b<c<d<k such that a,c belong to one part while b,d belong to another part.A partition which is not crossing is a non-crossing partition. Non-crossing partitions form a lattice with respect to refinement.A look at Fig- ure 2.1.1 should explain the terminology "non-crossing":one puts the points 1,...,k on the circle,and connects each point with the next member of its part (in cyclic order)by an internal path.Then,the partition is non-crossing if this can be achieved without arcs crossing each other. It is not hard to check that C is indeed the number of non-crossing partitions of.%.To see that,let n be a non-crossing partition of%and let j denote the largest element connected to 1(with j=1 if the part containing I is the set {1)). Then,because n is non-crossing,it induces non-crossing partitions on the sets {1,...,j-1}and j+1,...,k).Therefore,==17-1.With n=1,and comparing with (2.1.7),one sees that B&=Y. Exercise 2.1.5 Prove that for =EC such that=[-2,2],the Stieltjes transform

2.1 TRACES, MOMENTS AND COMBINATORICS 9 from which (2.1.6) follows (using that ˆβ(0) = 1 to choose the correct branch of the square-root). ⊓⊔ We note in passing that expanding (2.1.6) in power series in z in a neighborhood of zero, one gets (for |z| < 1/4) ˆβ(z) = 2∑ ∞ k=1 z k (2k−2)! k!(k−1)! 2z = ∞ ∑ k=0 (2k)! k!(k +1)! z k = ∞ ∑ k=0 z kCk , which provides an alternative proof of the fact that βk = Ck . Another useful interpretation of the Catalan numbers is that Ck counts the num￾ber of rooted planar trees with k edges. (A rooted planar tree is a planar graph with no cycles, with one distinguished vertex, and with a choice of ordering at each vertex; the ordering defines a way to “explore” the tree, starting at the root.) It is not hard to check that the Dyck paths of length 2k are in bijection with such rooted planar trees. See the proof of Lemma 2.1.6 in Section 2.1.3 for a formal construction of this bijection. We note in closing that a third interpretation of the Catalan numbers, particu￾larly useful in the context of Chapter 5, is that they count the non-crossing parti￾tions of the ordered set Kk := {1,2,...,k}. Definition 2.1.4 A partition of the set Kk := {1,2,...,k} is called crossing if there exists a quadruple (a,b,c,d) with 1 ≤ a < b < c < d ≤ k such that a,c belong to one part while b,d belong to another part. A partition which is not crossing is a non-crossing partition. Non-crossing partitions form a lattice with respect to refinement. A look at Fig￾ure 2.1.1 should explain the terminology “non-crossing”: one puts the points 1,...,k on the circle, and connects each point with the next member of its part (in cyclic order) by an internal path. Then, the partition is non-crossing if this can be achieved without arcs crossing each other. It is not hard to check that Ck is indeed the number γk of non-crossing partitions of Kk . To see that, let π be a non-crossing partition of Kk and let j denote the largest element connected to 1 (with j = 1 if the part containing 1 is the set {1}). Then, because π is non-crossing, it induces non-crossing partitions on the sets {1,..., j −1} and { j +1,...,k}. Therefore, γk = ∑ k j=1 γk−jγ j−1. With γ1 = 1, and comparing with (2.1.7), one sees that βk = γk . Exercise 2.1.5 Prove that for z ∈ C such that z 6∈ [−2,2], the Stieltjes transform

10 2.WIGNER MATRICES Fig.2.1.1.Non-crossing (left,(1,4),(2,3),(5,6))and crossing (right,(1,5),(2,3),(4,6)) partitions of the set.6. S(=)of the semicircle law (see Definition 2.4.1)equals s9=/名a)=t6 22 Hint:Either use the residue theorem,or relate S()to the generating function B(), see Remark 2.4.2. 2.1.2 Proof#I of Wigner's Theorem 2.1.1 Define the probability distribution LN=ELN by the relation (LN,A=E(LN, for all fEC,and set m :=(LN,x).Theorem 2.1.1 follows from the following two lemmas. Lemma 2.1.6 For every k EN, mnm候=mk. Lemma 2.1.7 For every kE Nand g >0. mP(（亿w,)-亿w,>e)=0 Indeed,assume that Lemmas 2.1.6 and 2.1.7 have been proved.To conclude the proof of Theorem 2.1.1,one needs to check that for any bounded continuous func- tionf, im(LN=(,in probability. (2.1.8)

10 2. WIGNER MATRICES 1 2 3 4 5 6 1 2 3 4 5 6 Fig. 2.1.1. Non-crossing (left, (1,4),(2,3),(5,6)) and crossing (right, (1,5),(2,3),(4,6)) partitions of the set K6. S(z) of the semicircle law (see Definition 2.4.1) equals S(z) = Z 1 λ −z σ(dλ) = −z+ √ z 2 −4 2z . Hint: Either use the residue theorem, or relate S(z)to the generating function ˆβ(z), see Remark 2.4.2. 2.1.2 Proof #1 of Wigner’s Theorem 2.1.1 Define the probability distribution L¯N = ELN by the relation hL¯N, fi = EhLN, fi for all f ∈ Cb, and set m N k := hL¯N,x k i. Theorem 2.1.1 follows from the following two lemmas. Lemma 2.1.6 For every k ∈ N, lim N→∞ m N k = mk . Lemma 2.1.7 For every k ∈ N and ε > 0, lim N→∞ P   hLN,x k i − hL¯N,x k i    > ε  = 0. Indeed, assume that Lemmas 2.1.6 and 2.1.7 have been proved. To conclude the proof of Theorem 2.1.1, one needs to check that for any bounded continuous func￾tion f , lim N→∞ hLN, fi = hσ, fi, in probability. (2.1.8)

2.1 TRACES,MOMENTS AND COMBINATORICS Toward this end,note first that an application of the Chebyshev inequality yields P(.) EBk Hence,by Lemma 2.1.6, P(apo>≥sa2s苏 N where we used that C<4.Thus,with B=5,it follows,noting that the lefthand side above is increasing in k, limsupP(《亿w,1B)>e=0 (2.1.9) V→o∞ In particular,when proving(2.1.8),we may and will assume that f is supported on the interval [-5,5]. Fix next such an f and 8>0.By the Weierstrass approximation theorem,one can find a polynomial (x)=such that Qse-fe≤8 x.<B Then, P(Lw.-(a./I>5)sP(ILw.Qs)-(Lx.Qs)>) +P(NZy.Os)-(a.Os)I>9)+p(IGLv.OsI> =:B+B+乃 By an application of Lemma 2.1.7,P-N0.Lemma 2.1.6 implies that PN 0,while (2.1.9)implies that P3-N-00.This completes the proof of Theorem 2.1.1 (modulo Lemmas 2.1.6 and 2.1.7). ◇ 2.1.3 Proof of Lemma 2.1.6:Words and Graphs The starting point of the proof of Lemma 2.1.6 is the following identity: 么x,内=E2 =方，立Exe-…tate (2.1.10)

2.1 TRACES, MOMENTS AND COMBINATORICS 11 Toward this end, note first that an application of the Chebyshev inequality yields P  hLN,|x| k 1|x|>Bi > ε  ≤ 1 ε EhLN,|x| k 1|x|>Bi ≤ hL¯N,x 2k i εBk . Hence, by Lemma 2.1.6, limsup N→∞ P  hLN,|x| k 1|x|>Bi > ε  ≤ hσ,x 2k i εBk ≤ 4 k εBk , where we used that Ck ≤ 4 k . Thus, with B = 5, it follows, noting that the lefthand side above is increasing in k, limsup N→∞ P  hLN,|x| k 1|x|>Bi > ε  = 0. (2.1.9) In particular, when proving (2.1.8), we may and will assume that f is supported on the interval [−5,5]. Fix next such an f and δ > 0. By the Weierstrass approximation theorem, one can find a polynomial Qδ (x) = ∑ L i=0 cix i such that sup x:|x|≤B |Qδ (x)− f(x)| ≤ δ 8 . Then, P(|hLN, fi − hσ, fi| > δ) ≤ P  |hLN,Qδ i − hL¯N,Qδ i| > δ 4  +P  |hL¯N,Qδ i − hσ,Qδ i| > δ 4  +P  |hLN,Qδ1|x|>Bi > δ 4  =: P1 +P2 +P3 . By an application of Lemma 2.1.7, P1 →N→∞ 0. Lemma 2.1.6 implies that P2 →N→∞ 0, while (2.1.9) implies that P3 →N→∞ 0. This completes the proof of Theorem 2.1.1 (modulo Lemmas 2.1.6 and 2.1.7). ⊓⊔ 2.1.3 Proof of Lemma 2.1.6 : Words and Graphs The starting point of the proof of Lemma 2.1.6 is the following identity: hL¯N,x k i = 1 N EtrX k N = 1 N N ∑ i1,...,ik=1 EXN(i1,i2)XN(i2,i3)···XN(ik−1,ik)XN(ik ,i1) =: 1 N N ∑ i1,...,ik=1 ET N i =: 1 N N ∑ i1,...,ik=1 T¯N i , (2.1.10)