Studies in Lower Bounding Probabilities of Evidence using the Markov
  Inequality
  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 which provides high confidence lower
bounds on probability of evidence but does not have any guarantees in terms of
relative or absolute error. Our proposed approximation is a randomized
importance sampling 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.
