7
$\begingroup$

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?

$\endgroup$
  • 7
    $\begingroup$ 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 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. $\endgroup$ – Sasho Nikolov Apr 22 '17 at 0:53
  • 6
    $\begingroup$ 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. The Analytic Combinatorics book by Flajolet and Sedgewick also has a wealth of examples. $\endgroup$ – Sasho Nikolov Apr 22 '17 at 1:02
  • $\begingroup$ @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? $\endgroup$ – Jardine Apr 22 '17 at 3:26
  • 2
    $\begingroup$ See the chapter by Vitter and Flajolet algo.inria.fr/flajolet/Publications/ViFl90.ps.gz $\endgroup$ – Sasho Nikolov Apr 22 '17 at 3:48
9
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.