An introduction to computational complexity in Markov Chain Monte Carlo methods

2020/04/14 by Izhar Asael Alonzo Matamoros, Matamoros, Izhar Asael Alonzo
Mathematics · #Computation (stat.CO) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Random Matrices and Applications #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2004.07083

openalex publication_date 2020/04/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The aim of this work is to give an introduction to the theoretical background and computational complexity of Markov chain Monte Carlo methods. Most of the mathematical results related to the convergence are not found in most of the statistical references, and computational complexity is still an open question for most of the MCMC methods. In this work, we provide a general overview, references, and discussion about all these theoretical subjects.

Citations

• A Conceptual Introduction to Hamiltonian Monte Carlo

Related

• The Convergence of Markov chain Monte Carlo Methods: From the Metropolis\n method to Hamiltonian Monte Carlo
• Complexity Bounds for MCMC via Diffusion Limits
• A Critical Review of Monte Carlo Algorithms Balancing Performance and Probabilistic Accuracy with AI Augmented Framework
• Markov Chain Monte Carlo Methods, a survey with some frequent misunderstandings
• A First Course in Monte Carlo Methods