On the computability of conditional probability

Abstract

As inductive inference and machine learning methods in computer science see continued success, researchers are aiming to describe ever more complex probabilistic models and inference algorithms. It is natural to ask whether there is a universal computational procedure for probabilistic inference. We investigate the computability of conditional probability, a fundamental notion in probability theory and a cornerstone of Bayesian statistics. We show that there are computable joint distributions with noncomputable conditional distributions, ruling out the prospect of general inference algorithms, even inefficient ones. Specifically, we construct a pair of computable random variables in the unit interval such that the conditional distribution of the first variable given the second encodes the halting problem. Nevertheless, probabilistic inference is possible in many common modeling settings, and we prove several results giving broadly applicable conditions under which conditional distributions are computable. In particular, conditional distributions become computable when measurements are corrupted by independent computable noise with a sufficiently smooth bounded density.

44 pages, 3 figures. Final published version

References in corpus (5)

• Church: a language for generative models
• Computing over the Reals: Foundations for Scientific Computing
• On the computability of conditional probability
• Computable de Finetti measures
• Computability of the Radon-Nikodym derivative

Cited by in corpus (13)

• A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics
• On the computability of conditional probability
• On computability and disintegration
• Building fast Bayesian computing machines out of intentionally stochastic, digital parts
• Towards Machine Wald
• Conditional probabilities and van Lambalgen theorem revisited
• Representations of measurable sets in computable measure theory
• AIDE: An algorithm for measuring the accuracy of probabilistic inference algorithms
• Probabilistic Reasoning across the Causal Hierarchy
• Quantifying the probable approximation error of probabilistic inference programs
• A Topological Perspective on Causal Inference
• Extensional Denotational Semantics of Higher-Order Probabilistic Programs, Beyond the Discrete Case
• Bayesian definition of random sequences with respect to conditional probabilities