Consider the normalized partial sums of a real-valued function F of a Markov chain,
¶
\[\phi_{n}:=n^{-1}\sum_{k=0}^{n-1}F(\Phi(k)),\qquad n\ge1.\]
¶
The chain {Φ(k):k≥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\dvtx \mathsf {X}\to(0,\infty)$ , $W\dvtx \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 π satisfying π(W)<∞, and the law of large numbers holds for any function F dominated by W:
¶
ϕn→ϕ:=π(F), a.s., n→∞.
¶
2. The lower error probability defined by $\mathsf {P}\{\phi_{n}\le c\}$ , for c<ϕ, n≥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.