Computable de Finetti measures
Copyright policy )Computable de Finetti measures
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.
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
- University of Hawaii System United States
- Massachusetts Institute of Technology Dept. of Economics United States
- Computer Science and Artificial Intelligence Laboratory (CSAIL) Massachusetts Institute of Technology (MIT) United States
- Massachusetts Institute of Technology United States
The de Finetti theorem, FOS: Computer and information sciences, Computer Science - Logic in Computer Science, 03D78, 60G09, 68Q10, 03F60, 68N18, Logic, functional programming, Mathematics - Statistics Theory, Machine Learning (stat.ML), Statistics Theory (math.ST), Computable probability theory, Probabilistic programming languages, Statistics - Machine Learning, Exchangeability for stochastic processes, FOS: Mathematics, Functional programming and lambda calculus, Computer Science - Programming Languages, Probability (math.PR), Mathematics - Logic, de Finetti theorem, exchangeability, probabilistic programming languages, Logic in Computer Science (cs.LO), Exchangeability, Mutation, computable probability theory, mutation, Computation over the reals, computable analysis, Logic (math.LO), Mathematics - Probability, Programming Languages (cs.PL)
The de Finetti theorem, FOS: Computer and information sciences, Computer Science - Logic in Computer Science, 03D78, 60G09, 68Q10, 03F60, 68N18, Logic, functional programming, Mathematics - Statistics Theory, Machine Learning (stat.ML), Statistics Theory (math.ST), Computable probability theory, Probabilistic programming languages, Statistics - Machine Learning, Exchangeability for stochastic processes, FOS: Mathematics, Functional programming and lambda calculus, Computer Science - Programming Languages, Probability (math.PR), Mathematics - Logic, de Finetti theorem, exchangeability, probabilistic programming languages, Logic in Computer Science (cs.LO), Exchangeability, Mutation, computable probability theory, mutation, Computation over the reals, computable analysis, Logic (math.LO), Mathematics - Probability, Programming Languages (cs.PL)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).13 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!