nLab de Finetti's theorem

Redirected from "De Finetti's theorem".
Contents

Context

Measure and probability theory

Limits and colimits

Contents

Idea

De Finetti’s theorem is one of the central results of probability theory, and it usually refers to any of the following related statements:

The statement involves mixtures of probability measures, and so probability measures over probability measures. This recursive construction is one motivation for introducing monads in probability theory. Indeed, categorically, the theorem can equivalently be expressed as follows:

Motivation

There are several ways of motivating de Finetti’s theorem. Here is one, which is very close to de Finetti’s original motivation, as explained in his original paper (de Finetti’29).

Consider a repeated experiment where we are uncertain about the probability distribution of the outcomes. For the simplest possible example, imagine repeatedly flipping a coin, but without knowing in advance the bias of the coin. One may be tempted to assume that the coin flips are independent, since “a coin has no memory”. However, this is not quite the case:

  • What we can say is that the coin flips are exchangeable, since the coin is always the same, and so every flip, and each subsequence of flips, follows the same distribution.
  • However, in general independence fails: there is hidden information in past flips about future flips: by flipping the coin repeatedly, we can get more and more certain about the coin’s bias. (For example, if we keep getting “heads”, we may start suspecting that the coin is not fair.)
  • If we instead know exactly the bias of the coin, there is no more hidden information that past flips have about future ones. Therefore, given the bias of the coin, the flips are conditionally independent.

De Finetti’s theorem says precisely that for every exchangeable process we have conditional independence of the variables given their distribution.

In measure-theoretic probability

Let XX be a standard Borel space (for example, the real line), and form the infinite product X X^\mathbb{N}.

Notice first of all that given the space PXP X of probability measures over XX (the Giry monad), the iid sampling map samp :PXX samp_\mathbb{N}:P X\to X^\mathbb{N} is exchangeable. In other words, given any finite permutation of the coordinates σ:X X \sigma: X^\mathbb{N}\to X^\mathbb{N}, and denoting the kernel induced by σ\sigma again by σ\sigma, the following diagram of Markov kernels commutes:

Consider now any (other) exchangeable probability measure pp on X X^\mathbb{N}. If we write it as a Markov kernel 1X 1\to X^\mathbb{N}, exchangeability means by definition that, once again, the following diagram commutes for every σ\sigma:

A way of stating de Finetti’s theorem is now to say that PXP X is the categorical limit of the diagram formed by the σ\sigma (the group action of finite permutations). In other words, given any exchangeable measure pp (or more generally any exchangeable kernel), there exists a unique measure (or kernel) uu making the following diagram commute:

Explicitly, this means that we can write pp as a convex mixture (with measure uu) of iid measures: for every measurable A 1,,A nXA_1,\dots,A_n\subseteq X,

p(A 1××A n)= PXsamp (A 1××A n|q)u(dq)= PX(q(A 1)q(A n))u(dq). p(A_1\times\dots\times A_n) \;=\; \int_{P X} samp_\mathbb{N}(A_1\times\dots\times A_n|q) \, u(d q) \;=\; \int_{P X} \big(q(A_1)\cdots q(A_n)\big)\,u(d q) .

This allows to define the space PXP X, i.e. the Giry monad, purely from its universal property. In terms of representable presheaves, one can say that the space of probability measure represents exchangeable processes.

Moreover, since the iid sampling map denotes conditional independence of its outputs given its input, the theorem implies that the various copies of XX are conditionally independent given the distribution (PXP X).

In Markov categories

Just as it happens for standard Borel spaces, in any observationally representable Markov category with conditionals and Kolmogorov products, a version of de Finetti’s theorem holds, and the proof is completely analogous to the measure-theoretic one (FGP’21).

See also (CFGKL) for a similar statement under different assumptions.

Conversely, one can define de Finetti limits in a Markov category as particular limits which are compatible with the Markov structure, and show that such a limit always gives a probability monad, making the Markov category representable (FFL’23, section 3.6).

In dagger categories

(For now, see here.)

Quantum versions

(For now, see the references.)

See also

References

The original paper by de Finetti:

Category-theoretic accounts:

For the quantum case:

  • Sam Staton and Ned Summers, Quantum de Finetti Theorems as Categorical Limits, and Limits of State Spaces of C *C^\ast-algebras, Proceedings of Quantum Physics and Logic, 2022. (arXiv)

  • Tobias Fritz and Antonio Lorenzin, Involutive Markov categories and the quantum de Finetti theorem, 2023. (arXiv)

Introductory videos:

  • Tobias Fritz, Categorical Probability and the de Finetti theorem, New York Category Seminar, 2021. (YouTube)

  • Paolo Perrone, Markov categories: a tutorial. Applied Category Theory (ACT) 2023, tutorial video. De Finetti’s theorem starting at time 1:16:30. (YouTube)

  • Paolo Perrone, Universal Properties in Probability Theory. Keynote talk, Category Theory (CT) 2023. De Finetti theorem starting at time 39:25 (YouTube)

  • Antonio Lorenzin, Involutive Markov categories and the quantum de Finetti theorem, The Oxford Advanced Seminar on Informatic Structures (OASIS), 2023. (YouTube)

category: probability

Last revised on November 21, 2024 at 08:37:03. See the history of this page for a list of all contributions to it.