Large deviation asymptotics and control variates for simulating large functions
type: Item
instance of: scholarly article
title: Large deviation asymptotics and control variates for simulating large functions
zbMATH Open document ID: 1094.60017
DOI: 10.1214/105051605000000737
published in: The Annals of Applied Probability
publication date: 2006-06-29T00:00:00Z
full work available at URL: https://arxiv.org/abs/math/0603328
review text: The author considers the normalized partial sums of a real-valued function \(F\) of a Markov chain, \[ \varphi_n:=n^{-1}\sum_{k=0}^{n-1} F(\Phi{(k)}),\qquad n\geq1. \] The chain \(\Phi(k)\), \({k\geq0}\), takes values in a general state space \(X\), with transition kernel \(P\), and it is assumed that the Lyapunov drift condition holds: \(PV\leq V-W+bI_C\) where \(V:X\rightarrow(0,\infty)\), \(W:X\rightarrow[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: \varphi_n\rightarrow\varphi:=\pi(F)\) as \(n\rightarrow{\infty}.\) 2. The lower error probability defined by \(P \varphi_n\leq c\), for \(c<\varphi, n\geq{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.
Mathematics Subject Classification ID: 60F10
Mathematics Subject Classification ID: 60J22
Mathematics Subject Classification ID: 60K35
Mathematics Subject Classification ID: 65C05
zbMATH DE Number: 5036883
zbMATH Keywords: Monte Carlo methods
zbMATH Keywords: ergodic theorems
zbMATH Keywords: Markov operators
zbMATH Keywords: spectral theory
author: Sean P. Meyn
reviewed by: Zdzisław Rychlik
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W2122551798
arXiv ID: math/0603328
cites work: Q3026011
cites work: On Deviations of the Sample Mean
cites work: Multiplicative ergodicity and large deviations for an irreducible Markov chain.
cites work: Strong large deviation and local limit theorems
cites work: In search of sensitivity in network optimization
cites work: Stability and convergence of moments for multiclass queueing networks via fluid limit models
cites work: A Fluid Heuristic for Minimizing Makespan in Job Shops
cites work: Large deviations for empirical measures of Markov chains
cites work: Large deviation lower bounds for arbitrary additive functionals of a Markov chain
cites work: On the Approximation of Complicated Dynamical Behavior
cites work: Q4391441
cites work: Q4692653
cites work: Asymptotic evaluation of certain markov process expectations for large time, II
cites work: Asymptotic evaluation of certain Markov process expectations for large time—III
cites work: Asymptotic evaluation of certain markov process expectations for large time. IV
cites work: Large deviations for products of empirical measures of dependent sequences
cites work: Q4433608
cites work: Q4549489
cites work: Some topics in regenerative steady-state simulation
cites work: A Liapounov bound for solutions of the Poisson equation
cites work: Hoeffding's inequality for uniformly ergodic Markov chains
cites work: Necessary conditions in limit theorems for cumulative processes.
cites work: On the central limit theorem for geometrically ergodic Markov chains
cites work: Approximating Martingales for Variance Reduction in Markov Process Simulation
cites work: Performance evaluation and policy selection in multiclass networks
cites work: On ergodicity and recurrence properties of a Markov chain by an application to an open jackson network
cites work: Large deviation lower bounds for additive functionals of Markov processes
cites work: Q3711415
cites work: Inequalities in Theorems of Ergodicity and Stability for Markov Chains with Common Phase Space. I
cites work: Spectral theory and limit theorems for geometrically ergodic Markov processes
cites work: Large deviations asymptotics and the spectral theory of multiplicatively regular Markov proces\-ses
cites work: Duality and linear programs for stability and performance analysis of queuing networks and scheduling policies
cites work: Q3951448
cites work: Workload models for stochastic networks: value functions and performance evaluation
cites work: Markov chains and stochastic stability
cites work: Computable bounds for geometric convergence rates of Markov chains
cites work: Control Variate Remedies
cites work: Markov additive processes. I: Eigenvalue properties and limit theorems
cites work: Markov additive processes. II: Large deviations
cites work: General Irreducible Markov Chains and Non-Negative Operators
cites work: Worst-case large-deviation asymptotics with application to queueing and information theory
cites work: Fluctuations of the entropy production in anharmonic chains
cites work: An introduction to the theory of large deviations
cites work: Large deviations and applications
cites work: Q5751666
cites work: Essential spectral radius for Markov semigroups. I: Discrete time case
description: scientific article