Operations Research Seminars Amsterdam

Chang-Han Rhee (CWI Amsterdam)
Thursday, 15 December 2016

Understanding the steady-state distributions of Markov chains is one of the central interests in operations research and Bayesian statistics. In this talk, we discuss a class of Monte Carlo methods, which we call exact estimation algorithms. The new approach provides (exactly) unbiased estimators for steady-state expectations associated with functionals of given Markov chains and provides a significant theoretical relaxation relative to exact sampling methods. We will first review the general principle for generating unbiased estimators when only biased samplers are available, and then discuss its close connection to the standard (biased) multilevel Monte Carlo methods. Then we will show how to apply this principle to constructing unbiased estimators for the class of positive Harris recurrent Markov chains, and for chains that are contracting on average. For positive Harris recurrent Markov chains, we also prove a Glivenko Cantelli type theorem for the new estimators.