A Chernoff Bound for Random Walks on Expander Graphs
- 1 August 1998
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 27 (4), 1203-1220
- https://doi.org/10.1137/s0097539794268765
Abstract
No abstract availableThis publication has 20 references indexed in Scilit:
- Expectations for Nonreversible Markov ChainsJournal of Mathematical Analysis and Applications, 1998
- A Probability Inequality for the Occupation Measure of a Reversible Markov ChainThe Annals of Applied Probability, 1995
- Eigenvalue Bounds on Convergence to Stationarity for Nonreversible Markov Chains, with an Application to the Exclusion ProcessThe Annals of Applied Probability, 1991
- A large deviations approach to error exponents in source coding and hypothesis testingIEEE Transactions on Information Theory, 1990
- Finite-time implications of relaxation times for stochastically monotone processesProbability Theory and Related Fields, 1988
- On the Markov Chain Simulation Method for Uniform Combinatorial Distributions and Simulated AnnealingProbability in the Engineering and Informational Sciences, 1987
- Eigenvalues and expandersCombinatorica, 1986
- λ1, Isoperimetric inequalities for graphs, and superconcentratorsJournal of Combinatorial Theory, Series B, 1985
- Central limit theorems and statistical inference for finite Markov chainsProbability Theory and Related Fields, 1974
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952