Rigorous confidence bounds for MCMC under a geometric drift condition (Q617654)

A Markov Chain Monte Carlo (MCMC) approximation \(\hat I_{t,n}(f)={1\over n}\sum_{i=t}^{t+n-1}f(X_i)\) is considered for \(I(f)=\int f(x)\pi(dx)\), where \(X_i\) is a Markov chain with a transition kernel \(P\) and the stationary distribution \(\pi\), \(t\) is the burn-in time. The authors derive explicit lower bounds for \(n\) and \(t\) that ensure the condition \(\Pr(|\hat I_{t,n}(f)-I(f)|\leq\varepsilon)\geq 1-\alpha\) for given \(\varepsilon\) and \(\alpha\). The bounds are given in terms of a drift condition towards a small set on the chain and in terms of the \(V\)-norm \(|\cdot|_V\) of the function \(f-I(f)\), where \(V\) is the drift function and \(|g|_V=\sup_x |g(x)|/V(x)\). In fact, some bounds are obtained for the mean square error of \(\hat I_{t,n}(f)\) and then Chebyshev's inequality is used to derive the desired estimates for the probabilities. The so called ``median trick'' is considered to minimize the computational cost. In this technique \(m\) independent copies of \(\hat I_{t,n}\) are simulated and their median is used as an estimate for \(I(f)\). A ``contracting normals'' example is investigated numerically in which e.g. for \(\varepsilon=0.1\), \(\alpha=10^{-3}\) the authors obtained the estimates \(m=15\), \(n=5.4\cdot 10^9\), \(t=218\). It is noted that in real simulations it was enough to let \(m=7\), \(t=0\), \(n=726\), so the obtained bounds are ``admittedly conservative''.