Large deviation asymptotics and control variates for simulating large functions

DOI10.1214/105051605000000737MaRDI QIDQ2494582zbMATH OpenOpenAlexFDO

Authors Sean P. Meyn

Publication date 29 June 2006

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0603328

zbMATH Keywords

Monte Carlo methodsspectral theoryergodic theoremsMarkov operators

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Monte Carlo methods (65C05) Large deviations (60F10) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: 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 nge1.] The chain $Phi(k):kge0$ takes values in a general state space $mathsfX$, with transition kernel $P$, and it is assumed that the Lyapunov drift condition holds: $PVleV-W+bmathbb{I}_C$ where $V:mathsfXo(0,infty)$, $W:mathsfXo[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 ophi:=pi(F),qquad{a.s.}, n oinfty.] 2. The lower error probability defined by $mathsfPph{i}_{n}lec$, for $c<phi$, $nge1$, 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.

Recommendations

• Large deviations for additive functionals of Markov chains
• Nonconventional large deviations theorems
• Large deviations for sums of random variables related to a chain
• Large deviations for sums of random variables connected into a Markov chain in approximation by Poisson law
• scientific article; zbMATH DE number 599147

Cites work

• scientific article; zbMATH DE number 4013703 (Why is no real title available?)
• scientific article; zbMATH DE number 3940343 (Why is no real title available?)
• scientific article; zbMATH DE number 3770836 (Why is no real title available?)
• scientific article; zbMATH DE number 1158743 (Why is no real title available?)
• scientific article; zbMATH DE number 1999206 (Why is no real title available?)
• scientific article; zbMATH DE number 1790424 (Why is no real title available?)
• scientific article; zbMATH DE number 194664 (Why is no real title available?)
• scientific article; zbMATH DE number 4186743 (Why is no real title available?)
• A Fluid Heuristic for Minimizing Makespan in Job Shops
• A Liapounov bound for solutions of the Poisson equation
• An introduction to the theory of large deviations
• Approximating Martingales for Variance Reduction in Markov Process Simulation
• Asymptotic evaluation of certain Markov process expectations for large time—III
• Asymptotic evaluation of certain markov process expectations for large time, II
• Asymptotic evaluation of certain markov process expectations for large time. IV
• Computable bounds for geometric convergence rates of Markov chains
• Control Variate Remedies
• Duality and linear programs for stability and performance analysis of queuing networks and scheduling policies
• Essential spectral radius for Markov semigroups. I: Discrete time case
• Fluctuations of the entropy production in anharmonic chains
• General Irreducible Markov Chains and Non-Negative Operators
• Hoeffding's inequality for uniformly ergodic Markov chains
• In search of sensitivity in network optimization
• Inequalities in Theorems of Ergodicity and Stability for Markov Chains with Common Phase Space. I
• Large deviation lower bounds for additive functionals of Markov processes
• Large deviation lower bounds for arbitrary additive functionals of a Markov chain
• Large deviations and applications
• Large deviations asymptotics and the spectral theory of multiplicatively regular Markov proces\-ses
• Large deviations for empirical measures of Markov chains
• Large deviations for products of empirical measures of dependent sequences
• Markov additive processes. I: Eigenvalue properties and limit theorems
• Markov additive processes. II: Large deviations
• Markov chains and stochastic stability
• Multiplicative ergodicity and large deviations for an irreducible Markov chain.
• Necessary conditions in limit theorems for cumulative processes.
• On Deviations of the Sample Mean
• On ergodicity and recurrence properties of a Markov chain by an application to an open jackson network
• On the Approximation of Complicated Dynamical Behavior
• On the central limit theorem for geometrically ergodic Markov chains
• Performance evaluation and policy selection in multiclass networks
• Some topics in regenerative steady-state simulation
• Spectral theory and limit theorems for geometrically ergodic Markov processes
• Stability and convergence of moments for multiclass queueing networks via fluid limit models
• Strong large deviation and local limit theorems
• Workload models for stochastic networks: value functions and performance evaluation
• Worst-case large-deviation asymptotics with application to queueing and information theory

Cited in

(8)

• Exponential transform of quadratic functional and multiplicative ergodicity of a Gauss-Markov process
• On the tail asymptotics of the area swept under the Brownian storage graph
• Large deviations for random dynamical systems and applications to hidden Markov models
• Large deviations for the empirical mean of an M/M/1 queue
• Tail behaviour of the area under a random process, with applications to queueing systems, insurance and percolations
• Linear variance bounds for particle approximations of time-homogeneous Feynman-Kac formulae
• Fundamental design principles for reinforcement learning algorithms
• The ODE method for stability of skip-free Markov chains with applications to MCMC

This page was built for publication: Large deviation asymptotics and control variates for simulating large functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2494582)