Hitting Time Asymptotics for Hard-Core Interactions on Grids

详细信息    查看全文

• 作者：F. R. Nardi ; A. Zocca ; S. C. Borst
• 关键词：Hard ; core model ; Hitting times ; Metropolis Markov chains ; Finite grid graphs ; Mixing times ; Low temperature
• 刊名：Journal of Statistical Physics
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：162
• 期：2
• 页码：522-576
• 全文大小：1,296 KB
• 参考文献：1.Beltrán, J., Landim, C.: Tunneling and metastability of continuous time Markov chains. J. Stat. Phys. 140(6), 1065–1114 (2010)MATH MathSciNet CrossRef
  2.Beltrán, J., Landim, C.: Metastability of reversible finite state Markov processes. Stoch. Process. Appl. 121(8), 1633–1677 (2011)MATH CrossRef
  3.Benois, O., Landim, C., Mourragui, M.: Hitting times of rare events in Markov chains. J. Stat. Phys. 153(6), 967–990 (2013)MATH MathSciNet CrossRef ADS
  4.Borgs, C., Chayes, J.T., Frieze, A., Tetali, P., Vigoda, E., Van, H.V.: Torpid mixing of some Monte Carlo Markov chain algorithms in statistical physics. In: 40th Annual Symposium on Foundations of Computer Science, 1999, pp. 218–229 (1999)
  5.Bovier, A., Eckhoff, M., Gayrard, V., Klein, M.: Metastability and low lying spectra in reversible Markov chains. Commun. Math. Phys. 228(2), 219–255 (2002)MATH MathSciNet CrossRef ADS
  6.Bovier, A., Eckhoff, M., Gayrard, V., Klein, M.: Metastability in reversible diffusion processes I. Sharp asymptotics for capacities and exit times. J. Eur. Math. Soc. 6(4), 399–424 (2004)MATH MathSciNet CrossRef
  7.Bovier, A., Gayrard, V., Klein, M.: Metastability in reversible diffusion processes II: precise asymptotics for small eigenvalues. J. Eur. Math. Soc. 7(1), 69–99 (2005)MATH MathSciNet CrossRef
  8.Cassandro, M., Galves, A., Olivieri, E., Vares, M.E.: Metastable behavior of stochastic dynamics: a pathwise approach. J. Stat. Phys. 35(5–6), 603–634 (1984)MATH MathSciNet CrossRef ADS
  9.Catoni, O.: Sharpe large deviations estimates for simulated annealing algorithms. Ann. Inst. Henri Poincaré 27(3), 291–383 (1991)MATH MathSciNet
  10.Catoni, O.: Rough large deviation estimates for simulated annealing: application to exponential schedules. Ann. Probab. 20(3), 1109–1146 (1992)MATH MathSciNet CrossRef
  11.Catoni, O.: Simulated annealing algorithms and Markov chains with rare transitions. In: Séminaire de probabilités XXXIII. Volume 1709 of Lecture Notes in Mathematics, pp. 69–119. Springer, Berlin (1999)
  12.Catoni, O., Cerf, R.: The exit path of a Markov chain with rare transitions. ESAIM Probab. Stat. 1, 95–144 (1997)MathSciNet CrossRef
  13.Catoni, O., Trouvé, A.: Parallel Annealing by Multiple Trials: A Mathematical Study. Simulated Annealing: Parallelization Techniques, pp. 129–144. Wiley, New York (1992)
  14.Cirillo, E.N.M., Nardi, F.R.: Metastability for a stochastic dynamics with a parallel heat bath updating rule. J. Stat. Phys. 110(1–2), 183–217 (2003)MATH MathSciNet CrossRef
  15.Cirillo, E.N.M., Nardi, F.R.: Relaxation height in energy landscapes: an application to multiple metastable states. J. Stat. Phys. 150(6), 1080–1114 (2013)MATH MathSciNet CrossRef ADS
  16.Cirillo, E.N.M., Nardi, F.R., Sohier, J.: A comparison between different cycle decompositions for Metropolis dynamics (2014). arXiv:​1401.​3522
  17.Cirillo, E.N.M., Nardi, F.R., Sohier, J.: Metastability for general dynamics with rare transitions: escape time and critical configurations. J. Stat. Phys. (2015)
  18.Cirillo, E.N.M., Nardi, F.R., Spitoni, C.: Metastability for reversible probabilistic cellular automata with self-interaction. J. Stat. Phys. 132(3), 431–471 (2008)MATH MathSciNet CrossRef ADS
  19.den Hollander, F., Nardi, F.R., Olivieri, E., Scoppola, E.: Droplet growth for three-dimensional Kawasaki dynamics. Probab. Theory Relat. Fields 125(2), 153–194 (2003)MATH CrossRef
  20.den Hollander, F., Olivieri, E., Scoppola, E.: Metastability and nucleation for conservative dynamics. J. Math. Phys. 41(3), 1424 (2000)MATH MathSciNet CrossRef ADS
  21.Fernandez, R., Manzo, F., Nardi, F.R., Scoppola, E.: Asymptotically exponential hitting times and metastability: a pathwise approach without reversibility (2014). arXiv:​1406.​2637v1
  22.Galvin, D.: Independent Sets in the Discrete Hypercube. Available on the Author’s Web Page, pp. 1–16 (2006)
  23.Galvin, D.: Sampling independent sets in the discrete torus. Random Struct. Algorithms 33(3), 356–376 (2008)MATH MathSciNet CrossRef
  24.Galvin, D., Tetali, P.: Slow mixing of Glauber dynamics for the hard-core model on regular bipartite graphs. Random Struct. Algorithms 28(4), 427–443 (2006)MATH MathSciNet CrossRef
  25.Gaunt, D.S., Fisher, M.E.: Hard-sphere lattice gases. I. Plane-square lattice. J. Chem. Phys. 43(8), 2840–2863 (1965)MathSciNet CrossRef ADS
  26.Holley, R.A., Stroock, D.W.: Simulated annealing via Sobolev inequalities. Commun. Math. Phys. 115(4), 553–569 (1988)MATH MathSciNet CrossRef ADS
  27.Kelly, F.P.: Loss networks. Ann. Appl. Probab. 1(3), 319–378 (1991)MATH MathSciNet CrossRef
  28.Kotecký, R., Olivieri, E.: Droplet dynamics for asymmetric Ising model. J. Stat. Phys. 70(5–6), 1121–1148 (1993)MATH CrossRef ADS
  29.Lee, C.-H., Eun, D.Y., Yun, S.-Y., Yi, Y.: From glauber dynamics to metropolis algorithm: smaller delay in optimal CSMA. In: 2012 IEEE International Symposium on Information Theory (ISIT) Proceedings, pp. 2681–2685. IEEE (2012)
  30.Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. AMS, Providence (2009)MATH
  31.Manzo, F., Nardi, F.R., Olivieri, E., Scoppola, E.: On the essential features of metastability: tunnelling time and critical configurations. J. Stat. Phys. 115(1/2), 591–642 (2004)MATH MathSciNet CrossRef ADS
  32.Miclo, L.: About relaxation time of finite generalized Metropolis algorithms. Ann. Appl. Probab. 12(4), 1492–1515 (2002)MATH MathSciNet CrossRef
  33.Nardi, F.R., Olivieri, E., Scoppola, E.: Anisotropy effects in nucleation for conservative dynamics. J. Stat. Phys. 119(3–4), 539–595 (2005)MATH MathSciNet CrossRef ADS
  34.Neves, E.J., Schonmann, R.H.: Critical droplets and metastability for a Glauber dynamics at very low temperatures. Commun. Math. Phys. 137(2), 209–230 (1991)MATH MathSciNet CrossRef ADS
  35.Olivieri, E., Scoppola, E.: Markov chains with exponentially small transition probabilities: first exit problem from a general domain. I. The reversible case. J. Stat. Phys. 79(3–4), 613–647 (1995)MATH MathSciNet CrossRef ADS
  36.Olivieri, E., Scoppola, E.: Markov chains with exponentially small transition probabilities: first exit problem from a general domain. II. The general case. J. Stat. Phys. 84(5–6), 987–1041 (1996)MATH MathSciNet CrossRef ADS
  37.Olivieri, E., Vares, M.E.: Large Deviations and Metastability. CUP, Cambridge (2005)CrossRef
  38.Randall, D.: Slow mixing of glauber dynamics via topological obstructions. In: Proceedings of SODA ’06, pp. 870–879 (2006)
  39.Scoppola, E.: Renormalization and graph methods for Markov chains. In: Advances in Dynamical Systems and Quantum Physics, pp. 260–281. Capri (1993)
  40.Trouvé, A.: Rough large deviation estimates for the optimal convergence speed exponent of generalized simulated annealing algorithms. Ann. Inst. H. Poincaré Probab. Stat. 32, 299–348 (1994)
  41.van den Berg, J., Steif, J.E.: Percolation and the hard-core lattice gas model. Stoch. Process. Appl. 49(2), 179–197 (1994)MATH CrossRef
  42.Wang, X., Kar, K.: Throughput modelling and fairness issues in CSMA/CA based ad-hoc networks. In: Proceedings INFOCOM, 2005, pp. 23–34. IEEE (2005)
  43.Zocca, A., Borst, S.C., van Leeuwaarden, J.S.H.: Mixing properties of CSMA networks on partite graphs. In: Proceedings of VALUETOOLS 2012, pp. 117–126. IEEE (2012)
  44.Zocca, A., Borst, S.C., van Leeuwaarden, J.S.H., Nardi, F.R.: Delay performance in random-access grid networks. Perform. Eval. 70(10), 900–915 (2013)CrossRef
  
• 作者单位：F. R. Nardi (1)
  A. Zocca (1)
  S. C. Borst (1) (2)
  
  1. Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, The Netherlands
  2. Department of Mathematics of Networks and Communications, Alcatel-Lucent Bell Labs, Murray Hill, NJ, USA
  
• 刊物类别：Physics and Astronomy
• 刊物主题：Physics
  Statistical Physics
  Mathematical and Computational Physics
  Physical Chemistry
  Quantum Physics
  
• 出版者：Springer Netherlands
• ISSN：1572-9613

文摘

We consider the hard-core model with Metropolis transition probabilities on finite grid graphs and investigate the asymptotic behavior of the first hitting time between its two maximum-occupancy configurations in the low-temperature regime. In particular, we show how the order-of-magnitude of this first hitting time depends on the grid sizes and on the boundary conditions by means of a novel combinatorial method. Our analysis also proves the asymptotic exponentiality of the scaled hitting time and yields the mixing time of the process in the low-temperature limit as side-result. In order to derive these results, we extended the model-independent framework in Manzo et al. (J Stat Phys 115(1/2):591–642, 2004) for first hitting times to allow for a more general initial state and target subset. Keywords Hard-core model Hitting times Metropolis Markov chains Finite grid graphs Mixing times Low temperature