Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-18T04:51:55.491Z Has data issue: false hasContentIssue false
  • English
  • Français

On computability and disintegration

Published online by Cambridge University Press:  28 July 2016

NATHANAEL L. ACKERMAN ,
CAMERON E. FREER  and
DANIEL M. ROY
NATHANAEL L. ACKERMAN
Affiliation:
Department of Mathematics, Harvard University, Cambridge, Massachusetts, U.S.A. Email: [email protected]
CAMERON E. FREER
Affiliation:
Department of Brain and Cognitive Sciences, Massachusetts Institute of Technology, and Gamalon Labs, Cambridge, Massachusetts, U.S.A. Email: [email protected]
DANIEL M. ROY
Affiliation:
Department of Statistical Sciences, University of Toronto, Toronto, Ontario, Canada Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We show that the disintegration operator on a complete separable metric space along a projection map, restricted to measures for which there is a unique continuous disintegration, is strongly Weihrauch equivalent to the limit operator Lim. When a measure does not have a unique continuous disintegration, we may still obtain a disintegration when some basis of continuity sets has the Vitali covering property with respect to the measure; the disintegration, however, may depend on the choice of sets. We show that, when the basis is computable, the resulting disintegration is strongly Weihrauch reducible to Lim, and further exhibit a single distribution realizing this upper bound.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 27 , Special Issue 8: Continuity, Computability, Constructivity: From Logic to Algorithms 2013 , December 2017 , pp. 1287 - 1314
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Ackerman, N.L., Freer, C.E. and Roy, D.M. (2010). On the computability of conditional probability. Preprint, arXiv:1005.3014.Google Scholar
Ackerman, N.L., Freer, C.E. and Roy, D.M. (2011). Noncomputable conditional distributions. In: Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science (LICS 2011), IEEE Computer Society 107–116.Google Scholar
Bosserhoff, V. (2008). Notions of probabilistic computability on represented spaces. Journal of Universal Computer Science 14 (6) 956–995.Google Scholar
Brattka, V. (2005). Effective Borel measurability and reducibility of functions. Mathematical Logic Quarterly 51 (1) 19–44.CrossRefGoogle Scholar
Brattka, V. and Gherardi, G. (2011a). Effective choice and boundedness principles in computable analysis. Bulletin of Symbolic Logic 17 (1) 73–117.CrossRefGoogle Scholar
Brattka, V. and Gherardi, G. (2011b). Weihrauch degrees, omniscience principles and weak computability. Journal of Symbolic Logic 76 (1) 143–176.CrossRefGoogle Scholar
Brattka, V., Gherardi, G. and Marcone, A. (2012). The Bolzano–Weierstrass Theorem is the jump of Weak Kőnig's Lemma. Annals of Pure Applied Logic 163 (6) 623–655.CrossRefGoogle Scholar
Brattka, V., Hölzl, R. and Gherardi, G. (2015). Probabilistic computability and choice. Information and Computation 242 249–286.CrossRefGoogle Scholar
Collins, P. (2009). A computable type theory for control systems. In: Proceedings of the 48th IEEE Conference on Decision and Control 5583–5543.Google Scholar
Collins, P. (2010). Computable analysis with applications to dynamical systems. Technical Report MAC-1002, Centrum Wiskunde & Informatica.Google Scholar
Escardó, M. (2004). Synthetic topology. Electronic Notes in Theoretical Computer Science 87 21–156.CrossRefGoogle Scholar
Fraser, D.A.S., McDunnough, P., Naderi, A. and Plante, A. (1995). On the definition of probability densities and sufficiency of the likelihood map. Probability and Mathematical Statistics 15 301–310.Google Scholar
Fraser, D.A.S. and Naderi, A. (1996). On the definition of conditional probability. In Research Developments in Probability and Statistics, VSP, Utrecht 23–26.Google Scholar
Gács, P. (2005). Uniform test of algorithmic randomness over a general space. Theoretical Computer Science 341 (1–3) 91–137.CrossRefGoogle Scholar
Hoyrup, M. and Rojas, C. (2009). Computability of probability measures and Martin-Löf randomness over metric spaces. Information and Computation 207 (7) 830–847.CrossRefGoogle Scholar
Hoyrup, M. and Rojas, C. (2011). Absolute continuity of measures and preservation of randomness. Preprint, http://www.loria.fr/~hoyrup/abscont.pdf.Google Scholar
Hoyrup, M., Rojas, C. and Weihrauch, K. (2012). Computability of the Radon–Nikodym derivative. Computability 1 (1) 3–13.CrossRefGoogle Scholar
Kallenberg, O. (2002). Foundations of Modern Probability, 2nd ed. Springer.CrossRefGoogle Scholar
Kolmogorov, A.N. (1933). Grundbegriffe der Wahrscheinlichkeitsrechnung, Springer.CrossRefGoogle Scholar
Pauly, A. (2016). On the topological aspects of the theory of represented spaces. Computability.CrossRefGoogle Scholar
Pauly, A. and Fouché, W. (2014). How constructive is constructing measures? arXiv:1409.3428v1.Google Scholar
Pfanzagl, J. (1979). Conditional distributions as derivatives. Annals of Probability 7 (6) 1046–1050.CrossRefGoogle Scholar
Schröder, M. (2002a). Admissible Representations for Continuous Computations. Ph.D. Thesis, Fachbereich Informatik, FernUniversität Hagen.Google Scholar
Schröder, M. (2002b). Effectivity in spaces with admissible multirepresentations. Mathematical Logic Quarterly 48 (suppl. 1) 78–90.3.0.CO;2-K>CrossRefGoogle Scholar
Schröder, M. (2007). Admissible representations for probability measures. Mathematical Logic Quarterly 53 (4–5) 431–445.CrossRefGoogle Scholar
Tjur, T. (1975). A Constructive Definition of Conditional Distributions. Preprint 13. Institute of Mathematical Statistics, University of Copenhagen.Google Scholar
Tjur, T. (1980). Probability Based on Radon Measures, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons.Google Scholar
Weihrauch, K. (2000). Computable Analysis: An Introduction, Springer.CrossRefGoogle Scholar