Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
From MaRDI portal
Publication:3203795
DOI10.2307/2000925zbMath0716.60073OpenAlexW4233055081MaRDI QIDQ3203795
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
Continuous-time Markov processes on general state spaces (60J25) Discrete-time Markov processes on general state spaces (60J05) Spectral problems; spectral geometry; scattering theory on manifolds (58J50) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Inequalities involving eigenvalues and eigenvectors (15A42) Linear operators on function spaces (general) (47B38) Stochastic methods applied to problems in equilibrium statistical mechanics (82B31) Continuous-time Markov processes on discrete state spaces (60J27)
Related Items (only showing first 100 items - show all)
The diameter of the uniform spanning tree of dense graphs ⋮ New Hilbert space tools for analysis of graph Laplacians and Markov processes ⋮ A Markovian and Roe-algebraic approach to asymptotic expansion in measure ⋮ Geometric bounds on the fastest mixing Markov chain ⋮ Asymptotic behaviors of random walks on countable groups ⋮ Some results characterizing the finite time behaviour of the simulated annealing algorithm. ⋮ Cheeger's inequalities for general symmetric forms and existence criteria for spectral gap ⋮ Expansion and Lack Thereof in Randomly Perturbed Graphs ⋮ Entropy inequalities for unbounded spin systems ⋮ Cheeger's inequalities for general symmetric forms and existence criteria for spectral gap. ⋮ Applications of geometric bounds to the convergence rate of Markov chains on \(\mathbb R^ {n}\). ⋮ On exponential convergence of dynamic queueing network and its applications ⋮ Chernoff and Berry–Esséen inequalities for Markov processes ⋮ ExponentialL 2-convergence andL 2-spectral gap for Markov processes ⋮ The local limit of the uniform spanning tree on dense graphs ⋮ Graphs, Vectors, and Matrices ⋮ Simulated tempering and swapping on mean-field models ⋮ A characterization of the smallest eigenvalue of a graph ⋮ Logarithmic Sobolev, isoperimetry and transport inequalities on graphs ⋮ Exponential convergence for attractive reversible subcritical nearest particle systems ⋮ Improved bounds for the large-time behaviour of simulated annealing ⋮ Variance bounding of delayed-acceptance kernels ⋮ On the two-dimensional dynamical Ising model in the phase coexistence region ⋮ Dimension spectrum of Axiom A diffeomorphisms. I: The Bowen-Margulis measure ⋮ Isoperimetry in Two-Dimensional Percolation ⋮ Geometric Approaches to the Estimation of the Spectral Gap of Reversible Markov Chains ⋮ Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow ⋮ Modulus of continuity eigenvalue bounds for homogeneous graphs and convex subgraphs with applications to quantum Hamiltonians ⋮ Spectral gap estimates in mean field spin glasses ⋮ Approximate counting, uniform generation and rapidly mixing Markov chains ⋮ On the Diaconis-Gangolli Markov Chain for Sampling Contingency Tables with Cell-Bounded Entries ⋮ Markov chain convergence: From finite to infinite ⋮ Coupling, spectral gap and related topics. II ⋮ On the layering transition of an SOS surface interacting with a wall. II: The Glauber dynamics ⋮ Slow mixing of Markov chains using fault lines and fat contours ⋮ Spectral gap and convergence rate for discrete-time Markov chains ⋮ Equivalence of boundary measures on covering trees of finite graphs ⋮ Geometric ergodicity and the spectral gap of non-reversible Markov chains ⋮ Phase transition for the mixing time of the Glauber dynamics for coloring regular trees ⋮ A Cheeger-type inequality on simplicial complexes ⋮ An invariance principle and a large deviation principle for the biased random walk on ⋮ Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point ⋮ Random Walks on Simplicial Complexes and the Normalized Hodge 1-Laplacian ⋮ Nodal domain count for the generalized graph \(p\)-Laplacian ⋮ On nodal domains and higher-order Cheeger inequalities of finite reversible Markov processes ⋮ Estimation of spectral gap for Markov chains ⋮ Weak log-Sobolev and \(L^p\) weak Poincaré inequalities for general symmetric forms ⋮ Recent progress on the random conductance model ⋮ Some Problems on Approximate Counting in Graphs and Matroids ⋮ An interlacing technique for spectra of random walks and its application to finite percolation clusters ⋮ Absence of mass gap for a class of stochastic contour models. ⋮ On the Diaconis-Gangolli Markov chain for sampling contingency tables with cell-bounded entries ⋮ Multi-way dual Cheeger constants and spectral bounds of graphs ⋮ Spectral gaps for a Metropolis-Hastings algorithm in infinite dimensions ⋮ Criteria of spectral gap for Markov operators ⋮ Variance bounding Markov chains ⋮ Non-equivalence of dynamical ensembles and emergent non-ergodicity ⋮ Speed of random walks, isoperimetry and compression of finitely generated groups ⋮ Exponential convergence rate in entropy ⋮ Simple Monte Carlo and the Metropolis algorithm ⋮ Comparison of Metric Spectral Gaps ⋮ On eigenfunctions of Markov processes on trees ⋮ Small-world MCMC and convergence to multi-modal distributions: from slow mixing to fast mixing ⋮ On the limitations of single-step drift and minorization in Markov chain convergence analysis ⋮ Nash inequalities for finite Markov chains ⋮ Spectral properties of integral operators in bounded, large intervals ⋮ Fast mixing of Metropolis-Hastings with unimodal targets ⋮ On a generalization of the preconditioned Crank-Nicolson metropolis algorithm ⋮ General Sobolev type inequalities for symmetric forms ⋮ Stability of the Gibbs sampler for Bayesian hierarchical models ⋮ Une variante de l'inégalité de Cheeger pour les chaînes de Markov finies ⋮ Convergence of Conditional Metropolis-Hastings Samplers ⋮ Estimating the spectral gap of a trace-class Markov operator ⋮ Glauber dynamics for the mean-field Potts model ⋮ Isoperimetric inequalities for non-local Dirichlet forms ⋮ \(L^p\)-Poincaré inequality for general symmetric forms ⋮ Subgeometric ergodicity of strong Markov processes ⋮ Polymer dynamics in the depinned phase: metastability with logarithmic barriers ⋮ Random walks among time increasing conductances: heat kernel estimates ⋮ Cutoff for random walk on dynamical Erdős-Rényi graph ⋮ Characterizing limits and opportunities in speeding up Markov chain mixing ⋮ Explicit error bounds for lazy reversible Markov chain Monte Carlo ⋮ Growth of periodic Grigorchuk groups ⋮ Convergence rates of Markov chains for some self-assembly and non-saturated Ising models ⋮ The spectra of multiplicative attribute graphs ⋮ Asymptotic optimality of isoperimetric constants ⋮ Simple conditions for metastability of continuous Markov chains ⋮ Poincaré and logarithmic Sobolev constants for metastable Markov chains via capacitary inequalities ⋮ Expectations for nonreversible Markov chains ⋮ Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions ⋮ What do we know about the Metropolis algorithm? ⋮ Conductance bounds on the L2 convergence rate of Metropolis algorithms on unbounded state spaces ⋮ Integrating and Sampling Cuts in Bounded Treewidth Graphs ⋮ Finite-Time Behavior of Slowly Cooled Annealing Chains ⋮ Consistent estimation of the spectrum of trace class data augmentation algorithms ⋮ MCMC for Imbalanced Categorical Data ⋮ Phase coexistence and torpid mixing in the 3-coloring model on ${\mathbb Z}^d$ ⋮ Hypercontractivity and logarithmic Sobolev inequality for non-primitive quantum Markov semigroups and estimation of decoherence rates ⋮ Censored Glauber dynamics for the mean field Ising model ⋮ On convergence rates of Gibbs samplers for uniform distributions
This page was built for publication: Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
