Concentration Inequalities for Functionals of Markov Chains With Applications to Variance Reduction

MCMC algorithms (Markov Chain Monte Carlo) find various applications in such fields as Bayesian Statistics and Statistical Physics. This is often the only reasonable method to sample from the distribution of interest, especially in high dimensions. But MCMC algorithms are known to suffer from high variance, hence some variance reduction techniques are called for. One of the natural approaches to variance reduction is to use control functionals, that is, to add variables, negatively correlated with the target one. The main question is how to construct such functionals. In this master thesis the new variance reduction method for Markov Chain Monte Carlo (MCMC) based on control variates is proposed and evaluated. The key concept of the method is to minimize directly some estimate for the asymptotic variance of Markov Chain, which allows to obtain strong theoretical guarantees for wide class of MCMC methods. Concentration inequalities for quadratic forms of Markov Chains, proved in this thesis, play crucial role in the performed analysis. Numerical performance of the algorithm is compared with current state-of-the-art method on different artificial and real-world benchmarks, showing superiority of the proposed method.