RANDOM MATRICES AND FREE PROBABILITY

Definition 1.1. A random variable $X$ has a standard gaussian distribution if it has density

$$f_X(x)=\frac{1}{\sqrt{2\pi }}{e}^{-\frac{x^2}{2}}$$

for $x\in ℝ$. This is the case of mean $0$ and variance $1$.

Proposition 1.2. If $X$ is standard gaussian, then

$$𝔼(X^{2k})=(2k-1)!!\text{ and }𝔼(X^{2k-1})=0$$

for $k\ge 1$.

Definition 1.3 (Set partitions). A partition of the set $[n]:=\{1,\dots ,n\}$ is a collection $\{V_1,\dots ,V_l\}$ of blocks, which are disjoint subsets of $[n]$, with $[n]={\bigcup <!--\; FUNCTION\; APPLICATION\; -->}_{i=1}^l{V}_i$. The set of partitions of $[n]$ will be denoted by $P(n)$. A pair partition is a partition whose blocks all have size $2$; the set of pair partitions of $[n]$ will be denoted by $P_2(n)$. Note that $P_2(n)=\varnothing$ when $n$ is odd.

Let $\varphi :P(n)\to S_n$ be the map which turns blocks into cycles, with the usual order inherited from $[n]$. This is obviously injective, and the range of $P_2(n)$ is the set of permutations in $S_n$ with order $2$ and no fixed points. We will refer interchangeably to $P_2(n)$ and its image in $S_n$; notice that in the case of $P_2(n)$, the arbitrary choice of order in the definition of $\varphi$ does not actually matter.

Example 1.4.

$$P_2(4)=\{\{\{1,2\},\{3,4\}\},\{\{1,3\},\{2,4\}\},\{\{1,4\},\{2,3\}\}\}$$

Proposition 1.5. We have $|P_2(2k)|=(2k-1)!!$ for $k\ge 1$.

Theorem 1.6 (Wick formula). Let $X_1,\dots ,X_n$ be gaussian with covariance matrix $\mathrm{\Sigma }$. Then for $𝐢:[k]\to [n]$, we have

$$𝔼(X_{𝐢(1)}\cdots X_{𝐢(k)})=\sum _{\pi \in P_2(k)}\prod _{(r,s)\in \pi }𝔼(X_{𝐢(r)}{X}_{𝐢(s)})\text{.}$$

Definition 1.7 (Complex gaussian). A standard complex gaussian variable $Z$ is obtained by letting $X$ and $Y$ be independent standard real gaussians and letting $Z=\frac{1}{\sqrt{2}}(X+\mathit{𝑖𝑌})$. This has mean $0$ and variance $1$:

$$𝔼(Z)=\frac{1}{\sqrt{2}}(𝔼(X)+\mathit{𝑖𝔼}(Y))=0$$

and

$$𝔼(Z\overline{Z})=\frac{1}{2}𝔼((X+\mathit{𝑖𝑌})(X-\mathit{𝑖𝑌}))=\frac{1}{2}(𝔼(X^2)+𝔼(Y^2))=1\text{.}$$

Proposition 1.8. Let $Z$ be a standard complex gaussian variable. Then

