CUED Publications database

Noncomputable conditional distributions

Ackerman, NL and Freer, CE and Roy, DM (2011) Noncomputable conditional distributions. Proceedings - Symposium on Logic in Computer Science. pp. 107-116. ISSN 1043-6871

Full text not available from this repository.


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. © 2011 IEEE.

Item Type: Article
Divisions: Div F > Computational and Biological Learning
Depositing User: Unnamed user with email
Date Deposited: 16 Jul 2015 13:08
Last Modified: 30 Nov 2015 07:11
DOI: 10.1109/LICS.2011.49