×

Computable exchangeable sequences have computable de Finetti measures. (English) Zbl 1233.03051

Ambos-Spies, Klaus (ed.) et al., Mathematical theory and computational practice. 5th conference on computability in Europe, CiE 2009, Heidelberg, Germany, July 19–24, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03072-7/pbk). Lecture Notes in Computer Science 5635, 218-231 (2009).
Summary: 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.
For the entire collection see [Zbl 1192.68004].

MSC:

03D78 Computation over the reals, computable analysis
60G09 Exchangeability for stochastic processes
68N18 Functional programming and lambda calculus

Software:

IBAL; Church
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alvarez-Manilla, M., Edalat, A., Saheb-Djahromi, N.: An extension result for continuous valuations. J. London Math. Soc. 61(2), 629–640 (2000) · Zbl 0960.60005 · doi:10.1112/S0024610700008681
[2] Aldous, D.J.: Representations for partially exchangeable arrays of random variables. J. Multivariate Analysis 11(4), 581–598 (1981) · Zbl 0474.60044 · doi:10.1016/0047-259X(81)90099-3
[3] Aldous, D.J.: Exchangeability and related topics. In: École d’été de probabilités de Saint-Flour, XIII–1983. Lecture Notes in Math., vol. 1117, pp. 1–198. Springer, Berlin (1985) · doi:10.1007/BFb0099421
[4] Austin, T.: On exchangeable random variables and the statistics of large graphs and hypergraphs. Probab. Surv. 5, 80–145 (2008) · Zbl 1189.60020 · doi:10.1214/08-PS124
[5] Bauer, A.: Realizability as the connection between constructive and computable mathematics. In: CCA 2005: Second Int. Conf. on Comput. and Complex in Analysis (2005)
[6] Brattka, V., Gherardi, G.: Borel complexity of topological operations on computable metric spaces. In: Cooper, S.B., Löwe, B., Sorbi, A. (eds.) CiE 2007. LNCS, vol. 4497, pp. 83–97. Springer, Heidelberg (2007) · Zbl 1139.03032 · doi:10.1007/978-3-540-73001-9_9
[7] Billingsley, P.: Probability and measure, 3rd edn. John Wiley & Sons Inc., New York (1995) · Zbl 0822.60002
[8] Bosserhoff, V.: Notions of probabilistic computability on represented spaces. J. of Universal Comput. Sci. 14(6), 956–995 (2008) · Zbl 1227.03058
[9] de Finetti, B.: Funzione caratteristica di un fenomeno aleatorio. Atti della R. Accademia Nazionale dei Lincei, Ser. 6. Memorie, Classe di Scienze Fisiche, Matematiche e Naturali 4, 251–299 (1931)
[10] de Finetti, B.: Theory of probability, vol. 2. John Wiley & Sons Ltd., London (1975) · Zbl 0328.60003
[11] Diaconis, P., Freedman, D.: Partial exchangeability and sufficiency. In: Statistics: applications and new directions (Calcutta, 1981), pp. 205–236. Indian Statist. Inst., Calcutta (1984)
[12] Diaconis, P., Janson, S.: Graph limits and exchangeable random graphs. Rendiconti di Matematica, Ser. VII 28(1), 33–61 (2008) · Zbl 1162.60009
[13] Edalat, A.: Domain theory and integration. Theoret. Comput. Sci. 151(1), 163–193 (1995) · Zbl 0872.28006 · doi:10.1016/0304-3975(95)00050-7
[14] Edalat, A.: The Scott topology induces the weak topology. In: 11th Ann. IEEE Symp. on Logic in Comput. Sci., pp. 372–381. IEEE Comput. Soc. Press, Los Alamitos (1996) · doi:10.1109/LICS.1996.561450
[15] Griffiths, T.L., Ghahramani, Z.: Infinite latent feature models and the Indian buffet process. In: Adv. in Neural Inform. Processing Syst., vol. 17, pp. 475–482. MIT Press, Cambridge (2005)
[16] Goodman, N.D., Mansinghka, V.K., Roy, D.M., Bonawitz, K., Tenenbaum, J.B.: Church: a language for generative models. In: Uncertainty in Artificial Intelligence (2008)
[17] Grubba, T., Schröder, M., Weihrauch, K.: Computable metrization. Math. Logic Q. 53(4-5), 381–395 (2007) · Zbl 1121.03084 · doi:10.1002/malq.200710009
[18] Hoover, D.N.: Relations on probability spaces and arrays of random variables, Institute for Advanced Study. Princeton, NJ (preprint) (1979)
[19] Hewitt, E., Savage, L.J.: Symmetric measures on Cartesian products. Trans. Amer. Math. Soc. 80, 470–501 (1955) · Zbl 0066.29604 · doi:10.1090/S0002-9947-1955-0076206-8
[20] Jones, C., Plotkin, G.: A probabilistic powerdomain of evaluations. In: Proc. of the Fourth Ann. Symp. on Logic in Comp. Sci., pp. 186–195. IEEE Press, Los Alamitos (1989) · Zbl 0716.06003 · doi:10.1109/LICS.1989.39173
[21] Kallenberg, O.: Foundations of modern probability, 2nd edn. Springer, New York (2002) · Zbl 0996.60001 · doi:10.1007/978-1-4757-4015-8
[22] Kallenberg, O.: Probabilistic symmetries and invariance principles. Springer, New York (2005) · Zbl 1084.60003
[23] Kingman, J.F.C.: Uses of exchangeability. Ann. Probability 6(2), 183–197 (1978) · Zbl 0374.60064 · doi:10.1214/aop/1176995566
[24] Kozen, D.: Semantics of probabilistic programs. J. Comp. System Sci. 22(3), 328–350 (1981) · Zbl 0476.68019 · doi:10.1016/0022-0000(81)90036-2
[25] Kemp, C., Tenenbaum, J., Griffiths, T., Yamada, T., Ueda, N.: Learning systems of concepts with an infinite relational model. In: Proc. of the 21st Nat. Conf. on Artificial Intelligence (2006)
[26] Lauritzen, S.L.: Extreme point models in statistics. Scand. J. Statist. 11(2), 65–91 (1984) · Zbl 0542.62002
[27] Mansinghka, V.K.: Natively Probabilistic Computing. PhD thesis, Massachusetts Institute of Technology (2009)
[28] Müller, N.T.: Computability on random variables. Theor. Comput. Sci. 219(1-2), 287–299 (1999) · Zbl 0916.68041 · doi:10.1016/S0304-3975(98)00292-8
[29] Pfeffer, A.: IBAL: A probabilistic rational programming language. In: Proc. of the 17th Int. Joint Conf. on Artificial Intelligence, pp. 733–740. Morgan Kaufmann Publ., San Francisco (2001)
[30] Park, S., Pfenning, F., Thrun, S.: A probabilistic language based on sampling functions. ACM Trans. Program. Lang. Syst. 31(1), 1–46 (2008) · Zbl 05517453 · doi:10.1145/1452044.1452048
[31] Pour-El, M.B., Richards, J.I.: Computability in analysis and physics. Springer, Berlin (1989) · Zbl 0678.03027 · doi:10.1007/978-3-662-21717-7
[32] Roy, D.M., Mansinghka, V.K., Goodman, N.D., Tenenbaum, J.B.: A stochastic programming perspective on nonparametric Bayes. In: Nonparametric Bayesian Workshop, Int. Conf. on Machine Learning (2008)
[33] Ryll-Nardzewski, C.: On stationary sequences of random variables and the de Finetti’s equivalence. Colloq. Math. 4, 149–156 (1957) · Zbl 0077.12302
[34] Rogers, Jr., H.: Theory of recursive functions and effective computability. McGraw-Hill, New York (1967) · Zbl 0183.01401
[35] Ramsey, N., Pfeffer, A.: Stochastic lambda calculus and monads of probability distributions. In: Proc. of the 29th ACM SIGPLAN-SIGACT Symp. on Principles of Program. Lang., pp. 154–165 (2002) · Zbl 1323.68150 · doi:10.1145/503272.503288
[36] Roy, D.M., Teh, Y.W.: The Mondrian process. In: Adv. in Neural Inform. Processing Syst., vol. 21 (2009)
[37] Schröder, M.: Admissible representations for probability measures. Math. Logic Q. 53(4-5), 431–445 (2007) · Zbl 1124.03019 · doi:10.1002/malq.200710010
[38] Sethuraman, J.: A constructive definition of Dirichlet priors. Statistica Sinica 4, 639–650 (1994) · Zbl 0823.62007
[39] Soare, R.I.: Recursively enumerable sets and degrees. Springer, Berlin (1987) · Zbl 0667.03030 · doi:10.1007/978-3-662-02460-7
[40] Schröder, M., Simpson, A.: Representing probability measures using probabilistic processes. J. Complex. 22(6), 768–782 (2006) · Zbl 1111.60003 · doi:10.1016/j.jco.2006.05.003
[41] Teh, Y.W., Görür, D., Ghahramani, Z.: Stick-breaking construction for the Indian buffet process. In: Proc. of the 11th Conf. on A.I. and Stat. (2007)
[42] Thibaux, R., Jordan, M.I.: Hierarchical beta processes and the Indian buffet process. In: Proc. of the 11th Conf. on A.I. and Stat. (2007)
[43] Weihrauch, K.: Computability on the probability measures on the Borel sets of the unit interval. Theoret. Comput. Sci. 219(1–2), 421–437 (1999) · Zbl 0916.68043 · doi:10.1016/S0304-3975(98)00298-9
[44] Weihrauch, K.: Computable analysis: an introduction. Springer, Berlin (2000) · Zbl 0956.68056 · doi:10.1007/978-3-642-56999-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.