Home | Current | Past volumes | About | Login | Notify | Contact | Search
 Probability Surveys > Vol. 15 (2018) open journal systems 


Sandpile models

Antal A. Járai, University of Bath, United Kingdom


Abstract
This survey is an extended version of lectures given at the Cornell Probability Summer School 2013. The fundamental facts about the Abelian sandpile model on a finite graph and its connections to related models are presented. We discuss exactly computable results via Majumdar and Dhar’s method. The main ideas of Priezzhev’s computation of the height probabilities in 2D are also presented, including explicit error estimates involved in passing to the limit of the infinite lattice. We also discuss various questions arising on infinite graphs, such as convergence to a sandpile measure, and stabilizability of infinite configurations.

AMS 2000 subject classifications: Primary 60K35; secondary 82B20.

Keywords: Abelian sandpile, chip-firing, uniform spanning tree, loop-erased random walk, Wilson’s algorithm, burning bijection, height probabilities.

Creative Common LOGO

Full Text: PDF


Járai, Antal A., Sandpile models, Probability Surveys, 15, (2018), 243-306 (electronic). DOI: 10.1214/14-PS228.

References

[1]    Siva R. Athreya and Antal A. Járai, Infinite volume limit for the stationary distribution of abelian sandpile models, Comm. Math. Phys. 249 (2004), no. 1, 197–213. MR2077255 (2005m:82106)

[2]    Per Bak, Chao Tang, and Kurt Wiesenfeld, Self-organized criticality, Phys. Rev. A (3) 38 (1988), no. 1, 364–374. MR949160 (89g:58126)

[3]    D. J. Barsky and M. Aizenman, Percolation critical exponents under the triangle condition, Ann. Probab. 19 (1991), no. 4, 1520–1536. MR1127713 (93b:60224)

[4]    Itai Benjamini, Russell Lyons, Yuval Peres, and Oded Schramm, Uniform spanning forests, Ann. Probab. 29 (2001), no. 1, 1–65. MR1825141 (2003a:60015)

[5]    Sandeep Bhupatiraju, Jack Hanson, and Antal A. Járai, Inequalities for critical exponents in d-dimensional sandpiles, Electron. J. Probab. 22 (2017), Paper No. 85, 51. MR3718713

[6]    Yvan Le Borgne and Dominique Rossin, On the identity of the sandpile group, Discrete Math. 256 (2002), no. 3, 775–790. LaCIM 2000 Conference on Combinatorics, Computer Science and Applications (Montreal, QC). MR1935788 (2003j:82054)

[7]    Béla Bollobás, Modern graph theory, Graduate Texts in Mathematics, vol. 184, Springer-Verlag, New York, 1998. MR1633290 (99h:05001)

[8]    S. R. Broadbent and J. M. Hammersley, Percolation processes. I. Crystals and mazes, Proc. Cambridge Philos. Soc. 53 (1957), 629–641. MR0091567 (19,989e)

[9]    Robert Burton and Robin Pemantle, Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances, Ann. Probab. 21 (1993), no. 3, 1329–1371. MR1235419 (94m:60019)

[10]    Sergio Caracciolo and Andrea Sportiello, Exact integration of height probabilities in the Abelian Sandpile model, J. Stat. Mech. Theory Exp. 9 (2012), P09013, 14. MR2994907

[11]    Deepak Dhar, Self-organized critical state of sandpile automaton models, Phys. Rev. Lett. 64 (1990), no. 14, 1613–1616. MR1044086 (90m:82053)

[12]    Deepak Dhar, Theoretical studies of self-organized criticality, Phys. A 369 (2006), no. 1, 29–70. MR2246566 (2007g:82042)

[13]    Deepak Dhar and S. N. Majumdar, Abelian sandpile model on the Bethe lattice, J. Phys. A 23 (1990), no. 19, 4333–4350. MR1076905 (91m:82098)

