De Finetti's theorem

In probability theory, de Finetti's theorem states that exchangeable observations are conditionally independent relative to some latent variable. An epistemic probability distribution could then be assigned to this variable. It is named in honor of Bruno de Finetti.

For the special case of an exchangeable sequence of Bernoulli random variables it states that such a sequence is a "mixture" of sequences of independent and identically distributed (i.i.d.) Bernoulli random variables.

A sequence of random variables is called exchangeable if the joint distribution of the sequence is unchanged by any permutation of the indices. While the variables of the exchangeable sequence are not themselves independent, only exchangeable, there is an underlying family of i.i.d. random variables. That is, there are underlying, generally unobservable, quantities that are i.i.d. – exchangeable sequences are mixtures of i.i.d. sequences.

Background

A Bayesian statistician often seeks the conditional probability distribution of a random quantity given the data. The concept of exchangeability was introduced by de Finetti. De Finetti's theorem explains a mathematical relationship between independence and exchangeability.[1]

An infinite sequence

${\displaystyle X_{1},X_{2},X_{3},\dots }$

of random variables is said to be exchangeable if for any natural number n and any two finite sequences i₁, ..., i_n and j₁, ..., j_n (with each of the is distinct, and each of the js distinct), the two sequences

${\displaystyle X_{i_{1}},\dots ,X_{i_{n}}{\text{ and }}X_{j_{1}},\dots ,X_{j_{n}}}$

both have the same joint probability distribution.

If an identically distributed sequence is independent, then the sequence is exchangeable; however, the converse is false—there exist exchangeable random variables that are not statistically independent, for example the Pólya urn model.

Statement of the theorem

A random variable X has a Bernoulli distribution if Pr(X = 1) = p and Pr(X = 0) = 1 − p for some p ∈ (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 rather than a sum.

More precisely, suppose X₁, X₂, X₃, ... is an infinite exchangeable sequence of Bernoulli-distributed random variables. Then there is some probability distribution m on the interval [0, 1] and some random variable Y such that

• The probability distribution of Y is m, and
• The conditional probability distribution of the whole sequence X₁, X₂, X₃, ... given the value of Y is described by saying that
  • X₁, X₂, X₃, ... are conditionally independent given Y, and
  • For any i ∈ {1, 2, 3, ...}, the conditional probability that X_i = 1, given the value of Y, is Y.

Another way of stating the theorem

Suppose ${\displaystyle X_{1},X_{2},X_{3},\ldots }$ is an infinite exchangeable sequence of Bernoulli random variables. Then ${\displaystyle X_{1},X_{2},X_{3},\ldots }$ are conditionally independent and identically distributed given the exchangeable sigma-algebra (i.e., the sigma-algebra of events measurable with respect to ${\displaystyle X_{1},X_{2},\ldots }$ and invariant under finite permutations of the indices).

Example

Here is 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 \lim _{n\rightarrow \infty }{\frac {X_{1}+\cdots +X_{n}}{n}}={\begin{cases}2/3&{\text{with probability }}1/2,\\9/10&{\text{with probability }}1/2.\end{cases}}}$

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.

Extensions

Versions of de Finetti's theorem for finite exchangeable sequences,[2][3] and for Markov exchangeable sequences[4] 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.[5]

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.[6]

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

Extensions of de Finetti's theorem to quantum states have been found to be useful in quantum information,[8][9][10] in topics like quantum key distribution[11] and entanglement detection.[12]

See also

• Choquet theory
• Hewitt–Savage zero–one law
• Krein–Milman theorem

References

1. See the Oxford lecture notes of Steffen Lauritzen http://www.stats.ox.ac.uk/~steffen/teaching/grad/definetti.pdf
2. Diaconis, P.; Freedman, D. (1980). "Finite exchangeable sequences". Annals of Probability. 8 (4): 745–764. doi:10.1214/aop/1176994663. MR 0577313. Zbl 0434.60034.
3. Szekely, G. J.; Kerns, J. G. (2006). "De Finetti's theorem for abstract finite exchangeable sequences". Journal of Theoretical Probability. 19 (3): 589–608. doi:10.1007/s10959-006-0028-z.
4. Diaconis, P.; Freedman, D. (1980). "De Finetti's theorem for Markov chains". Annals of Probability. 8 (1): 115–130. doi:10.1214/aop/1176994828. MR 0556418. Zbl 0426.60064.
5. Persi Diaconis and Svante Janson (2008) "Graph Limits and Exchangeable Random Graphs",Rendiconti di Matematica, Ser. VII 28(1), 33–61.
6. Cameron Freer and Daniel Roy (2009) "Computable exchangeable sequences have computable de Finetti measures", Proceedings of the 5th Conference on Computability in Europe: Mathematical Theory and Computational Practice, Lecture Notes in Computer Science, Vol. 5635, pp. 218–231.
7. Koestler, Claus; Speicher, Roland (2009). "A noncommutative de Finetti theorem: Invariance under quantum permutations is equivalent to freeness with amalgamation". Commun. Math. Phys. 291 (2): 473–490. arXiv:0807.0677. Bibcode:2009CMaPh.291..473K. doi:10.1007/s00220-009-0802-8.
8. Caves, Carlton M.; Fuchs, Christopher A.; Schack, Ruediger (2002-08-20). "Unknown quantum states: The quantum de Finetti representation". Journal of Mathematical Physics. 43 (9): 4537–4559. arXiv:quant-ph/0104088. Bibcode:2002JMP....43.4537C. doi:10.1063/1.1494475. ISSN 0022-2488.
9. J. Baez (2007). "This Week's Finds in Mathematical Physics (Week 251)". Retrieved 29 April 2012.
10. Brandao, Fernando G.S.L.; Harrow, Aram W. (2013-01-01). "Quantum De Finetti Theorems Under Local Measurements with Applications". Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing. STOC '13. New York, NY, USA: ACM: 861–870. arXiv:1210.6367. doi:10.1145/2488608.2488718. ISBN 9781450320290.
11. Renner, Renato (2005-12-30). "Security of Quantum Key Distribution". arXiv:quant-ph/0512258.
12. Doherty, Andrew C.; Parrilo, Pablo A.; Spedalieri, Federico M. (2005-01-01). "Detecting multipartite entanglement". Physical Review A. 71 (3): 032333. arXiv:quant-ph/0407143. Bibcode:2005PhRvA..71c2333D. doi:10.1103/PhysRevA.71.032333.

External links

• Accardi, L. (2001) [1994], "De Finetti theorem", Encyclopedia of Mathematics, EMS Press
• What is so cool about De Finetti's representation theorem?
• Using de Finetti's Theorem to model COVID-19