<p>Here is a different proof, adapted from the monograph <em>The semicircle law, free random variables and entropy</em>. 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.</p>

<p>If we open $Y_n^d$ up and use the exchangeability of the $X_i$, we see that
$$
\begin{align*}
\EE[Y_n^d] &amp;= \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}} \\ &amp;\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}] \\ &amp;=
\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$.</p>

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

CC BY-SA 3.0
2017-04-27T18:29:30.687Z
2017-04-27T18:29:30.687Z
Yuval Filmus
<p>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)}.$$</p>

<p>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}\}|.$$</p>

<p>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.</p>

CC BY-SA 3.0
2017-04-23T02:56:00.517Z
2017-04-23T15:43:44.113Z
2017-04-23T15:43:44.113Z
Yury
<p>Today, I heard the following statement in a talk: </p>

<blockquote>
  <p>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$.</p>
</blockquote>

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

<p>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?</p>

CC BY-SA 3.0
2017-04-22T00:53:29.710Z
It's the 4th moment: a Gaussian, being a symmetric distribution, has all its odd degree moments equal to 0. In fact this is true for any even degree moment. From the [moment generating function](https://en.wikipedia.org/wiki/Moment-generating_function) you see that the degree $(2k)$ moment of a standard Gaussian is $(2k)! / (2^k k!)$, which is easily seen to be the number of perfect matchings of the complete graph on $2k$ vertices. I'd be curious to see a more directly combinatorial explanation of this fact.
Sasho Nikolov
CC BY-SA 3.0
2017-04-22T01:02:58.990Z
As for "Are there other examples like this where discrete quantities can be related to continuous quantities?" this is a *ridiculous broad* topic. In a way, *all* of analytic number theory is an answer. For a concrete example, check the [circle method](https://en.wikipedia.org/wiki/Hardy%E2%80%93Littlewood_circle_method). The [Analytic Combinatorics](http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html) book by Flajolet and Sedgewick also has a wealth of examples.
Sasho Nikolov
CC BY-SA 3.0
2017-04-22T03:26:44.200Z
@SashoNikolov  Thanks for the explanation. I corrected the 4th moment part. Can you please point me to an actual application in CS Theory of such connections, perhaps a recent manuscript or article?
Jardine
CC BY-SA 3.0
2017-04-22T03:48:15.560Z
See the chapter by Vitter and Flajolet http://algo.inria.fr/flajolet/Publications/ViFl90.ps.gz
Sasho Nikolov
<graph-theory><pr.probability><matching><st.statistics>
What is the connection between moments of Gaussians and perfect matchings of graphs?
Jardine
# What is the connection between moments of Gaussians and perfect matchings of graphs?

(Asked by: username_0 on 2017-04-21)

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?

**Tags:** graph-theory, pr.probability, matching, st.statistics
> **Comments:**
> **username_1**: It's the 4th moment: a Gaussian, being a symmetric distribution, has all its odd degree moments equal to 0. In fact this is true for any even degree moment. From the [moment generating function](https://en.wikipedia.org/wiki/Moment-generating_function) you see that the degree $(2k)$ moment of a standard Gaussian is $(2k)! / (2^k k!)$, which is easily seen to be the number of perfect matchings of the complete graph on $2k$ vertices. I'd be curious to see a more directly combinatorial explanation of this fact.  
> **username_1**: As for "Are there other examples like this where discrete quantities can be related to continuous quantities?" this is a *ridiculous broad* topic. In a way, *all* of analytic number theory is an answer. For a concrete example, check the [circle method](https://en.wikipedia.org/wiki/Hardy%E2%80%93Littlewood_circle_method). The [Analytic Combinatorics](http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html) book by Flajolet and Sedgewick also has a wealth of examples.  
> **username_0**: @SashoNikolov  Thanks for the explanation. I corrected the 4th moment part. Can you please point me to an actual application in CS Theory of such connections, perhaps a recent manuscript or article?  
> **username_1**: See the chapter by Vitter and Flajolet http://algo.inria.fr/flajolet/Publications/ViFl90.ps.gz  

---

## 2 answers

### Answer by username_3 on 2017-04-23. Score: 11 | Accepted answer

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 by username_2 on 2017-04-27. Score: 6

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.


---

