Logarithmic Sobolev inequalities for finite Markov chains
From MaRDI portal
(Redirected from Publication:2564686)
The authors describe this as an expository paper but in addition to providing an overview of its subject matter it includes many new calculations and examples. It is one of a series of papers dealing with the following question: how soon does a finite-state Markov chain reach approximate stationarity? Closeness to stationarity is measured by some distance between distributions, such as total variation, relative entropy, chi-square etc. The answer is of particular interest in the case of examples involving a dimensional or a size parameter and where one is interested in the order of magnitude of the time to approximate stationarity in terms of the parameter. In this respect logarithmic Sobolev inequalities complement traditional eigenvalue techniques and work for nonreversible chains in continuous time, although the best results are stated for reversible chains. A crucial role is played by the log-Sobolev constant which replaces the spectral gap in explicit bounds. The paper includes a reasonably self-contained treatment of logarithmic Sobolev inequalities in the context of finite Markov chains, presents the connection with hypercontractivity, compares the merits of log-Sobolev techniques with their eigenvalue counterparts and discusses a wealth of examples, often giving sharp answers to the question raised above. To cite but one example, spectral methods show that after time \(t\) of order \(n^2\) the Metropolis algorithm for the symmetric binomial distribution with parameter \(n\) is close to stationarity, while log-Sobolev methods show that order \({1\over 2} n\log n\) is sufficient. Other examples treated are natural chains on the box of side \(n\) in \(d\) dimensions, exclusion processes, random graphs, random walks on finite circles or hypercubes, random transpositions on the symmetric group etc. The paper covers continuous time as well as discrete time chains where possible and concludes with the calculation of the log-Sobolev constants of all Markov kernels on a two-point space and of sequences of i.i.d. random elements from a finite state space.
Recommendations
Cites work
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- An application of Harnack inequalities to random walk on nilpotent quotients
- An Example in the Theory of Hypercontractive Semigroups
- Comparison techniques for random walk on finite groups
- Comparison theorems for reversible Markov chains
- Diffusion of color in the simple exclusion process
- Diffusion on compact Riemannian manifolds and logarithmic Sobolev inequalities
- Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
- Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process
- Eigenvalues and expanders
- Generating a random permutation with random transpositions
- Geometric bounds for eigenvalues of Markov chains
- scientific article; zbMATH DE number 420886 (Why is no real title available?)
- scientific article; zbMATH DE number 447275 (Why is no real title available?)
- scientific article; zbMATH DE number 44579 (Why is no real title available?)
- scientific article; zbMATH DE number 194234 (Why is no real title available?)
- scientific article; zbMATH DE number 3487716 (Why is no real title available?)
- scientific article; zbMATH DE number 1210292 (Why is no real title available?)
- scientific article; zbMATH DE number 522891 (Why is no real title available?)
- scientific article; zbMATH DE number 522894 (Why is no real title available?)
- scientific article; zbMATH DE number 3249395 (Why is no real title available?)
- scientific article; zbMATH DE number 3367521 (Why is no real title available?)
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- Invariance principle and empirical mean large deviations of the critical Ornstein-Uhlenbeck process
- Logarithmic Sobolev Inequalities
- Logarithmic Sobolev inequalities and stochastic Ising models
- Logarithmic Sobolev inequalities and the spectrum of Schrödinger operators
- Logarithmic Sobolev inequalities and the spectrum of Sturm-Liouville operators
- Moderate growth and random walk on finite groups
- Nash inequalities for finite Markov chains
- On discrete inhomogeneous exit problems
- Spectral gap and logarithmic Sobolev inequality for Kawasaki and Glauber dynamics
- Strong uniform times and finite random walks
- The logarithmic Sobolev inequality for discrete spin systems on a lattice
- Time to Reach Stationarity in the Bernoulli–Laplace Diffusion Model
- Walks on generating sets of Abelian groups
- What do we know about the Metropolis algorithm?
Cited in
(only showing first 100 items - show all)- The logarithmic Sobolev constant of some finite Markov chains
- Ricci curvature of Markov chains on metric spaces
- Rate of relaxation for a mean-field zero-range process
- Conditions for rapid mixing of parallel and simulated tempering on multimodal distributions
- Rates of convergence of some multivariate Markov chains with polynomial eigenfunctions
- Random quantum circuits are approximate 2-designs
- On modified logarithmic Sobolev inequalities for Bernoulli and Poisson measures
- Relaxation of product Markov chains on product spaces
- What do we know about the Metropolis algorithm?
- Exponential integrability and transportation cost related to logarithmic Sobolev inequalities
- Log-Sobolev inequalities and sampling from log-concave distributions
- Chernoff-type bound for finite Markov chains
- Logarithmic Sobolev inequality for some models of random walks
- Precise estimates on the rate at which certain diffusions tend to equilibrium
- Coupling, spectral gap and related topics. II
- On the log-Sobolev constant for the simple random walk on the \(n\)-cycle: The even cases
- Relaxation time of anisotropic simple exclusion processes and quantum Heisenberg models.
- Exponential decay of entropy in the random transposition and Bernoulli-Laplace models
- Mixing times of lozenge tiling and card shuffling Markov chains
- Importance sampling for families of distributions
- Multiscale diffusion processes with periodic coefficients and an application to solute transport in porous media
- Logarithmic Sobolev inequality for symmetric forms
- Nonstationary Markovian queues
- Mixed and isoperimetric estimates on the log-Sobolev constants of graphs and Markov chains
- Strong hypercontractivity and relative subharmonicity
- Exponential convergence rate in Boltzmann-Shannon entropy
- Boolean functions: influence, threshold and noise
- A characterization of a class of convex log-Sobolev inequalities on the real line
- Weak atomic convergence of finite voter models toward Fleming-Viot processes
- On sensitivity of uniform mixing times
- Lower bounds for the rate of convergence for continuous-time inhomogeneous Markov chains with a finite state space
- Spectral gap estimates in mean field spin glasses
- Hitting time and mixing time bounds of Stein's factors
- On sensitivity of mixing times and cutoff
- Entropy production in nonlinear recombination models
- Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains
- Concentration of normalized sums and a central limit theorem for noncorrelated random variables
- Sobolev inequalities and Myers's diameter theorem for an abstract Markov generator
- Entropy inequalities for unbounded spin systems
- Efficient Markovian couplings: Examples and counterexamples.
- Walks on generating sets of Abelian groups
- Phase transition for the mixing time of the Glauber dynamics for coloring regular trees
- Cutoff for the Ising model on the lattice
- Mixing of the symmetric exclusion processes in terms of the corresponding single-particle random walk
- Convergence rate of Markov chain methods for genomic motif discovery
- Time inhomogeneous Markov chains with wave-like behavior
- The decay function of nonhomogeneous birth-death processes, with application to mean-field models
- Every ``lower psi-mixing Markov chain is ``interlaced rho-mixing
- On limiting characteristics for a non-stationary two-processor heterogeneous system with catastrophes, server failures and repairs
- Modified log-Sobolev inequality for a compact pure jump Markov process with degenerate jumps
- Fast mixing of Metropolis-Hastings with unimodal targets
- Convergence to equilibrium for a directed (1+d)-dimensional polymer
- A polynomial upper bound for the mixing time of edge rotations on planar maps
- Cutoff for the Bernoulli-Laplace urn model with o(n) swaps
- Concentration inequalities for bounded functionals via log-Sobolev-type inequalities
- Entropy-information inequalities under curvature-dimension conditions for continuous-time Markov chains
- Random-cluster dynamics on random regular graphs in tree uniqueness
- Complete logarithmic Sobolev inequalities via Ricci curvature bounded below
- The entropy method under curvature-dimension conditions in the spirit of Bakry-Émery in the discrete setting of Markov chains
- Modified log-Sobolev inequalities, Beckner inequalities and moment estimates
- A sharp log-Sobolev inequality for the multislice
- Coalescing and branching simple symmetric exclusion process
- Hypercontractivity and logarithmic Sobolev inequality for non-primitive quantum Markov semigroups and estimation of decoherence rates
- On mixing of Markov chains: coupling, spectral independence, and entropy factorization
- Log-Sobolev inequality for the multislice, with applications
- 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)
- Entropy decay in the Swendsen-Wang dynamics on \(\mathbb{Z}^d\)
- Exact convergence analysis of the independent Metropolis-Hastings algorithms
- No cutoff in spherically symmetric trees
- The-square-and-add Markov chain
- Logarithmic Sobolev inequalities for finite spin systems and applications
- Talagrand inequality at second order and application to Boolean analysis
- Quantum reverse hypercontractivity: its tensorization and application to strong converses
- Cutoff for the Swendsen-Wang dynamics on the lattice
- A comparison principle for random walk on dynamical percolation
- The exclusion process mixes (almost) faster than independent particles
- On interweaving relations
- Fisher information and logarithmic Sobolev inequality for matrix-valued functions
- Modified log-Sobolev inequalities for strongly log-concave distributions
- The interchange process on high-dimensional products
- Induced idleness leads to deterministic heavy traffic limits for queue-based random-access algorithms
- Block factorization of the relative entropy via spatial mixing
- Ollivier's Ricci curvature, local clustering and curvature-dimension inequalities on graphs
- Logarithmic Harnack inequalities for general graphs with positive Ricci curvature
- On graph parameters guaranteeing fast sandpile diffusion
- Higher order concentration for functions of weakly dependent random variables
- Polynomial mixing time of edge flips on quadrangulations
- Poincaré and logarithmic Sobolev constants for metastable Markov chains via capacitary inequalities
- An inequality connecting entropy distance, Fisher information and large deviations
- Improved log-Sobolev inequalities, hypercontractivity and uncertainty principle on the hypercube
- Boolean constant degree functions on the slice are juntas
- Harmonicity and invariance on slices of the Boolean cube
- Mixing times for a constrained Ising process on the two-dimensional torus at low density
- Entropy dissipation estimates for the linear Boltzmann operator
- \(L^1\)-Poincaré inequality for discrete time Markov chains
- Logarithmic Sobolev inequality for zero-range dynamics
- On reverse hypercontractivity
- Acceleration of convergence to equilibrium in Markov chains by breaking detailed balance
- A characterization of \(L_{2}\) mixing and hypercontractivity via hitting times and maximal inequalities
This page was built for publication: Logarithmic Sobolev inequalities for finite Markov chains
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2564686)