$$𝔼(Z^m{\overline{Z}}^n)=\{\begin{array}{cc}m!\hfill & \text{if }m=n\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$$

for $m,n\ge 0$.

Remark 1.9. By multilinearity, the structure of the Wick formula is retained when one replaces some of the real gaussians with complex gaussians and/or their adjoints. We will use this observation freely.

Definition 1.10 (Gaussian unitary ensemble). Let $A={(a_{\mathit{𝑖𝑗}})}_{1\le i,j\le N}$ be a matrix where

• $\{a_{\mathit{𝑖𝑖}}:1\le i\le N\}$ are iid real gaussian with mean $0$ and variance $\frac{1}{N}$,
• $\{a_{\mathit{𝑖𝑗}}:1\le i/mo>j\le N\}are\; iid\; complex\; gaussian\; with\; mean$ 0$,\; variance$ \frac{1}{N}$,\; and$
• $a_{\mathit{𝑖𝑗}}=\overline{a_{\mathit{𝑗𝑖}}}$ for $1\le j/mo>i\le N.$

The point of this definition is that $A$ is self-adjoint with independent gaussian entries, except as required by the self-adjointness. The choice of variance $\frac{1}{N}$ is for normalization and will play an important role when we make $N\to \infty$.

Definition 1.11. Let $(\mathrm{\Omega },F,P)$ be a probability space and for $1\le i,j\le N$, let $a_{\mathit{𝑖𝑗}}:\mathrm{\Omega }\to ℂ$ be a random variable. Assume that $A={(a_{\mathit{𝑖𝑗}})}_{i,j}$ is self-adjoint. This random matrix produces a random probability measure

$${\nu }_A:=\frac{1}{N}\sum _{i=1}^N{\delta }_{{\lambda }_i}$$

on $ℝ$, where ${\lambda }_1,\dots ,{\lambda }_N$ are the eigenvalues of $A$. This is called the empirical spectral distribution (or ESD) of $A$.

The average eigenvalue distribution of $A$, denoted by ${\mu }_A$, is simply the mean of ${\nu }_A$: define ${\mu }_A$ by

$${\int \; <!--\; nolimits\; -->}_{ℝ}f(x)d{\mu }_A(x)=𝔼\left({\int \; <!--\; nolimits\; -->}_{ℝ}f(x)d{\nu }_A(x)\right)$$

for measurable $f$. This gives us a nice way to access the moments:

$${\int \; <!--\; nolimits\; -->}_{ℝ}{x}^{m}d{\mu }_A(x)=𝔼\left({\int \; <!--\; nolimits\; -->}_{ℝ}{x}^{m}d{\nu }_A(x)\right)=𝔼\left(\frac{1}{N}\sum _{i=1}^N{\lambda }_i^m\right)=𝔼{\mathrm{tr}}_N(A^m)\text{.}$$

Theorem 1.12 (Wigner’s semicircle law). Let $A$ be the random matrix from Definition 1.10. Then ${\mu }_A\to \mu$ weakly as $N\to \infty$, where $\mathit{𝑑𝜇}=f\mathit{𝑑𝑥}$ with

$$f(x)=\{\begin{array}{cc}\frac{1}{2\pi }\sqrt{4-x^2}\hfill & \text{if }x\in [-2,2]\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}\text{.}$$

Remark 1.13. The mode of convergence in Theorem 1.12 can be strengthened. Namely, one can show ${\nu }_A\to \mu$ weakly in probability or weakly almost surely. This could be a good starting point for your project.

Notation 1.14. Let ${\gamma }_n=(1,\dots ,n)$. We will use the notation $\#(\cdot )$ for the number of disjoint cycles in a permutation (including singletons/fixed points).

Theorem 1.15 (Genus expansion). We have

$$𝔼({\mathrm{tr}}_N(A^m))=\sum _{\pi \in P_2(m)}{\left(\frac{1}{N}\right)}^{\frac{m}{2}+1-\#({\gamma }_m\pi )}$$

for $m\ge 1$. When $m$ is odd, the formula above should be read as an empty sum, i.e. as $0$.

Remark 1.16. For $\pi \in P_2(2k)$, there are at least two ways to interpret the exponent $k+1-\#({\gamma }_{2k}\pi )$. It is $2g_{\pi }$, where $g_{\pi }$ is defined in either of the following two ways:

1. $g_{\pi }$ is the genus of the surface obtained from a polygon with $2k$ sides by gluing the sides together in pairs according to $\pi$;
2. $g_{\pi }$ is the smallest possible genus for which the following can be done: put the elements of $[2k]$ on a circle clockwise, make that circle the boundary of a surface with genus $g_{\pi }$, and draw $\pi$ on the surface without crossings.

This is where the phrase “genus expansion” comes from.

Exercise 1.17. In this exercise, you will show that the moments of a standard gaussian variable count pair partitions.

1. Let $X$ be a standard gaussian variable. Prove that

   $$𝔼(X^{2k})=(2k-1)!!\text{ and }𝔼(X^{2k-1})=0$$

   for all $k\ge 1$. Use integration by parts to find a recursion.

2. Prove that $|P_2(2k)|=(2k-1)!!$ by putting $P_2(2k)$ in bijection with a set of cardinality $(2k-1)|P_2(2k-2)|$.

Exercise 1.18. In this exercise, you will prove the Wick formula: if $X_1,\dots ,X_n$ are gaussian with mean $0$ and covariance matrix $\mathrm{\Sigma }$, then

$$𝔼(X_{𝐢(1)}\cdots X_{𝐢(k)})=\sum _{\pi \in P_2(k)}\prod _{(r,s)\in \pi }𝔼(X_{𝐢(r)}{X}_{𝐢(s)})$$

for all $𝐢:[k]\to [n]$.

1. Assume $\mathrm{\Sigma }$ is diagonal and prove the claim.
2. Prove the claim in general by diagonalizing $\mathrm{\Sigma }$ and using the multilinearity of the claimed formula.

Exercise 1.19 ([3, Exercise 1.6]). Let $Z$ be a standard complex gaussian variable. Show that the moments are

$$𝔼(Z^m{\overline{Z}}^n)=\{\begin{array}{cc}m!\hfill & \text{if }m=n\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}\text{.}$$

Hint: start by showing that

$$𝔼(Z^m{\overline{Z}}^n)=\frac{1}{\pi }{\int \; <!--\; nolimits\; -->}_{{ℝ}^2}{(t_1+i{t}_2)}^m{(t_1-i{t}_2)}^n{e}^{-(t_1^2+t_2^2)}d{t}_{1}d{t}_1$$

and then switch to polar coordinates to show that

$$𝔼(Z^m{\overline{Z}}^n)=\frac{1}{\pi }{\int \; <!--\; nolimits\; -->}_0^{2\pi }{\int \; <!--\; nolimits\; -->}_0^{\infty }{r}^{m+n+1}{e}^{\mathit{𝑖𝜃}(m-n)}{e}^{-r^2}\mathit{𝑑𝑟}\mathit{𝑑𝜃}\text{.}$$

Use this to prove the claim.

Theorem 1.15 (Genus expansion). We have

$$𝔼({\mathrm{tr}}_N(A^m))=\sum _{\pi \in P_2(m)}{\left(\frac{1}{N}\right)}^{\frac{m}{2}+1-\#({\gamma }_m\pi )}$$

for $m\ge 1$. When $m$ is odd, the formula above should be read as an empty sum, i.e. as $0$.

Definition 2.1. A partition $\pi \in P(n)$ is said to be noncrossing if the following situation never occurs: there are some blocks $V,W\in \pi$ with $V\ne W$, and some $a,c\in V$ and $b,d\in W$ with $a/mo>b/mo>c/mo>d.\; The\; set\; of\; noncrossing\; partitions\; of$ [n]$is\; denoted\; by$ \mathit{𝑁𝐶}(n)$.$

Theorem 2.2 ([1]). We have $\#(\mathit{𝛾𝜋})\le k+1$ for all $\pi \in P_2(2k)$. Moreover, we have equality if and only if $\pi$ is noncrossing.

Notation 2.3. Write $N{C}_2(m)$ for the non-crossing pair partitions of $[m]$. When $m$ is odd, $N{C}_2(m)$ is of course empty.

Proposition 2.4. We have

$$|N{C}_2(2k)|=\frac{1}{k+1}\left(\genfrac{}{}{0.0pt}{}{2k}{k}\right)\text{ and }|N{C}_2(2k-1)|=0$$

for all $k\ge 1$.

Definition 2.5. The $k$-th Catalan number is $\mathrm{Cat}(k):=\frac{1}{k+1}\left(\genfrac{}{}{0.0pt}{}{2k}{k}\right)$.

Corollary 2.6. We have

$$\underset{N\to \infty }{\lim <!--\; FUNCTION\; APPLICATION\; -->}𝔼({\mathrm{tr}}_N(A^{2k}))=\mathrm{Cat}(k)\text{ and }\underset{N\to \infty }{\lim <!--\; FUNCTION\; APPLICATION\; -->}𝔼({\mathrm{tr}}_N(A^{2k-1}))=0$$

for $k\ge 1$.

Theorem 2.2 ([1]). We have $\#(\mathit{𝛾𝜋})\le k+1$ for all $\pi \in P_2(2k)$. Moreover, we have equality if and only if $\pi$ is noncrossing.

Lemma 2.7. Let $\alpha \in S_n$ and let $\tau =(i,j)$ be a transposition. Then

$$\#(\mathit{𝛼𝜏})=\{\begin{array}{cc}\#(\alpha )+1\hfill & \text{if }i\text{ and }j\text{ are in the same cycle of }\alpha \hfill \\ \#(\alpha )-1\hfill & \text{if }i\text{ and }j\text{ are in different cycles of }\alpha \hfill \end{array}\text{.}$$

Remark 2.8. The permutation ${\gamma }_{2k}\pi$ can be thought of in terms of a building process: each pair in $\pi$ is a transposition, which bumps the cycle count up or down by $1$. We start with the one cycle of ${\gamma }_{2k}$, and the maximal situation is that each of the $k$ pairs in $\pi$ increases the number of cycles. This makes $\#({\gamma }_{2k}\pi )\le k+1$.

For example, let $k=3$ and $\pi =(1,4)(2,3)(5,6)$. Then we start at $(1,2,3,4,5,6)$ with $1$ cycle. Next, we multiply by $(1,4)$:

$$(1,2,3,4,5,6)(1,4)=(1,5,6)(2,3,4)$$

which has two cycles. Next,

$$(1,2,3,4,5,6)(1,4)(2,3)=(1,5,6)(2,4)(3)$$

which has three cycles. Finally,

$$(1,2,3,4,5,6)(1,4)(2,3)(5,6)=(1,5)(2,4)(3)(6)$$

which has four cycles. This is the maximal situation: each pair split a cycle in two.

On the other hand, now consider $\pi =(1,5)(2,3)(4,6)$. Then we again start at $(1,2,3,4,5,6)$ with $1$ cycle. Then

$$(1,2,3,4,5,6)(1,5)=(1,6)(2,3,4,5)$$

has two cycles, as before. Next,

$$(1,2,3,4,5,6)(1,5)(2,3)=(1,6)(2,4,5)(3)$$

which is another splitting step (notice we haven’t arrived at the crossing yet) giving us three cycles. The last step is different:

$$(1,2,3,4,5,6)(1,5)(2,3)(4,6)=(1,6,5,2,4)(3)$$

which is back down to two cycles. This is the generic situation: we can have both splits and merges.

Definition 2.9. For $\alpha \in S_n$, let $|\alpha |$ be the length of $\alpha$: the minimal number of transpositions needed to factor $\alpha$. For $\alpha ,\beta \in S_n$, write $d(\alpha ,\beta ):=|{\alpha }^{-1}\beta |$.

Proposition 2.10. Notation as above. Then

1. $|\alpha |=n-\#(\alpha )$ for all $\alpha \in S_n$;
2. $(S_n,d)$ is a metric space.

Proposition 2.11 ([1]). Let $\varphi :P(n)\to S_n$ be the injective map which turns blocks into cycles. Let

$$S_{\mathit{𝑁𝐶}}({\gamma }_n):=\{\alpha \in S_n:d(e,\alpha )+d(\alpha ,{\gamma }_n)=d(e,{\gamma }_n)\}\text{.}$$

Then $S_{\mathit{𝑁𝐶}}({\gamma }_n)$ is the range of ${\varphi |}_{\mathit{𝑁𝐶}(n)}$.

Question 2.12. We just showed that the moments of the average eigenvalue distribution of a GUE converge to the Catalan numbers. How do we know this is a moment sequence, and how do we know this determines the weak limit of the average eigenvalue distribution?

Proposition 2.13. Let $\mathit{𝑑𝜇}=f(x)\mathit{𝑑𝑥}$ where

$$f(x)=\{\begin{array}{cc}\frac{1}{2\pi }\sqrt{4-x^2}\hfill & \text{if }x\in [-2,2]\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}\text{.}$$

Then

$${\int \; <!--\; nolimits\; -->}_{ℝ}{x}^{2k}\mathit{𝑑𝜇}(x)=\frac{1}{k+1}\left(\genfrac{}{}{0.0pt}{}{2k}{k}\right)\text{ and }{\int \; <!--\; nolimits\; -->}_{ℝ}{x}^{2k-1}\mathit{𝑑𝜇}(x)=0$$

for all $k\ge 1$.

Question 2.12${}^{\prime }$. If ${({\mu }_n)}_{n\ge 1}$ is a sequence in $\mathrm{Prob}(ℝ)$ and $\mu \in \mathrm{Prob}(ℝ)$ has

$$\underset{n\to \infty }{\lim <!--\; FUNCTION\; APPLICATION\; -->}{\int \; <!--\; nolimits\; -->}_{ℝ}{x}^{m}d{\mu }_n(x)={\int \; <!--\; nolimits\; -->}_{ℝ}{x}^m\mathit{𝑑𝜇}(x)$$

for all $m\ge 1$, then does ${\mu }_n$ converge to $\mu$ in some meaningful sense at the level of measures?

Theorem 2.14. Let $\mu$ be a probability measure on $ℝ$ with compact support.

1. If $\nu$ is another probability measure on $ℝ$ with

   $${\int \; <!--\; nolimits\; -->}_{ℝ}{x}^m\mathit{𝑑𝜇}(x)={\int \; <!--\; nolimits\; -->}_{ℝ}{x}^m\mathit{𝑑𝜈}(x)$$

   for all $m\ge 1$, then $\mu =\nu$.

2. If ${({\mu }_n)}_{n\ge 1}$ is a sequence of probability measures on $ℝ$ with

   $$\underset{n\to \infty }{\lim <!--\; FUNCTION\; APPLICATION\; -->}{\int \; <!--\; nolimits\; -->}_{ℝ}{x}^{m}d{\mu }_n(x)={\int \; <!--\; nolimits\; -->}_{ℝ}{x}^{,}\mathit{𝑑𝜇}(x)$$

   for all $m\ge 1$, then ${\mu }_n\to \mu$ weakly as $n\to \infty$.

Definition 2.15. A $\ast$-algebra is a unital associative algebra over $ℂ$ with an operation $𝒜\to 𝒜:a\mapsto a^{\ast }$ which is conjugate-linear and has ${(a^{\ast })}^{\ast }=a$ and ${(\mathit{𝑎𝑏})}^{\ast }=b^{\ast }{a}^{\ast }$ for all $a,b\in 𝒜$. An element $a\in 𝒜$ is said to be positive if $a=b^{\ast }b$ for some $b\in 𝒜$.

Definition 2.16. A $\ast$-probability space is a pair $(𝒜,\phi )$ where $𝒜$ is a $\ast$-algebra and $\phi$ is a linear functional on $𝒜$ with $\phi (a^{\ast }a)\ge 0$ for all $a\in 𝒜$, and $\phi (1)=1$.

Remark 2.17. The point of Definition 2.16 is to view the elements of $𝒜$ as “random variables” and the linear functional $\phi$ as the “expectation”. This abstraction becomes useful when one needs to consider noncommutative objects as random variables.

Example 2.18 (Commutative case). Let $(\mathrm{\Omega },F,P)$ be a (classical) probability space, i.e. a measure space with total measure $1$. Let $𝒜:=L^{\infty }(\mathrm{\Omega },F,P)$ be the algebra of essentially bounded functions, and let $\phi$ be the linear functional defined by

$$\phi (f)={\int \; <!--\; nolimits\; -->}_{\mathrm{\Omega }}f(\omega )\mathit{𝑑𝑃}(\omega )$$

for $f\in 𝒜$. This is a $\ast$-probability space, where the $\ast$-operation is complex conjugation – in fact, it has a lot of analytic structure that we will put aside for now.

Example 2.19 (Finite moments). Major objection to Example 2.18: many random variables we care about are not bounded. We can set up a similar example that will actually be more relevant for us: let $𝒜=L^{\infty -}(\mathrm{\Omega },F,P)$ where $L^{\infty -}(\mathrm{\Omega },F,P):={\bigcap <!--\; FUNCTION\; APPLICATION\; -->}_{p\ge 1}{L}^p(\mathrm{\Omega },F,P)$, i.e. the algebra of random variables with all moments finite. (Use Hölder’s inequality to show $𝒜$ is a $\ast$-algebra: once to show $L^p\supseteq L^q$ for $p\le q$, and once to show $\mathit{𝑓𝑔}\in L^1$ for $f,g\in 𝒜$.) The expectation $\phi$ is defined in the same way, by integrating functions against $P$. This is again a $\ast$-probability space.

Example 2.20 (Scalar matrices). Let $𝒜=M_N$ be the algebra of $N\times N$ matrices and let $\phi (A)=\frac{1}{N}\mathrm{Tr}(A)$. This is a $\ast$-probability space which is not commutative.

Example 2.21 (Random matrices). Let $𝒜=M_N(L^{\infty -}(\mathrm{\Omega },F,P))$ be the $\ast$-algebra of matrices with entries that are RVs with finite moments, and let $\phi$ be the expected trace: $\phi (A)=𝔼\mathrm{tr}(A)$. For example, our GUE random matrix lives here.

Example 2.22 (Group algebra). Let $G$ be a group and let $𝒜:=ℂ[G]$. The expectation is defined by

$$\phi \left(\sum _{g\in G}{a}_{g}g\right)=a_e\text{.}$$

This is a $\ast$-probability space.

Exercise 2.23. In this exercise, you will enumerate the noncrossing pairings and show that they are counted by the moments of the semicircle distribution. (1) and (2) are classic textbook combinatorics. (3) is a somewhat involved calculus problem.

1. Find a recursion for $|N{C}_2(2k)|$. Think back to the enumeration of $P_2(2k)$.
2. Show that $\mathrm{Cat}(k):=\frac{1}{k+1}\left(\genfrac{}{}{0.0pt}{}{2k}{k}\right)$ satisfy the same recursion that you found in (1). To do this, first show that with $C(z):={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{k=0}^{\infty }\mathrm{Cat}(k)z^k$, we have $C(z)=\frac{1-\sqrt{1-4z}}{2z}$, and derive the functional equation $C(z)=1+\mathit{𝑧𝐶}{(z)}^2$. Recover the recursion from this functional equation.

3. Let $\mathit{𝑑𝜇}=f(x)\mathit{𝑑𝑥}$ where

   $$f(x)=\{\begin{array}{cc}\frac{1}{2\pi }\sqrt{1-4x}\hfill & \text{if }x\in [-2,2]\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}\text{.}$$

   Show that

   $${\int \; <!--\; nolimits\; -->}_{ℝ}{x}^{2k}\mathit{𝑑𝜇}(x)=\mathrm{Cat}(k)\text{ and }{\int \; <!--\; nolimits\; -->}_{ℝ}{x}^{2k-1}\mathit{𝑑𝜇}(x)$$

   for $k\ge 1$. To do this, make the substitution $x=2\cos <!--\; FUNCTION\; APPLICATION\; -->𝜃$. You can use the following identity without proof:

   $${\int \; <!--\; nolimits\; -->}_0^{\pi }{\cos <!--\; FUNCTION\; APPLICATION\; -->}^{2m}𝜃\mathit{𝑑𝜃}=\frac{(2m-1)!!}{(2m)!!}\pi \text{.}$$

Exercise 2.24. In this exercise, you will fill in the details of why convergence in moments implies weak convergence in the case of the semicircular law. In both parts, let $\mu$ be a probability measure on $ℝ$ with compact support. This is part genuine exercise, part “book report”. Both parts require some knowledge of measure theory.

1. Let $\nu$ be a probability measure on $ℝ$ with

   $${\int \; <!--\; nolimits\; -->}_{ℝ}{x}^m\mathit{𝑑𝜇}(x)={\int \; <!--\; nolimits\; -->}_{ℝ}{x}^m\mathit{𝑑𝜈}(x)$$

   for all $m\ge 1$. Prove that $\mu =\nu$. Note: there is no assumption that $\nu$ has compact support! Be careful and think about how to get around this issue.

2. Let ${({\mu }_n)}_{n\ge 1}$ be a sequence of probability measures on $ℝ$ with

   $$\underset{n\to \infty }{\lim <!--\; FUNCTION\; APPLICATION\; -->}{\int \; <!--\; nolimits\; -->}_{ℝ}{x}^{m}d{\mu }_n(x)={\int \; <!--\; nolimits\; -->}_{ℝ}{x}^m\mathit{𝑑𝜇}(x)$$

   for all $m\ge 1$. Prove that ${\mu }_n\to \mu$ weakly. This is standard textbook material (Billingsley P& Theorems 30.1 and 30.2). What I’m looking for is a concise summary of the argument that addresses its various subtleties: for example, how exactly is (1) being used, how do you establish tightness, etc. You don’t need to reproduce proofs of basic classical theorems, like Markov inequality or Helly selection theorem/Prokhorov’s theorem.

Definition 3.1 (Group-theoretical freeness). Let $G$ be a group and let $\{G_i:i\in I\}$ be a family of subgroups. The subgroups are free if for all $k\ge 1$, for all $i_1,\dots ,i_k\in I$ with $i_j\ne i_{j+1}$, and for all $g_j\in G_{i_j}$ with $g_j\ne e$, we have $g_1\cdots g_k\ne e$.

Definition 3.2 (Freeness of subalgebras). Let $(𝒜,\phi )$ be a $\ast$-probability space, and let $\{{𝒜}_i:i\in I\}$ be a family of unital $\ast$-subalgebras. The family $\{{𝒜}_i:i\in I\}$ is said to be freely independent (or free) if for all $k\ge 1$, for all $i_1,\dots ,i_k\in I$ with $i_j\ne i_{j+1}$, and for all $a_j\in {𝒜}_{i_j}$ with $\phi (a_j)=0$, we have $\phi (a_1\cdots a_k)=0$.

Proposition 3.3. Let $G$ be a group and let $\{G_i:i\in I\}$ be a family of subgroups. Then the subgroups are free in the group-theoretical sense if and only if the subalgebras $ℂ[G_i]$ of $ℂ[G]$ are freely independent with respect to $\phi$.

Definition 3.4 (Freeness of variables). Let $(𝒜,\phi )$ be a $\ast$-probability space and let $\{a_i:i\in I\}$ be a family in $𝒜$. For $i\in I$, let ${𝒜}_i$ be the $\ast$-subalgebra of $𝒜$ generated by $a_i$. The family $\{a_i:i\in I\}$ is said to be freely independent (or free) if the family $\{{𝒜}_i:i\in I\}$ is freely independent.

Example 3.5. Suppose that $𝒜$ and $B$ are freely independent subalgebras of some ambient algebra. Let’s look at some words with mixtures between $𝒜$ and $B$.

Length two: for $a\in 𝒜$ and $b\in B$, freeness says

$$0=\phi ((a-\phi (a))(b-\phi (b)))=\phi (\mathit{𝑎𝑏})-\phi (a)\phi (b)$$

so $\phi (\mathit{𝑎𝑏})=\phi (a)\phi (b)$.

Length three: for $a_1,a_2\in 𝒜$ and $b\in B$, freeness says

$$\phi ((a-\phi (a))(b-\phi (b))(a-\phi (a)))=0\text{.}$$

Expanding and using the length two factorization, this says

$$\begin{array}{llll}\hfill 0& =\phi (a_{1}b{a}_2)-\phi (a_2)\phi (a_{1}b)-\phi (b)\phi (a_1{a}_2)+\phi (a_1)\phi (a_2)\phi (b)& \hfill & \\ \hfill & -\phi (a_1)\phi (b{a}_2)+\phi (a_1)\phi (a_2)\phi (b)+\phi (a_1)\phi (b)\phi (a_2)-\phi (a_1)\phi (a_2)\phi (b)& \hfill & \\ \hfill & =\phi (a_{1}b{a}_2)-\phi (a_2)\phi (a_1)\phi (b)-\phi (b)\phi (a_1{a}_2)+\phi (a_1)\phi (a_2)\phi (b)& \hfill & \\ \hfill & -\phi (a_1)\phi (b)\phi (a_2)+\phi (a_1)\phi (a_2)\phi (b)+\phi (a_1)\phi (b)\phi (a_2)-\phi (a_1)\phi (a_2)\phi (b)& \hfill & \\ \hfill & =\phi (a_{1}b{a}_2)-\phi (a_1{a}_2)\phi (b)& \hfill & \end{array}$$

so $\phi (a_{1}b{a}_2)=\phi (a_1{a}_2)\phi (b)$.

IMPORTANT: this factorization pattern does not continue. The same kind of calculation, with $a_1,a_2\in 𝒜$ and $b_1,b_2\in B$, shows that

$$\phi (a_1{b}_1{a}_2{b}_2)=\phi (a_1{a}_2)\phi (b_1)\phi (b_2)+\phi (a_1)\phi (a_2)\phi (b_1{b}_2)-\phi (a_1)\phi (b_1)\phi (a_2)\phi (b_2)\text{.}$$

The point of all this is that mixed moments only depend on mixed moments from the same subalgebra, via some complicated pattern.

Proposition 3.6. Let $(𝒜,\phi )$ be a $\ast$-probability space and let $\{{𝒜}_i:i\in I\}$ be freely independent $\ast$-subalgebras. Let $B$ be the $\ast$-subalgebra of $𝒜$ generated by $\{{𝒜}_i:i\in I\}$. Then ${\phi |}_B$ is uniquely determined by $\{{\phi |}_{{𝒜}_i}:i\in I\}$.

Theorem 3.7 ([5]). We have

$$\underset{N\to \infty }{\lim <!--\; FUNCTION\; APPLICATION\; -->}\phi \left({\left(\frac{a_1+\cdots +a_N}{\sqrt{N}}\right)}^m\right)=\{\begin{array}{cc}\mathrm{Cat}(k)\hfill & \text{if }m=2k\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$$

for $m\ge 1$.

Notation 3.8. For $𝐢:[m]\to \mathbb{N}$, let $\ker <!--\; FUNCTION\; APPLICATION\; -->(𝐢)$ be the partition of $[m]$ defined by letting $p$ and $q$ be in the same block if and only if $𝐢(p)=𝐢(q)$.

Lemma 3.9. If $𝐢,𝐣:[m]\to \mathbb{N}$ have $\ker <!--\; FUNCTION\; APPLICATION\; -->(𝐢)=\ker <!--\; FUNCTION\; APPLICATION\; -->(𝐣)$, then

$$\phi (a_{𝐢(1)}\cdots a_{𝐢(m)})=\phi (a_{𝐣(1)}\cdots a_{𝐣(m)})\text{.}$$

Notation 3.10. In light of Lemma 3.9, for $\pi \in P(m)$, write $\phi (\pi )$ for the common value of $\phi (a_{𝐢(1)}\cdots a_{𝐢(m)})$ where $𝐢:[m]\to [N]$ has $\ker <!--\; FUNCTION\; APPLICATION\; -->(𝐢)=\pi$. Let $A_{\pi }^N$ be the number of maps $𝐢:[m]\to [N]$ with $\ker <!--\; FUNCTION\; APPLICATION\; -->(𝐢)=\pi$.

Lemma 3.11. If $\pi \in P(m)$ and there is some $V\in \pi$ with $|V|=1$, then $\phi (\pi )=0$.