Mathematical aspects of mixing times in Markov chains.

DOI10.1561/0400000003zbMATH Open1193.68138OpenAlexW4205463258MaRDI QIDQ3587573FDOQ3587573

Publication date: 8 September 2010

Published in: Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1561/0400000003

Recommendations

Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
scientific article; zbMATH DE number 18982
Evolving sets, mixing and heat kernel bounds
Logarithmic Sobolev inequalities for finite Markov chains

zbMATH Keywords

examples advanced functional techniques basic bounds on mixing times evolving set methods lower bounds on mixing times and their consequences

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Analysis of algorithms and problem complexity (68Q25) Markov and semi-Markov decision processes (90C40)

Cited In (66)

Geometric and spectral consequences of curvature bounds on tessellations
The mixing time of the Newman-Watts small world
An algorithm for estimating non-convex volumes and other integrals in \(n\) dimensions
The spectral gap of sparse random digraphs
Harmonic analysis on directed graphs and applications: from Fourier analysis to wavelets
Mixing time of Markov chains for the 1-2 model
Generalized Markov chain tree theorem and Kemeny's constant for a class of non-Markovian matrices
Mixing time guarantees for unadjusted Hamiltonian Monte Carlo
Sharp bounds on eigenvalues via spectral embedding based on signless Laplacians
Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
Stationary frequencies and mixing times for neutral drift processes with spatial structure
Improved mixing rates of directed cycles by added connection
An inequality for functions on the Hamming cube
Cutoff for random lifts of weighted graphs
On the control of opinion dynamics in social networks
On the fastest finite Markov processes
A note on the relaxation time of two Markov chains on rooted phylogenetic tree spaces
Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
Hitting time and mixing time bounds of Stein's factors
Deterministic encryption with the Thorp shuffle
Uniform random posets
Pattern discrete and mixed hit-and-run for global optimization
On efficient randomized algorithms for finding the PageRank vector
From local averaging to emergent global behaviors: the fundamental role of network interconnections
Deterministic random walks for rapidly mixing chains
Sensitivity of mixing times in Eulerian digraphs
Focused most probable world computations in probabilistic logic programs
Entropy dissipation estimates for inhomogeneous zero-range processes
Analysis of non-reversible Markov chains via similarity orbits
Gradient and passive circuit structure in a class of non-linear dynamics on a graph
Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
Cutoff for the mean-field zero-range process with bounded monotone rates
Random quantum circuits are approximate 2-designs
A version of Aldous' spectral-gap conjecture for the zero range process
Random Walks on Randomly Evolving Graphs
Quantifying the Dissipation Enhancement of Cellular Flows
Uniform accuracy of the maximum likelihood estimates for probabilistic models of biological sequences
Cutoff for the mean-field zero-range process
Sequential Monte Carlo for maximum weight subgraphs with application to solving image jigsaw puzzles
Using histograms to better answer queries to probabilistic logic programs
The Markov chain Monte Carlo revolution
Modified log-Sobolev inequalities for strong-Rayleigh measures
Topics in Markov chains: mixing and escape rate
Expander graphs and their applications
Transport-entropy inequalities and curvature in discrete-space Markov chains
Mixing and hitting times for Gibbs samplers and other non-Feller processes
Mixing time estimation in reversible Markov chains from a single sample path
Some things we've learned (about Markov chain Monte Carlo)
A sharp log-Sobolev inequality for the multislice
Eigenvalues of LRU via a linear algebraic approach
Sampling the Fermi statistics and other conditional product measures
Mixing time and expansion of non-negatively curved Markov chains
Improved mixing time bounds for the Thorp shuffle and \(L\)-reversal chain
Markov chains on finite fields with deterministic jumps
Approximate spectral gaps for Markov chain mixing times in high dimensions
Universality of cutoff for exclusion with reservoirs
The varentropy criterion is sharp on expanders
The generalized distance spectrum of a graph and applications
On the spectral radius and stiffness of Markov jump process rate matrices
Title not available (Why is that?)
Upgrading MLSI to LSI for reversible Markov chains
Sensitivity of mixing times of Cayley graphs
Spectral gap of the symmetric inclusion process
On the \(\alpha\)-lazy version of Markov chains in estimation and testing problems
Cutoff for non-negatively curved Markov chains
Improved estimation of relaxation time in nonreversible Markov chains

This page was built for publication: Mathematical aspects of mixing times in Markov chains.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3587573)