Tail Estimates for Sums of Variables Sampled by a Random Walk

Source abstract

We prove tail estimates for variables of the form ∑ i f ( X i ), where ( X i ) i is a sequence of states drawn from a reversible Markov chain, or, equivalently, from a random walk on an undirected graph. The estimates are in terms of the range of the function f , its variance, and the spectrum of the graph. The purpose of our estimates is to determine the number of chain/walk samples which are required for approximating the expectation of a distribution on vertices of a graph, especially an expander. The estimates must therefore provide information for fixed number of samples (as in Gillman's [4]) rather than just asymptotic information. 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 sub-Gaussian variables.