The Computational Complexity of Estimating MCMC Convergence Time

DOI10.1007/978-3-642-22935-0_36zbMath1343.68289arXiv1007.0089OpenAlexW2963196743MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Statistical difference beyond the polarizing regime, Minimals Plus: an improved algorithm for the random generation of linear extensions of partially ordered sets, The Computational Complexity of Estimating MCMC Convergence Time, Mixing time estimation in reversible Markov chains from a single sample path, The complexity of estimating min-entropy

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