arXiv:0912.1072 Abstract | arXiv Analytics

arXiv:0912.1072 [math.LO]Abstract References Reviews Resources

Computable de Finetti measures

Published 2009-12-06, updated 2011-12-19Version 2

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.

Comments: 32 pages. Final journal version; expanded somewhat, with minor corrections. To appear in Annals of Pure and Applied Logic. Extended abstract appeared in Proceedings of CiE '09, LNCS 5635, pp. 218-231

Journal: Annals of Pure and Applied Logic 163 (2012) pp. 530-546

DOI: 10.1016/j.apal.2011.06.011

Categories: math.LO, cs.LO, cs.PL, math.PR, math.ST, stat.ML, stat.TH

Subjects: 03D78, 60G09, 68Q10, 03F60, 68N18

Keywords: finetti measures, computable, real random variables, probabilistic functional programming languages, finettis theorem

Tags: journal article

Related articles:

arXiv:2006.05629 [math.LO] (Published 2020-06-10)

The Universal Theory Of The Hyperfinite II$_1$ Factor Is Not Computable

Isaac Goldbring, Bradd Hart

arXiv:1109.6749 [math.LO] (Published 2011-09-30)

Characterizing the strongly jump-traceable sets via randomness