Structure and eigenvalues of heat-bath Markov chains

DOI10.1016/J.LAA.2014.04.018MaRDI QIDQ2451698zbMATH OpenOpenAlexWikidataFDO

Authors Catherine Greenhill, Mario Ullrich, Martin Dyer

Publication date 4 June 2014

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

contingency tableseigenvaluesheat-bathMarkov chainspositive semidefinitestochastic matrices

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Stochastic matrices (15B51) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Contingency tables (62H17)

Abstract: We prove that heat-bath chains (which we define in a general setting) have no negative eigenvalues. Two applications of this result are presented: one to single-site heat-bath chains for spin systems and one to a heat-bath Markov chain for sampling contingency tables. Some implications of our main result for the analysis of the mixing time of heat-bath Markov chains are discussed. We also prove an alternative characterisation of heat-bath chains, and consider possible generalisations.

Recommendations

• On sampling with Markov chains
• Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
• Heat-bath random walks with Markov bases
• Sampling contingency tables
• On the Convergence of Reversible Markov Chains

Cites work

• Approach to equilibrium of Glauber dynamics in the one phase region. I: The attractive case
• Comparison theorems for reversible Markov chains
• Critical Ising on the square lattice mixes in polynomial time
• Ergodic Markov chains with finite convergence time
• Fast Convergence of Markov Chain Monte Carlo Algorithms for Phylogenetic Reconstruction with Homogeneous Data on Closely Related Species
• scientific article; zbMATH DE number 1885142 (Why is no real title available?)
• scientific article; zbMATH DE number 1418384 (Why is no real title available?)
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Markov chain comparison
• Markov chains with finite convergence time
• Matrix Analysis
• On the class of Markov chains with finite convergence time
• Polynomial-time counting and sampling of two-rowed contingency tables
• Rapid mixing for lattice colourings with fewer colours
• Rapid mixing of Swendsen-Wang dynamics in two dimensions
• Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
• The Swendsen-Wang process does not always mix rapidly

Cited in

(9)

• On the coupling time of the heat-bath process for the Fortuin-Kasteleyn random-cluster model
• Sparse analytic hierarchy process: an experimental analysis
• Heat-bath random walks with Markov bases
• Mixing of the Glauber dynamics for the ferromagnetic Potts model
• Speeding up switch Markov chains for sampling bipartite graphs with given degree sequence
• The hit-and-run version of top-to-random
• Explaining the effects of non-convergent sampling in the training of energy-based models
• Optimal mixing for randomly sampling edge colorings on trees down to the max degree
• Rapid mixing via coupling independence for spin systems with unbounded degree

This page was built for publication: Structure and eigenvalues of heat-bath Markov chains

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