the moment method and non-crossing pairings

The moment method is the first and most hands-on proof that the eigenvalue histogram of a Wigner matrix is a semicircle. Its idea is borrowed straight from Volume I's method of moments for ordinary convergence in distribution: a measure on the line (with light tails) is determined by its sequence of moments, so to show a random measure converges to a target, you show every moment converges to the target's moment. For random matrices the moments of the eigenvalue distribution are computable without ever finding an eigenvalue — through the trace.

The key identity is that the k-th moment of the empirical spectral distribution is a normalised trace: the integral of x^k against mu_{H_N} equals (1/N) sum over i of lambda_i^k = (1/N) trace(H_N^k). Now expand the trace of the k-th power as a sum over closed sequences of indices i_1 -> i_2 -> ... -> i_k -> i_1: trace(H_N^k) = sum over such closed walks of the product H_{i_1 i_2} H_{i_2 i_3} ... H_{i_k i_1}. Taking the expectation, every walk contributes E of a product of entries. Because the entries are independent with mean zero, a walk contributes nothing unless every edge it uses is traversed an even number of times — each entry must be paired with itself to survive. Counting which pairings survive the N -> infinity scaling is then a pure combinatorics problem: when k = 2m is even, the dominant contributions come from walks that are encoded by non-crossing pair partitions of the 2m steps, walks that trace out a tree (a planar structure). The number of such non-crossing pairings of 2m objects is exactly the Catalan number C_m, and the odd moments vanish — which is precisely the moment sequence of the semicircle.

Non-crossing pairings are the heart of the matter. Draw the 2m steps as points on a line and connect paired steps by arcs above the line: a pairing is non-crossing if no two arcs intersect. Non-crossing pairings of 2m points number C_m = (1/(m+1)) binomial(2m, m), the Catalan numbers, and they are in bijection with planar trees, balanced parenthesisations, and Dyck paths. The crossing pairings, by contrast, force the closed walk to revisit fewer distinct indices and so come with an extra power of 1/N that kills them in the limit. This combinatorial dichotomy — non-crossing survives, crossing dies — is the same structure that reappears in free probability, where freeness is defined by exactly the vanishing of crossing (alternating) moments. A caveat: the moment method needs all moments of the entries to be finite (or careful truncation), and it proves convergence of the bulk density but is poorly suited to the edge, where the largest eigenvalue requires moments of growing order k ~ N^(2/3) and far more delicate counting.