Mathematical Aspects of Mixing Times in Markov Chains
From MaRDI portal
Publication:3587573
DOI10.1561/0400000003zbMath1193.68138OpenAlexW4205463258MaRDI QIDQ3587573
Ravi Montenegro, Prasad Tetali
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
examplesadvanced functional techniquesbasic bounds on mixing timesevolving set methodslower bounds on mixing times and their consequences
Computational methods in Markov chains (60J22) Analysis of algorithms and problem complexity (68Q25) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Markov and semi-Markov decision processes (90C40)
Related Items
Cutoff for random lifts of weighted graphs ⋮ Markov chains on finite fields with deterministic jumps ⋮ The generalized distance spectrum of a graph and applications ⋮ From local averaging to emergent global behaviors: the fundamental role of network interconnections ⋮ Gradient and passive circuit structure in a class of non-linear dynamics on a graph ⋮ Uniform random posets ⋮ Some things we've learned (about Markov chain Monte Carlo) ⋮ Cutoff for the mean-field zero-range process with bounded monotone rates ⋮ Deterministic Random Walks for Rapidly Mixing Chains ⋮ Eigenvalues of LRU via a linear algebraic approach ⋮ Random Walks on Randomly Evolving Graphs ⋮ Quantifying the Dissipation Enhancement of Cellular Flows ⋮ Modified log-Sobolev inequalities for strong-Rayleigh measures ⋮ Unnamed Item ⋮ Improved estimation of relaxation time in nonreversible Markov chains ⋮ Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs ⋮ Universality of cutoff for exclusion with reservoirs ⋮ On the \(\alpha\)-lazy version of Markov chains in estimation and testing problems ⋮ Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point ⋮ An algorithm for estimating non-convex volumes and other integrals in \(n\) dimensions ⋮ Upgrading MLSI to LSI for reversible Markov chains ⋮ Uniform accuracy of the maximum likelihood estimates for probabilistic models of biological sequences ⋮ Expander graphs and their applications ⋮ Transport-Entropy Inequalities and Curvature in Discrete-Space Markov Chains ⋮ An Inequality for Functions on the Hamming Cube ⋮ Sensitivity of Mixing Times in Eulerian Digraphs ⋮ Geometric and Spectral Consequences of Curvature Bounds on Tessellations ⋮ Mixing time and expansion of non-negatively curved Markov chains ⋮ Pattern discrete and mixed hit-and-run for global optimization ⋮ Focused most probable world computations in probabilistic logic programs ⋮ A note on the relaxation time of two Markov chains on rooted phylogenetic tree spaces ⋮ Stationary frequencies and mixing times for neutral drift processes with spatial structure ⋮ Improved mixing rates of directed cycles by added connection ⋮ Approximate Spectral Gaps for Markov Chain Mixing Times in High Dimensions ⋮ Entropy dissipation estimates for inhomogeneous zero-range processes ⋮ Hitting time and mixing time bounds of Stein's factors ⋮ Using Histograms to Better Answer Queries to Probabilistic Logic Programs ⋮ Deterministic encryption with the Thorp shuffle ⋮ On the control of opinion dynamics in social networks ⋮ Sampling the Fermi statistics and other conditional product measures ⋮ Cutoff for the mean-field zero-range process ⋮ Sequential Monte Carlo for maximum weight subgraphs with application to solving image jigsaw puzzles ⋮ The spectral gap of sparse random digraphs ⋮ The Markov chain Monte Carlo revolution ⋮ Improved mixing time bounds for the Thorp shuffle and \(L\)-reversal chain ⋮ Mixing and hitting times for Gibbs samplers and other non-Feller processes ⋮ Analysis of non-reversible Markov chains via similarity orbits ⋮ A sharp log-Sobolev inequality for the multislice ⋮ On the spectral radius and stiffness of Markov jump process rate matrices ⋮ On the fastest finite Markov processes ⋮ Mixing time of Markov chains for the 1-2 model ⋮ A version of Aldous' spectral-gap conjecture for the zero range process ⋮ Mixing time estimation in reversible Markov chains from a single sample path ⋮ Random quantum circuits are approximate 2-designs ⋮ Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results ⋮ Unnamed Item ⋮ Harmonic analysis on directed graphs and applications: from Fourier analysis to wavelets ⋮ 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 ⋮ On efficient randomized algorithms for finding the PageRank vector