[14]    D. Dhar, P. Ruelle, S. Sen, and D.-N. Verma, Algebraic aspects of abelian sandpile models, J. Phys. A 28 (1995), no. 4, 805–831. MR1326322

[15]    Maximilian Dürre, Conformal covariance of the abelian sandpile height one field, Stochastic Process. Appl. 119 (2009), no. 9, 2725–2743. MR2554026 (2011c:60311)

[16]    Anne Fey, Lionel Levine, and Yuval Peres, Growth rates and explosions in sandpiles, J. Stat. Phys. 138 (2010), no. 1-3, 143–159. MR2594895 (2011c:82051)

[17]    Anne Fey, Lionel Levine, and David B. Wilson, Approach to criticality in sandpiles, Phys. Rev. E (3) 82 (2010), no. 3, 031121, 14. MR2787987 (2012a:82060)

[18]    Anne Fey, Ronald Meester, and Frank Redig, Stabilizability and percolation in the infinite volume sandpile model, Ann. Probab. 37 (2009), no. 2, 654–675. MR2510019 (2010c:60289)

[19]    Anne Fey-den Boer and Frank Redig, Organized versus self-organized criticality in the abelian sandpile model, Markov Process. Related Fields 11 (2005), no. 3, 425–442. MR2175021 (2006g:60136)

[20]    Robert Fitzner, Non-backtracking lace expansion, PhD Thesis, Technical University Eindhoven, 2013.

[21]    Robert Fitzner and Remco van der Hofstad, Mean-field behavior for nearest-neighbor percolation in d > 10, Electron. J. Probab. 22 (2017), Paper No. 43, 65. MR3646069

[22]    Yasunari Fukai and Kôhei Uchiyama, Potential kernel for two-dimensional random walk, Ann. Probab. 24 (1996), no. 4, 1979–1992. MR1415236 (97m:60098)

[23]     Geoffrey Grimmett, Percolation, 2nd ed., Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 321, Springer-Verlag, Berlin, 1999. MR1707339 (2001a:60114)

[24]    Geoffrey Grimmett, The random-cluster model, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 333, Springer-Verlag, Berlin, 2006. MR2243761 (2007m:60295)

[25]    Olle Häggström, Random-cluster measures and uniform spanning trees, Stochastic Process. Appl. 59 (1995), no. 2, 267–275. MR1357655 (97b:60170)

