Google Research

Studies in Lower Bounding Probability of Evidence using the Markov Inequality

  • Vibhav Gogate
  • Bozhena Bidyuk
  • Rina Dechter
UAI, Morgan Kaufmann (2007)


Computing the probability of evidence even with known error bounds is NP-hard. In this paper we address this hard problem by settling on an easier problem. We propose an approximation that provides high confidence lower bounds on probability of evidence. Our proposed approximation is a randomized importance sampling based scheme that uses the Markov inequality. However, a straight-forward application of the Markov inequality may lead to poor lower bounds. We, therefore propose several heuristic measures to improve its performance in practice. Empirical evaluation of our scheme with state-of-the-art lower bounding schemes reveals the promise of our approach.

Research Areas

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work