Positivity of hit-and-run and related algorithms
Mario Ullrich (Friedrich Schiller University Jena)
Abstract
We prove positivity of the Markov operators that correspond to the hit-and-run algorithm, random scan Gibbs sampler, slice sampler and Metropolis algorithm with positive proposal. In particular, the results show that it is not necessary to consider the lazy versions of these Markov chains. The proof relies on a well known lemma which relates the positivity of the product $MTM^*$, for some operators $M$ and $T$, to the positivity of $T$. It remains to find that kind of representation of the Markov operator with a positive operator $T$.
Full Text: Download PDF | View PDF online (requires PDF plugin)
Pages: 1-8
Publication Date: June 26, 2013
DOI: 10.1214/ECP.v18-2507
References
- Kannan, Ravi; Lovász, László; Simonovits, Miklós. Random walks and an $O^ *(n^ 5)$ volume algorithm for convex bodies. Random Structures Algorithms 11 (1997), no. 1, 1--50. MR1608200
- Kreyszig, Erwin. Introductory functional analysis with applications. Wiley Classics Library. John Wiley & Sons, Inc., New York, 1989. xvi+688 pp. ISBN: 0-471-50459-9 MR0992618
- Lawler, Gregory F.; Sokal, Alan D. Bounds on the $L^ 2$ spectrum for Markov chains and Markov processes: a generalization of Cheeger's inequality. Trans. Amer. Math. Soc. 309 (1988), no. 2, 557--580. MR0930082
- Liu, Jun S.; Wong, Wing H.; Kong, Augustine. Covariance structure and convergence rate of the Gibbs sampler with various scans. J. Roy. Statist. Soc. Ser. B 57 (1995), no. 1, 157--169. MR1325382
- Lovász, László. Hit-and-run mixes fast. Math. Program. 86 (1999), no. 3, Ser. A, 443--461. MR1733749
- Lovász, László; Simonovits, Miklós. Random walks in a convex body and an improved volume algorithm. Random Structures Algorithms 4 (1993), no. 4, 359--412. MR1238906
- Lovász, László; Vempala, Santosh. Fast algorithms for logconcave functions: sampling, rounding, integration and optimization, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (Washington, DC, USA), FOCS '06, IEEE Computer Society, 2006, pp. 57--68.
- Lovász, László; Vempala, Santosh. Hit-and-run from a corner. SIAM J. Comput. 35 (2006), no. 4, 985--1005 (electronic). MR2203735
- Lovász, László; Vempala, Santosh. Simulated annealing in convex bodies and an $O^ *(n^ 4)$ volume algorithm. J. Comput. System Sci. 72 (2006), no. 2, 392--417. MR2205290
- Lovász, László; Vempala, Santosh. The geometry of logconcave functions and sampling algorithms. Random Structures Algorithms 30 (2007), no. 3, 307--358. MR2309621
- Mathé, Peter; Novak, Erich. Simple Monte Carlo and the Metropolis algorithm, J. Complexity 23 (2007), no. 4-6, 673--696.
- Meyn, Sean; Tweedie, Richard L. Markov chains and stochastic stability. Second edition. With a prologue by Peter W. Glynn. Cambridge University Press, Cambridge, 2009. xxviii+594 pp. ISBN: 978-0-521-73182-9 MR2509253
- Mira, Antonietta; Tierney, Luke. Efficiency and convergence properties of slice samplers. Scand. J. Statist. 29 (2002), no. 1, 1--12. MR1894377
- Roberts, Gareth O.; Rosenthal, Jeffrey S. General state space Markov chains and MCMC algorithms. Probab. Surv. 1 (2004), 20--71. MR2095565
- Rudolf, Daniel. Explicit error bounds for lazy reversible Markov chain Monte Carlo. J. Complexity 25 (2009), no. 1, 11--24. MR2475305
- Rudolf, Daniel. Explicit error bounds for Markov chain Monte Carlo, Dissertationes Math. 485 (2012), 93 pp.
- Smith, Robert L. Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions. Oper. Res. 32 (1984), no. 6, 1296--1308. MR0775260
- Ullrich, Mario. Rapid mixing of Swendsen-Wang and single-bond dynamics in two dimensions, ArXiv e-prints (2012).
- Ullrich, Mario. Rapid mixing of Swendsen-Wang dynamics in two dimensions, Ph.D. thesis, Friedrich-Schiller-Universität Jena, Germany, 2012.
This work is licensed under a Creative Commons Attribution 3.0 License.