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

DOI10.1214/105051607000000078zbMATH Open1131.60067OpenAlexW2100410713MaRDI QIDQ2467601FDOQ2467601

Authors Vladislav Kargin

Publication date 28 January 2008

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0508538

zbMATH Keywords

Markov chainlarge deviationsspectral gapBernstein inequalityHoeffding inequality

Mathematics Subject Classification ID

Large deviations (60F10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

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.

Recommendations

• Large deviations for vector-valued functionals of a Markov chain: Lower bounds
• scientific article; zbMATH DE number 4117550
• scientific article; zbMATH DE number 168146
• A deviation inequality for non-reversible Markov processes
• Large Deviation Bounds for Markov Chains
• A probability inequality for the occupation measure of a reversible Markov chain
• scientific article; zbMATH DE number 2076269

Cites work

• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• scientific article; zbMATH DE number 3533576 (Why is no real title available?)
• scientific article; zbMATH DE number 2042290 (Why is no real title available?)
• A Convexity Property in the Theory of Random Variables Defined on a Finite Markov Chain
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A probability inequality for the occupation measure of a reversible Markov chain
• An Extension of S. N. Bernstein’s Inequalities to Multidimensional Distributions
• An Extremal Problem in Probability Theory
• Asymptotic evaluation of certain markov process expectations for large time, II
• Chernoff-type bound for finite Markov chains
• On an Infinite-Dimensional Version of S. N. Bernstein’s Inequalities
• Probability Inequalities for Sums of Bounded Random Variables
• Probability Inequalities for the Sum of Independent Random Variables
• Some dimension-free features of vector-valued martingales

Cited in

(7)

• A probability inequality for the occupation measure of a reversible Markov chain
• A martingale minimax exponential inequality for Markov chains
• Tail Estimates for Sums of Variables Sampled by a Random Walk
• Concentration of Markov chains with bounded moments
• Large deviations for correlated random variables described by a matrix product ansatz
• Large deviations and full Edgeworth expansions for finite Markov chains with applications to the analysis of genomic sequences
• A deviation inequality for non-reversible Markov processes

This page was built for publication: A large deviation inequality for vector functions on finite reversible Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2467601)