Logarithmic Sobolev inequalities for finite Markov chains

1996/08/01 by Persi Diaconis, P. Diaconis, Laurent Saloff‐Coste +1 · 61 citations
Mathematics · #Graph theory and applications #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics

paper · pdf · doi:10.1214/aoap/1034968224

openalex publication_date 1996/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

This is an expository paper on the use of logarithmic Sobolev inequalities for bounding rates of convergence of Markov chains on finite state spaces to their stationary distributions. Logarithmic Sobolev inequalities complement eigenvalue techniques and work for nonreversible chains in continuous time. Some aspects of the theory simplify considerably with finite state spaces and we are able to give a self-contained development. Examples of applications include the study of a Metropolis chain for the binomial distribution, sharp results for natural chains on the box of side n in d dimensions and improved rates for exclusion processes. We also show that for most r-regular graphs the log-Sobolev constant is of smaller order than the spectral gap. The log-Sobolev constant of the asymmetric two-point space is computed exactly as well as the log-Sobolev constant of the complete graph on n points.

Citations

• Logarithmic Sobolev Inequalities

Cited by

• Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions
• On reverse hypercontractivity
• Temporal Difference Learning as Gradient Splitting
• Supplementary Material for Random Cayley Graphs Project
• The East model: recent results and new progresses
• Graph Hörmander Systems
• Long time behaviour of one facilitated kinetically constrained models: results and open problems
• Eldan's Stochastic Localization and the KLS Conjecture: Isoperimetry, Concentration and Mixing
• Hydrodynamic limit and density fluctuations of a reaction-diffusion equation
• Cuts in Cartesian Products of Graphs
• L^p estimates for Feynman-Kac propagators with time-dependent reference measures
• Extremal of Log Sobolev inequality and W entropy on noncompact manifolds
• Functional Inequalities and Random Walks on Increasing Subsets of the Hypercube
• Entropy decay in the Swendsen-Wang dynamics on \mathbb Z^d
• Correlation and Brascamp-Lieb inequalities for Markov semigroups
• Concentration of Haar measures, with an application to random matrices
• Convergence to equilibrium for a directed (1+d)-dimensional polymer
• Functional inequalities for Gaussian convolutions of compactly supported measures: explicit bounds and dimension dependence
• Computing the norm of nonnegative matrices and the log-Sobolev constant of Markov chains
• A Noise Sensitivity Theorem for Schreier Graphs
• Flow Decomposition Reveals Dynamical Structure of Markov Process
• Logarithmic Sobolev inequality for the inhomogeneous zero range process
• Some notes on higher order concentration of measure
• Complexity of mixed Schatten norms of quantum maps
• A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
• Discrete Bochner inequalities via the Bochner-Bakry-Emery approach for Markov chains
• Markov chain methods for small-set expansion
• Hypercontractivity and its applications
• Absorb and Converge: Provable Convergence Guarantee for Absorbing Discrete Diffusion Models
• A Robust \widetildeO(1/√(T)) Rate for Unprojected TD Learning with Linear Function Approximation
• Lattice Path Matroids: Negative Correlation and Fast Mixing
• Estimating the decoherence time using non-commutative Functional Inequalities
• Non-linear Log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems
• Relaxation time of L-reversal chains and other chromosome shuffles
• Ollivier’s Ricci Curvature, Local Clustering and Curvature-Dimension Inequalities on Graphs
• Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains
• On the convergence of densities of finite voter models to the Wright-Fisher diffusion
• Improved annealing for sampling from multimodal distributions via landscape modification
• Sharp log-Sobolev inequalities on finite cyclic groups
• A simple reduction from a biased measure on the discrete cube to the uniform measure
• Separation cut-offs for birth and death chains
• Logarithmic Sobolev inequality for zero-range dynamics
• Concentration of quantum states from quantum functional and transportation cost inequalities
• The mixing time for simple exclusion
• Noise and conditional entropy evolution
• Entanglement from Expansion: High Rank-Width in Deterministic Graphs
• Concentration of normalized sums and a central limit theorem for noncorrelated random variables
• Edge-isoperimetric inequalities and influences
• Eigenvalues, Inequalities, and Ergodic Theory
• From Boltzmann to random matrices and beyond
• Heat kernels, intrinsic contractivity and ergodicity of discrete-time Markov chains killed by potentials
• Mixing times of lozenge tiling and card shuffling Markov chains
• Fredrickson-Andersen one spin facilitated model out of equilibrium
• Comparison of Channels: Criteria for Domination by a Symmetric Channel
• Superpolynomial Speedups Based on Almost Any Quantum Circuit
• Convergence rate of Markov chain methods for genomic motif discovery
• Exponential decay of matrix Φ-entropies on Markov semigroups with applications to dynamical evolutions of quantum ensembles
• Matrix Poincaré, Φ-Sobolev inequalities, and quantum ensembles
• Poincaré-Type Inequalities for Compact Degenerate Pure Jump Markov Processes
• Subexponential Bohnenblust-Hille Inequalities on Finite Cyclic Groups
• Faster Mixing of the Jerrum-Sinclair Chain

Related

• Sum-of-Squares proofs of logarithmic Sobolev inequalities on finite Markov chains
• Upgrading MLSI to LSI for reversible Markov chains
• Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains
• Log-Sobolev, isoperimetry and transport inequalities on graphs
• Intrinsic regularity in the discrete log-Sobolev inequality