Tail estimates for sums of variables sampled from a random walk

Roy Wagner

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…