Noncomputable Conditional Distributions
Authors:
- Nathanael L. AckermanNANathanael L. Ackerman
- Cameron E. FreerCFCameron E. Freer
- Daniel M. RoyDRDaniel M. Roy
- 1 June 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10436871,p. 107-116
Abstract
We study the computability of conditional probability, a fundamental notion in probability theory and Bayesian statistics. In the elementary discrete setting, a ratio of probabilities defines conditional probability. In more general settings, conditional probability is defined axiomatically, and the search for more constructive definitions is the subject of a rich literature in probability theory and statistics. However, we show that in general one cannot compute conditional probabilities. Specifically, we construct a pair of computable random variables (X, Y) in the unit interval whose conditional distribution P[Y|X] encodes the halting problem. Nevertheless, probabilistic inference has proven remarkably successful in practice, even in infinite-dimensional continuous settings. We prove several results giving general conditions under which conditional distributions are computable. In the discrete or dominated setting, under suitable computability hypotheses, conditional distributions are computable. Likewise, conditioning is a computable operation in the presence of certain additional structure, such as independent absolutely continuous noise.Keywords
This publication has 30 references indexed in Scilit:
- Uniform test of algorithmic randomness over a general spaceTheoretical Computer Science, 2005
- Foundations of Modern Probability2002
- Theory of Statistics1995
- Computability in Analysis and Physics1989
- Paradoxes in conditional probabilityJournal of Multivariate Analysis, 1988
- Conditional Distributions as DerivativesThe Annals of Probability, 1979
- Probabilistic recursive functionsTransactions of the American Mathematical Society, 1973
- A recursive function, defined on a compact interval and having a continuous derivative that is not recursive.The Michigan Mathematical Journal, 1971
- Communication in the Presence of NoiseProceedings of the IRE, 1949
- Transmission of Information1Bell System Technical Journal, 1928