The computational complexity of estimating MCMC convergence time
From MaRDI portal
Abstract: An important problem in the implementation of Markov Chain Monte Carlo algorithms is to determine the convergence time, or the number of iterations before the chain is close to stationarity. For many Markov chains used in practice this time is not known. Even in cases where the convergence time is known to be polynomial, the theoretical bounds are often too crude to be practical. Thus, practitioners like to carry out some form of statistical analysis in order to assess convergence. This has led to the development of a number of methods known as convergence diagnostics which attempt to diagnose whether the Markov chain is far from stationarity. We study the problem of testing convergence in the following settings and prove that the problem is hard in a computational sense: Given a Markov chain that mixes rapidly, it is hard for Statistical Zero Knowledge (SZK-hard) to distinguish whether starting from a given state, the chain is close to stationarity by time t or far from stationarity at time ct for a constant c. We show the problem is in AM intersect coAM. Second, given a Markov chain that mixes rapidly it is coNP-hard to distinguish whether it is close to stationarity by time t or far from stationarity at time ct for a constant c. The problem is in coAM. Finally, it is PSPACE-complete to distinguish whether the Markov chain is close to stationarity by time t or far from being mixed at time ct for c at least 1.
Recommendations
- Markov Chain Monte Carlo Convergence Diagnostics: A Comparative Review
- Complexity bounds for Markov chain Monte Carlo algorithms via diffusion limits
- Computational complexity of Markov chain Monte Carlo methods for finite Markov random fields
- A Coupling-Regeneration Scheme for Diagnosing Convergence in Markov Chain Monte Carlo Algorithms
- scientific article; zbMATH DE number 1246228
Cites work
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- Bayes and empirical Bayes methods for data analysis.
- Bayesian Modeling Using WinBUGS
- scientific article; zbMATH DE number 420886 (Why is no real title available?)
- scientific article; zbMATH DE number 1885142 (Why is no real title available?)
- scientific article; zbMATH DE number 2117879 (Why is no real title available?)
- scientific article; zbMATH DE number 849920 (Why is no real title available?)
- Markov Chain Monte Carlo Convergence Diagnostics: A Comparative Review
- One-Way Secret-Key Agreement and Applications to Circuit Polarization and Immunization of Public-Key Encryption
- Polynomial-Time Approximation Algorithms for the Ising Model
- Relationships between nondeterministic and deterministic tape complexities
- Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm
- Stationarity detection in the initial transient problem
- The computational complexity of estimating MCMC convergence time
Cited in
(7)- Statistical difference beyond the polarizing regime
- Minimals Plus: an improved algorithm for the random generation of linear extensions of partially ordered sets
- Mixing time estimation in reversible Markov chains from a single sample path
- The complexity of estimating min-entropy
- The computational complexity of estimating MCMC convergence time
- Computational complexity of Markov chain Monte Carlo methods for finite Markov random fields
- scientific article; zbMATH DE number 7249109 (Why is no real title available?)
This page was built for publication: The computational complexity of estimating MCMC convergence time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3088115)
