What is the connection between moments of Gaussians and perfect matchings of graphs?

Question

Today, I heard the following statement in a talk:

The 4th moment of a $1$-dimensional Gaussian distribution with mean $0$ and variance $1$ is the same as the number of perfect matchings of a complete graph of $4$ vertices, which is $3$.

Unfortunately, the speaker did not have enough time to go into the details of this.

Firstly, it is very astonishing to me that something continuous can be related to something discrete as precisely as this, that is, beyond the limits of things like approximating a discrete sum with an integral. Secondly, what is the intuition behind this? Any pointers? Are there other examples like this where discrete quantities can be related to continuous quantities?

Answer 1

This fact is a corollary of a more general theorem. Let $\gamma_1,\dots, \gamma_{2n}$ be (jointly) Gaussian random variables; we don't assume that they are independent or identically distributed. Let $c_{ij} = {\mathbb E}[\gamma_i \gamma_j]$ be the covariance of $\gamma_i$ and $\gamma_j$. Consider the complete graph on $\{1, \dots, 2n\}$; assign weight $c_{ij}$ to edge $(i,j)$. Let the cost of a perfect matching $M$ (i.e. a matching of size $n$) be the product of weights of the edges in $M$: $$\mathrm{cost}(M)=\prod_{(i,j)\in M} c_{ij}.$$ Then $${\mathbb E}[\gamma_1 \gamma_2 \cdots \gamma_{2n}] = \sum_{M\text{ is a perfect matching}} \mathrm{cost(M)}.$$

We get the formula for the $2n$-th moment of a Gaussian random variable by letting $\gamma_1 = \dots = \gamma_{2n} = \gamma$, where $\gamma\sim{\cal N}(0,1)$. We have, $c_{ij} = 1$ and $\mathrm{cost}(M) = 1$ for every perfect matching $M$; thus, $${\mathbb E}[\gamma^{2n}] = {\mathbb E}[\gamma_1 \gamma_2 \cdots \gamma_{2n}] = |\{M: M \text{ is a perfect matching}\}|.$$

The proof of the theorem is not difficult at all. Also I think that its statement is not surprising. Indeed, the joint distribution $\gamma_1, \dots, \gamma_{2n}$ is completely characterized by weights/covariances $c_{ij}$ and variances $\sigma_i = {\mathbb E}[\gamma_i^2]$ (that is, by the covariance matrix of $\gamma_i$'s). Thus $P={\mathbb E}[\gamma_1 \gamma_2 \cdots \gamma_{2n}]$ is a function of parameters $\{c_{ij},\sigma_i\}_{i,j}$. It is easy to see that $P$ does not depend on $\sigma_i$'s — if we add a Gaussian r.v. $\gamma'$, independent from all $\gamma_i$'s, to some $\gamma_{a}$, variance $\sigma_a$ will change, but neither $P$ nor parameters $c_{ij}$ and $\sigma_{b}$ (for $b\neq a$) will change. Thus, $P$ must depend only on $c_{ij}$'s. Further, the expression for $P$ must be symmetric and homogeneous (if we multiply all $\gamma_i$'s by $\alpha$, then $c_{ij}$'s are multiplied by $\alpha^2$ and $P$ is multiplied by $\alpha^{2n}$). Given these observations, the statement of the theorem looks very natural.

Answer 2

Here is a different proof, adapted from the monograph The semicircle law, free random variables and entropy. Let $X_i$ be an infinite sequence of i.i.d. variables with distribution $\Pr[X_i = 1] = \Pr[X_i = -1] = 1/2$, so that $ Y_n :=\frac{X_1+\cdots+X_n}{\sqrt{n}} $ converges in distribution to a standard Gaussian. We will show how to compute the limit of $\newcommand{\EE}{\mathbb{E}} \EE[Y_n^d]$ (for even $d$), which is the same as the $d$th moment of a standard Gaussian.

If we open $Y_n^d$ up and use the exchangeability of the $X_i$, we see that $$ \begin{align*} \EE[Y_n^d] &= \sum_{t=1}^d \sum_{\substack{\lambda \vdash n\colon \\ \text{$\lambda$ has $t$ parts}}} \binom{d}{\lambda_1,\ldots,\lambda_t} n(n-1)\cdots(n-t+1) \frac{\EE[X_1^{\lambda_1} \cdots X_t^{\lambda_t}]}{n^{d/2}} \\ &\sim \sum_{t=1}^d \sum_{\substack{\lambda \vdash n\colon \\ \text{$\lambda$ has $t$ parts}}} \binom{d}{\lambda_1,\ldots,\lambda_t} n^{t-d/2} \EE[X_1^{\lambda_1} \cdots X_t^{\lambda_t}] \\ &= \sum_{t=1}^d \sum_{\substack{\lambda \vdash n\colon \\ \text{$\lambda$ has $t$ parts}, \\ \text{all $\lambda_i$ are even}}} \binom{d}{\lambda_1,\ldots,\lambda_t} n^{t-d/2}. \end{align*} $$ Since all $\lambda_i$ are even, necessarily $t \leq d/2$. When we take the limit $n\to\infty$, only terms with $t = d/2$ survive. There is in fact only one such term, the partition $\underbrace{2,\ldots,2}_{\text{$d/2$ times}}$. Therefore $$ \EE[N(0,1)^d] = \lim_{n\to\infty} \EE[Y_n^d] = \binom{d}{\underbrace{2,\ldots,2}_{\text{$d/2$ times}}}. $$ But $\binom{d}{\underbrace{2,\ldots,2}_{\text{$d/2$ times}}}$ is the number of ways to pair up the elements of $\{1,\ldots,d\}$, that is, the number of perfect matchings in $K_d$.

In the case of free probability, similar arguments involving non-crossing partitions are encountered in the computation of the moments of the semicircle law.