[26]    J. M. Hammersley, Percolation processes: Lower bounds for the critical probability, Ann. Math. Statist. 28 (1957), 790–795. MR0101564 (21 #374)

[27]    J. M. Hammersley, Bornes supérieures de la probabilité critique dans un processus de filtration, Le calcul des probabilités et ses applications. Paris, 15-20 juillet 1958, Colloques Internationaux du Centre National de la Recherche Scientifique, LXXXVII, Centre National de la Recherche Scientifique, Paris, 1959, pp. 17–37 (French). MR0105751 (21 #4487)

[28]    Takashi Hara, Remco van der Hofstad, and Gordon Slade, Critical two-point functions and the lace expansion for spread-out high-dimensional percolation and related models, Ann. Probab. 31 (2003), no. 1, 349–408. MR1959796 (2005c:60130)

[29]    Takashi Hara and Gordon Slade, Mean-field critical behaviour for percolation in high dimensions, Comm. Math. Phys. 128 (1990), no. 2, 333–391. MR1043524 (91a:82037)

[30]    Takashi Hara and Gordon Slade, The scaling limit of the incipient infinite cluster in high-dimensional percolation. I. Critical exponents, J. Statist. Phys. 99 (2000), no. 5-6, 1075–1168. MR1773141 (2001g:82053a)

[31]    Takashi Hara and Gordon Slade, The scaling limit of the incipient infinite cluster in high-dimensional percolation. II. Integrated super-Brownian excursion, J. Math. Phys. 41 (2000), no. 3, 1244–1293. Probabilistic techniques in equilibrium and nonequilibrium statistical physics. MR1757958 (2001g:82053b)

[32]    T. E. Harris, A lower bound for the critical probability in a certain percolation process, Proc. Cambridge Philos. Soc. 56 (1960), 13–20. MR0115221 (22 #6023)

[33]    Alexander E. Holroyd, Lionel Levine, Karola Mészáros, Yuval Peres, James Propp, and David B. Wilson, Chip-firing and rotor-routing on directed graphs, In and out of equilibrium. 2, Progr. Probab., vol. 60, Birkhäuser, Basel, 2008, pp. 331–364. MR2477390 (2010f:82066)

[34]    J. Ben Hough, Manjunath Krishnapur, Yuval Peres, and Bálint Virág, Determinantal processes and independence, Probab. Surv. 3 (2006), 206–229. MR2216966 (2006m:60068)

[35]    Tom Hutchcroft, Universality of high-dimensional spanning forests and sandpiles, ArXiv e-prints, (2018), available at 1804.04120.

[36]    Eugene V. Ivashkevich, Dmitri V. Ktitarev, and Vyatcheslav B Priezzhev, Waves of topplings in an Abelian sandpile, Phys. A 209 (1994), no. 3–4, 347–360.

[37]    E. V. Ivashkevich and Vyatcheslav B. Priezzhev, Introduction to the sandpile model, Phys. A 254 (1998), no. 1–2, 97–116.

[38]    Antal A. Járai, Abelian sandpiles: an overview and results on certain transitive graphs, Markov Process. Related Fields 18 (2012), no. 1, 111–156. MR2952022

[39]    Antal A. Járai and Russell Lyons, Ladder sandpiles, Markov Process. Related Fields 13 (2007), no. 3, 493–518. MR2357385 (2010c:82064)

[40]    Antal A. Járai and Frank Redig, Infinite volume limit of the abelian sandpile model in dimensions d 3, Probab. Theory Related Fields 141 (2008), no. 1-2, 181–212. MR2372969 (2009c:60268)

[41]    Antal A. Járai, Frank Redig, and Ellen Saada, Approaching criticality via the zero dissipation limit in the abelian avalanche model, J. Stat. Phys. 159 (2015), no. 6, 1369–1407. MR3350375

[42]    Antal A. Járai, Wioletta Ruszel, and Ellen Saada, Mean-field avalanche size exponent for sandpiles on Galton-Watson trees, ArXiv e-prints, (2018), available at 1807.01809.

[43]    Antal A. Járai and Nicolás Werning, Minimal configurations and sandpile measures, J. Theoret. Probab. 27 (2014), no. 1, 153–167. MR3174221

[44]    Monwhea Jeng, Geoffroy Piroux, and Philippe Ruelle, Height variables in the Abelian sandpile model: scaling fields and correlations, J. Stat. Mech. Theory Exp., (2006), P10015+63.

[45]    Henrik Jeldtoft Jensen, Self-organized criticality, Cambridge Lecture Notes in Physics, vol. 10, Cambridge University Press, Cambridge, 1998. Emergent complex behavior in physical and biological systems. MR1689042 (2001d:92003)

[46]    Adrien Kassel and David B. Wilson, The looping rate and sandpile density of planar graphs, Amer. Math. Monthly 123 (2016), no. 1, 19–39. MR3453533

[47]    Richard W. Kenyon and David B. Wilson, Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on planar graphs, J. Amer. Math. Soc. 28 (2015), no. 4, 985–1030. MR3369907

[48]    Harry Kesten, The critical probability of bond percolation on the square lattice equals 1
2, Comm. Math. Phys. 74 (1980), no. 1, 41–59. MR575895 (82c:60179)

[49]    Harry Kesten, Scaling relations for 2D-percolation, Comm. Math. Phys. 109 (1987), no. 1, 109–156. MR879034 (88k:60174)

[50]    Gady Kozma and Asaf Nachmias, Arm exponents in high dimensional percolation, J. Amer. Math. Soc. 24 (2011), no. 2, 375–409. MR2748397 (2012a:60273)

[51]    Gady Kozma and Ehud Schreiber, An asymptotic expansion for the discrete harmonic potential, Electron. J. Probab. 9 (2004), no. 1, 1–17 (electronic). MR2041826 (2005f:60165)

[52]    Gregory F. Lawler and Vlada Limic, Random walk: a modern introduction, Cambridge Studies in Advanced Mathematics, vol. 123, Cambridge University Press, Cambridge, 2010. MR2677157 (2012a:60132)

[53]    Gregory F. Lawler, Oded Schramm, and Wendelin Werner, One-arm exponent for critical 2D percolation, Electron. J. Probab. 7 (2002), no. 2, 13 pp. (electronic). MR1887622 (2002k:60204)

[54]    Lionel Levine and Yuval Peres, Strong spherical asymptotics for rotor-router aggregation and the divisible sandpile, Potential Anal. 30 (2009), no. 1, 1–27. MR2465710 (2010d:60112)

[55]    Lionel Levine and Yuval Peres, The looping constant of d, Random Structures Algorithms 45 (2014), no. 1, 1–13. MR3231081

[56]    Lionel Levine and Yuval Peres, Laplacian growth, sandpiles, and scaling limits, Bull. Amer. Math. Soc. (N.S.) 54 (2017), no. 3, 355–382. DOI 10.1090/bull/1573. MR3662912

[57]    Lionel Levine and James Propp, What is a sandpile?, Notices Amer. Math. Soc. 57 (2010), no. 8, 976–979. MR2667495

[58]    Russell Lyons, Benjamin J. Morris, and Oded Schramm, Ends in uniform spanning forests, Electron. J. Probab. 13 (2008), no. 58, 1702–1725. MR2448128 (2010a:60031)

[59]    Russell Lyons with Yuval Peres, Probability on Trees and Networks, Cambridge University Press, 2013, in preparation. Current version available at http://mypage.iu.edu/~rdlyons/.

[60]    Christian Maes, Frank Redig, and Ellen Saada, The infinite volume limit of dissipative abelian sandpiles, Comm. Math. Phys. 244 (2004), no. 2, 395–417. MR2031036 (2004k:82070)

[61]    C. Maes, F. Redig, and E. Saada, Abelian sandpile models in infinite volume, Sankhya 67 (2005), no. 4, 634–661. MR2283006

[62]    Christian Maes, Frank Redig, Ellen Saada, and A. Van Moffaert, On the thermodynamic limit for a one-dimensional sandpile process, Markov Process. Related Fields 6 (2000), no. 1, 1–21. MR1758981 (2001k:60142)

[63]    S. N. Majumdar and D. Dhar, Height correlations in the Abelian sandpile model, J. Phys. A 24 (1991), no. 7, L357–L362.

[64]    S. N. Majumdar and D. Dhar, Equivalence between the Abelian sandpile model and the q 0 limit of the Potts model, Phys. A 185 (1992), no. 1–4, 129–145.

[65]    S. S. Manna, Large-scale simulation of avalanche cluster distribution in sand pile model, J. Statist. Phys. 59 (1990), no. 1-2, 509–521.

[66]    Ronald Meester and Corrie Quant, Connections between ‘self-organised’ and ‘classical’ criticality, Markov Process. Related Fields 11 (2005), no. 2, 355–370. MR2150148 (2006d:82054)

[67]    Ronald Meester, Frank Redig, and Dmitri Znamenski, The abelian sandpile: a mathematical introduction, Markov Process. Related Fields 7 (2001), no. 4, 509–523. MR1893138 (2003f:60175)

[68]    Criel Merino López, Chip firing and the Tutte polynomial, Ann. Comb. 1 (1997), no. 3, 253–259. MR1630779 (99k:90232)

[69]    Wesley Pegden and Charles K. Smart, Convergence of the Abelian sandpile, Duke Math. J. 162 (2013), no. 4, 627–642. MR3039676

[70]    Robin Pemantle, Choosing a spanning tree for the integer lattice uniformly, Ann. Probab. 19 (1991), no. 4, 1559–1574. MR1127715 (92g:60014)

[71]    Geoffroy Piroux, Philippe Ruelle, Logarithmic scaling for height variables in the Abelian sandpile model, Phys. Lett. B 607 (2005), 188–196.

[72]    Vahagn S. Poghosyan, S. Y. Grigorev, Vyatcheslav B. Priezzhev, and Philippe Ruelle, Logarithmic two-point correlators in the abelian sandpile model, J. Stat. Mech. Theory Exp., (2010), no. 7, P07025, 27. MR2720344 (2012a:82026)

[73]    Vahagn S. Poghosyan and, Vyatcheslav B. Priezzhev, The problem of predecessors on spanning trees, Acta Polytechnica 51 (2011), no. 2.

[74]    Vahagn S. Poghosyan, Vyatcheslav B. Priezzhev, and Philippe Ruelle, Return probability for the loop-erased random walk and mean height in the Abelian sandpile model: a proof, J. Stat. Mech. Theory Exp., (2011), P10004+12.

[75]    Vyatcheslav B. Priezzhev, Structure of two-dimensional sandpile. I. Height probabilities, J. Statist. Phys. 74 (1994), no. 5–6, 955–979.

[76]    Vyatcheslav B. Priezzhev, The upper critical dimension of the abelian sandpile model, J. Statist. Phys. 98 (2000), no. 3–4, 667–684. MR1749227 (2000m:82022)

[77]    Vyatcheslav B. Priezzhev, Deepak Dhar, Abhishek Dhar, and Supriya Krishnamurthy, Eulerian walkers as a model of self-organized criticality, Phys. Rev. Lett. 77 (1996), no. 25, 5079–5082.

[78]    Balázs Ráth and Bálint Tóth, Erdʺo  s-Rényi random graphs + forest fires = self-organized criticality, Electron. J. Probab. 14 (2009), no. 45, 1290–1327. MR2511285 (2010h:60269)

[79]    Frank Redig, Mathematical aspects of the abelian sandpile model, Mathematical statistical physics, Elsevier B. V., Amsterdam, 2006, pp. 657–729. MR2581895 (2011g:60182)

[80]    Laurent Saloff-Coste, Random walks on finite groups, Probability on discrete structures, Encyclopaedia Math. Sci., vol. 110, Springer, Berlin, 2004, pp. 263–346. MR2023654

[81]    Klaus Schmidt and Evgeny Verbitskiy, Abelian sandpiles and the harmonic model, Comm. Math. Phys. 292 (2009), no. 3, 721–759. DOI 10.1007/s00220-009-0884-3. MR2551792

[82]    Stanislav Smirnov, Critical percolation in the plane: conformal invariance, Cardy’s formula, scaling limits, C. R. Acad. Sci. Paris Sér. I Math. 333 (2001), no. 3, 239–244 (English, with English and French summaries). MR1851632 (2002f:60193)

[83]    Stanislav Smirnov and Wendelin Werner, Critical exponents for two-dimensional percolation, Math. Res. Lett. 8 (2001), no. 5-6, 729–744. MR1879816 (2003i:60173)

[84]    Frank Spitzer, Principles of random walk, 2nd ed., Springer-Verlag, New York, 1976. Graduate Texts in Mathematics, Vol. 34. MR0388547 (52 #9383)

[85]    David Bruce Wilson, Generating random spanning trees more quickly than the cover time, Computing, (Philadelphia, PA, 1996), ACM, New York, 1996, pp. 296–303. MR1427525




Home | Current | Past volumes | About | Login | Notify | Contact | Search

Probability Surveys. ISSN: 1549-5787