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.


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
Divisions: Div F > Computational and Biological Learning
Depositing User: Cron Job
Date Deposited: 15 Dec 2015 13:36
Last Modified: 18 Jan 2016 06:19
DOI: 10.1007/978-3-642-03073-4_23