Large deviation asymptotics and control variates for simulating large functions

DOI10.1214/105051605000000737zbMATH Open1094.60017arXivmath/0603328OpenAlexW2122551798MaRDI QIDQ2494582FDOQ2494582

Authors: Sean P. Meyn 

Publication date: 29 June 2006

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

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.

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

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

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)

Cites Work

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