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

## 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: | 04 Feb 2015 23:00 |

Last Modified: | 05 Feb 2015 06:29 |

DOI: | 10.1007/978-3-642-03073-4_23 |