
Open access
Author
Date
2008-03Type
- Journal Article
ETH Bibliography
no
Altmetrics
Abstract
We prove tail estimates for variables of the form P i f(Xi), where (Xi)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 subgaussian variables. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000121661Publication status
publishedExternal links
Journal / series
Combinatorics, Probability & ComputingVolume
Pages / Article No.
Publisher
Cambridge University PressOrganisational unit
09591 - Wagner, Roy / Wagner, Roy
Notes
Note: there is a stupid typo in the journal version of theorem 2. Published online 1 March 2008More
Show all metadata
ETH Bibliography
no
Altmetrics