Efficient shape-constrained inference for the autocovariance sequence from a reversible Markov chain

In this paper, we study the problem of estimating the autocovariance sequence resulting from a reversible Markov chain. A motivating application for studying this problem is the estimation of the asymptotic variance in central limit theorems for Markov chains. The asymptotic variance quantifies uncertainties in averages of the form $M^{-1}\sum_{t=0}^{M-1}g(X_t)$, where $X_0,X_1,...$ are iterates from a Markov chain. It is well known that the autocovariances from reversible Markov chains can be represented as the moments of a unique positive measure supported on $[-1,1]$. We propose a novel shape-constrained estimator of the autocovariance sequence. Our approach is based on the key observation that the representability of the autocovariance sequence as a moment sequence imposes certain shape constraints, which we can exploit in the estimation procedure. We examine the theoretical properties of the proposed estimator and provide strong consistency guarantees for our estimator. In particular, for reversible Markov chains satisfying a geometric drift condition, we show that our estimator is strongly consistent for the true autocovariance sequence with respect to an $\ell_2$ distance, and that our estimator leads to strongly consistent estimates of the asymptotic variance. Finally, we perform empirical studies to illustrate the theoretical properties of the proposed estimator as well as to demonstrate the effectiveness of our estimator in comparison with other current state-of-the-art methods for Markov chain Monte Carlo variance estimation, including batch means, spectral variance estimators, and the initial convex sequence estimator.