De Finetti's theorem

Statement of the theorem

A random variable X has a Bernoulli distribution if ${\displaystyle Pr(X=1)=p}$ and ${\displaystyle Pr(X=0)=1-p}$ for some ${\displaystyle p\in (0,1)}$.

De Finetti's theorem states that the probability distribution of any infinite exchangeable sequence of Bernoulli random variables is a "mixture" of the probability distributions of independent and identically distributed sequences of Bernoulli random variables. "Mixture", in this sense, means a weighted average, but this need not mean a finite or countably infinite (i.e., discrete) weighted average: it can be an integral over a measure rather than a sum.

More precisely, suppose ${\displaystyle X_1,X_2,X_3,\dots }$ is an infinite exchangeable sequence of Bernoulli-distributed random variables. Then there is some probability measure ${\displaystyle m}$ on the interval ${\displaystyle [0,1]}$ and some random variable ${\displaystyle Y}$ such that

• The probability measure of ${\displaystyle Y}$ is ${\displaystyle m}$, and
• The conditional probability distribution of the whole sequence ${\displaystyle X_1,X_2,X_3,\dots }$ given the value of ${\displaystyle Y}$ is described by saying that
  • ${\displaystyle X_1,X_2,X_3,\dots }$ are conditionally independent given ${\displaystyle Y}$, and
  • For any ${\displaystyle i\in \{1,2,3,\dots \}}$, the conditional probability that ${\displaystyle X_i=1}$, given the value of ${\displaystyle Y}$, is ${\displaystyle Y}$.

Another way of stating the theorem

Suppose ${\displaystyle X_1,X_2,X_3,\dots }$ is an infinite exchangeable sequence of Bernoulli random variables. Then ${\displaystyle X_1,X_2,X_3,\dots }$ are conditionally independent and identically distributed given the exchangeable sigma-algebra (i.e., the sigma-algebra consisting of events that are measurable with respect to ${\displaystyle X_1,X_2,\dots }$ and invariant under finite permutations of the indices).

A plain-language consequence of the theorem

According to David Spiegelhalter (ref 1) the theorem provides a pragmatic approach to de Finetti's statement that "Probability does not exist". If our view of the probability of a sequence of events is subjective but remains unaffected by the order in which we make our observations, then the sequence can be regarded as exchangeable. De Finetti's theorem then implies that believing the sequence to be exchangeable is mathematically equivalent to acting as if the events are independent and have an objective underlying probability of occurring, with our uncertainty about what that probability is being expressed by a subjective probability distribution function. According to Spiegelhalter: ″This is remarkable: it shows that, starting from a specific, but purely subjective, expression of convictions, we should act as if events were driven by objective chances."

Example

As a concrete example, we construct a sequence

${\displaystyle X_1,X_2,X_3,\dots }$

of random variables, by "mixing" two i.i.d. sequences as follows.

We assume p = 2/3 with probability 1/2 and p = 9/10 with probability 1/2. Given the event p = 2/3, the conditional distribution of the sequence is that the X_i are independent and identically distributed and X₁ = 1 with probability 2/3 and X₁ = 0 with probability 1 − 2/3. Given the event p = 9/10, the conditional distribution of the sequence is that the X_i are independent and identically distributed and X₁ = 1 with probability 9/10 and X₁ = 0 with probability 1 − 9/10.

This can be interpreted as follows: Make two biased coins, one showing "heads" with 2/3 probability and one showing "heads" with 9/10 probability. Flip a fair coin once to decide which biased coin to use for all flips that are recorded. Here "heads" at flip i means X_i=1.

The independence asserted here is conditional independence, i.e. the Bernoulli random variables in the sequence are conditionally independent given the event that p = 2/3, and are conditionally independent given the event that p = 9/10. But they are not unconditionally independent; they are positively correlated.

In view of the strong law of large numbers, we can say that

