Computable de Finetti measures

DOI10.1016/J.APAL.2011.06.011zbMATH Open1247.03098arXiv0912.1072OpenAlexW2144567031MaRDI QIDQ764273FDOQ764273

Authors: Cameron E. Freer, Daniel M. Roy 

Publication date: 13 March 2012

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Abstract: We prove a computable version of de Finetti's theorem on exchangeable sequences of real random variables. As a consequence, exchangeable stochastic processes expressed in probabilistic functional programming languages can be automatically rewritten as procedures that do not modify non-local state. Along the way, we prove that a distribution on the unit interval is computable if and only if its moments are uniformly computable.

Full work available at URL: https://arxiv.org/abs/0912.1072

Recommendations

• Computable exchangeable sequences have computable de Finetti measures
• An elementary proof of de Finetti's theorem
• An information-theoretic proof of a finite de Finetti theorem
• A continuous version of De Finetti's theorem
• De Finetti-type theorems: An analytical approach

zbMATH Keywords

exchangeabilityfunctional programmingmutationde Finetti theoremcomputable probability theoryprobabilistic programming languages

Mathematics Subject Classification ID

Computation over the reals, computable analysis (03D78) Exchangeability for stochastic processes (60G09) Functional programming and lambda calculus (68N18)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Representations for partially exchangeable arrays of random variables
• Graph limits and exchangeable random graphs
• LCF considered as a programming language
• Title not available (Why is that?)
• Title not available (Why is that?)
• A tutorial on computable analysis
• Title not available (Why is that?)
• Symmetric Measures on Cartesian Products
• Title not available (Why is that?)
• A convenient category of domains
• Probabilistic Symmetries and Invariance Principles
• Title not available (Why is that?)
• Stochastic lambda calculus and monads of probability distributions
• Uses of exchangeability
• On exchangeable random variables and the statistics of large graphs and hypergraphs
• Recursively enumerable sets and degrees
• Computing over the reals: foundations for scientific computing.
• Computability on subsets of metric spaces.
• Computability on continuous, lower semi-continuous and upper semi-continuous real functions
• Title not available (Why is that?)
• On stationary sequences of random variables and the de Finetti's equivalence
• Semi-decidability of may, must and probabilistic testing in a higher-type setting
• Domains for Computation in Mathematics, Physics and Exact Real Arithmetic
• Computability on random variables
• Computability on the probability measures on the Borel sets of the unit interval
• Representing probability measures using probabilistic processes
• Induction and recursion on the partial real line with applications to Real PCF
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computable exchangeable sequences have computable de Finetti measures
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computable metrization
• Admissible representations for probability measures

Cited In (10)

• Title not available (Why is that?)
• An application of computable distributions to the semantics of probabilistic programming languages
• Probabilistic computability and choice
• Computable Measure Theory and Algorithmic Randomness
• Computability of probability distributions and characteristic functions
• Algorithmic barriers to representing conditional independence
• Computable measures coprojection consistent with ordering relation is not necessarily computable
• Computable exchangeable sequences have computable de Finetti measures
• Computable randomness and betting for computable probability spaces
• A generalization of hierarchical exchangeability on trees to directed acyclic graphs

Uses Software

• IBAL
• Church

This page was built for publication: Computable de Finetti measures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q764273)