Large deviation asymptotics and control variates for simulating large functions

• 成果类型: Article
• 署名作者: Meyn, SP
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/105051605000000737
• 发表日期: 2006
• 页码: 310-339
• 关键词: markov process expectations; additive-functionals; queuing-networks; SPECTRAL THEORY; LIMIT-THEOREMS; Lower bounds; time; CONVERGENCE; STABILITY

摘要

Consider the normalized partial sums of a real-valued function F of a Markov chain. [GRAPHICS] The chain {phi(k):k >= 0} takes values in a general state space X, with transition kernel P, and it is assumed that the Lyapunov drift condition holds: PV <= V - W + bII(C) where V : X -> (0, infinity). W : X -> [1. infinity]. 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) < infinity, and the law of large numbers holds for any function F dominated by W: phi(n) -> phi: = pi(F). a.s., n -> infinity. 2. The lower error probability defined by P{phi(n) <= c}, for c < phi, n >= 1, satisfies a large deviation limit theorem when the function F satisfies it 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 it 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 it central limit theorem.