The Computational Complexity of Estimating MCMC Convergence Time

DOI10.1007/978-3-642-22935-0_36zbMath1343.68289arXiv1007.0089MaRDI QIDQ3088115

Andrej Bogdanov, Nayantara Bhatnagar, Elchanan Mossel

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

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

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W20: Randomized algorithms

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Related Items

The complexity of estimating min-entropy, 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 Computational Complexity of Estimating MCMC Convergence Time

Uses Software

• CODA
• WinBUGS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm
• Relationships between nondeterministic and deterministic tape complexities
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• The Computational Complexity of Estimating MCMC Convergence Time
• Markov Chain Monte Carlo Convergence Diagnostics: A Comparative Review
• Polynomial-Time Approximation Algorithms for the Ising Model
• Bayesian Modeling Using WinBUGS
• Stationarity detection in the initial transient problem
• One-Way Secret-Key Agreement and Applications to Circuit Polarization and Immunization of Public-Key Encryption