Tail estimates for sums of variables sampled from a random walk
Abstract
Description
We prove tail estimates for variables $\sum_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.
V4: published version; theorems 1&2 slightly revised V3: Improved Bennett inequality V2: Corrected version. Confusion concerning definition of $β$ resolved. Results given both in terms of sepctral gap and second largest absolute value of an eigenvalue. Sign error in statement of Theorem 4 corrected. Other minor and cosmetic corrections included as well
V4: published version; theorems 1&2 slightly revised V3: Improved Bennett inequality V2: Corrected version. Confusion concerning definition of $β$ resolved. Results given both in terms of sepctral gap and second largest absolute value of an eigenvalue. Sign error in statement of Theorem 4 corrected. Other minor and cosmetic corrections included as well