Geometric allocation approach for the transition kernel of a Markov chain

zbMATH Open1320.65021arXiv1106.3562MaRDI QIDQ5501599FDOQ5501599

Authors: Hidemaro Suwa, Synge Todo 

Publication date: 4 August 2015

Abstract: We introduce a new geometric approach that constructs a transition kernel of Markov chain. Our method always minimizes the average rejection rate and even reduce it to zero in many relevant cases, which cannot be achieved by conventional methods, such as the Metropolis-Hastings algorithm or the heat bath algorithm (Gibbs sampler). Moreover, the geometric approach makes it possible to find not only a reversible but also an irreversible solution of rejection-free transition probabilities. This is the first versatile method that can construct an irreversible transition kernel in general cases. We demonstrate that the autocorrelation time (asymptotic variance) of the Potts model becomes more than 6 times as short as that by the conventional Metropolis-Hastings algorithm. Our algorithms are applicable to almost all kinds of Markov chain Monte Carlo methods and will improve the efficiency.

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

Recommendations

• Approximations of geometrically ergodic reversible Markov chains
• Irreversible Monte Carlo algorithms for efficient sampling
• Geometric ergodicity of Metropolis algorithms
• Jump Markov chains and rejection-free Metropolis algorithms
• On the geometric ergodicity of Metropolis-Hastings algorithms

zbMATH Keywords

Markov chainreversibilitydetailed balancetransition kernelgeometric allocation

Mathematics Subject Classification ID

Numerical analysis or methods applied to Markov chains (65C40)

Cited In (3)

• Reducing rejection exponentially improves Markov chain Monte Carlo sampling
• Markov Kernels Local Aggregation for Noise Vanishing Distribution Sampling
• Algorithms for improving efficiency of discrete Markov chains

This page was built for publication: Geometric allocation approach for the transition kernel of a Markov chain

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