A Chernoff bound for random walks on expander graphs
- 30 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 680-691
- https://doi.org/10.1109/sfcs.1993.366819
Abstract
We consider a finite random walk on a weighted graph G; we show that the sample average of visits to a set of vertices A converges to the stationary probability /spl pi/(A) with error probability exponentially small in the length of the random walk and the square of the size of the deviation from /spl pi/(A). The exponential bound is in terms of the expansion of G and improves previous results. We show that the method of taking the sample average from one trajectory is a more efficient estimate of /spl pi/(A) than the standard method of generating independent sample points from several trajectories. Using this more efficient sampling method, we improve the algorithms of Jerrum and Sinclair (1989) for approximating the number of perfect matchings in a dense graph and for approximating the partition function of an Ising system. We also give a fast estimate of the entropy of a random walk on an unweighted graph.Keywords
This publication has 25 references indexed in Scilit:
- Eigenvalue Bounds on Convergence to Stationarity for Nonreversible Markov Chains, with an Application to the Exclusion ProcessThe Annals of Applied Probability, 1991
- Approximate counting, uniform generation and rapidly mixing Markov chainsInformation and Computation, 1989
- A random polynomial time algorithm for approximating the volume of convex bodiesPublished by Association for Computing Machinery (ACM) ,1989
- Dispersers, deterministic amplification, and weak random sourcesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Limit Theorems for Harris Markov Chains, ITheory of Probability and Its Applications, 1987
- How hard is it to marry at random? (On the approximation of the permanent)Published by Association for Computing Machinery (ACM) ,1986
- Large deviations, hypotheses testing, and source coding for finite Markov chainsIEEE Transactions on Information Theory, 1985
- Explicit Concentrators from Generalized N-GonsSIAM Journal on Algebraic Discrete Methods, 1984
- On the Computation of Multidimensional Integrals by the Monte-Carlo MethodTheory of Probability and Its Applications, 1971
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952