  Markov chain (MC) algorithms are ubiquitous in machine learning and
statistics and many other disciplines. Typically, these algorithms can be
formulated as acceptance rejection methods. In this work we present a novel
estimator applicable to these methods, dubbed Markov chain importance sampling
(MCIS), which efficiently makes use of rejected proposals. For the unadjusted
Langevin algorithm, it provides a novel way of correcting the discretization
error. Our estimator satisfies a central limit theorem and improves on error
per CPU cycle, often to a large extent. As a by-product it enables estimating
the normalizing constant, an important quantity in Bayesian machine learning
and statistics.
