×

Markov chain decomposition for convergence rate analysis. (English) Zbl 1017.60080

The authors consider a reversible Markov chain on a state space \(\Omega\) and estimate its special gap. Let \(P(x,dy)\) be the transition probability kernel of a Markov chain that is reversible with respect to a probability density. The authors describe the “pieces” of the chain \(P\). Let \(A_1,\dots, A_m\) be subsets of \(\Omega\) such that \(\bigcup A_i=\Omega\). For each \(i= 1,\dots, m\), the authors define a new Markov chain on \(A_i\). The transition kernel \(P_{[A_i]}\) of the new chain is \[ P_{[A_i]}(x,B)= P(x,B)+ 1_{[x\in B]} P(x, A^c_i),\qquad x\in A_i,\;B\subset A_i.\tag{1} \] Now they define \[ Z:= \sum^m_{i=1} \pi[A_i]\tag{2} \] and the “maximum overlap” \(\Theta\) of the covering \([A_1,\dots, A_m]\) by \[ \Theta:= \max_{x\in\Omega}\|i: x\in A_i\|.\tag{3} \] Then \[ 1\leq Z\leq\Theta.\tag{4} \] Also they introduce a crude model of the movement of the original chain among the “pieces”. They consider a state space \(a_1,\dots, a_m\) of \(m\) points representing our \(m\) pieces and define the transition probabilities for a discrete Markov chain on this finite state space: \[ P_H(a_i, a_j)= {\pi[A_i, A_j]\over \Theta\pi[A_i]}\quad\text{and}\quad P_H(a_i, a_i)= 1-\sum_{j\neq i} P_H(a_i, a_j).\tag{5} \] To describe the rate of convergence to equilibrium, the authors use the spectral gap. For example the first theorem presented is
Theorem 1.1 (State decomposition theorem). With the equations (1)–(5) it results \[ \text{Gap}(P)\geq {1\over\Theta^2} \text{Gap}(P_H(\min\text{ Gap } P_{[A_i]})),\qquad i= 1,\dots, m. \] Section 2 treats simulated tempering. Section 3 is devoted to the Metropolis algorithm and umbrella sampling. Section 4 is entitled “State decomposition”. Section 5 treats density decomposition. The last part of the note contains an appendix, in which the authors consider the Caraciolo-Pelissetto-Sokal result and the Madras-Piccioni result.

MSC:

60J05 Discrete-time Markov processes on general state spaces
65C40 Numerical analysis or methods applied to Markov chains
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI

References:

