A Chernoff Bound for Random Walks on Expander Graphs

DOI10.1137/S0097539794268765MaRDI QIDQ4210091zbMATHOpenAlexWikidataFDO

Authors David Gillman

Publication date 20 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539794268765

zbMATH Keywords

graphentropyrandom walkmatchinglarge deviationseigenvaluepartition functionapproximate countingIsing systemexpanderMarkov source

Mathematics Subject Classification ID

Markov processes: estimation; hidden Markov models (62M05) Large deviations (60F10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Analysis of algorithms and problem complexity (68Q25) Source coding (94A29)

Recommendations

• scientific article; zbMATH DE number 878897
• Tail Estimates for Sums of Variables Sampled by a Random Walk
• A matrix expander Chernoff bound
• On sampling with Markov chains

Cited in

(43)

• Fixed Precision MCMC Estimation by Median of Products of Averages
• The Swendsen–Wang dynamics on trees
• Mixing time estimation in reversible Markov chains from a single sample path
• Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications
• Finding large expanders in graphs: from topological minors to induced subgraphs
• Random walks on rotating expanders
• Random walks on hyperbolic spaces: concentration inequalities and probabilistic Tits alternative
• Optimal Hoeffding bounds for discrete reversible Markov chains.
• The Littlewood-Offord problem for Markov chains
• An introduction to randomness extractors
• A Hoeffding inequality for Markov chains
• A local central limit theorem for random walks on expander graphs
• Tail Estimates for Sums of Variables Sampled by a Random Walk
• Occupation measure for random walk on the circle
• Concentration of Markov chains with bounded moments
• Mixing of the upper triangular matrix walk
• Cutoff for random walk on dynamical Erdős-Rényi graph
• Logarithmic reduction of the level of randomness in some probabilistic geometric constructions
• Estimating graph parameters with random walks
• Function-specific mixing times and concentration away from equilibrium
• A matrix expander Chernoff bound
• Local correctability of expander codes
• Expander graphs and their applications
• Approach to equilibrium for random walks on graphs and for stochastic infinite particle processes
• Linear cover time is exponentially unlikely
• Approximate and dynamic rank aggregation
• Nonasymptotic bounds on the estimation error of MCMC algorithms
• scientific article; zbMATH DE number 7758327 (Why is no real title available?)
• Cover time of a random graph with a degree sequence. II: Allowing vertices of degree two.
• Deterministic approximation of random walks in small space
• Uniform Chernoff and Dvoretzky-Kiefer-Wolfowitz-type inequalities for Markov chains and related processes
• Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds
• scientific article; zbMATH DE number 7650126 (Why is no real title available?)
• The worm process for the Ising model is rapidly mixing
• Testing the \((s,t)\) connectivity of graphs and digraphs
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Distributed protocols against mobile eavesdroppers
• Efficient Simulation of High Dimensional Gaussian Vectors
• DEX: self-healing expanders
• Imperfect gaps in Gap-ETH and PCPs
• Rigorous confidence bounds for MCMC under a geometric drift condition
• Typically-correct derandomization for small time and space
• On sufficient conditions for spanning structures in dense graphs

This page was built for publication: A Chernoff Bound for Random Walks on Expander Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210091)