De Finetti / exchangeability and the symmetric group

Intuition [Beginner]

Imagine you flip a coin 100 times and record heads and tails. If you shuffle the order of the results, the sequence "looks the same" — the joint probability of any particular pattern depends only on the number of heads, not on where they appear. This symmetry under reordering is called exchangeability.

Exchangeability is a weaker condition than independence. Independent coin flips are exchangeable, but exchangeable sequences can have dependencies — they just have to be symmetric dependencies. De Finetti's theorem says that every infinite exchangeable sequence is a mixture of independent sequences: you first pick a coin with a random bias, then flip that coin independently.

Why does this concept exist? Because exchangeability captures the notion of "symmetric uncertainty" in a way that is both weaker and more realistic than independence, and the symmetric group $S_n$ is the exact algebraic structure encoding this symmetry.

Visual [Beginner]

A diagram showing five binary sequences of length 4, all with the same number of 1s but in different positions. An arrow labelled "$S_4$ acts by permuting positions" connects them, indicating they all have the same probability under exchangeability.

Exchangeability means all sequences with the same number of 1s are equally likely, regardless of the positions of the 1s.

Worked example [Beginner]

Consider sequences of three coin flips, each either H (heads) or T (tails). There are $2^3=8$ possible sequences.

Step 1. An exchangeable distribution assigns the same probability to all sequences with the same number of heads. There are four types: 0 heads (TTT), 1 head (HTT, THT, TTH), 2 heads (HHT, HTH, THH), and 3 heads (HHH).

Step 2. An exchangeable distribution is specified by four numbers $p_0,p_1,p_2,p_3$ with $p_0+3p_1+3p_2+p_3=1$, where $p_k$ is the probability of each individual sequence with exactly $k$ heads.

Step 3. A mixture of i.i.d. coin flips works as follows: pick a bias $\theta$ from some distribution, then flip independently with probability $\theta$ of heads. The probability of a sequence with $k$ heads is the total of ${\theta }^k(1-\theta {)}^{3-k}$ across all values of $\theta$, weighted by the distribution of $\theta$.

What this tells us: de Finetti's theorem says every exchangeable distribution on infinite sequences has this mixture-of-i.i.d. form. For finite sequences, the approximation is close: Diaconis and Freedman showed the error is at most $2/n$ in total variation distance for sequences of length $n$.

Check your understanding [Beginner]

Formal definition [Intermediate+]

Let $(\Omega ,\mathcal{F},P)$ be a probability space and let $X_1,X_2,\dots ,X_n$ be random variables taking values in a measurable space $(\mathcal{X},\mathcal{B})$. The sequence is exchangeable if for every permutation $\sigma \in S_n$:

$$(X_1,X_2,\dots ,X_n)\stackrel{d}{=}(X_{\sigma (1)},X_{\sigma (2)},\dots ,X_{\sigma (n)}),$$

where $\stackrel{d}{=}$ denotes equality in distribution. Equivalently, the joint law $\mu$ on ${\mathcal{X}}^n$ is invariant under the action of $S_n$ on ${\mathcal{X}}^n$ by coordinate permutation: $\sigma \cdot (x_1,\dots ,x_n)=(x_{\sigma (1)},\dots ,x_{\sigma (n)})$.

An infinite sequence $(X_i{)}_{i=1}^{\infty }$ is exchangeable if every finite subsequence $(X_1,\dots ,X_n)$ is exchangeable, for all $n$.

Definition (Mixture of i.i.d.). A probability measure $\mu$ on ${\mathcal{X}}^n$ is a mixture of i.i.d. measures if there exists a probability measure $\nu$ on the space $\mathcal{P}(\mathcal{X})$ of probability measures on $\mathcal{X}$ such that:

$$\mu (A_1\times \cdots \times A_n)={\int }_{\mathcal{P}(\mathcal{X})}\prod _{i=1}^n\rho (A_i)d\nu (\rho ).$$

Every mixture of i.i.d. measures is exchangeable (because the product measure ${\rho }^n$ is exchangeable and mixtures preserve exchangeability).

Counterexamples to common slips

• Exchangeability does not imply independence. The Polya urn model produces exchangeable but dependent sequences: drawing balls without replacement from an urn gives exchangeable draws that are negatively correlated.
• Finite exchangeability is strictly weaker than infinite extendibility. A sequence of length $n$ can be exchangeable without being extendable to an exchangeable sequence of length $n+1$. The Diaconis-Freedman theorem quantifies the gap.
• De Finetti's theorem requires infinite sequences. The exact representation as a mixture of i.i.d. measures holds only for infinite exchangeable sequences. For finite sequences, the representation is approximate.

