A Chernoff Bound for Random Walks on Expander Graphs

DOI10.1137/S0097539794268765zbMath0911.60016OpenAlexW2139964991WikidataQ29300692 ScholiaQ29300692MaRDI QIDQ4210091

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

entropygrapheigenvaluepartition functionmatchinglarge deviationsrandom walkexpanderapproximate countingIsing systemMarkov source

Mathematics Subject Classification ID

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

Related Items (35)

Optimal Hoeffding bounds for discrete reversible Markov chains. ⋮ Approximate and dynamic rank aggregation ⋮ DEX: self-healing expanders ⋮ A Hoeffding inequality for Markov chains ⋮ Occupation measure for random walk on the circle ⋮ Fixed Precision MCMC Estimation by Median of Products of Averages ⋮ Mixing of the upper triangular matrix walk ⋮ Rigorous confidence bounds for MCMC under a geometric drift condition ⋮ On sufficient conditions for spanning structures in dense graphs ⋮ The Swendsen–Wang dynamics on trees ⋮ Distributed protocols against mobile eavesdroppers ⋮ Finding large expanders in graphs: from topological minors to induced subgraphs ⋮ Unnamed Item ⋮ Tail Estimates for Sums of Variables Sampled by a Random Walk ⋮ Expander graphs and their applications ⋮ Unnamed Item ⋮ Testing the \((s,t)\) connectivity of graphs and digraphs ⋮ Nonasymptotic bounds on the estimation error of MCMC algorithms ⋮ Unnamed Item ⋮ Function-specific mixing times and concentration away from equilibrium ⋮ Concentration of Markov chains with bounded moments ⋮ The worm process for the Ising model is rapidly mixing ⋮ An Introduction to Randomness Extractors ⋮ Logarithmic reduction of the level of randomness in some probabilistic geometric constructions ⋮ Cutoff for random walk on dynamical Erdős-Rényi graph ⋮ Efficient Simulation of High Dimensional Gaussian Vectors ⋮ Imperfect gaps in Gap-ETH and PCPs ⋮ Typically-correct derandomization for small time and space ⋮ The Littlewood-Offord problem for Markov chains ⋮ Mixing time estimation in reversible Markov chains from a single sample path ⋮ Uniform Chernoff and Dvoretzky-Kiefer-Wolfowitz-type inequalities for Markov chains and related processes ⋮ Random walks on hyperbolic spaces: concentration inequalities and probabilistic Tits alternative ⋮ Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems ⋮ Cover time of a random graph with a degree sequence II: Allowing vertices of degree two ⋮ Local correctability of expander codes

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