Asymptotic conditional probabilities: The unary case (1996)by A.J. Grove, J.Y. Halpern, and D. Koller
Abstract:
Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for firstorder sentences. Given firstorder sentences phi and theta, we consider the structures with domain {1,...,N} that satisfy theta, and compute the fraction of them in which PHI is true. We then consider what happens to this fraction as N gets large. This extends the work on 01 laws that considers the limiting probability of firstorder sentences, by considering asymptotic conditional probabilities. As shown by Liogonkii, if there is a nonunary predicate symbol in the vocabulary, asymptotic conditional probabilities do not always exist. We extend this result to show that asymptotic conditional probabilities do not always exist for any reasonable notion of limit. Liogonkii also showed that the problem of deciding whether the limit exists is undecidable. We analyze the complexity of three problems with respect to this limit: deciding whether it is welldefined, whether it exists, and whether it lies in some nontrivial interval. Matching upper and lower bounds are given for all three problems, showing them to be highly undecidable.
Download Information
A.J. Grove, J.Y. Halpern, and D. Koller (1996). "Asymptotic conditional probabilities: The unary case." SIAM Journal on Computing, 25(1), 151.
Full version of paper in STOC '92.


Bibtex citation
@article{Grove+al:96a,
title = {Asymptotic conditional probabilities: The unary case},
author = {A.J. Grove and J.Y. Halpern and D. Koller},
journal = {SIAM Journal on Computing},
volume = 25,
number = 1,
month = {February},
year = 1996,
pages = {151},
note = {Full version of paper in STOC '92},
}
full list
