Chernoff-type bound for finite Markov chains
From MaRDI portal
Publication:1296608
DOI10.1214/aoap/1028903453zbMath0938.60027OpenAlexW1985380836MaRDI QIDQ1296608
Publication date: 2 August 1999
Published in: The Annals of Applied Probability (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1214/aoap/1028903453
Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Large deviations (60F10)
Related Items (40)
Scalable estimation of epidemic thresholds via node sampling ⋮ Optimal Hoeffding bounds for discrete reversible Markov chains. ⋮ Chernoff and Berry–Esséen inequalities for Markov processes ⋮ Exponential inequalities and functional central limit theorems for random fields ⋮ A Hoeffding inequality for Markov chains ⋮ Adaptive Huber regression on Markov-dependent data ⋮ Random enriched trees with applications to random graphs ⋮ Fixed Precision MCMC Estimation by Median of Products of Averages ⋮ Transport-information inequalities for Markov chains ⋮ Mixing of the upper triangular matrix walk ⋮ A new Poisson-type deviation inequality for Markov jump processes with positive Wasserstein curvature ⋮ Curvature, concentration and error estimates for Markov chain Monte Carlo ⋮ On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting? ⋮ Multiple random walks on graphs: mixing few to cover many ⋮ Concentration inequalities for output statistics of quantum Markov processes ⋮ Hoeffding's inequality for non-irreducible Markov models ⋮ Large and moderate deviations for bounded functions of slowly mixing Markov chains ⋮ Tail Estimates for Sums of Variables Sampled by a Random Walk ⋮ Chen-Stein method for the uncovered set of random walk on \(\mathbb{Z}_n^d\) for \(d \ge 3\) ⋮ Splitting fields of characteristic polynomials of random elements in arithmetic groups ⋮ Unnamed Item ⋮ Mod-ϕ Convergence, II: Estimates on the Speed of Convergence ⋮ Hoeffding's inequalities for geometrically ergodic Markov chains on general state space ⋮ Function-specific mixing times and concentration away from equilibrium ⋮ Concentration of Markov chains with bounded moments ⋮ A nonconventional local limit theorem ⋮ The worm process for the Ising model is rapidly mixing ⋮ A large deviation inequality for vector functions on finite reversible Markov chains ⋮ On the CLT for rotations and BV functions ⋮ Fast Low-Cost Estimation of Network Properties Using Random Walks ⋮ General Bernstein-like inequality for additive functionals of Markov chains ⋮ Sensor networks: from dependence analysis via matroid bases to online synthesis ⋮ Hoeffding's inequality for Markov processes via solution of Poisson's equation ⋮ The Littlewood-Offord problem for Markov chains ⋮ Graph limits of random graphs from a subset of connected k‐trees ⋮ Generalized high-dimensional trace regression via nuclear norm regularization ⋮ Uniform Chernoff and Dvoretzky-Kiefer-Wolfowitz-type inequalities for Markov chains and related processes ⋮ Approximate \(p\)-values for local sequence alignments. ⋮ Unnamed Item ⋮ On efficient randomized algorithms for finding the PageRank vector
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process
- Comparison theorems for reversible Markov chains
- A probability inequality for the occupation measure of a reversible Markov chain
- Logarithmic Sobolev inequalities for finite Markov chains
- On the Product of Semi-Groups of Operators
- On Deviations of the Sample Mean
- Probability Inequalities for the Sum of Independent Random Variables
- On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated Annealing
- More Exact Statement of Limit Theorems for Homogeneous Markov Chains
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Inequalities: theory of majorization and its applications
This page was built for publication: Chernoff-type bound for finite Markov chains