[1] BORGS, C., CHAy ES, J. T., FRIEZE, A., KIM, J. H., TETALI, P., VIGODA, E. and VU, V. H.
[2] . Torpid mixing of some MCMC algorithms in statistical physics. In Proceedings of the 40th IEEE Sy mposium on Foundations of Computer Science 218-229. IEEE, New York.
[3] BRODER, A. Z. (1986). How hard is it to marry at random? (On the approximation of the permanent). In Proceedings of the 18th ACM Sy mposium on Theory of Computing 50-58. ACM, New York. [Erratum in Broder, A. Z. (1988). Proceedings of the 20th ACM Sy mposium on Theory of Computing 551.]
[4] BUBLEY, R. and Dy ER, M. (1997). Path coupling, Dobrushin uniqueness, and approximate counting. Technical Report 97.04, School of Computer Science, University of Leeds.
[5] CARACCIOLO, S., PELISSETTO, A. and SOKAL, A. D. (1992). Two remarks on simulated tempering. Unpublished manuscript.
[6] COOPER, C., Dy ER, M., FRIEZE, A. and RUE, R. (2000). Mixing properties of the Swendsen-Wang process on the complete graph and narrow grids. J. Math. Phy s. 41 1499-1527. · Zbl 1019.82011 · doi:10.1063/1.533194
[7] DIACONIS, P. and SALOFF-COSTE, L. (1993a). Comparison techniques for random walks on finite groups. Ann. Probab. 21 2131-2156. · Zbl 0790.60011 · doi:10.1214/aop/1176989013
[8] DIACONIS, P. and SALOFF-COSTE, L. (1993b). Comparison theorems for reversible Markov chains. Ann. Appl. Probab. 3 696-730. · Zbl 0799.60058 · doi:10.1214/aoap/1177005359
[9] DIACONIS, P. and STROOCK, D. (1993). Geometric bounds for Markov chains. Ann. Appl. Probab. 1 36-61. · Zbl 0731.60061 · doi:10.1214/aoap/1177005980
[10] GEy ER, C. J. (1991). Markov chain Monte Carlo maximum likelihood. In Computing Science and Statistics: Proceedings of the 23rd Sy mposium on the Interface (E. M. Keramidas, ed.) 156-163. Interface Foundation, Fairfax Station, VA.
[11] GEy ER, C. J. and THOMPSON, E. A. (1995). Annealing Markov chain Monte Carlo with applications to ancestral inference. J. Amer. Statist. Assoc. 90 909-920. · Zbl 0850.62834 · doi:10.2307/2291325
[12] HALMOS, P. R. (1982). A Hilbert Space Problem Book, 2nd ed. Springer, New York. · Zbl 0496.47001
[13] JERRUM, M. R. and SINCLAIR, A. J. (1989). Approximating the permanent. SIAM J. Comput. 18 1149-1178. · Zbl 0723.05107 · doi:10.1137/0218077
[14] LUBY, M., RANDALL, D. and SINCLAIR, A. J. (1995). Markov chain algorithms for planar lattice structures. In Proc. 36th IEEE Sy mposium on Foundations of Computer Science 150-159. · Zbl 0938.68927
[15] IEEE, New York.
[16] LUBY, M., RANDALL, D. and SINCLAIR, A. J. (2001). Markov chains for planar lattice structures. SIAM J. Comput. 31 167-192. · Zbl 0992.82013 · doi:10.1137/S0097539799360355
[17] LUBY, M. and VIGODA, E. (1997). Approximately counting up to four. In Proc. 29th ACM Sy mposium on Theory of Computing 682-687. ACM, New York. · Zbl 0963.68150
[18] LUBY, M. and VIGODA, E. (1999). Fast convergence of the Glauber dy namics for sampling independent sets. Random Structures Algorithms 15 229-241. · Zbl 0941.65010 · doi:10.1002/(SICI)1098-2418(199910/12)15:3/4<229::AID-RSA3>3.0.CO;2-X
[19] MADRAS, N. (1998). Umbrella sampling and simulated tempering. In Numerical Methods for Poly meric Sy stems (S. G. Whittington, ed.) 19-32. Springer, New York. · Zbl 0924.65147
[20] MADRAS, N. and PICCIONI, M. (1999). Importance sampling for families of distributions. Ann. Appl. Probab. 9 1202-1225. · Zbl 0966.60061 · doi:10.1214/aoap/1029962870
[21] MADRAS, N. and RANDALL, D. (1996). Factoring graphs to bound mixing rates. In Proc. 37th IEEE Sy mposium on Foundations of Computer Science 194-203. IEEE, New York.
[22] MADRAS, N. and SLADE, G. (1993). The Self-Avoiding Walk. Birkhäuser, Boston. · Zbl 0780.60103
[23] MARINARI, E. and PARISI, G. (1992). Simulated tempering: a new Monte Carlo scheme. Europhy s. Lett. 19 451-458.
[24] ORLANDINI, E. (1998). Monte Carlo study of poly mer sy stems by Multiple Markov Chain method. In Numerical Methods for Poly meric Sy stems (S. G. Whittington, ed.) 33-58. Springer, New York. · Zbl 0926.60081
[25] RANDALL, D. and TETALI, P. (1998). Analy zing Glauber dy namics by comparison of Markov chains. In Proc. LATIN ’98: Theoretical Informatics. Lecture Notes in Computer Sci. 1380 292-304. Springer, New York. · doi:10.1007/BFb0054330
[26] ROBERTS, G. O. and ROSENTHAL, J. S. (1997). Geometric ergodicity and hy brid Markov chains. Electron. Comm. Probab. 2 13-25. · Zbl 0890.60061
[27] ROBERTS, G. O. and TWEEDIE, R. L. (2001). Geometric L2 and L1 convergence are equivalent for reversible Markov chains. J. Appl. Probab. 38A 37-41. · Zbl 1011.60050 · doi:10.1239/jap/1085496589
[28] SINCLAIR, A. J. (1993). Randomized Algorithms for Counting and Generating Combinatorial Structures. Birkhäuser, Boston. · Zbl 0780.68096
[29] SOKAL, A. D. and THOMAS, L. E. (1989). Exponential convergence to equilibrium for a class of random-walk models. J. Statist. Phy s. 54 797-828. · Zbl 0668.60061 · doi:10.1007/BF01019776
[30] TIERNEY, L. (1998). A note on Metropolis-Hastings kernels for general state spaces. Ann. Appl. Probab. 8 1-9. · Zbl 0935.60053 · doi:10.1214/aoap/1027961031
[31] TORRIE, G. M. and VALLEAU, J. P. (1977). Nonphysical sampling distributions in Monte Carlo free energy estimation: Umbrella sampling. J. Comput. Phy s. 23 187-199.
[32] WELSH, D. J. A. (1993). Complexity: Knots, Colourings, and Counting. Cambridge Univ. Press. · Zbl 0799.68008
[33] YOSIDA, K. (1980). Functional Analy sis, 6th ed. Springer, Berlin.
[34] ZHENG, Z. (1999). Analy sis of swapping and tempering Monte Carlo algorithms. Ph.D. Thesis, York Univ.
[35] TORONTO, ONTARIO M3J 1P3 CANADA E-MAIL: madras@mathstat.yorku.ca COLLEGE OF COMPUTING AND SCHOOL OF MATHEMATICS GEORGIA INSTITUTE OF TECHNOLOGY ATLANTA GEORGIA 30332-0280 E-MAIL: randall@cc.gatech.edu
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.