乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T04:24:28Z","timestamp":1728361468452},"reference-count":50,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2023,11,8]],"date-time":"2023-11-08T00:00:00Z","timestamp":1699401600000},"content-version":"am","delay-in-days":365,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#am"},{"start":{"date-parts":[[2022,11,8]],"date-time":"2022-11-08T00:00:00Z","timestamp":1667865600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF\u20101850443","CCF\u20102007022","CCF\u20102007287"],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[2023,7]]},"abstract":"Abstract<\/jats:title>The Swendsen\u2013Wang algorithm is a sophisticated, widely\u2010used Markov chain for sampling from the Gibbs distribution for the ferromagnetic Ising and Potts models. This chain has proved difficult to analyze, due in part to its global nature. We present optimal bounds on the convergence rate of the Swendsen\u2013Wang algorithm for the complete \u2010ary tree. Our bounds extend to the non\u2010uniqueness region and apply to all boundary conditions. We show that the spatial mixing conditions known asvariance mixing<\/jats:italic>andentropy mixing<\/jats:italic>imply spectral gap and mixing time, respectively, for the Swendsen\u2013Wang dynamics on the \u2010ary tree. We also show that these bounds are asymptotically optimal. As a consequence, we establish mixing for the Swendsen\u2013Wang dynamics forall<\/jats:italic>boundary conditions throughout (and beyond) the tree uniqueness region. Our proofs feature a novel spectral view of the variance mixing condition and utilize recent work on block factorization of entropy.<\/jats:p>","DOI":"10.1002\/rsa.21121","type":"journal-article","created":{"date-parts":[[2022,11,9]],"date-time":"2022-11-09T06:00:05Z","timestamp":1667973605000},"page":"791-831","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["The Swendsen\u2013Wang dynamics on trees"],"prefix":"10.1002","volume":"62","author":[{"given":"Antonio","family":"Blanca","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Pennsylvania State University State College Pennsylvania USA"}]},{"given":"Zongchen","family":"Chen","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Massachusetts Institute of Technology Cambridge Massachusetts USA"}]},{"given":"Daniel","family":"\u0160tefankovi\u010d","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Rochester Rochester New York USA"}]},{"given":"Eric","family":"Vigoda","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of California Santa Barbara California USA"}]}],"member":"311","published-online":{"date-parts":[[2022,11,8]]},"reference":[{"issue":"10","key":"e_1_2_10_2_1","first-page":"1258","article-title":"New connectivity and MSF algorithms for shuffle\u2010exchange network and PRAM","volume":"36","author":"Awerbuch B.","year":"1987","journal-title":"IEEE Comput Arch. Lett."},{"key":"e_1_2_10_3_1","doi-asserted-by":"crossref","unstructured":"V. L.AlevandL. C.Lau Improved analysis of higher order random walks and applications Proc. 61st Annu. IEEE Symp. Found. Comput. Sci. (FOCS). IEEE 2020.","DOI":"10.1145\/3357713.3384317"},{"key":"e_1_2_10_4_1","doi-asserted-by":"crossref","unstructured":"N.Anari K.Liu andS.Oveis Gharan Spectral independence in high\u2010dimensional expanders and applications to the hardcore model Proc. 52nd Annu. ACM Symp. Theory Comput. (STOC) 2020.","DOI":"10.1109\/FOCS46700.2020.00125"},{"key":"e_1_2_10_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-011-0353-8"},{"key":"e_1_2_10_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-004-0369-4"},{"key":"e_1_2_10_7_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1935.0122"},{"key":"e_1_2_10_8_1","doi-asserted-by":"crossref","unstructured":"A.Blanca P.Caputo D.Parisi A.Sinclair andE.Vigoda Entropy decay in the Swendsen\u2010Wang dynamics. Preprint 2020. Available from arXiv at:https:\/\/arxiv.org\/abs\/2007.06931.","DOI":"10.1145\/3406325.3451095"},{"key":"e_1_2_10_9_1","doi-asserted-by":"crossref","unstructured":"A.Blanca P.Caputo D.Parisi A.Sinclair andE.Vigoda Entropy decay in the Swendsen\u2010Wang dynamics on\u2124d$$ {\\mathbb{Z}}^d $$ Proc. 53st Annu. ACM Symp. Theory Comput (STOC) 2021.","DOI":"10.1214\/21-AAP1702"},{"key":"e_1_2_10_10_1","doi-asserted-by":"crossref","unstructured":"A.Blanca P.Caputo A.Sinclair andE.Vigoda Spatial mixing and non\u2010local Markov chains Proc. 29th Annu. ACM\u2010SIAM Symp. Discr. Algor. (SODA) 2018 pp. 1965\u20131980.","DOI":"10.1137\/1.9781611975031.128"},{"key":"e_1_2_10_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1219722"},{"key":"e_1_2_10_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/19-AAP1505"},{"key":"e_1_2_10_13_1","unstructured":"A.BlancaandA.Sinclair Dynamics for the mean\u2010field random\u2010cluster model Proc. 19th Int. Worksh. Random. Comput. 2015 pp. 528\u2013543."},{"key":"e_1_2_10_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20569"},{"key":"e_1_2_10_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-021-04237-1"},{"key":"e_1_2_10_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008792"},{"key":"e_1_2_10_17_1","doi-asserted-by":"crossref","unstructured":"A.Coja\u2010Oghlan A.Galanis L. A.Goldberg J. B.Ravelomanana D.Stefankovic andE.Vigoda Metastability of the Potts ferromagnet on random regular graphs. Preprint 2022. Available from arXiv at: arXiv preprint arXiv:2202.05777.","DOI":"10.1007\/s00220-023-04644-6"},{"key":"e_1_2_10_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<242::AID-RSA4>3.0.CO;2-C"},{"key":"e_1_2_10_19_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1904507"},{"key":"e_1_2_10_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-012-0599-2"},{"issue":"6","key":"e_1_2_10_21_1","first-page":"1363","article-title":"Discontinuity of the phase transition for the planar random\u2010cluster and Potts models with q>4$$ q>4 $$","volume":"54","author":"Duminil\u2010Copin H.","year":"2022","journal-title":"Annales de l'ENS"},{"key":"e_1_2_10_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-016-2759-8"},{"key":"e_1_2_10_23_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1034968224"},{"key":"e_1_2_10_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20004"},{"key":"e_1_2_10_25_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevD.38.2009"},{"key":"e_1_2_10_26_1","unstructured":"A.Galanis D.\u0160tefankovi\u010d andE.Vigoda Swendsen\u2010Wang algorithm on the mean\u2010field Potts model Proc. 19th Int. Worksh. Random. Comput. 2015 pp. 815\u2013828."},{"key":"e_1_2_10_27_1","doi-asserted-by":"publisher","DOI":"10.1515\/9783110850147"},{"key":"e_1_2_10_28_1","doi-asserted-by":"crossref","unstructured":"A.GerschenfeldandA.Montanari Reconstruction for models on random graphs Proc. 48th Annu IEEE Symp. Found. Comput. Sci. (FOCS) 2007 pp. 194\u2013204.","DOI":"10.1109\/FOCS.2007.58"},{"key":"e_1_2_10_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268765"},{"key":"e_1_2_10_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01247839"},{"key":"e_1_2_10_31_1","doi-asserted-by":"crossref","unstructured":"T. P.HayesandA.Sinclair A general lower bound for mixing of single\u2010site dynamics on graphs Proc. 46th Annu. IEEE Symp. Found. Comput. Sci. (FOCS) 2005 pp. 511\u2013520.","DOI":"10.1109\/SFCS.2005.6"},{"key":"e_1_2_10_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10071"},{"key":"e_1_2_10_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2017.11.017"},{"key":"e_1_2_10_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-8005-3"},{"key":"e_1_2_10_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"key":"e_1_2_10_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-4149(98)00086-6"},{"key":"e_1_2_10_37_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X"},{"key":"e_1_2_10_38_1","doi-asserted-by":"publisher","DOI":"10.1090\/mbk\/058"},{"key":"e_1_2_10_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-009-0963-5"},{"key":"e_1_2_10_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02101929"},{"key":"e_1_2_10_41_1","doi-asserted-by":"crossref","unstructured":"F.Martinelli A.Sinclair andD.Weitz The Ising model on trees: Boundary conditions and mixing time Proc. 44th Annu. IEEE Symp. Found. Comput. Sci. (FOCS) 2003 628\u2013639.","DOI":"10.1109\/SFCS.2003.1238235"},{"key":"e_1_2_10_42_1","unstructured":"F.Martinelli A.Sinclair andD.Weitz Fast mixing for independent sets colorings and other model on trees Proc. 15th Annu. ACM\u2010SIAM Symp. Discr. Algor. (SODA). ACM 2004 pp. 449\u2013458."},{"volume-title":"Mathematical aspects of mixing times in Markov chains","year":"2006","author":"Montenegro R.","key":"e_1_2_10_43_1"},{"key":"e_1_2_10_44_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1060202828"},{"key":"e_1_2_10_45_1","doi-asserted-by":"publisher","DOI":"10.1214\/11-AOP737"},{"key":"e_1_2_10_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/120885498"},{"key":"e_1_2_10_47_1","series-title":"Lectures on Probability Theory and Statistics","first-page":"301","volume-title":"Lectures on finite Markov chains","author":"Saloff\u2010Coste L.","year":"1997"},{"key":"e_1_2_10_48_1","doi-asserted-by":"publisher","DOI":"10.1214\/10-AOP584"},{"key":"e_1_2_10_49_1","doi-asserted-by":"publisher","DOI":"10.1214\/16-AAP1253"},{"key":"e_1_2_10_50_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.58.86"},{"key":"e_1_2_10_51_1","doi-asserted-by":"publisher","DOI":"10.4064\/dm502-0-1"}],"container-title":["Random Structures & Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.21121","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/rsa.21121","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/am-pdf\/10.1002\/rsa.21121","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.21121","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T19:32:01Z","timestamp":1728329521000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.21121"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,8]]},"references-count":50,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["10.1002\/rsa.21121"],"URL":"https:\/\/doi.org\/10.1002\/rsa.21121","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"type":"print","value":"1042-9832"},{"type":"electronic","value":"1098-2418"}],"subject":[],"published":{"date-parts":[[2022,11,8]]},"assertion":[{"value":"2021-05-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}