{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T08:26:28Z","timestamp":1791447988685,"version":"4.3.3"},"reference-count":21,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2008,11,1]],"date-time":"2008-11-01T00:00:00Z","timestamp":1225497600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2008,11]]},"abstract":"<jats:p>We consider Glauber dynamics on finite spin systems. The mixing time of Glauber dynamics can be bounded in terms of the influences of sites on each other. We consider three parameters bounding these influences: \u03b1, the total influence on a site, as studied by Dobrushin; \u03b1\u2032, the total influence of a site, as studied by Dobrushin and Shlosman; and \u03b1\u2033, the total influence of a site in any given context, which is related to the path-coupling method of Bubley and Dyer. It is known that if any of these parameters is less than 1 then random-update Glauber dynamics (in which a randomly chosen site is updated at each step) is rapidly mixing. It is also known that the Dobrushin condition \u03b1 &lt; 1 implies that systematic-scan Glauber dynamics (in which sites are updated in a deterministic order) is rapidly mixing. This paper studies two related issues, primarily in the context of systematic scan: (1) the relationship between the parameters \u03b1, \u03b1\u2032 and \u03b1\u2033, and (2) the relationship between proofs of rapid mixing using Dobrushin uniqueness (which typically use analysis techniques) and proofs of rapid mixing using path coupling. We use matrix balancing to show that the Dobrushin\u2013Shlosman condition \u03b1\u2032 &lt; 1 implies rapid mixing of systematic scan. An interesting question is whether the rapid mixing results for scan can be extended to the \u03b1 = 1 or \u03b1\u2032 = 1 case. We give positive results for the rapid mixing of systematic scan for certain \u03b1 = 1 cases. As an application, we show rapid mixing of systematic scan (for any scan order) for heat-bath Glauber dynamics for proper<jats:italic>q<\/jats:italic>-colourings of a degree-\u0394 graph<jats:italic>G<\/jats:italic>when<jats:italic>q<\/jats:italic>\u2265 2\u0394.<\/jats:p>","DOI":"10.1017\/s0963548308009437","type":"journal-article","created":{"date-parts":[[2008,10,6]],"date-time":"2008-10-06T06:08:45Z","timestamp":1223273325000},"page":"761-779","source":"Crossref","is-referenced-by-count":14,"title":["Dobrushin Conditions and Systematic Scan"],"prefix":"10.1017","volume":"17","author":[{"given":"MARTIN","family":"DYER","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"LESLIE ANN","family":"GOLDBERG","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"MARK","family":"JERRUM","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2008,11,1]]},"reference":[{"key":"S0963548308009437_ref15","unstructured":"[15] Pedersen K. Personal communication."},{"key":"S0963548308009437_ref2","doi-asserted-by":"crossref","unstructured":"[2] Bubley R. and Dyer M. E. (1997) Path coupling: A technique for proving rapid mixing in Markov chains. In Proc. 38th Annual Symposium on Foundations of Computer Science (FOCS '97), pp. 223\u2013231.","DOI":"10.1109\/SFCS.1997.646111"},{"key":"S0963548308009437_ref1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-25.3.564"},{"key":"S0963548308009437_ref9","doi-asserted-by":"publisher","DOI":"10.1214\/105051605000000683"},{"key":"S0963548308009437_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(99)00263-3"},{"key":"S0963548308009437_ref13","doi-asserted-by":"crossref","unstructured":"[13] Lov\u00e1sz L. and Winkler P. (1995) Mixing of random walks and other diffusions on a graph. In Surveys in Combinatorics ( Rowlinson P. , ed.), Vol. 218 of London Mathematical Society Lecture Notes, pp. 119\u2013154.","DOI":"10.1017\/CBO9780511662096.007"},{"key":"S0963548308009437_ref7","doi-asserted-by":"publisher","DOI":"10.1137\/1115049"},{"key":"S0963548308009437_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(01)00320-2"},{"key":"S0963548308009437_ref18","volume-title":"The Statistical Mechanics of Lattice Gases","author":"Simon","year":"1993"},{"key":"S0963548308009437_ref6","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005980"},{"key":"S0963548308009437_ref5","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005359"},{"key":"S0963548308009437_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02199113"},{"key":"S0963548308009437_ref20","first-page":"21","article-title":"A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models","volume":"7","author":"Sokal","year":"2001","journal-title":"Markov Processes and Related Fields"},{"key":"S0963548308009437_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4899-6653-7_20"},{"key":"S0963548308009437_ref17","volume-title":"Non-Negative Matrices and Markov Chains","author":"Seneta","year":"2006"},{"key":"S0963548308009437_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300000390"},{"key":"S0963548308009437_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/0022-1236(82)90053-2"},{"key":"S0963548308009437_ref10","doi-asserted-by":"publisher","DOI":"10.1214\/154957806000000041"},{"key":"S0963548308009437_ref21","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20073"},{"key":"S0963548308009437_ref14","doi-asserted-by":"crossref","unstructured":"[14] Martin R. and Randall D. (2000) Sampling adsorbing staircase walks using a new Markov chain decomposition method. In Proc. 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2000), pp. 492\u2013502.","DOI":"10.1109\/SFCS.2000.892137"},{"key":"S0963548308009437_ref11","first-page":"101","volume-title":"Surveys in Combinatorics","author":"Dyer","year":"1999"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548308009437","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T08:22:58Z","timestamp":1557822178000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548308009437\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,11]]},"references-count":21,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2008,11]]}},"alternative-id":["S0963548308009437"],"URL":"https:\/\/doi.org\/10.1017\/s0963548308009437","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,11]]}}}