A non-asymptotic error analysis for parallel Monte Carlo estimation from many short Markov chains

Abstract Single-chain Markov chain Monte Carlo simulates realizations from a Markov chain to estimate expectations with the empirical average. The single-chain simulation is generally of considerable length and restricts many advantages of modern parallel computation. This paper constructs a novel many-short-chains Monte Carlo (MSC) estimator by averaging over multiple independent sums from Markov chains of a guaranteed short length. The computational advantage is the independent Markov chain simulations can be fast and may be run in parallel, but require a well-designed initial distribution constructed from importance sampling. Alternatively, the MSC estimator introduced here is a method to improve estimation properties in importance sampling by additionally simulating a Markov chain. A non-asymptotic error analysis is developed for the MSC estimator under both geometric and multiplicative drift conditions on the Markov chain that allows a theory for estimation of highly irregular and unbounded functions. Empirical performance is illustrated on an autoregressive process and the Pólya-Gamma Gibbs sampler for Bayesian logistic regression to predict cardiovascular disease.