CUED Publications database

Computable exchangeable sequences have computable de finetti measures

Freer, CE and Roy, DM (2009) Computable exchangeable sequences have computable de finetti measures. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5635 L. pp. 218-231. ISSN 0302-9743

Full text not available from this repository.

Abstract

We prove a uniformly computable version of de Finetti's theorem on exchangeable sequences of real random variables. In the process, we develop machinery for computably recovering a distribution from its sequence of moments, which suffices to prove the theorem in the case of (almost surely) continuous directing random measures. In the general case, we give a proof inspired by a randomized algorithm which succeeds with probability one. Finally, we show how, as a consequence of the main theorem, exchangeable stochastic processes in probabilistic functional programming languages can be rewritten as procedures that do not use mutation. © 2009 Springer Berlin Heidelberg.

Item Type: Article
Uncontrolled Keywords: Computable probability theory De Finetti Exchangeability Mutation Probabilistic programming languages
Subjects: UNSPECIFIED
Divisions: Div F > Computational and Biological Learning
Depositing User: Cron Job
Date Deposited: 07 Mar 2014 12:20
Last Modified: 08 Dec 2014 02:27
DOI: 10.1007/978-3-642-03073-4_23