Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T16:39:05.270Z Has data issue: false hasContentIssue false

Asymptotic conditional probabilities: The non-unary case

Published online by Cambridge University Press:  12 March 2014

Adam J. Grove
Affiliation:
Nec Research Institute, 4 Independence Way, Princeton, NJ 08540, E-mail: grove@research.nj.nec.com
Joseph Y. Halpern
Affiliation:
IBM Almaden Research Center, 650 Harry RD., San Jose, CA 95120, E-mail: halpern@almaden.ibm.com
Daphne Koller
Affiliation:
Department of Computer Science, Stanford University, Stanford, CA 94305, E-mail: daphne@cs.stanford.edu

Abstract

Motivated by problems that arise in computing degrees of belief, we consider the problem of computing asymptotic conditional probabilities for first-order sentences. Given first-order sentences φ and θ, we consider the structures with domain {1, …, N} that satisfy θ, and compute the fraction of them in which φ is true. We then consider what happens to this fraction as N gets large. This extends the work on 0-1 laws that considers the limiting probability of first-order sentences, by considering asymptotic conditional probabilities. As shown by Liogon'kiĭ [24], if there is a non-unary 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. Liogon'kiĭ 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 well-defined, 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.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1996

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.)

Article purchase

Temporarily unavailable