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

DOI10.1214/105051607000000078zbMATH Open1131.60067arXivmath/0508538OpenAlexW2100410713MaRDI QIDQ2467601FDOQ2467601

Vladislav Kargin

Publication date: 28 January 2008

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

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.

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

Recommendations

• Large deviations for vector-valued functionals of a Markov chain: Lower bounds
• scientific article; zbMATH DE number 4117550
• scientific article
• 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

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)

Cites Work

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

Cited In (7)

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

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)