Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality

DOI10.2307/2000925zbMATH Open0716.60073OpenAlexW4233055081MaRDI QIDQ3203795FDOQ3203795

Authors: Gregory F. Lawler, Alan D. Sokal 

Publication date: 1988

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2000925

Recommendations

• Applications of geometric bounds to the convergence rate of Markov chains on \(\mathbb R^ {n}\).
• Generalization of discrete-time geometric bounds to convergence rate of Markov processes on Rⁿ
• Geometric bounds for eigenvalues of Markov chains
• Cheeger inequalities for absorbing Markov chains
• Une variante de l'inégalité de Cheeger pour les chaînes de Markov finies

zbMATH Keywords

Markov chainsexponential convergence to equilibriumRiemannian manifoldMarkovian jump processes

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Inequalities involving eigenvalues and eigenvectors (15A42) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Discrete-time Markov processes on general state spaces (60J05) Continuous-time Markov processes on general state spaces (60J25) Linear operators on function spaces (general) (47B38) Spectral problems; spectral geometry; scattering theory on manifolds (58J50) Continuous-time Markov processes on discrete state spaces (60J27) Stochastic methods applied to problems in equilibrium statistical mechanics (82B31)

Cited In (only showing first 100 items - show all)

• Convergence of conditional Metropolis-Hastings samplers
• Isoperimetric inequalities and Markov chains
• A Markovian and Roe-algebraic approach to asymptotic expansion in measure
• About the \(L^2\) analyticity of Markov operators on graphs
• On exponential convergence of dynamic queueing network and its applications
• Variance bounding Markov chains
• Recent progress on the random conductance model
• \(L^p\)-Poincaré inequality for general symmetric forms
• Estimation of spectral gap for Markov chains
• Censored Glauber dynamics for the mean field Ising model
• On a generalization of the preconditioned Crank-Nicolson metropolis algorithm
• A probabilistic approach to Carne's bound
• A Cheeger-type inequality on simplicial complexes
• On nodal domains and higher-order Cheeger inequalities of finite reversible Markov processes
• Conductance bounds on the L² convergence rate of Metropolis algorithms on unbounded state spaces
• MCMC for imbalanced categorical data
• Random walks on simplicial complexes and the normalized Hodge 1-Laplacian
• Computable bounds on the spectral gap for unreliable Jackson networks
• Evolving sets, mixing and heat kernel bounds
• Spectral gaps for a Metropolis-Hastings algorithm in infinite dimensions
• On eigenfunctions of Markov processes on trees
• On the two-dimensional dynamical Ising model in the phase coexistence region
• Small-world MCMC and convergence to multi-modal distributions: from slow mixing to fast mixing
• Stability of the Gibbs sampler for Bayesian hierarchical models
• On the layering transition of an SOS surface interacting with a wall. II: The Glauber dynamics
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Convergence rates of Markov chains for some self-assembly and non-saturated Ising models
• Polymer dynamics in the depinned phase: metastability with logarithmic barriers
• Absence of mass gap for a class of stochastic contour models.
• Phase coexistence and torpid mixing in the 3-coloring model on \({\mathbb Z}^d\)
• ExponentialL 2-convergence andL 2-spectral gap for Markov processes
• Comparison of metric spectral gaps
• The spectra of multiplicative attribute graphs
• Slow mixing of Markov chains using fault lines and fat contours
• Laplacians and the Cheeger inequality for directed graphs
• Asymptotic optimality of isoperimetric constants
• Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
• Nash inequalities for finite Markov chains
• The geometry of kernelized spectral clustering
• Chernoff and Berry–Esséen inequalities for Markov processes
• Explicit error bounds for lazy reversible Markov chain Monte Carlo
• Cheeger's inequalities for general symmetric forms and existence criteria for spectral gap
• Multi-way dual Cheeger constants and spectral bounds of graphs
• Sobolev type inequalities for general symmetric forms
• Simulated tempering and swapping on mean-field models
• Logarithmic Sobolev, isoperimetry and transport inequalities on graphs
• Subgeometric ergodicity of strong Markov processes
• Geometric Approaches to the Estimation of the Spectral Gap of Reversible Markov Chains
• Glauber dynamics for the mean-field Potts model
• Dimension spectrum of Axiom A diffeomorphisms. I: The Bowen-Margulis measure
• Exponential convergence rate in entropy
• Spectral gap for an unrestricted Kawasaki type dynamics
• Applications of geometric bounds to the convergence rate of Markov chains on \(\mathbb R^ {n}\).
• On convergence rates of Gibbs samplers for uniform distributions
• What do we know about the Metropolis algorithm?
• On hyperboundedness and spectrum of Markov operators
• On the Diaconis-Gangolli Markov chain for sampling contingency tables with cell-bounded entries
• Criteria of spectral gap for Markov operators
• Computation of expectations by Markov chain Monte Carlo methods
• Entropy inequalities for unbounded spin systems
• Spectral properties of integral operators in bounded, large intervals
• Spectral gap and convergence rate for discrete-time Markov chains
• Expectations for nonreversible Markov chains
• Cheeger's inequalities for general symmetric forms and existence criteria for spectral gap.
• Geometric ergodicity and the spectral gap of non-reversible Markov chains
• Simple Monte Carlo and the Metropolis algorithm
• Spectral gap estimates in mean field spin glasses
• Some results characterizing the finite time behaviour of the simulated annealing algorithm.
• A characterization of the smallest eigenvalue of a graph
• Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions
• Une variante de l'inégalité de Cheeger pour les chaînes de Markov finies
• Cheeger-type isoperimetric inequalities for birth-death processes
• Cheeger inequalities for absorbing Markov chains
• Expansion in supercritical random subgraphs of the hypercube and its consequences
• Fast mixing of Metropolis-Hastings with unimodal targets
• Simple conditions for metastability of continuous Markov chains
• Non-equivalence of dynamical ensembles and emergent non-ergodicity
• The diameter of the uniform spanning tree of dense graphs
• Expansion and Lack Thereof in Randomly Perturbed Graphs
• Markov chain convergence: From finite to infinite
• Consistent estimation of the spectrum of trace class data augmentation algorithms
• Phase transition for the mixing time of the Glauber dynamics for coloring regular trees
• Isoperimetry in two-dimensional percolation
• Sharp edge, vertex, and mixed Cheeger inequalities for finite Markov kernels
• Some problems on approximate counting in graphs and matroids
• The local limit of the uniform spanning tree on dense graphs
• Graphs, vectors, and matrices
• Characterizing limits and opportunities in speeding up Markov chain mixing
• Isoperimetric inequalities for non-local Dirichlet forms
• Equivalence of boundary measures on covering trees of finite graphs
• Explicit convergence bounds for Metropolis Markov chains: isoperimetry, spectral gaps and profiles
• Improved bounds for the large-time behaviour of simulated annealing
• Integrating and sampling cuts in bounded treewidth graphs
• Spectral triadic decompositions of real-world networks
• Generalization of discrete-time geometric bounds to convergence rate of Markov processes on Rⁿ
• On the Diaconis-Gangolli Markov Chain for Sampling Contingency Tables with Cell-Bounded Entries
• Cutoff for random walk on dynamical Erdős-Rényi graph
• Variance bounding of delayed-acceptance kernels
• Random walks among time increasing conductances: heat kernel estimates

This page was built for publication: Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality

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