Exchangeability — Mathematics Knowledge System

Overview

A sequence of random variables X_1, X_2, ... is exchangeable if the joint distribution is invariant under any finite permutation of indices. Exchangeability is strictly weaker than independence (every i.i.d. sequence is exchangeable, but not conversely) and strictly stronger than stationarity. De Finetti's theorem characterizes exchangeable sequences as conditionally i.i.d. given a latent parameter -- a cornerstone of Bayesian statistics justifying the use of prior distributions.

Intuition

Exchangeable variables are 'symmetric': the order does not matter for the joint distribution. Drawing balls without replacement from an urn is exchangeable (but not independent): P(X_1 = red, X_2 = blue) = P(X_1 = blue, X_2 = red). The key insight from de Finetti: if you cannot tell the order, there must be hidden information (a latent theta) conditioning on which the variables ARE independent. Exchangeability is the Bayesian version of 'data are i.i.d. up to unknown parameters.'

Formal Definition

Definition

A sequence X_1, X_2, ... of random variables is (infinitely) exchangeable if for every n and every permutation sigma of {1,...,n}, the joint distributions of (X_1,...,X_n) and (X_{sigma(1)},...,X_{sigma(n)}) are equal. A finite sequence is finitely exchangeable if this holds for all permutations.

(X_1, \ldots, X_n) \overset{d}{=} (X_{\sigma(1)}, \ldots, X_{\sigma(n)}) \text{ for all permutations } \sigma \text{ of } \{1,\ldots,n\}

Exchangeability (finite)

\text{i.i.d.} \implies \text{exchangeable} \implies \text{stationary (pairwise)}

Hierarchy of symmetry

P(X_1 = x_1, \ldots, X_n = x_n) = \int \prod_{i=1}^n p(x_i \mid \theta)\,\mu(d\theta)

De Finetti representation (discrete)

Notation

Notation	Meaning
$\sigma$	Permutation of indices {1,...,n}
$\mu$	De Finetti mixing measure on the space of latent parameters

Theorems

Theorem 1: Theorem 1 (Finitely Exchangeable but not Infinitely)

\text{Sampling without replacement from a finite urn produces a finitely exchangeable sequence (all orderings equally likely) that is NOT infinitely exchangeable. Infinite exchangeability requires the de Finetti representation.}

Theorem 2: Theorem 2 (Hewitt-Savage 0-1 Law)

\text{For an infinitely exchangeable sequence, every event that is invariant under all finite permutations (a 'symmetric' event) has probability 0 or 1. Such events are in the exchangeable sigma-algebra.}

Worked Examples

1
Count equally likely orderings. Total ways to arrange 5 balls: 5! = 120. P(X_1=R, X_2=B): choose 1 of 3 reds first, then 1 of 2 blues: 3*2=6 ways for first two draws, from 5*4=20 possible ordered pairs.
$P(X_1=R, X_2=B) = \frac{3}{5} \cdot \frac{2}{4} = \frac{6}{20} = \frac{3}{10}$
2
P(X_1=B, X_2=R): 2/5 * 3/4 = 6/20 = 3/10. Same probability!
$P(X_1=B, X_2=R) = \frac{2}{5} \cdot \frac{3}{4} = \frac{6}{20} = \frac{3}{10}$
3
P(X_1=R, X_2=B) = P(X_1=B, X_2=R) = 3/10. The marginal pairs are exchangeable.
$(X_1, X_2) \text{ is exchangeable: } P(X_1=r,X_2=b) = P(X_1=b,X_2=r) \text{ for all } r,b$

✓ Answer

Sampling without replacement is exchangeable: P(X_1=R, X_2=B) = P(X_1=B, X_2=R) = 3/10.

Practice Problems

Mediumfree response

Are the order statistics X_(1) <= X_(2) <= ... <= X_(n) of i.i.d. random variables exchangeable? Why or why not?

Mediumfree response

A coin is flipped repeatedly, but the bias theta is drawn once from Uniform[0,1] and fixed for all flips. Are the resulting flips exchangeable? Are they i.i.d.?

Common Mistakes

Common Mistake

Thinking exchangeable sequences are always independent

Exchangeable sequences can be highly correlated. The latent variable theta introduces positive correlation: knowing X_1 = 1 raises P(X_2 = 1) because it gives information about theta.

Common Mistake

Confusing finite and infinite exchangeability

Finite exchangeability (invariance under permutations of n indices) does NOT imply infinite exchangeability. Only infinite exchangeability gives de Finetti's representation.

Quiz

Summary

X_1, X_2, ... is exchangeable if the joint distribution is invariant under finite permutations.
Hierarchy: i.i.d. => exchangeable => stationary. Neither implication reverses.
Sampling without replacement is finitely but not infinitely exchangeable.
De Finetti's theorem: infinite exchangeability iff X_i are conditionally i.i.d. given a latent theta.
Bayesian interpretation: the prior on theta encodes the de Finetti mixing measure.

References

BookAldous, D. -- Exchangeability and Related Topics (Lecture Notes in Mathematics)
BookDurrett, R. -- Probability: Theory and Examples, Chapter 6
WebsiteWikipedia -- Exchangeability