${\displaystyle \underset{n\to \mathrm{\infty }}{lim}\frac{X_1+\cdots +X_n}{n}=\{\begin{array}{ll}2/3& \text{with probability }1/2,\\ 9/10& \text{with probability }1/2.\end{array}}$

Rather than concentrating probability 1/2 at each of two points between 0 and 1, the "mixing distribution" can be any probability distribution supported on the interval from 0 to 1; which one it is depends on the joint distribution of the infinite sequence of Bernoulli random variables.

The definition of exchangeability, and the statement of the theorem, also makes sense for finite length sequences

${\displaystyle X_1,\dots ,X_n,}$

but the theorem is not generally true in that case. It is true if the sequence can be extended to an exchangeable sequence that is infinitely long. The simplest example of an exchangeable sequence of Bernoulli random variables that cannot be so extended is the one in which X₁ = 1 − X₂ and X₁ is either 0 or 1, each with probability 1/2. This sequence is exchangeable, but cannot be extended to an exchangeable sequence of length 3, let alone an infinitely long one.

As a categorical limit

De Finetti's theorem can be expressed as a categorical limit in the category of Markov kernels.

Let ${\displaystyle (X,\mathcal{A})}$ be a standard Borel space, and consider the space of sequences on ${\displaystyle X}$, the countable product ${\displaystyle X^{\mathbb{N}}}$ (equipped with the product sigma-algebra).

Given a finite permutation ${\displaystyle \sigma }$, denote again by ${\displaystyle \sigma }$ the permutation action on ${\displaystyle X^{\mathbb{N}}}$, as well as the Markov kernel ${\displaystyle X^{\mathbb{N}}\to X^{\mathbb{N}}}$ induced by it. In terms of category theory, we have a diagram with a single object, ${\displaystyle X^{\mathbb{N}}}$, and a countable number of arrows, one for each permutation.

Recall now that a probability measure ${\displaystyle p}$ is equivalently a Markov kernel from the one-point measurable space. A probability measure ${\displaystyle p}$ on ${\displaystyle X^{\mathbb{N}}}$ is exchangeable if and only if, as Markov kernels, ${\displaystyle \sigma \circ p=p}$ for every permutation ${\displaystyle \sigma }$. More generally, given any standard Borel space ${\displaystyle Y}$, one can call a Markov kernel ${\displaystyle k:Y\to X}$ exchangeable if ${\displaystyle \sigma \circ k=k}$ for every ${\displaystyle \sigma }$, i.e. if the following diagram commutes,

giving a cone.

De Finetti's theorem can be now stated as the fact that the space ${\displaystyle PX}$ of probability measures over ${\displaystyle X}$ (Giry monad) forms a universal (or limit) cone. More in detail, consider the Markov kernel ${\displaystyle {\mathrm{i}\mathrm{i}\mathrm{d}}_{\mathbb{N}}:PX\to X^{\mathbb{N}}}$ constructed as follows, using the Kolmogorov extension theorem:

${\displaystyle {\mathrm{i}\mathrm{i}\mathrm{d}}_{\mathbb{N}}(A_1\times \cdots \times A_n\times X\times \dots |p)=p(A_1)\cdots p(A_n)}$

for all measurable subsets ${\displaystyle A_1,\dots ,A_n}$ of ${\displaystyle X}$. Note that we can interpret this kernel as taking a probability measure ${\displaystyle p\in PX}$ as input and returning an iid sequence on ${\displaystyle X^{\mathbb{N}}}$ distributed according to ${\displaystyle p}$. Since iid sequences are exchangeable, ${\displaystyle {\mathrm{i}\mathrm{i}\mathrm{d}}_{\mathbb{N}}:PX\to X^{\mathbb{N}}}$ is an exchangeable kernel in the sense defined above. The kernel ${\displaystyle {\mathrm{i}\mathrm{i}\mathrm{d}}_{\mathbb{N}}:PX\to X^{\mathbb{N}}}$ doesn't just form a cone, but a limit cone: given any exchangeable kernel ${\displaystyle k:Y\to X}$, there exists a unique kernel ${\displaystyle \tilde{k}:Y\to PX}$ such that ${\displaystyle k={\mathrm{i}\mathrm{i}\mathrm{d}}_{\mathbb{N}}\circ \tilde{k}}$, i.e. making the following diagram commute:

In particular, for any exchangeable probability measure ${\displaystyle p}$ on ${\displaystyle X^{\mathbb{N}}}$, there exists a unique probability measure ${\displaystyle \tilde{p}}$ on ${\displaystyle PX}$ (i.e. a probability measure over probability measures) such that ${\displaystyle p={\mathrm{i}\mathrm{i}\mathrm{d}}_{\mathbb{N}}\circ \tilde{p}}$, i.e. such that for all measurable subsets ${\displaystyle A_1,\dots ,A_n}$ of ${\displaystyle X}$,

${\displaystyle p(A_1\times \cdots \times A_n\times X\times \dots )={\int }_{PX}{\mathrm{i}\mathrm{i}\mathrm{d}}_{\mathbb{N}}(A_1\times \cdots \times A_n\times X\times \dots |q)\tilde{p}(dq)={\int }_{PX}q(A_1)\cdots q(A_n)\tilde{p}(dq).}$

In other words, ${\displaystyle p}$ is a mixture of iid measures on ${\displaystyle X}$ (the ones formed by ${\displaystyle q}$ in the integral above).

Extensions

Versions of de Finetti's theorem for finite exchangeable sequences, and for Markov exchangeable sequences have been proved by Diaconis and Freedman and by Kerns and Szekely. Two notions of partial exchangeability of arrays, known as separate and joint exchangeability lead to extensions of de Finetti's theorem for arrays by Aldous and Hoover.

The computable de Finetti theorem shows that if an exchangeable sequence of real random variables is given by a computer program, then a program which samples from the mixing measure can be automatically recovered.

In the setting of free probability, there is a noncommutative extension of de Finetti's theorem which characterizes noncommutative sequences invariant under quantum permutations.

Extensions of de Finetti's theorem to quantum states have been found to be useful in quantum information, in topics like quantum key distribution and entanglement detection. A multivariate extension of de Finetti's theorem can be used to derive Bose–Einstein statistics from the statistics of classical (i.e. independent) particles.