Key theorem with proof [Intermediate+]

Theorem (De Finetti's theorem — de Finetti 1937, Hewitt-Savage 1955). An infinite sequence $(X_i{)}_{i=1}^{\infty }$ of $\{0,1\}$-valued random variables is exchangeable if and only if there exists a probability measure $\nu$ on $[0,1]$ such that for all $n$ and all $(x_1,\dots ,x_n)\in \{0,1{\}}^n$:

$$P(X_1=x_1,\dots ,X_n=x_n)={\int }_0^1\prod _{i=1}^n{\theta }^{x_i}(1-\theta {)}^{1-x_i}d\nu (\theta ).$$

Proof. We prove the binary case using the method of moments and the law of large numbers.

Step 1 (Exchangeability implies the frequency is sufficient). Define $S_n=X_1+\cdots +X_n$. By exchangeability, the probability $P(X_1=x_1,\dots ,X_n=x_n)$ depends only on $s_n=x_1+\cdots +x_n$. So the exchangeable law is determined by the numbers $P(S_n=k)$ for $k=0,1,\dots ,n$.

Step 2 (Existence of the mixing measure). Define ${\bar{X}}_n=S_n/n$. By exchangeability and the de Finetti strong law (which we prove next), the empirical frequency ${\bar{X}}_n$ converges almost surely to some random variable $\Theta$ taking values in $[0,1]$. Define $\nu$ as the distribution of $\Theta$.

Step 3 (Conditioning on the limit gives independence). Let $\mathcal{T}={\bigcap }_{n=1}^{\infty }\sigma (X_{n+1},X_{n+2},\dots )$ be the tail $\sigma$-algebra. By the Kolmogorov zero-one law applied conditionally, $\Theta$ is $\mathcal{T}$-measurable, and conditional on $\Theta =\theta$, the random variables $X_1,X_2,\dots$ are i.i.d. Bernoulli$(\theta )$.

Step 4 (Verify the mixture formula). For any $(x_1,\dots ,x_n)$:

$$P(X_1=x_1,\dots ,X_n=x_n)=\mathbb{E}[P(X_1=x_1,\dots ,X_n=x_n\mid \Theta )]=\mathbb{E}\left[\prod _{i=1}^n{\Theta }^{x_i}(1-\Theta {)}^{1-x_i}\right]={\int }_0^1\prod _{i=1}^n{\theta }^{x_i}(1-\theta {)}^{1-x_i}d\nu (\theta ).\square$$

Bridge. De Finetti's theorem builds toward the spectral analysis of permutation data in 07.05.11 by identifying exchangeable sequences as the $S_n$-invariant measures on the product space, and appears again in 07.05.13 where the Gelfand pair structure extends the exchangeability analysis to partial observations. The foundational reason the theorem works is that the tail $\sigma$-algebra provides the mixing measure, which is exactly the quotient of the product space by the infinite symmetric group action. The central insight is that exchangeability is invariance under $S_n$, and this is exactly the condition that makes the Fourier analysis on the symmetric group relevant to probability theory; the bridge is between the group-theoretic notion of $S_n$-invariance and the probabilistic notion of conditional independence, putting these together via the representation-theoretic machinery of 07.05.05.

Exercises [Intermediate+]

Advanced results [Master]

Theorem 1 (Hewitt-Savage 1955: general de Finetti theorem). Let $\mathcal{X}$ be a standard Borel space. An infinite sequence $(X_i{)}_{i\ge 1}$ of $\mathcal{X}$-valued random variables is exchangeable if and only if there exists a random probability measure $\rho$ on $\mathcal{X}$ (with distribution $\nu$ on $\mathcal{P}(\mathcal{X})$) such that conditional on $\rho$, the sequence is i.i.d. with law $\rho$:

$$P(X_1\in A_1,\dots ,X_n\in A_n)={\int }_{\mathcal{P}(\mathcal{X})}\prod _{i=1}^n\rho (A_i)d\nu (\rho ).$$

The mixing measure $\nu$ is unique. This extends de Finetti's binary theorem to arbitrary measurable spaces.

Theorem 2 (Diaconis-Freedman 1980: finite exchangeability approximation). For any exchangeable distribution $\mu$ on ${\mathcal{X}}^n$ (where $\mathcal{X}$ is finite), there exists a mixture of i.i.d. measures ${\mu }^{\ast }$ on ${\mathcal{X}}^n$ such that $\Vert \mu -{\mu }^{\ast }{\Vert }_{\mathrm{TV}}\le 2|\mathcal{X}{|}^2/(n+1)$. For binary sequences ($|\mathcal{X}|=2$), the bound is $2/(n+1)$.

This was proved by Diaconis and Freedman 1980 in Ann. Probab. 8 using a direct combinatorial comparison between exchangeable and mixture-of-i.i.d. distributions.

Theorem 3 (Exchangeability and the Choquet theorem). The set of exchangeable measures on ${\mathcal{X}}^n$ is a convex set. By the Choquet theorem, every exchangeable measure is an integral over the extreme points. The extreme points are the ergodic measures (measures that cannot be decomposed as a non-identity convex combination of other exchangeable measures). For infinite sequences, de Finetti's theorem identifies the extreme points as the product measures ${\rho }^{\otimes \infty }$.

Theorem 4 (Aldous 1985: exchangeability and representation theory). The set of exchangeable probability measures on ${\mathcal{X}}^n$ can be identified with the set of $S_n$-invariant measures on ${\mathcal{X}}^n$, which in turn corresponds to the positive cone in the fixed-point subspace of $S_n$ acting on the space of measures. The spectral decomposition of this fixed-point subspace via the irreducible representations of $S_n$ gives the structure of the exchangeable measures.

This was developed by Aldous 1985 in Exchangeability and Related Topics and connects the probabilistic notion to the representation-theoretic framework.

Theorem 5 (Exchangeability and sufficiency). For an exchangeable sequence $(X_1,\dots ,X_n)$, the order statistic $(X_{(1)},X_{(2)},\dots ,X_{(n)})$ (the sorted values) is a sufficient statistic. This is a consequence of exchangeability: the likelihood depends on the data only through the empirical distribution.

Theorem 6 (Exchangeable pairs and Stein's method). An exchangeable pair $(X,X^{\prime })$ is a pair of random variables such that $(X,X^{\prime })\stackrel{d}{=}(X^{\prime },X)$. Stein's method for proving central limit theorems uses exchangeable pairs: if $(X,X^{\prime })$ is exchangeable and $\mathbb{E}[X^{\prime }\mid X]=(1-\lambda )X$, then $X$ is approximately Gaussian with variance controlled by $\lambda$ and $\mathbb{E}[(X^{\prime }-X{)}^2\mid X]$.

This was developed by Stein 1972 and systematised by Chatterjee 2008 in Stein's Method for Concentration Inequalities.

Synthesis. De Finetti's theorem provides the foundational reason that the symmetric group enters probability theory through exchangeability. The central insight is that $S_n$-invariance of the joint law on ${\mathcal{X}}^n$ is the probabilistic content of exchangeability, and putting these together with the Choquet theorem, the extreme $S_n$-invariant measures are the product measures. This is exactly the content that builds toward the spectral analysis in 07.05.11 where the $S_n$-Fourier transform decomposes exchangeable functions, and appears again in the partial ranking framework of 07.05.13 where $S_n\times S_{n-k}$-invariance replaces pure exchangeability. The bridge is between the group-theoretic notion of invariance and the probabilistic notion of conditional independence; the pattern generalises from binary sequences to arbitrary state spaces via the Hewitt-Savage theorem, and identifies the representation theory of $S_n$ as the natural language for symmetric dependence structures. The Diaconis-Freedman bound quantifies how closely finite exchangeability approximates the mixture-of-i.i.d. ideal, putting a precise number on the gap between the finite and infinite theories.

Full proof set [Master]

Proposition 1 (Exchangeable measures are $S_n$-invariant). A probability measure $\mu$ on ${\mathcal{X}}^n$ is exchangeable if and only if it is invariant under the action of $S_n$ on ${\mathcal{X}}^n$ by coordinate permutation.

Proof. By definition, $\mu$ is exchangeable iff for every permutation $\sigma \in S_n$ and every measurable rectangle $A=A_1\times \cdots \times A_n$:

$$\mu (A_1\times \cdots \times A_n)=\mu (A_{\sigma (1)}\times \cdots \times A_{\sigma (n)}).$$

This is precisely the statement that $\mu (\sigma \cdot A)=\mu (A)$ for all $\sigma$ and $A$, which is $S_n$-invariance of the measure. $\square$

Proposition 2 (Mixtures of i.i.d. are exchangeable). If $\nu$ is any probability measure on $\mathcal{P}(\mathcal{X})$ and $\mu =\int {\rho }^{\otimes n}d\nu (\rho )$, then $\mu$ is exchangeable.

Proof. For any $\sigma \in S_n$ and measurable $A=A_1\times \cdots \times A_n$:

$$\mu (\sigma \cdot A)=\int {\rho }^{\otimes n}(A_{\sigma (1)}\times \cdots \times A_{\sigma (n)})d\nu (\rho )=\int \prod _{i=1}^n\rho (A_{\sigma (i)})d\nu (\rho )=\int \prod _{i=1}^n\rho (A_i)d\nu (\rho )=\mu (A).$$

The third equality uses that the product is commutative, so reordering the factors does not change the value. $\square$

Connections [Master]

• Spectral analysis of permutation data 07.05.11. Exchangeable measures on ${\mathcal{X}}^n$ are the $S_n$-invariant measures, and the spectral decomposition of $L^2({\mathcal{X}}^n)$ with respect to the $S_n$-action provides the Fourier-analytic framework for studying them. The first-order spectral component in 07.05.11 corresponds to the marginal distribution (the "mean" of the mixing measure), and higher components correspond to higher moments of the mixing measure.

• Random walk upper bound lemma 07.05.05. The Upper Bound Lemma bounds the distance from an $S_n$-invariant measure to uniformity by character sums, which is a spectral bound on exchangeable measures. The mixing time of random walks on finite groups produces exchangeable distributions at each time step, and the spectral analysis of exchangeability connects to the convergence analysis in 07.05.05.

• Partially ranked data 07.05.13. The Gelfand pair $(S_n,S_{n-k})$ extends the exchangeability framework: partial ranking data is exchangeable under a larger symmetry group (the subgroup permuting unranked items among themselves). The spectral decomposition of partial rankings in 07.05.13 is the Gelfand pair analogue of the de Finetti decomposition for full rankings.

• Character orthogonality 07.01.04. The character orthogonality relations of 07.01.04 are the analytical tool that makes the spectral decomposition of exchangeable measures work. The characters span the space of $S_n$-invariant functions on ${\mathcal{X}}^n$, and the orthogonality relations ensure the decomposition is unique and explicit.

Historical & philosophical context [Master]

De Finetti introduced the concept of exchangeability and proved the representation theorem for binary sequences in his 1937 paper La prévision: ses lois logiques, ses sources subjectives ^{[deFinetti1937]} published in Ann. Inst. H. Poincaré 7. His motivation was to provide a subjective Bayesian foundation for probability: instead of assuming a "true" parameter $\theta$, one assumes exchangeable observations and derives the existence of $\theta$ as a mathematical consequence.

Hewitt and Savage 1955 generalised de Finetti's theorem to arbitrary standard Borel spaces in Symmetric Measures on Cartesian Products ^{[HewittSavage1955]}, establishing the result in its modern form using the Choquet theorem on extreme points of convex sets.

Diaconis and Freedman 1980 proved the finite exchangeability approximation in Finite Exchangeable Sequences ^{[DiaconisFreedman1980]} published in Ann. Probab. 8, showing that the total variation distance between an exchangeable distribution on $n$ variables and the closest mixture of i.i.d. is at most $2|\mathcal{X}{|}^2/(n+1)$. This result quantifies the practical relevance of de Finetti's theorem for finite data.

Bibliography [Master]

@article{deFinetti1937,
  author = {de Finetti, Bruno},
  title = {La pr\'{e}vision: ses lois logiques, ses sources subjectives},
  journal = {Ann. Inst. H. Poincar\'{e}},
  volume = {7},
  year = {1937},
  pages = {1--68},
}

@article{HewittSavage1955,
  author = {Hewitt, Edwin and Savage, Leonard J.},
  title = {Symmetric Measures on Cartesian Products},
  journal = {Trans. Amer. Math. Soc.},
  volume = {80},
  year = {1955},
  pages = {470--501},
}

@article{DiaconisFreedman1980,
  author = {Diaconis, Persi and Freedman, David},
  title = {Finite Exchangeable Sequences},
  journal = {Ann. Probab.},
  volume = {8},
  year = {1980},
  pages = {739--759},
}

@book{Aldous1985,
  author = {Aldous, David J.},
  title = {Exchangeability and Related Topics},
  publisher = {Springer},
  year = {1985},
  series = {Lecture Notes in Mathematics},
  volume = {1117},
}