Logarithmic Sobolev inequalities for finite Markov chains

DOI10.1214/AOAP/1034968224zbMath0867.60043OpenAlexW2077810240WikidataQ62111462 ScholiaQ62111462MaRDI QIDQ2564686

Laurent Saloff-Coste, Persi Diaconis

Publication date: 4 August 1997

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aoap/1034968224

zbMATH Keywords

random walksrandom graphsMarkov chainlogarithmic Sobolev inequalitieshypercontractivitylog-Sobolev techniques

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Sums of independent random variables; random walks (60G50) Continuous-time Markov processes on discrete state spaces (60J27)

Related Items (only showing first 100 items - show all)

Quasi-factorization and multiplicative comparison of subalgebra-relative entropy ⋮ Logarithmic Sobolev inequality for zero-range dynamics ⋮ Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs ⋮ A bound on partitioning clusters ⋮ Exact convergence analysis of the independent Metropolis-Hastings algorithms ⋮ No cutoff in spherically symmetric trees ⋮ On reverse hypercontractivity ⋮ A note on concentration for polynomials in the Ising model ⋮ Entropy dissipation estimates in a zero-range dynamics ⋮ The-square-and-add Markov chain ⋮ Stability and exponential convergence of continuous-time Markov chains ⋮ Modified log-Sobolev inequalities and two-level concentration ⋮ Unnamed Item ⋮ Random matrices with log-range correlations, and log-Sobolev inequalities ⋮ Logarithmic Sobolev inequalities for finite spin systems and applications ⋮ Spectral Properties of Circulant Quantum Markov Semigroups ⋮ Acceleration of convergence to equilibrium in Markov chains by breaking detailed balance ⋮ Talagrand inequality at second order and application to Boolean analysis ⋮ A characterization of \(L_{2}\) mixing and hypercontractivity via hitting times and maximal inequalities ⋮ Quantum reverse hypercontractivity: its tensorization and application to strong converses ⋮ Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems ⋮ Cutoff for the Swendsen-Wang dynamics on the lattice ⋮ Off-diagonal heat kernel estimates for symmetric diffusions in a degenerate ergodic environment ⋮ The Swendsen–Wang dynamics on trees ⋮ Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs ⋮ Universal cutoff for Dyson Ornstein Uhlenbeck process ⋮ Modified log-Sobolev inequalities for strong-Rayleigh measures ⋮ Cutoff for the averaging process on the hypercube and complete bipartite graphs ⋮ Dynamical Gibbs variational principles for irreversible interacting particle systems with applications to attractor properties ⋮ Upgrading MLSI to LSI for reversible Markov chains ⋮ Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics ⋮ Discrete logarithmic Sobolev inequalities in Banach spaces ⋮ Poisson approximation in \(\chi^2\) distance by the Stein-Chen approach ⋮ Exponential decay of matrix Φ-entropies on Markov semigroups with applications to dynamical evolutions of quantum ensembles ⋮ Logarithmic Sobolev inequalities for mollified compactly supported measures ⋮ A comparison principle for random walk on dynamical percolation ⋮ The exclusion process mixes (almost) faster than independent particles ⋮ Hypercontractivity of Spherical Averages in Hamming Space ⋮ Matrix Poincaré, Φ-Sobolev inequalities, and quantum ensembles ⋮ On interweaving relations ⋮ Gradient flow structure and exponential decay of the sandwiched Rényi divergence for primitive Lindblad equations with GNS-detailed balance ⋮ Fisher information and logarithmic Sobolev inequality for matrix-valued functions ⋮ The dual Cheeger constant and spectra of infinite graphs ⋮ Concentration of quantum states from quantum functional and transportation cost inequalities ⋮ Modified log-Sobolev inequalities for strongly log-concave distributions ⋮ A general lower bound for mixing of single-site dynamics on graphs ⋮ On Quantitative Noise Stability and Influences for Discrete and Continuous Models ⋮ Ricci curvature of metric spaces ⋮ Quantum logarithmic Sobolev inequalities and rapid mixing ⋮ Analyzing Glauber dynamics by comparison of Markov chains ⋮ The interchange process on high-dimensional products ⋮ Induced idleness leads to deterministic heavy traffic limits for queue-based random-access algorithms ⋮ Local tail bounds for functions of independent random variables ⋮ Block factorization of the relative entropy via spatial mixing ⋮ The sub-Gaussian constant and concentration inequalities ⋮ ON CONVEX SOBOLEV INEQUALITIES AND THE RATE OF CONVERGENCE TO EQUILIBRIUM FOR FOKKER-PLANCK TYPE EQUATIONS ⋮ Ollivier's Ricci curvature, local clustering and curvature-dimension inequalities on graphs ⋮ Hypercontractivity for a quantum Ornstein-Uhlenbeck semigroup ⋮ Logarithmic Harnack inequalities for general graphs with positive Ricci curvature ⋮ Cutoff for General Spin Systems with Arbitrary Boundary Conditions ⋮ Modified logarithmic Sobolev inequalities for some models of random walk ⋮ On upper bound for the quantum entropy ⋮ On graph parameters guaranteeing fast sandpile diffusion ⋮ Hypercontractivity in finite-dimensional matrix algebras ⋮ Binomial-Poisson entropic inequalities and the M/M/∞queue ⋮ Higher order concentration for functions of weakly dependent random variables ⋮ Unnamed Item ⋮ Edge-Isoperimetric Inequalities and Influences ⋮ Entropy production of doubly stochastic quantum channels ⋮ From Boltzmann to random matrices and beyond ⋮ Approximate tensorization of entropy at high temperature ⋮ Discrete Ricci curvature bounds for Bernoulli-Laplace and random transposition models ⋮ On quantitative convergence to quasi-stationarity ⋮ Information percolation and cutoff for the stochastic Ising model ⋮ Polynomial mixing time of edge flips on quadrangulations ⋮ Uncertainty Quantification for Markov Processes via Variational Principles and Functional Inequalities ⋮ A reverse log-Sobolev inequality in the Segal-Bargmann space ⋮ Poincaré and logarithmic Sobolev constants for metastable Markov chains via capacitary inequalities ⋮ Anticoncentration for subgraph statistics ⋮ Logarithmic Sobolev inequalities in discrete product spaces ⋮ An inequality connecting entropy distance, Fisher information and large deviations ⋮ On Linear Hypocoercive BGK Models ⋮ Comparison of Swendsen-Wang and heat-bath dynamics ⋮ Improved log-Sobolev inequalities, hypercontractivity and uncertainty principle on the hypercube ⋮ Boolean constant degree functions on the slice are juntas ⋮ Logarithmic Sobolev inequalities in non-commutative algebras ⋮ Uniform Chernoff and Dvoretzky-Kiefer-Wolfowitz-type inequalities for Markov chains and related processes ⋮ Harmonicity and invariance on slices of the Boolean cube ⋮ Logarithmic Sobolev constant for the dilute Ising lattice gas dynamics below the percolation threshold. ⋮ Mixing times for a constrained Ising process on the two-dimensional torus at low density ⋮ On swapping and simulated tempering algorithms. ⋮ Entropy dissipation estimates for the linear Boltzmann operator ⋮ Improved quantum hypercontractivity inequality for the qubit depolarizing channel ⋮ Mixing times for the Swapping Algorithm on the Blume-Emery-Griffiths model ⋮ Entropy inequalities for unbounded spin systems ⋮ Log-Sobolev inequality for the multislice, with applications ⋮ Boolean functions: influence, threshold and noise ⋮ A spectral condition for spectral gap: fast mixing in high-temperature Ising models ⋮ Spatial networks and percolation. Abstracts from the workshop held January 17--23, 2021 (hybrid meeting) ⋮ Elementary proof of logarithmic Sobolev inequalities for Gaussian convolutions on \(\mathbb{R}\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nash inequalities for finite Markov chains
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process
• Geometric bounds for eigenvalues of Markov chains
• Strong uniform times and finite random walks
• Eigenvalues and expanders
• Invariance principle and empirical mean large deviations of the critical Ornstein-Uhlenbeck process
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Logarithmic Sobolev inequalities and the spectrum of Schrödinger operators
• Diffusion on compact Riemannian manifolds and logarithmic Sobolev inequalities
• Logarithmic Sobolev inequalities and the spectrum of Sturm-Liouville operators
• The logarithmic Sobolev inequality for discrete spin systems on a lattice
• What do we know about the Metropolis algorithm?
• Comparison theorems for reversible Markov chains
• Spectral gap and logarithmic Sobolev inequality for Kawasaki and Glauber dynamics
• Comparison techniques for random walk on finite groups
• Moderate growth and random walk on finite groups
• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• On discrete inhomogeneous exit problems
• An application of Harnack inequalities to random walk on nilpotent quotients
• Logarithmic Sobolev inequalities and stochastic Ising models
• Walks on generating sets of Abelian groups
• An Example in the Theory of Hypercontractive Semigroups
• Generating a random permutation with random transpositions
• Diffusion of color in the simple exclusion process
• Logarithmic Sobolev Inequalities
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Time to Reach Stationarity in the Bernoulli–Laplace Diffusion Model

This page was built for publication: Logarithmic Sobolev inequalities for finite Markov chains