Unbiased Time-Average Estimators for Markov Chains

We consider a time-average estimator f_k of a functional of a Markov chain. Under a coupling assumption, we show that the expectation of f_k has a limit μ as the number of time steps goes to infinity. We describe a modification of f_k that yields an unbiased estimator ${\widehat{f}}_k$ of μ. It is shown that ${\widehat{f}}_k$ is square integrable and has finite expected running time. Under certain conditions, ${\widehat{f}}_k$ can be built without any precomputations and is asymptotically at least as efficient as f_k, up to a multiplicative constant arbitrarily close to one. Our approach also provides an unbiased estimator for the bias of f_k. We study applications to volatility forecasting, queues, and the simulation of high-dimensional Gaussian vectors. Our numerical experiments are consistent with our theoretical findings.