My home page
My group
Professional activities

Daphne Koller Publications

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 first-order sentences. Given first-order 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 0-1 laws that considers the limiting probability of first-order sentences, by considering asymptotic conditional probabilities. As shown by Liogonkii, 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. 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 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.

Download Information

A.J. Grove, J.Y. Halpern, and D. Koller (1996). "Asymptotic conditional probabilities: The unary case." SIAM Journal on Computing, 25(1), 1-51. Full version of paper in STOC '92. pdf ps.gz

Bibtex citation

  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 = {1--51},
  note = {Full version of paper in STOC '92},

full list
Click to go to robotics Click to go to theory Click to go to CS Stanford Click to go to Stanford's Webpage
home | biography | research | papers | my group
courses | professional activities | FAQ | personal