Exchangeability and de Finetti

Independence is a strong assumption: it says the joint law is a product. Exchangeability asks only for symmetry — that the joint law be unchanged by relabelling the observations. It is strictly weaker, and it is the natural hypothesis whenever a sequence is generated by "the same mechanism" without that mechanism being known.

De Finetti's theorem says the weakening is exactly one degree: every exchangeable sequence is a mixture of i.i.d. sequences. Structurally it is a decomposition theorem for symmetric measures on product spaces, in the same family as the ergodic decomposition of laws-of-large-numbers.md §4.

References: Kallenberg, Probabilistic Symmetries and Invariance Principles; Aldous, Exchangeability and Related Topics; Kingman, "Uses of exchangeability" (1978).

1. Definition

Definition. A finite sequence $X_1,\dots ,X_n$ is exchangeable if

$$(X_{\pi (1)},\dots ,X_{\pi (n)})\stackrel{d}{=}(X_1,\dots ,X_n)\text{for every permutation }\pi \in S_n.$$

An infinite sequence is exchangeable if every finite initial segment is.

I.i.d. $\Rightarrow$ exchangeable, since a product measure is symmetric when the factors coincide. The converse fails:

Pólya's urn. Start with one red and one blue ball; at each step draw one uniformly and return it together with an extra ball of the same colour. Let $X_k=>1\{k\text{-th draw is red}\}$. The probability of any particular sequence with $j$ reds among $n$ draws is $$\frac{j!(n-j)!}{(n+1)!},$$ which depends only on $j$ — so the sequence is exchangeable. It is emphatically not independent: $P(X_2=1\mid X_1=1)=2/3\ne 1/2$. Successive draws reinforce one another, yet order does not matter.

Exchangeability is thus symmetry without independence, and it is preserved under mixing: if $X$ is i.i.d. conditionally on some parameter $\Theta$, and $\Theta$ is random, the unconditional sequence is exchangeable (the conditional product laws are symmetric, and averaging preserves symmetry). De Finetti's theorem is the converse.

Finite exchangeability is different. Sample two balls without replacement from an urn with one of each colour: $(X_1,X_2)$ is exchangeable but $P(X_1=X_2)=0$, which no mixture of i.i.d. pairs can produce (a mixture always has $P(X_1=X_2)\ge 1/2$). The theorem below genuinely requires an infinite sequence; for finite $n$ there is only an approximation, with error $O(1/n)$ (Diaconis–Freedman).

2. De Finetti's Theorem

Theorem (de Finetti, 1931; Hewitt–Savage, 1955). Let $(X_k{)}_{k\ge 1}$ be an infinite exchangeable sequence with values in a standard Borel space $E$. Then there is a random probability measure $\Theta$ on $E$ — measurable with respect to the exchangeable $\sigma$-algebra $\mathcal{E}$ — such that, conditionally on $\Theta$, the $X_k$ are i.i.d. with law $\Theta$. Equivalently, there is a unique probability measure $\pi$ on the space $\mathcal{P}(E)$ of laws with

$$P(X_1\in B_1,\dots ,X_n\in B_n)={\int }_{\mathcal{P}(E)}\prod _{i=1}^n\theta (B_i)\pi (d\theta ).$$

In the binary case $E=\{0,1\}$ this is de Finetti's original statement: an exchangeable $\{0,1\}$-sequence is a mixture of Bernoulli$(\theta )$ sequences,

$$P(X_1=\cdots =X_n=1)={\int }_0^1{\theta }^n\pi (d\theta ),$$

so the sequence of probabilities is a Hausdorff moment sequence and $\pi$ is recovered by the Hausdorff moment problem. For Pólya's urn, $\pi$ is uniform on $[0,1]$.

Proof sketch. By the strong law applied conditionally, the empirical measures ${\Theta }_n=\frac{1}{n}{\sum }_{k\le n}{\delta }_{X_k}$ converge a.s. to a random measure $\Theta$, which is $\mathcal{E}$-measurable. A reverse-martingale argument (martingales.md §3) using the downward theorem shows $E[f(X_1)\cdots f(X_n)\mid \mathcal{E}]={\prod }_i\int fd\Theta$; conditional independence follows, and uniqueness of $\pi$ from the fact that $\Theta$ is a function of the sequence. $\square$

$\Theta$ is not a hidden parameter smuggled in. It is constructed from the sequence as the limit of empirical measures — the theorem produces it, and by the strong law it is a.s. determined by the observations. The mixing measure $\pi$ is the law of $\Theta$, i.e. the marginal law of that limit.

3. Relation to the Zero–One Laws

Hewitt–Savage §3 says the exchangeable $\sigma$-algebra is trivial for i.i.d. sequences. De Finetti says that for a general exchangeable sequence, $\mathcal{E}$ carries exactly the mixing parameter — and conditioning on it restores the i.i.d. case. The two statements are the extreme and general forms of one picture:

The same structure appeared in laws-of-large-numbers.md §4: for a non-ergodic measure-preserving system, Birkhoff's limit is $E[X\mid \mathcal{I}]$ rather than a constant. Ergodic decomposition, de Finetti representation, and the extreme-point (Choquet) decomposition of the convex set of symmetric measures are three views of one theorem: the extreme points of the convex set of exchangeable laws are exactly the i.i.d. laws, and every point is a unique barycentre of extreme points.

4. Generalizations

• Partial exchangeability (Diaconis–Freedman): invariance under permutations within groups gives mixtures of independent, group-wise identical sequences; Markov-exchangeability characterizes mixtures of Markov chains.
• Exchangeable arrays (Aldous–Hoover): a two-dimensional array invariant under separate row and column permutations is representable as $X_{ij}=f(\alpha ,{\xi }_i,{\eta }_j,{\zeta }_{ij})$ with i.i.d. uniforms. This is the structure theorem behind graph limits (graphons).
• Continuous-time symmetries (Kallenberg): rotatability, contractability, and stationarity admit analogous representations, of which Brownian motion's invariance properties are an instance.

5. What the Theorem Does and Does Not Establish

• What it proves. A structural fact about symmetric measures on product spaces: the exchangeable laws form a simplex whose extreme points are the i.i.d. laws. Everything in §2 is a statement about measures.
• What it does not prove. It does not show that objective chances are dispensable, nor that they are real. The theorem is neutral: it says that whenever a symmetric law is given, a parameter with an i.i.d.-conditional structure can be constructed — as a limit of empirical measures. Whether the constructed $\Theta$ should be identified with a chance, a credence about a chance, or nothing at all is a philosophical question this folder does not take up (README §Scope).
• Its hypotheses are restrictive. Infinite exchangeability is essential (§1), and the standard Borel assumption is the same one that regular conditional distributions §5 needs, for the same reason: the proof conditions on $\mathcal{E}$.

6. Where This Is Used

• Zero–one laws §3 — the i.i.d. extreme case.
• Laws of large numbers §4 — the ergodic-decomposition analogue.
• Martingales §3 — the reverse-martingale proof.
• The Kolmogorov extension theorem — exchangeable sequences as a consistent, permutation-invariant fdd specification.