Systematic scan for sampling colorings. (English) Zbl 1095.60024
The systematic scan for some spin system is studied. The most part of the paper is devoted to proper \(q\)-colorings of a path of \(n\) vertices (the one-dimensional \(q\)-state Potts model at zero temperature). Tight (i.e., matching within a constant factor) upper and lower bounds on mixing time are provided. Measuring mixing time in terms of the number of updates of individual vertices (so that one scan equal to \(n\) updates), the authors show that when \(q=3,\) mixing occurs in \(\Theta(n^3\log n)\) updates, whether Glauber dynamics or systematic scan is used; while when \(q\geq 4\), mixing occurs in \(\Theta(n\log n)\) updates, again independently of whether Glauber or scan is used. Also for “\(H\)-colorings” model arbitrary spin systems with symmetric “hard” constraints it is shown that for any \(H\), Glauber mixes in \(O(n^5)\) updates and scan in \(O(n^6)\) updates.
Reviewer: Utkir Rozikov (Tashkent)
MSC:
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
| 05C15 | Coloring of graphs and hypergraphs |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68W20 | Randomized algorithms |
| 82B20 | Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics |
References:
| [1] | Aldous, D. (1982). Some inequalities for reversible Markov chains. J. London Math. Soc. (2) 25 564–576. · Zbl 0489.60077 · doi:10.1112/jlms/s2-25.3.564 |
| [2] | Aldous, D. and Fill, J. (1996). Reversible Markov chains and random walks on graphs. Available at http://oz.berkeley.edu/users/aldous/RWG/book.html. |
| [3] | Amit, Y. (1996). Convergence properties of the Gibbs sampler for perturbations of Gaussians. Ann. Statist. 24 122–140. · Zbl 0854.60066 · doi:10.1214/aos/1033066202 |
| [4] | Azuma, K. (1967). Weighted sums of certain dependent random variables. Tôhoku Math. J. 19 357–367. · Zbl 0178.21103 · doi:10.2748/tmj/1178243286 |
| [5] | Benjamini, I., Berger, N., Hoffman, C. and Mossel, E. (2005). Mixing times of the biased card shuffling and the asymmetric exclusion process. Trans. Amer. Math. Soc. 357 3013–3029. · Zbl 1071.60095 · doi:10.1090/S0002-9947-05-03610-X |
| [6] | Bubley, R. and Dyer, M. (1997). Path coupling: A technique for proving rapid mixing in Markov chains. Proceedings of the 38th IEEE Annual Symposium on Foundations of Computer Science 223–231. |
| [7] | Cooper, C., Dyer, M. and Frieze, A. (2001). On Markov chains for randomly \(H\)-colouring a graph. J. Algorithms 39 117–134. · Zbl 0974.68149 · doi:10.1006/jagm.2000.1142 |
| [8] | Diaconis, P. and Ram, A. (2000). Analysis of systematic scan metropolis algorithm using Iwahori–Hecke algebra techniques. Michigan Math. J. 48 157–190. · Zbl 0998.60069 · doi:10.1307/mmj/1030132713 |
| [9] | Diaconis, P. and Saloff-Coste, L. (1993). Comparison theorems for reversible Markov chains. Ann. Appl. Probab. 3 696–730. JSTOR: · Zbl 0799.60058 · doi:10.1214/aoap/1177005359 |
| [10] | Diaconis, P. and Stroock, D. (1991). Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab. 1 36–61. · Zbl 0731.60061 · doi:10.1214/aoap/1177005980 |
| [11] | Durrett, R. (1991). Probability : Theory and Examples . Brooks/Cole Publishing Company. · Zbl 0709.60002 |
| [12] | Dyer, M., Frieze, A. and Jerrum, M. (2002). On counting independent sets in sparse graphs. SIAM J. Comput. 31 1527–1541. · Zbl 1041.68045 · doi:10.1137/S0097539701383844 |
| [13] | Dyer, M., Goldberg, L. A., Greenhill, C., Jerrum, M. and Mitzenmacher, M. (2001). An extension of path coupling and its application to the Glauber dynamics for graph colorings. SIAM J. Comput. 30 1962–1975. · Zbl 0999.05035 · doi:10.1137/S0097539700372708 |
| [14] | Dyer, M., Goldberg, L. A., Jerrum, M. and Martin, R. (2004). Markov chain comparison. · Zbl 1189.60135 · doi:10.1214/154957806000000041 |
| [15] | Dyer, M., Jerrum, M. and Vigoda, E. (2004). Rapidly mixing Markov chains for dismantleable constraint graphs. In Proceedings of a DIMACS/DIMATIA Workshop on Graphs, Morphisms and Statistical Physics (J. Nesetril and P. Winkler, eds.). · Zbl 1061.05031 |
| [16] | Fill, J. A. (1991). Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process. Ann. Appl. Probab. 1 62–87. JSTOR: · Zbl 0726.60069 · doi:10.1214/aoap/1177005981 |
| [17] | Fishman, G. S. (1996). Coordinate selection rules for Gibbs sampling. Ann. Appl. Probab. 6 444–465. · Zbl 0855.60060 · doi:10.1214/aoap/1034968139 |
| [18] | Glauber, R. J. (1963). Time-dependent statistics of the Ising model. J. Math. Phys. 4 294–307. · Zbl 0145.24003 · doi:10.1063/1.1703954 |
| [19] | Goldberg, L. A., Kelk, S. and Paterson, M. (2004). The complexity of choosing an \(H\)-colouring (nearly) uniformly at random. SIAM J. Comput. 33 416–432. · Zbl 1105.68114 · doi:10.1137/S0097539702408363 |
| [20] | Goldberg, L. A., Martin, R. and Paterson, M. (2004). Random sampling of \(3\)-colourings in \(\mathbbZ^2\). Random Structures Algorithms 24 279–302. · Zbl 1044.60100 · doi:10.1002/rsa.20002 |
| [21] | Janson, S., Łuczak, T. and Rucinski, A. (2000). Random Graphs . Wiley, New York. |
| [22] | Jerrum, M. (1995). A very simple algorithm for estimating the number of \(k\)-colourings of a low-degree graph. Random Structures Algorithms 7 157–165. · Zbl 0833.60070 · doi:10.1002/rsa.3240070205 |
| [23] | Jerrum, M. (2003). Counting, Sampling and Integrating: Algorithms and Complexity . Birkhäuser, Boston. · Zbl 1011.05001 |
| [24] | Kenyon, C. and Randall, D. (2000). Personal communication. |
| [25] | Luby, M., Randall, D. and Sinclair, A. J. (2001). Markov chain algorithms for planar lattice structures. SIAM J. Comput. 31 167–192. · Zbl 0992.82013 · doi:10.1137/S0097539799360355 |
| [26] | Sinclair, A. (1992). Improved bounds for mixing rates of Markov chains and multicommodity flow. Combin. Probab. Comput. 1 351–370. · Zbl 0801.90039 · doi:10.1017/S0963548300000390 |
| [27] | Sinclair, A. and Jerrum, M. (1989). Approximate counting, uniform generation and rapidly mixing Markov chains. Inform. and Comput. 82 93–133. · Zbl 0668.05060 · doi:10.1016/0890-5401(89)90067-9 |
| [28] | van den Berg, J. (1993). A uniqueness condition for Gibbs measures, with application to the \(2\)-dimensional Ising antiferromagnet. Commun. Math. Phys. 152 161–166. · Zbl 0768.60098 · doi:10.1007/BF02097061 |
| [29] | Wilson, D. B. (2004). Mixing times of lozenge tiling and card shuffling Markov chains. Ann. Appl. Probab. 14 274–325. · Zbl 1040.60063 · doi:10.1214/aoap/1075828054 |
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.
