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

• 成果类型: Article
• 署名作者: Kargin, Vladislav
• 署名单位: New York University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/105051607000000078
• 发表日期: 2007
• 页码: 1202-1221
• 关键词: random-variables; probability-inequalities; asymptotic evaluation; process expectations; large time

摘要

Let S-N be the sum of vector-valued functions defined on a finite Markov chain. An analogue of the Bemstein-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.