Loading…
Tight bounds for mixing of the Swendsen–Wang algorithm at the Potts transition point
We study two widely used algorithms for the Potts model on rectangular subsets of the hypercubic lattice —heat bath dynamics and the Swendsen–Wang algorithm—and prove that, under certain circumstances, the mixing in these algorithms is torpid or slow. In particular, we show that for heat bath dynami...
Saved in:
| Published in: | Probability theory and related fields 2012-04, Vol.152 (3-4), p.509-557 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c419t-9560efc4bc454e912c357f5295a9d169adc00b7565c52412b4cca3eb4335bcb13 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c419t-9560efc4bc454e912c357f5295a9d169adc00b7565c52412b4cca3eb4335bcb13 |
| container_end_page | 557 |
| container_issue | 3-4 |
| container_start_page | 509 |
| container_title | Probability theory and related fields |
| container_volume | 152 |
| creator | Borgs, Christian Chayes, Jennifer T. Tetali, Prasad |
| description | We study two widely used algorithms for the Potts model on rectangular subsets of the hypercubic lattice
—heat bath dynamics and the Swendsen–Wang algorithm—and prove that, under certain circumstances, the mixing in these algorithms is
torpid
or slow. In particular, we show that for heat bath dynamics throughout the region of phase coexistence, and for the Swendsen–Wang algorithm at the transition point, the mixing time in a box of side length
L
with periodic boundary conditions has upper and lower bounds which are exponential in
L
d
-1
. This work provides the first upper bound of this form for the Swendsen–Wang algorithm, and gives lower bounds for both algorithms which significantly improve the previous lower bounds that were exponential in
L
/(log
L
)
2
. |
| doi_str_mv | 10.1007/s00440-010-0329-0 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_1019647231</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2661267661</sourcerecordid><originalsourceid>FETCH-LOGICAL-c419t-9560efc4bc454e912c357f5295a9d169adc00b7565c52412b4cca3eb4335bcb13</originalsourceid><addsrcrecordid>eNp1kc1KAzEQx4MoWKsP4C3oxcvq5Gu3OUrxCwoKVj0u2TTbprRJTbKoN9_BN_RJTK0gCB5mBmZ-85-BP0KHBE4JQHUWATiHAkgORmUBW6hHOKMFhZJvox6QalAMQJBdtBfjHAAo47SHHsd2Oku48Z2bRNz6gJf21bop9i1OM4PvX0weGPf5_vGkclstpj7YNFtilb6BO59SxCkoF22y3uGVty7to51WLaI5-Kl99HB5MR5eF6Pbq5vh-ajQnMhUSFGCaTVvNBfcSEI1E1UrqBRKTkgp1UQDNJUohRaUE9pwrRUzDWdMNLohrI9ONrqr4J87E1O9tFGbxUI547tYEyCy5BVla_ToDzr3XXD5u1rSqiIDymmGjv-DaFkSWlY5Z4psKB18jMG09SrYpQpv-V69tqPe2FFnO-q1HTn1Ed3sxMy6qQm_yv8vfQGgvIxb</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2661267661</pqid></control><display><type>article</type><title>Tight bounds for mixing of the Swendsen–Wang algorithm at the Potts transition point</title><source>ABI/INFORM Collection</source><source>Business Source Ultimate【Trial: -2024/12/31】【Remote access available】</source><source>Springer Link</source><creator>Borgs, Christian ; Chayes, Jennifer T. ; Tetali, Prasad</creator><creatorcontrib>Borgs, Christian ; Chayes, Jennifer T. ; Tetali, Prasad</creatorcontrib><description>We study two widely used algorithms for the Potts model on rectangular subsets of the hypercubic lattice
—heat bath dynamics and the Swendsen–Wang algorithm—and prove that, under certain circumstances, the mixing in these algorithms is
torpid
or slow. In particular, we show that for heat bath dynamics throughout the region of phase coexistence, and for the Swendsen–Wang algorithm at the transition point, the mixing time in a box of side length
L
with periodic boundary conditions has upper and lower bounds which are exponential in
L
d
-1
. This work provides the first upper bound of this form for the Swendsen–Wang algorithm, and gives lower bounds for both algorithms which significantly improve the previous lower bounds that were exponential in
L
/(log
L
)
2
.</description><identifier>ISSN: 0178-8051</identifier><identifier>EISSN: 1432-2064</identifier><identifier>DOI: 10.1007/s00440-010-0329-0</identifier><identifier>CODEN: PTRFEU</identifier><language>eng</language><publisher>Berlin/Heidelberg: Springer-Verlag</publisher><subject>Algorithms ; Boundary conditions ; Computer science ; Dynamic tests ; Dynamics ; Economics ; Equilibrium ; Finance ; Heat ; Insurance ; Lattices ; Lower bounds ; Management ; Markov analysis ; Mathematical analysis ; Mathematical and Computational Biology ; Mathematical and Computational Physics ; Mathematics ; Mathematics and Statistics ; Operations Research/Decision Theory ; Phase transitions ; Probability ; Probability theory ; Probability Theory and Stochastic Processes ; Quantitative Finance ; Statistical physics ; Statistics for Business ; Studies ; Temperature ; Theoretical ; Topological manifolds ; Transition points ; Upper bounds</subject><ispartof>Probability theory and related fields, 2012-04, Vol.152 (3-4), p.509-557</ispartof><rights>Springer-Verlag 2010</rights><rights>Springer-Verlag 2010.</rights><rights>Springer-Verlag 2012</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c419t-9560efc4bc454e912c357f5295a9d169adc00b7565c52412b4cca3eb4335bcb13</citedby><cites>FETCH-LOGICAL-c419t-9560efc4bc454e912c357f5295a9d169adc00b7565c52412b4cca3eb4335bcb13</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/2661267661/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$H</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/2661267661?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,780,784,11688,27924,27925,36060,36061,44363,74767</link.rule.ids></links><search><creatorcontrib>Borgs, Christian</creatorcontrib><creatorcontrib>Chayes, Jennifer T.</creatorcontrib><creatorcontrib>Tetali, Prasad</creatorcontrib><title>Tight bounds for mixing of the Swendsen–Wang algorithm at the Potts transition point</title><title>Probability theory and related fields</title><addtitle>Probab. Theory Relat. Fields</addtitle><description>We study two widely used algorithms for the Potts model on rectangular subsets of the hypercubic lattice
—heat bath dynamics and the Swendsen–Wang algorithm—and prove that, under certain circumstances, the mixing in these algorithms is
torpid
or slow. In particular, we show that for heat bath dynamics throughout the region of phase coexistence, and for the Swendsen–Wang algorithm at the transition point, the mixing time in a box of side length
L
with periodic boundary conditions has upper and lower bounds which are exponential in
L
d
-1
. This work provides the first upper bound of this form for the Swendsen–Wang algorithm, and gives lower bounds for both algorithms which significantly improve the previous lower bounds that were exponential in
L
/(log
L
)
2
.</description><subject>Algorithms</subject><subject>Boundary conditions</subject><subject>Computer science</subject><subject>Dynamic tests</subject><subject>Dynamics</subject><subject>Economics</subject><subject>Equilibrium</subject><subject>Finance</subject><subject>Heat</subject><subject>Insurance</subject><subject>Lattices</subject><subject>Lower bounds</subject><subject>Management</subject><subject>Markov analysis</subject><subject>Mathematical analysis</subject><subject>Mathematical and Computational Biology</subject><subject>Mathematical and Computational Physics</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Operations Research/Decision Theory</subject><subject>Phase transitions</subject><subject>Probability</subject><subject>Probability theory</subject><subject>Probability Theory and Stochastic Processes</subject><subject>Quantitative Finance</subject><subject>Statistical physics</subject><subject>Statistics for Business</subject><subject>Studies</subject><subject>Temperature</subject><subject>Theoretical</subject><subject>Topological manifolds</subject><subject>Transition points</subject><subject>Upper bounds</subject><issn>0178-8051</issn><issn>1432-2064</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2012</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNp1kc1KAzEQx4MoWKsP4C3oxcvq5Gu3OUrxCwoKVj0u2TTbprRJTbKoN9_BN_RJTK0gCB5mBmZ-85-BP0KHBE4JQHUWATiHAkgORmUBW6hHOKMFhZJvox6QalAMQJBdtBfjHAAo47SHHsd2Oku48Z2bRNz6gJf21bop9i1OM4PvX0weGPf5_vGkclstpj7YNFtilb6BO59SxCkoF22y3uGVty7to51WLaI5-Kl99HB5MR5eF6Pbq5vh-ajQnMhUSFGCaTVvNBfcSEI1E1UrqBRKTkgp1UQDNJUohRaUE9pwrRUzDWdMNLohrI9ONrqr4J87E1O9tFGbxUI547tYEyCy5BVla_ToDzr3XXD5u1rSqiIDymmGjv-DaFkSWlY5Z4psKB18jMG09SrYpQpv-V69tqPe2FFnO-q1HTn1Ed3sxMy6qQm_yv8vfQGgvIxb</recordid><startdate>20120401</startdate><enddate>20120401</enddate><creator>Borgs, Christian</creator><creator>Chayes, Jennifer T.</creator><creator>Tetali, Prasad</creator><general>Springer-Verlag</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7SC</scope><scope>7WY</scope><scope>7WZ</scope><scope>7XB</scope><scope>87Z</scope><scope>88I</scope><scope>8AL</scope><scope>8AO</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>8FL</scope><scope>8G5</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GNUQQ</scope><scope>GUQSH</scope><scope>H8D</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>L.-</scope><scope>L6V</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M0C</scope><scope>M0N</scope><scope>M2O</scope><scope>M2P</scope><scope>M7S</scope><scope>MBDVC</scope><scope>P5Z</scope><scope>P62</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PTHSS</scope><scope>Q9U</scope><scope>0U~</scope><scope>1-H</scope><scope>L.0</scope></search><sort><creationdate>20120401</creationdate><title>Tight bounds for mixing of the Swendsen–Wang algorithm at the Potts transition point</title><author>Borgs, Christian ; Chayes, Jennifer T. ; Tetali, Prasad</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c419t-9560efc4bc454e912c357f5295a9d169adc00b7565c52412b4cca3eb4335bcb13</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2012</creationdate><topic>Algorithms</topic><topic>Boundary conditions</topic><topic>Computer science</topic><topic>Dynamic tests</topic><topic>Dynamics</topic><topic>Economics</topic><topic>Equilibrium</topic><topic>Finance</topic><topic>Heat</topic><topic>Insurance</topic><topic>Lattices</topic><topic>Lower bounds</topic><topic>Management</topic><topic>Markov analysis</topic><topic>Mathematical analysis</topic><topic>Mathematical and Computational Biology</topic><topic>Mathematical and Computational Physics</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Operations Research/Decision Theory</topic><topic>Phase transitions</topic><topic>Probability</topic><topic>Probability theory</topic><topic>Probability Theory and Stochastic Processes</topic><topic>Quantitative Finance</topic><topic>Statistical physics</topic><topic>Statistics for Business</topic><topic>Studies</topic><topic>Temperature</topic><topic>Theoretical</topic><topic>Topological manifolds</topic><topic>Transition points</topic><topic>Upper bounds</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Borgs, Christian</creatorcontrib><creatorcontrib>Chayes, Jennifer T.</creatorcontrib><creatorcontrib>Tetali, Prasad</creatorcontrib><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>ABI/INFORM Collection</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection</collection><collection>Science Database (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest Pharma Collection</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>Research Library (Alumni Edition)</collection><collection>Materials Science & Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central UK/Ireland</collection><collection>Advanced Technologies & Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>Research Library Prep</collection><collection>Aerospace Database</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer Science Database</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ProQuest Engineering Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>ABI/INFORM Collection</collection><collection>Computing Database</collection><collection>ProQuest Research Library</collection><collection>Science Database</collection><collection>ProQuest Engineering Database</collection><collection>Research Library (Corporate)</collection><collection>ProQuest Advanced Technologies & Aerospace Database</collection><collection>ProQuest Advanced Technologies & Aerospace Collection</collection><collection>One Business (ProQuest)</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>Engineering Collection</collection><collection>ProQuest Central Basic</collection><collection>Global News & ABI/Inform Professional</collection><collection>Trade PRO</collection><collection>ABI/INFORM Professional Standard</collection><jtitle>Probability theory and related fields</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Borgs, Christian</au><au>Chayes, Jennifer T.</au><au>Tetali, Prasad</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Tight bounds for mixing of the Swendsen–Wang algorithm at the Potts transition point</atitle><jtitle>Probability theory and related fields</jtitle><stitle>Probab. Theory Relat. Fields</stitle><date>2012-04-01</date><risdate>2012</risdate><volume>152</volume><issue>3-4</issue><spage>509</spage><epage>557</epage><pages>509-557</pages><issn>0178-8051</issn><eissn>1432-2064</eissn><coden>PTRFEU</coden><abstract>We study two widely used algorithms for the Potts model on rectangular subsets of the hypercubic lattice
—heat bath dynamics and the Swendsen–Wang algorithm—and prove that, under certain circumstances, the mixing in these algorithms is
torpid
or slow. In particular, we show that for heat bath dynamics throughout the region of phase coexistence, and for the Swendsen–Wang algorithm at the transition point, the mixing time in a box of side length
L
with periodic boundary conditions has upper and lower bounds which are exponential in
L
d
-1
. This work provides the first upper bound of this form for the Swendsen–Wang algorithm, and gives lower bounds for both algorithms which significantly improve the previous lower bounds that were exponential in
L
/(log
L
)
2
.</abstract><cop>Berlin/Heidelberg</cop><pub>Springer-Verlag</pub><doi>10.1007/s00440-010-0329-0</doi><tpages>49</tpages><oa>free_for_read</oa></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0178-8051 |
| ispartof | Probability theory and related fields, 2012-04, Vol.152 (3-4), p.509-557 |
| issn | 0178-8051 1432-2064 |
| language | eng |
| recordid | cdi_proquest_miscellaneous_1019647231 |
| source | ABI/INFORM Collection; Business Source Ultimate【Trial: -2024/12/31】【Remote access available】; Springer Link |
| subjects | Algorithms Boundary conditions Computer science Dynamic tests Dynamics Economics Equilibrium Finance Heat Insurance Lattices Lower bounds Management Markov analysis Mathematical analysis Mathematical and Computational Biology Mathematical and Computational Physics Mathematics Mathematics and Statistics Operations Research/Decision Theory Phase transitions Probability Probability theory Probability Theory and Stochastic Processes Quantitative Finance Statistical physics Statistics for Business Studies Temperature Theoretical Topological manifolds Transition points Upper bounds |
| title | Tight bounds for mixing of the Swendsen–Wang algorithm at the Potts transition point |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T23%3A25%3A37IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Tight%20bounds%20for%20mixing%20of%20the%20Swendsen%E2%80%93Wang%20algorithm%20at%20the%20Potts%20transition%20point&rft.jtitle=Probability%20theory%20and%20related%20fields&rft.au=Borgs,%20Christian&rft.date=2012-04-01&rft.volume=152&rft.issue=3-4&rft.spage=509&rft.epage=557&rft.pages=509-557&rft.issn=0178-8051&rft.eissn=1432-2064&rft.coden=PTRFEU&rft_id=info:doi/10.1007/s00440-010-0329-0&rft_dat=%3Cproquest_cross%3E2661267661%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c419t-9560efc4bc454e912c357f5295a9d169adc00b7565c52412b4cca3eb4335bcb13%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2661267661&rft_id=info:pmid/&rfr_iscdi=true |