Tail Estimates for Sums of Variables Sampled by a Random Walk

DOI10.1017/S0963548307008772MaRDI QIDQ3512608zbMATH OpenFDO

Authors Roi Wagner

Publication date 21 July 2008

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Markov processes: estimation; hidden Markov models (62M05)

Abstract: We prove tail estimates for variables $su{m}_{i}f(X_i)$, where $(X_i{)}_i$ is the trajectory of a random walk on an undirected graph (or, equivalently, a reversible Markov chain). The estimates are in terms of the maximum of the function $f$, its variance, and the spectrum of the graph. Our proofs are more elementary than other proofs in the literature, and our results are sharper. We obtain Bernstein and Bennett-type inequalities, as well as an inequality for subgaussian variables.

Recommendations

• Tail probabilities of a random walk on an interval
• Estimates for the tail probability of the supremum of a random walk with independent increments
• Tail asymptotics for the supremum of a random walk when the mean is not finite
• Tail Probabilities of Randomly Weighted Sums of Random Variables with Dominated Variation
• Limit theorems of continuous-time random walks with tails
• Bounds for tail probabilities of the sample variance
• Series of tail distributions of finitely inhomogeneous random walks
• Uniform estimate for the tail probabilities of randomly weighted sums
• On Probabilities of Large Deviations for Random Walks. I. Regularly Varying Distribution Tails
• Tail estimates for one-dimensional random walk in random environment

Cites work

• A Chernoff Bound for Random Walks on Expander Graphs
• A large deviation inequality for vector functions on finite reversible Markov chains
• A probability inequality for the occupation measure of a reversible Markov chain
• Chernoff-type bound for finite Markov chains
• Expander graphs and their applications
• Logarithmic reduction of the level of randomness in some probabilistic geometric constructions
• Optimal Hoeffding bounds for discrete reversible Markov chains.
• Probability Inequalities for the Sum of Independent Random Variables

Cited in

(7)

• Concentration of Markov chains with bounded moments
• A Hoeffding inequality for Markov chains
• A Chernoff Bound for Random Walks on Expander Graphs
• Uniform Chernoff and Dvoretzky-Kiefer-Wolfowitz-type inequalities for Markov chains and related processes
• Fast Low-Cost Estimation of Network Properties Using Random Walks
• scientific article; zbMATH DE number 7758327 (Why is no real title available?)
• Concentration inequalities for sums of Markov-dependent random matrices

This page was built for publication: Tail Estimates for Sums of Variables Sampled by a Random Walk

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