A large deviation inequality for vector functions on finite reversible Markov chains

Vladislav Kargin

doi:10.1214/105051607000000078

A large deviation inequality for vector functions on finite reversible Markov chains

Vladislav Kargin

Mathematics and Statistics

Binghamton University

Research output: Contribution to journal › Article › peer-review

6 Scopus citations

Abstract

Let S_N be the sum of vector-valued functions defined on a finite Markov chain. An analogue of the Bernstein-Hoeffding inequality is derived for the probability of large deviations of S_N and relates the probability to the spectral gap of the Markov chain. Examples suggest that this inequality is better than alternative inequalities if the chain has a sufficiently large spectral gap and the function is high-dimensional.

Original language	English
Pages (from-to)	1202-1221
Number of pages	20
Journal	Annals of Applied Probability
Volume	17
Issue number	4
DOIs	https://doi.org/10.1214/105051607000000078
State	Published - 2007

Keywords

Bernstein inequality
Hoeffding inequality
Large deviations
Markov chain
Spectral gap

Access to Document

10.1214/105051607000000078

Cite this

@article{e85c8680304c48bfae794898384567c1,

title = "A large deviation inequality for vector functions on finite reversible Markov chains",

abstract = "Let SN be the sum of vector-valued functions defined on a finite Markov chain. An analogue of the Bernstein-Hoeffding inequality is derived for the probability of large deviations of SN and relates the probability to the spectral gap of the Markov chain. Examples suggest that this inequality is better than alternative inequalities if the chain has a sufficiently large spectral gap and the function is high-dimensional.",

keywords = "Bernstein inequality, Hoeffding inequality, Large deviations, Markov chain, Spectral gap",

author = "Vladislav Kargin",

year = "2007",

doi = "10.1214/105051607000000078",

language = "English",

volume = "17",

pages = "1202--1221",

journal = "Annals of Applied Probability",

issn = "1050-5164",

publisher = "Institute of Mathematical Statistics",

number = "4",

}

TY - JOUR

T1 - A large deviation inequality for vector functions on finite reversible Markov chains

AU - Kargin, Vladislav

PY - 2007

Y1 - 2007

N2 - Let SN be the sum of vector-valued functions defined on a finite Markov chain. An analogue of the Bernstein-Hoeffding inequality is derived for the probability of large deviations of SN and relates the probability to the spectral gap of the Markov chain. Examples suggest that this inequality is better than alternative inequalities if the chain has a sufficiently large spectral gap and the function is high-dimensional.

AB - Let SN be the sum of vector-valued functions defined on a finite Markov chain. An analogue of the Bernstein-Hoeffding inequality is derived for the probability of large deviations of SN and relates the probability to the spectral gap of the Markov chain. Examples suggest that this inequality is better than alternative inequalities if the chain has a sufficiently large spectral gap and the function is high-dimensional.

KW - Bernstein inequality

KW - Hoeffding inequality

KW - Large deviations

KW - Markov chain

KW - Spectral gap

UR - https://www.scopus.com/pages/publications/39449109688

U2 - 10.1214/105051607000000078

DO - 10.1214/105051607000000078

M3 - Article

SN - 1050-5164

VL - 17

SP - 1202

EP - 1221

JO - Annals of Applied Probability

JF - Annals of Applied Probability

IS - 4

ER -

A large deviation inequality for vector functions on finite reversible Markov chains

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this