Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains

DOI10.1214/105051604000000639zbMath1067.60065arXivmath/0503537OpenAlexW2022380818MaRDI QIDQ1769410

Prasad Tetali, Eric Vigoda, Jung-Bae Son, Mark R. Jerrum

Publication date: 21 March 2005

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

Full work available at URL: https://arxiv.org/abs/math/0503537

zbMATH Keywords

spectral gap logarithmic Sobolev inequalities Poincaré inequalities Markov chain Monte Carlo algorithms mixing time of Markov chains decomposition of Markov chains restriction and projection Markov chains

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Markov processes: estimation; hidden Markov models (62M05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Numerical analysis or methods applied to Markov chains (65C40) Randomized algorithms (68W20)

Related Items

Universality of cutoff for graphs with an added random matching, Metastable states, quasi-stationary distributions and soft measures, Spectral gap for open Jackson networks, The diameter of the uniform spanning tree of dense graphs, Quantitative contraction rates for Markov chains on general state spaces, Equivalence of a mixing condition and the LSI in spin systems with infinite range interaction, \(L^p\) estimates for Feynman-Kac propagators with time-dependent reference measures, The spectral gap for quasi-birth and death processes, Elementary bounds on mixing times for decomposable Markov chains, Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs, Complexity results for MCMC derived from quantitative bounds, Modified log-Sobolev inequalities for strong-Rayleigh measures, Mixing time for the asymmetric simple exclusion process in a random environment, Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid, Unnamed Item, Unnamed Item, Poincaré and logarithmic Sobolev inequalities by decomposition of the energy landscape, Modified log-Sobolev inequalities for strongly log-concave distributions, Approximate Spectral Gaps for Markov Chain Mixing Times in High Dimensions, On the limitations of single-step drift and minorization in Markov chain convergence analysis, Entropy dissipation estimates for inhomogeneous zero-range processes, \(L^2\)-decay rate for non-ergodic Jackson network, Partial differential equations and stochastic methods in molecular dynamics, On fine properties of mixtures with respect to concentration of measure and Sobolev type inequalities, Mixing time of critical Ising model on trees is polynomial in the height, Polymer dynamics in the depinned phase: metastability with logarithmic barriers, The logarithmic Sobolev constant of some finite Markov chains, Simple conditions for metastability of continuous Markov chains, Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids, Bounding the lumping error in Markov chain dynamics, Mixing and hitting times for Gibbs samplers and other non-Feller processes, Approximately counting bases of bicircular matroids, A sharp log-Sobolev inequality for the multislice, Spectral gap for jump processes by decomposition method, Linking and cutting spanning trees, Mixing times for a constrained Ising process on the two-dimensional torus at low density, Metastability for expanding bubbles on a sticky substrate

Cites Work