×

On swapping and simulated tempering algorithms. (English) Zbl 1075.60545

Summary: We study the relationships between two Markov chain Monte Carlo algorithms – the swapping algorithm (also known as the Metropolis-coupled algorithm) and the simulated tempering algorithm. We give a proof that the spectral gap of the simulated tempering chain is bounded below by a multiple of that of the swapping chain.

MSC:

60J05 Discrete-time Markov processes on general state spaces
65C05 Monte Carlo methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chen, M. F., Estimation of spectral gap for Markov chains, Acta Math. Sin. New Ser., 12, 4, 337-360 (1996) · Zbl 0867.60038
[2] Chen, M. F.; Wang, F. Y., Estimation of spectral gap for elliptic operators, Trans. AMS, 349, 1239-1267 (1997) · Zbl 0872.35072
[3] Coluzzi, B., Numerical simulations on the 4D Heisenberg spinglass, J. Phys. A: Math. Gen., 28, 747-754 (1995) · Zbl 0850.82063
[4] Diaconis, P.; Saloff-Coste, L., Logarithmic Sobolev inequalities for finite Markov chains, Ann. Appl. Probab., 6, 695-750 (1996) · Zbl 0867.60043
[5] Diaconis, P.; Saloff-Coste, L., What do we know about the metropolis algorithm?, J. Comput. System Sci., 57, 20-36 (1998) · Zbl 0920.68054
[6] Diaconis, P.; Stroock, D., Geometric bounds for eigenvalues of Markov chains, Ann. Appl. Probab., 1, 36-61 (1991) · Zbl 0731.60061
[7] Fernández, L. A.; Marinari, E.; Ruiz-Lorenzo, J. J., Tempering dynamics and relaxation times in the 3D ising model, J. Phys. I France, 5, 1247-1254 (1995)
[8] Geyer, C.J., 1991. Markov Chain Monte Carlo maximum likelihood. In: Keramidas, E.M. (Ed.), Computing Science and Statistics: Proceedings of the 23rd Symposium on the Interface, Interface Foundation, Fairfax Station, pp. 156-163.; Geyer, C.J., 1991. Markov Chain Monte Carlo maximum likelihood. In: Keramidas, E.M. (Ed.), Computing Science and Statistics: Proceedings of the 23rd Symposium on the Interface, Interface Foundation, Fairfax Station, pp. 156-163.
[9] Geyer, C. J., Estimation and optimization of functions, (Gilks, W. R.; Richardson, S.; Spiegelhalter, D. J., Markov Chain Monte Carlo in Practice (1996), Chapman & Hall: Chapman & Hall London), 241-258 · Zbl 0841.62044
[10] Geyer, C. J.; Thompson, E. A., Annealing Markov chain Monte Carlo with applications to ancestral inference, J. Amer. Statist. Assoc., 90, 909-920 (1995) · Zbl 0850.62834
[11] Kerler, W., Rehberg, P., 1994. Simulated-tempering approach to Spin-glass Simulations. cond-mat/9402049.; Kerler, W., Rehberg, P., 1994. Simulated-tempering approach to Spin-glass Simulations. cond-mat/9402049.
[12] Madras, N., 1998. Umbrella sampling and simulated tempering. In: Whittington, S.G. (Ed.), Numerical Methods for Polymeric Systems, IMA Vol. Mathematical Applications, 102, Springer, New York, pp. 19-32.; Madras, N., 1998. Umbrella sampling and simulated tempering. In: Whittington, S.G. (Ed.), Numerical Methods for Polymeric Systems, IMA Vol. Mathematical Applications, 102, Springer, New York, pp. 19-32. · Zbl 0924.65147
[13] Madras, N.; Randall, D., Markov chain decomposition for convergence rate analysis, Ann. Appl. Probab., 12, 581-606 (2002) · Zbl 1017.60080
[14] Madras, N.; Piccioni, M., Importance sampling for families of distributions, Ann. Appl. Probab., 9, 1202-1225 (1999) · Zbl 0966.60061
[15] Madras, N., Zheng, Z., 2003. On the swapping algorithm. Random Struct. Algorithms, to appear.; Madras, N., Zheng, Z., 2003. On the swapping algorithm. Random Struct. Algorithms, to appear. · Zbl 1013.60074
[16] Marinari, E., Optimized Monte Carlo methods, (Kertész, J.; Kondor, I., Advances in Computer Simulation (1998), Springer: Springer New York), 50-81 · Zbl 0898.65099
[17] Marinari, E.; Parisi, G., Simulated tempering: a new Monte Carlo scheme, Europhys. Lett., 19, 451-458 (1992)
[18] Neal, R., Sampling from multimodal distributions using tempered transitions, Statist. Comput., 6, 353-366 (1996)
[19] Orlandini, E., 1998. Monte Carlo study of polymer systems by multiple Markov Chain method. In Whittington, S.G. (Ed.), Numerical Methods for Polymeric Systems. IMA Vol. Mathematical Applications, 102, Springer, New York, pp. 33-57.; Orlandini, E., 1998. Monte Carlo study of polymer systems by multiple Markov Chain method. In Whittington, S.G. (Ed.), Numerical Methods for Polymeric Systems. IMA Vol. Mathematical Applications, 102, Springer, New York, pp. 33-57. · Zbl 0926.60081
[20] Rosenthal, J. S., Convergence rates for Markov Chains, SIAM Rev., 37, 387-405 (1995) · Zbl 0833.60069
[21] Sinclair, A., Algorithms for Random Generation and Counting: A Markov Chain Approach (1993), Birkhäuser: Birkhäuser Boston · Zbl 0780.68096
[22] Thomas, D. C.; Gauderman, W. J., Gibbs sampling methods in genetics, (Gilks, W. R.; Richardson, S.; Spiegelhalter, D. J., Markov Chain Monte Carlo in Practice (1996), Chapman & Hall: Chapman & Hall London), 419-440 · Zbl 0839.62101
[23] Vicari, E., Monte Carlo simulation of lattice \(CP^{N−1}\) models at large N, Phys. Lett. B, 309, 139-144 (1993)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.