Large deviation asymptotics and control variates for simulating large functions

Abstract

Consider the normalized partial sums of a real-valued function $F$ of a Markov chain, \[ϕ_n:=n^{-1}\sum_{k=0}^{n-1}F(Φ(k)),\qquad n\ge1.\] The chain $\{\Phi (k):k\ge 0\}$ takes values in a general state space $\mathsf{X}$, with transition kernel $P$, and it is assumed that the Lyapunov drift condition holds: $PV\le V-W+b{\mathbb{I}}_C$ where $V:\mathsf{X}\to (0,\infty )$, $W:\mathsf{X}\to [1,\infty )$, the set $C$ is small and $W$ dominates $F$. Under these assumptions, the following conclusions are obtained: 1. It is known that this drift condition is equivalent to the existence of a unique invariant distribution $\pi$ satisfying $\pi (W)<\infty$, and the law of large numbers holds for any function $F$ dominated by $W$: \[ϕ_n\toϕ:=π(F),\qquad{a.s.}, n\to\infty.\] 2. The lower error probability defined by $\mathsf{P}\{{\varphi }_n\le c\}$, for $c<\varphi$, $n\ge 1$, satisfies a large deviation limit theorem when the function $F$ satisfies a monotonicity condition. Under additional minor conditions an exact large deviations expansion is obtained. 3. If $W$ is near-monotone, then control-variates are constructed based on the Lyapunov function $V$, providing a pair of estimators that together satisfy nontrivial large asymptotics for the lower and upper error probabilities. In an application to simulation of queues it is shown that exact large deviation asymptotics are possible even when the estimator does not satisfy a central limit theorem.

Published at http://dx.doi.org/10.1214/105051605000000737 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• Fluctuations of the Entropy Production in Anharmonic Chains

Cited by in corpus (8)

• Linear Variance Bounds for Particle Approximations of Time-Homogeneous Feynman-Kac Formulae
• The ODE method for stability of skip-free Markov chains with applications to MCMC
• Most likely paths to error when estimating the mean of a reflected random walk
• On the tail asymptotics of the area swept under the Brownian storage graph
• Exponential transform of quadratic functional and multiplicative ergodicity of a Gauss-Markov process
• Control Variates for Reversible MCMC Samplers
• Variance Reduction in Simulation of Multiclass Processing Networks
• Tail behaviour of the area under a random process, with applications to queueing systems, insurance and percolations