Large deviation asymptotics and control variates for simulating large functions

Details Large deviation asymptotics and control variates for simulating large functions Large deviation asymptotics and control variates for simulating large functions

2006-03-14

arxiv.org/abs/math/0603328v1

Annals of Applied Probability 2006, Vol. 16, No. 1, 310-339

Mathematics

Probability

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

Scientific paper

10.1214/105051605000000737

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 $\{\Phi(k):k\ge0\}$ 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$: \[\phi_n\to\phi:=\pi(F),\qquad{a.s.}, n\to\infty.\] 2. The lower error probability defined by $\mathsf {P}\{\phi_n\le c\}$, for $c<\phi$, $n\ge1$, 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.

Affiliated with

Also associated with

No associations

Rating

Large deviation asymptotics and control variates for simulating large functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Large deviation asymptotics and control variates for simulating large functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Large deviation asymptotics and control variates for simulating large functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-704773