Hoeffding's inequality for uniformly ergodic Markov chains

被引：85

作者：

Glynn, PW

Ormoneit, D

机构：

[1] Stanford Univ, Dept Management Sci & Engn, Stanford, CA 94305 USA

[2] Stanford Univ, Dept Comp Sci, Stanford, CA 94305 USA

来源：

STATISTICS & PROBABILITY LETTERS | 2002年 / 56卷 / 02期

关键词：

Hoeffding's inequality; Markov chains; large deviations;

D O I：

10.1016/S0167-7152(01)00158-4

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

We provide a generalization of Hoeffding's inequality to partial sums that are derived from a uniformly ergodic Markov chain. Our exponential inequality on the deviation of these sums from their expectation is particularly useful in situations where we require uniform control on the constants appearing in the bound. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：143 / 146

页数：4

共 11 条

[1]

[Anonymous], 1992, Stochastic Stability of Markov chains

[2]

Asmussen S., 1992, ACM Transactions on Modeling and Computer Simulation, V2, P130, DOI 10.1145/137926.137932

[3]

Azuma K., 1967, TOHOKU MATH J, V19, P357, DOI DOI 10.2748/TMJ/1178243286

[4] Multiplicative ergodicity and large deviations for an irreducible Markov chain [J].

Balaji, S ;

Meyn, SP .

STOCHASTIC PROCESSES AND THEIR APPLICATIONS, 2000, 90 (01) :123-144

[5]

Devroye L., 1996, A probabilistic theory of pattern recognition

[6]

Doob J. L., 1953, Stochastic processes, V101

[7] PROBABILITY-INEQUALITIES FOR SUMS OF BOUNDED RANDOM-VARIABLES [J].

HOEFFDING, W .

JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 1963, 58 (301) :13-+

[8]

ORMONEIT D, 2001, IN PRESS IEEE T OPTI

[9]

PUTEMAN ML, 1994, MARKOV DECISION PROC

[10]

ROSENTHAL JS, 1992, RATES CONVERGENCE GI

← 1 2 →