Fast approximate simulation of finite long-range spin systems. (English) Zbl 1479.60148

Summary: Tau leaping is a popular method for performing fast approximate simulation of certain continuous time Markov chain models typically found in chemistry and biochemistry. This method is known to perform well when the transition rates satisfy some form of scaling behaviour. In a similar spirit to tau leaping, we propose a new method for approximate simulation of spin systems which approximates the evolution of spin at each site between sampling epochs as an independent two-state Markov chain. When combined with fast summation methods, our method offers considerable improvement in speed over the standard Doob-Gillespie algorithm. We provide a detailed analysis of the error incurred for both the number of sites incorrectly labelled and for linear functions of the state.


60H35 Computational methods for stochastic equations (aspects of stochastic analysis)
60K35 Interacting random processes; statistical mechanics type models; percolation theory
65C05 Monte Carlo methods


Full Text: DOI arXiv Link


[1] Alonso, D. and McKane, A. (2002). Extinction dynamics in mainland-island metapopulations: A \(n\) patch stochastic model. Bull. Math. Biol. 64 913-958. · Zbl 1334.92323
[2] Anderson, D. F., Ganguly, A. and Kurtz, T. G. (2011). Error analysis of tau-leap simulation methods. Ann. Appl. Probab. 21 2226-2262. · Zbl 1234.60066
[3] Anderson, D. F. and Higham, D. J. (2012). Multilevel Monte Carlo for continuous time Markov chains, with applications in biochemical kinetics. Multiscale Model. Simul. 10 146-179. · Zbl 1262.60072
[4] Anderson, D. F., Higham, D. J. and Sun, Y. (2014). Complexity of multilevel Monte Carlo tau-leaping. SIAM J. Numer. Anal. 52 3106-3127. · Zbl 1327.60136
[5] Anderson, D. F. and Koyama, M. (2012). Weak error analysis of numerical methods for stochastic models of population processes. Multiscale Model. Simul. 10 1493-1524. · Zbl 1411.60103
[6] Anderson, D. F. and Mattingly, J. C. (2011). A weak trapezoidal method for a class of stochastic differential equations. Commun. Math. Sci. 9 301-318. · Zbl 1288.60085
[7] Barbour, A. D. and Luczak, M. J. (2015). Individual and patch behaviour in structured metapopulation models. J. Math. Biol. 71 713-733. · Zbl 1334.92327
[8] Barbour, A. D., McVinish, R. and Pollett, P. K. (2015). Connecting deterministic and stochastic metapopulation models. J. Math. Biol. 71 1481-1504. · Zbl 1350.92039
[9] Barnes, J. and Hut, P. (1986). A hierarchical \[O(N\log N)\] force-calculation algorithm. Nature 324 446.
[10] Barrio, M., Burrage, K. and Burrage, P. (2015). Stochastic linear multistep methods for the simulation of chemical kinetics. J. Chem. Phys. 142 064101.
[11] Boucheron, S., Lugosi, G. and Massart, P. (2013). Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford Univ. Press, Oxford. · Zbl 1337.60003
[12] Brand, S. P. C., Tildesley, M. J. and Keeling, M. J. (2015). Rapid simulation of spatial epidemics: A spectral method. J. Theoret. Biol. 370 121-134. · Zbl 1337.92203
[13] De Masi, A. (2003). Spin systems with long range interactions. In From Classical to Modern Probability. Progress in Probability 54 25-81. Birkhäuser, Basel. · Zbl 1035.82012
[14] Devroye, L. and Lugosi, G. (2001). Combinatorial Methods in Density Estimation. Springer Series in Statistics. Springer, New York. · Zbl 0964.62025
[15] Doob, J. L. (1942). Topics in the theory of Markoff chains. Trans. Amer. Math. Soc. 52 37-64. · Zbl 0063.09001
[16] Doob, J. L. (1945). Markoff chains—Denumerable case. Trans. Amer. Math. Soc. 58 455-473. · Zbl 0063.01146
[17] Dzhaparidze, K. and van Zanten, J. H. (2001). On Bernstein-type inequalities for martingales. Stochastic Process. Appl. 93 109-117. · Zbl 1051.60022
[18] Ethier, S. N. and Kurtz, T. G. (2005). Markov Processes: Characterization and Convergence. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. Wiley, New York.
[19] Frigo, M. and Johnson, S. G. (1998). FFTW: An adaptive software architecture for the FFT. In Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP’98 (Cat. No. 98CH36181) 3 1381-1384. IEEE, New York.
[20] Giles, M. B. (2008). Multilevel Monte Carlo path simulation. Oper. Res. 56 607-617. · Zbl 1167.65316
[21] Gillespie, D. T. (1976). A general method for numerically simulating the stochastic time evolution of coupled chemical reactions. J. Comput. Phys. 22 403-434.
[22] Gillespie, D. T. (1977). Exact stochastic simulation of coupled chemical reactions. J. Phys. Chem. 81 2340-2361.
[23] Gillespie, D. T. (2001). Approximate accelerated stochastic simulation of chemically reacting systems. J. Chem. Phys. 115 1716-1733.
[24] Gray, A. G. and Moore, A. W. (2001). ‘\(N\)-body’ problems in statistical learning. In Advances in Neural Information Processing Systems 13 (T. K. Leen, T. G. Dietterich and V. Tresp, eds.) 521-527. MIT Press, Cambridge.
[25] Greengard, L. and Rokhlin, V. (1987). A fast algorithm for particle simulations. J. Comput. Phys. 73 325-348. · Zbl 0629.65005
[26] Greengard, L. and Strain, J. (1991). The fast Gauss transform. SIAM J. Sci. Statist. Comput. 12 79-94. · Zbl 0721.65089
[27] Hackbusch, W. (2015). Hierarchical Matrices: Algorithms and Analysis. Springer Series in Computational Mathematics 49. Springer, Heidelberg. · Zbl 1336.65041
[28] Hamada, M. and Takasu, F. (2019). Equilibrium properties of the spatial SIS model as a point pattern dynamics—How is infection distributed over space? J. Theoret. Biol. 468 12-26. · Zbl 1411.92273
[29] Hanski, I. (1994). A practical model of metapopulation dynamics. J. Anim. Ecol. 63 151-162.
[30] Hodgkinson, L., McVinish, R. and Pollett, P. K. (2020). Normal approximations for discrete-time occupancy processes. Stochastic Process. Appl. 130 6414-6444. · Zbl 1450.60036
[31] Klebaner, F. C. (2012). Introduction to Stochastic Calculus with Applications. World Scientific Co., Inc., River Edge, NJ. · Zbl 1274.60005
[32] Léonard, C. (1990). Some epidemic systems are long range interacting particle systems. In Stochastic Processes in Epidemic Theory (C. Picard, ed.) 170-183. Springer, New York. · Zbl 0718.92020
[33] Liggett, T. M. (1999). Stochastic Interacting Systems: Contact, Voter and Exclusion Processes. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 324. Springer, Berlin. · Zbl 0949.60006
[34] Liggett, T. M. (2005). Interacting Particle Systems. Classics in Mathematics. Springer, Berlin.
[35] Liggett, T. M. (2010). Stochastic models for large interacting systems and related correlation inequalities. Proc. Natl. Acad. Sci. USA 107 16413-16419. · Zbl 1256.60037
[36] McVinish, R. and Pollett, P. K. (2014). The limiting behaviour of Hanski’s incidence function metapopulation model. J. Appl. Probab. 51 297-316. · Zbl 1291.92109
[37] Mourrat, J.-C. and Weber, H. (2017). Convergence of the two-dimensional dynamic Ising-Kac model to \[{\Phi_2^4}\]. Comm. Pure Appl. Math. 70 717-812. · Zbl 1364.82013
[38] Shalev-Shwartz, S. and Ben-David, S. (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge Univ. Press, Cambridge. · Zbl 1305.68005
[39] Sznitman, A.-S. (1991). Topics in propagation of chaos. In École D’Été de Probabilités de Saint-Flour XIX—1989. Lecture Notes in Math. 1464 165-251. Springer, Berlin. · Zbl 0732.60114
[40] Vituškin, A. G. (1961). Theory of the Transmission and Processing of Information. Pergamon Press, New York-Oxford.
[41] Yang, C., Duraiswami, R., Gumerov, N. and Davis, L. (2003). Improved fast Gauss transform and efficient kernel density estimation. In Proceedings Ninth IEEE International Conference on Computer Vision 464-471. IEEE, New York
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.