×

Biased random walks on random graphs. (English) Zbl 1388.60170

Sidoravicius, V. (ed.) et al., Probability and statistical physics in St. Petersburg. St. Petersburg School Probability and Statistical Physics, St. Petersburg State University, St. Petersburg, Russia, June 18–29, 2012. Providence, RI: American Mathematical Society (AMS) (ISBN 978-1-4704-2248-6/hbk; 978-1-4704-2883-9/ebook). Proceedings of Symposia in Pure Mathematics 91, 99-153 (2016).
Introduction: These notes cover one of the topics programmed for the St. Petersburg School in Probability and Statistical Physics of June 2012. The aim is to review recent mathematical developments in the field of random walks in random environment (RWRE). For a detailed background on RWREs we refer the reader to [O. Zeitouni, Lect. Notes Math. 1837, 191–312 (2004; Zbl 1060.60103)] or [A.-S. Sznitman [School and conference on probability theory, Trieste, Italy, 2002. Trieste: ICTP – The Abdus Salam International Centre for Theoretical Physics. 203–266 (2004; Zbl 1060.60102)].
Our main focus will be on directionally transient and reversible random walks on different types of underlying graph structures, such as \(\mathbb{Z}\), trees and \(\mathbb{Z}^d\) for \(d\geq 2\).
Rather than speaking abstractly about the current state of the field, we decide to first dive into the heart of the subject by presenting rapidly a simple model which encapsulates most of the key questions we want to address in those notes. We feel this will give the reader a clear framework and provide an early motivation to understand the issues at hand.
For the entire collection see [Zbl 1341.60001].

MSC:

60K37 Processes in random environments
05C80 Random graphs (graph-theoretic aspects)
05C81 Random walks on graphs
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
PDFBibTeX XMLCite
Full Text: arXiv

References:

[1] Aid{\'e}kon, Elie, Transient random walks in random environment on a Galton-Watson tree, Probab.Theory Related Fields, 142, 3-4, 525-559 (2008) · Zbl 1146.60078 · doi:10.1007/s00440-007-0114-x
[2] A{\`“{\i }}d{\'”e}kon, Elie, Speed of the biased random walk on a Galton-Watson tree, Probab. Theory Related Fields, 159, 3-4, 597-617 (2014) · Zbl 1307.60113 · doi:10.1007/s00440-013-0515-y
[3] Aldous, David, The continuum random tree. III, Ann. Probab., 21, 1, 248-289 (1993) · Zbl 0791.60009
[4] S. Alexander, and R. Orbach, Density of states on fractals: “fractons”. J. Physique (Paris) Lett.I, 43 (1982), L625-L631.
[5] M. Barma, and D. Dhar, Directed diffusion in a percolation network. J. Phys. C: Solid State Phys. 16,(1983), 1451-1458.
[6] Barlow, Martin T.; J{\'a}rai, Antal A.; Kumagai, Takashi; Slade, Gordon, Random walk on the incipient infinite cluster for oriented percolation in high dimensions, Comm. Math. Phys., 278, 2, 385-431 (2008) · Zbl 1144.82030 · doi:10.1007/s00220-007-0410-4
[7] Ben Arous, G{\'e}rard; Bovier, Anton; Cern{\'y}, Ji{\v{r}}{\'{\i }}, Universality of the REM for dynamics of mean-field spin glasses, Comm. Math. Phys., 282, 3, 663-695 (2008) · Zbl 1208.82024 · doi:10.1007/s00220-008-0565-7
[8] Ben Arous, G{\'e}rard; Bovier, Anton; Gayrard, V{\'e}ronique, Glauber dynamics of the random energy model. II. Aging below the critical temperature, Comm. Math. Phys., 236, 1, 1-54 (2003) · Zbl 1037.82039 · doi:10.1007/s00220-003-0799-3
[9] G. Ben Arous, M. Cabezas, I. Cerny, and R. Royfman, Randomly trapped random walks. (2013) Preprint. · Zbl 1329.60354
[10] G. Ben Arous and M. Cabezas, Scaling limits for the random walks on the I.I.C. and I.P.C. on regular trees. (2013) Preprint.
[11] Ben Arous, G{\'e}rard; Cern{\'y}, Ji{\v{r}}{\'{\i }}, Dynamics of trap models. Mathematical statistical physics, 331-394 (2006), Elsevier B. V., Amsterdam · Zbl 1458.82019 · doi:10.1016/S0924-8099(06)80045-4
[12] Ben Arous, G{\'e}rard; Fribergh, Alexander; Gantert, Nina; Hammond, Alan, Biased random walks on Galton-Watson trees with leaves, Ann. Probab., 40, 1, 280-338 (2012) · Zbl 1239.60091 · doi:10.1214/10-AOP620
[13] G. Ben Arous, A. Fribergh, and V. Sidoravicius, The Lyons-Pemantle-Peres problem for high biases. To appear in Comm. Pure Appl. Math. (2013). · Zbl 1294.05143
[14] Ben Arous, G{\'e}rard; G{\`“u}n, Onur, Universality and extremal aging for dynamics of spin glasses on subexponential time scales, Comm. Pure Appl. Math., 65, 1, 77-127 (2012) · Zbl 1237.82043 · doi:10.1002/cpa.20372
[15] Ben Arous, G{\'e}rard; Hammond, Alan, Randomly biased walks on subcritical trees, Comm. Pure Appl. Math., 65, 11, 1481-1527 (2012) · Zbl 1254.60094 · doi:10.1002/cpa.21416
[16] Ben Arous, G\'erard; Hu, Yueyun; Olla, Stefano; Zeitouni, Ofer, Einstein relation for biased random walk on Galton-Watson trees, Ann. Inst. Henri Poincar\'e Probab. Stat., 49, 3, 698-721 (2013) · Zbl 1296.60266 · doi:10.1214/12-AIHP486
[17] Berger, Noam; Biskup, Marek, Quenched invariance principle for simple random walk on percolation clusters, Probab. Theory Related Fields, 137, 1-2, 83-120 (2007) · Zbl 1107.60066 · doi:10.1007/s00440-006-0498-z
[18] Berger, Noam; Gantert, Nina; Peres, Yuval, The speed of biased random walk on percolation clusters, Probab. Theory Related Fields, 126, 2, 221-242 (2003) · Zbl 1029.60087 · doi:10.1007/s00440-003-0258-2
[19] Bertoin, Jean, L\'evy processes, Cambridge Tracts in Mathematics 121, x+265 pp. (1996), Cambridge University Press, Cambridge · Zbl 0861.60003
[20] J. P. Bouchaud, Weak ergodicity breaking and aging in disordered systems. J. Phys. I (France) 2 (1992), 1705-1713.
[21] Chandra, Ashok K.; Raghavan, Prabhakar; Ruzzo, Walter L.; Smolensky, Roman; Tiwari, Prasoon, The electrical resistance of a graph captures its commute and cover times, Comput. Complexity, 6, 4, 312-340 (1996/97) · Zbl 0905.60049 · doi:10.1007/BF01270385
[22] Chayes, J. T.; Chayes, L.; Newman, C. M., The stochastic geometry of invasion percolation, Comm. Math. Phys., 101, 3, 383-407 (1985)
[23] Croydon, David, Convergence of simple random walks on random discrete trees to Brownian motion on the continuum random tree, Ann. Inst. Henri Poincar\'e Probab. Stat., 44, 6, 987-1019 (2008) · Zbl 1187.60083 · doi:10.1214/07-AIHP153
[24] Croydon, D. A.; Fribergh, A.; Kumagai, T., Biased random walk on critical Galton-Watson trees conditioned to survive, Probab. Theory Related Fields, 157, 1-2, 453-507 (2013) · Zbl 1283.60125 · doi:10.1007/s00440-012-0462-z
[25] De Masi, A.; Ferrari, P. A.; Goldstein, S.; Wick, W. D., An invariance principle for reversible Markov processes. Applications to random motions in random environments, J. Statist. Phys., 55, 3-4, 787-855 (1989) · Zbl 0713.60041 · doi:10.1007/BF01041608
[26] Dembo, Amir; Deuschel, Jean-Dominique, Markovian perturbation, response and fluctuation dissipation theorem, Ann. Inst. Henri Poincar\'e Probab. Stat., 46, 3, 822-852 (2010) · Zbl 1196.82092 · doi:10.1214/10-AIHP370
[27] Dembo, Amir; Sun, Nike, Central limit theorem for biased random walk on multi-type Galton-Watson trees, Electron. J. Probab., 17, no. 75, 40 pp. (2012) · Zbl 1255.60031 · doi:10.1214/EJP.v17-2294
[28] D. Dhar, Diffusion and drift on percolation networks in an external field. J. of Phys. A. 17 (1984) (5), 257-259.
[29] D. Dhar and D. Stauffer, Drift and trapping in biased diffusion on disordered lattices. Int. J. Mod. Phys. C. 9 (1998) (2), 349-355.
[30] Dolgopyat, D.; Goldsheid, I., Quenched limit theorems for nearest neighbour random walks in 1D random environment, Comm. Math. Phys., 315, 1, 241-277 (2012) · Zbl 1260.60187 · doi:10.1007/s00220-012-1539-3
[31] Doyle, Peter G.; Snell, J. Laurie, Random walks and electric networks, Carus Mathematical Monographs 22, xiv+159 pp. (1984), Mathematical Association of America, Washington, DC · Zbl 0583.60065
[32] Durrett, Richard, Probability: theory and examples, xiii+503 pp. (1996), Duxbury Press, Belmont, CA · Zbl 0709.60002
[33] Enriquez, N., Sabot, C. and Zindy, O. (2007). A probabilistic representation of constants in Kesten’s renewal theorem. Probab. Theory Related Fields 144, 581-613. · Zbl 1168.60034
[34] Enriquez, Nathana{\`“e}l; Sabot, Christophe; Zindy, Olivier, Limit laws for transient random walks in random environment on \(\mathbb{Z} \), Ann. Inst. Fourier (Grenoble), 59, 6, 2469-2508 (2009) · Zbl 1200.60093
[35] Enriquez, Nathana{\`“e}l; Sabot, Christophe; Zindy, Olivier, Aging and quenched localization for one-dimensional random walks in random environment in the sub-ballistic regime, Bull. Soc. Math. France, 137, 3, 423-452 (2009) · Zbl 1186.60108
[36] Enriquez, Nathana{\`“e}l; Sabot, Christophe; Tournier, Laurent; Zindy, Olivier, Quenched limits for the fluctuations of transient random walks in random environment on \(\mathbb{Z}^1\), Ann. Appl. Probab., 23, 3, 1148-1187 (2013) · Zbl 1279.60126 · doi:10.1214/12-AAP867
[37] N. Enriquez, C. Sabot, L. Tournier, and O. Zindy, Stable fluctuations for ballistic random walks in random environment on \(\mathbb{Z} \). Preprint (2013). · Zbl 1279.60126
[38] Enriquez, Nathana{\`“e}l; Sabot, Christophe; Tournier, Laurent; Zindy, Olivier, Quenched limits for the fluctuations of transient random walks in random environment on \(\mathbb{Z}^1\), Ann. Appl. Probab., 23, 3, 1148-1187 (2013) · Zbl 1279.60126 · doi:10.1214/12-AAP867
[39] Ethier, Stewart N.; Kurtz, Thomas G., Markov processes, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, x+534 pp. (1986), John Wiley & Sons, Inc., New York · Zbl 1089.60005 · doi:10.1002/9780470316658
[40] Fontes, L. R. G.; Isopi, M.; Newman, C. M., Random walks with strongly inhomogeneous rates and singular diffusions: convergence, localization and aging in one dimension, Ann. Probab., 30, 2, 579-604 (2002) · Zbl 1015.60099 · doi:10.1214/aop/1023481003
[41] R. Fitzner, Non-backtracking lace expension, Ph.D. Thesis, The Eindhoven University of Technology, (2013), http://www.win.tue.nl/rfitzner/NoBLE/index.html
[42] R. Fitzner and R. van der Hofstad, Nearest-neighbor percolation function is continuous for \(d15\). (2015) Preprint
[43] Fribergh, Alexander, The speed of a biased random walk on a percolation cluster at high density, Ann. Probab., 38, 5, 1717-1782 (2010) · Zbl 1205.60171 · doi:10.1214/09-AOP521
[44] Fribergh, Alexander, Biased random walk in positive random conductances on \(\mathbb{Z}^d\), Ann. Probab., 41, 6, 3910-3972 (2013) · Zbl 1291.60209 · doi:10.1214/13-AOP835
[45] Fribergh, Alexander; Hammond, Alan, Phase transition for the speed of the biased random walk on the supercritical percolation cluster, Comm. Pure Appl. Math., 67, 2, 173-245 (2014) · Zbl 1290.60104 · doi:10.1002/cpa.21491
[46] J. Geiger, and G. Kersting, The Galton-Watson tree conditioned on its height. Proc. 7th Vilnius Conv. on Prob. and Math. Stat. (1998). Editors: B. Grigelionis, J. Kubilius, V. Paulauskas, H. Pragarauskas and V. Statulevicius. VSP, Zeist, The Netherlands. · Zbl 1021.60065
[47] Gnedenko, B. V.; Kolmogorov, A. N., Limit distributions for sums of independent random variables, ix+264 pp. (1954), Addison-Wesley Publishing Company, Inc., Cambridge, Mass. · Zbl 0056.36001
[48] Grimmett, Geoffrey, Percolation, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 321, xiv+444 pp. (1999), Springer-Verlag, Berlin · Zbl 0926.60004 · doi:10.1007/978-3-662-03981-6
[49] Hammond, Alan, Stable limit laws for randomly biased walks on supercritical trees, Ann. Probab., 41, 3A, 1694-1766 (2013) · Zbl 1304.60110 · doi:10.1214/12-AOP752
[50] W. Havlin and D. Ben-Avraham Diffusion in disordered media, Advances in Physics. 51(1), (2002), 187-292.
[51] Heathcote, C. R.; Seneta, E.; Vere-Jones, D., A refinement of two theorems in the theory of branching processes, Teor. Verojatnost. i Primenen., 12, 341-346 (1967) · Zbl 0166.14202
[52] Heydenreich, Markus; van der Hofstad, Remco; Hulshof, Tim, Random walk on the high-dimensional IIC, Comm. Math. Phys., 329, 1, 57-115 (2014) · Zbl 1302.82050 · doi:10.1007/s00220-014-1931-2
[53] van der Hofstad, Remco; J{\'a}rai, Antal A., The incipient infinite cluster for high-dimensional unoriented percolation, J. Statist. Phys., 114, 3-4, 625-663 (2004) · Zbl 1061.82016 · doi:10.1023/B:JOSS.0000012505.39213.6a
[54] Iglehart, Donald L., Extreme values in the \(GI/G/1\) queue, Ann. Math. Statist., 43, 627-635 (1972) · Zbl 0238.60072
[55] T. Kumagai, Random walks on disordered media and their scaling limits. Notes on Saint-Flour Lectures 2010. · Zbl 1360.60003
[56] Kesten, Harry, Subdiffusive behavior of random walk on a random cluster, Ann. Inst. H. Poincar\'e Probab. Statist., 22, 4, 425-487 (1986) · Zbl 0632.60106
[57] Kesten, Harry, The incipient infinite cluster in two-dimensional percolation, Probab. Theory Related Fields, 73, 3, 369-394 (1986) · Zbl 0584.60098 · doi:10.1007/BF00776239
[58] Kesten, H.; Kozlov, M. V.; Spitzer, F., A limit law for random walk in a random environment, Compositio Math., 30, 145-168 (1975) · Zbl 0388.60069
[59] Kesten, H.; Ney, P.; Spitzer, F., The Galton-Watson process with mean one and finite variance, Teor. Verojatnost. i Primenen., 11, 579-611 (1966) · Zbl 0158.35202
[60] Kozma, Gady; Nachmias, Asaf, The Alexander-Orbach conjecture holds in high dimensions, Invent. Math., 178, 3, 635-654 (2009) · Zbl 1180.82094 · doi:10.1007/s00222-009-0208-4
[61] Lyons, Russell, Random walks, capacity and percolation on trees, Ann. Probab., 20, 4, 2043-2088 (1992) · Zbl 0766.60091
[62] Lyons, Russell; Pemantle, Robin, Random walk in a random environment and first-passage percolation on trees, Ann. Probab., 20, 1, 125-136 (1992) · Zbl 0751.60066
[63] R. Lyons and Y. Peres, Probability on trees and networks. Book in progress. Available at http://mypage.iu.edu/rdlyons/prbtree/prbtree.html · Zbl 1376.05002
[64] Lyons, Russell; Pemantle, Robin; Peres, Yuval, Biased random walks on Galton-Watson trees, Probab. Theory Related Fields, 106, 2, 249-264 (1996) · Zbl 0859.60076 · doi:10.1007/s004400050064
[65] Lyons, Russell; Pemantle, Robin; Peres, Yuval, Ergodic theory on Galton-Watson trees: speed of random walk and dimension of harmonic measure, Ergodic Theory Dynam. Systems, 15, 3, 593-619 (1995) · Zbl 0819.60077 · doi:10.1017/S0143385700008543
[66] R. Lyons, R. Pemantle, and Y. Peres, Unsolved problems concerning random walks on trees. IMA Vol. Math. Appl. 84 (1997),223-237. · Zbl 0867.60067
[67] Mathieu, P.; Piatnitski, A., Quenched invariance principles for random walks on percolation clusters, Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 463, 2085, 2287-2307 (2007) · Zbl 1131.82012 · doi:10.1098/rspa.2007.1876
[68] Meerschaert, Mark M.; Scheffler, Hans-Peter, Limit theorems for continuous-time random walks with infinite mean waiting times, J. Appl. Probab., 41, 3, 623-638 (2004) · Zbl 1065.60042
[69] Mehrdad, Behzad; Sen, Sanchayan; Zhu, Lingjiong, The speed of a biased walk on a Galton-Watson tree without leaves is monotonic with respect to progeny distributions for high values of bias, Ann. Inst. Henri Poincar\'e Probab. Stat., 51, 1, 304-318 (2015) · Zbl 1314.60160 · doi:10.1214/13-AIHP573
[70] M{\`“o}rters, Peter; Ortgiese, Marcel; Sidorova, Nadia, Ageing in the parabolic Anderson model, Ann. Inst. Henri Poincar\'”e Probab. Stat., 47, 4, 969-1000 (2011) · Zbl 1268.82031 · doi:10.1214/10-AIHP394
[71] Peterson, Jonathon, Quenched limits for transient, ballistic, sub-Gaussian one-dimensional random walk in random environment, Ann. Inst. Henri Poincar\'e Probab. Stat., 45, 3, 685-709 (2009) · Zbl 1178.60071 · doi:10.1214/08-AIHP149
[72] Peterson, Jonathon; Zeitouni, Ofer, Quenched limits for transient, zero speed one-dimensional random walk in random environment, Ann. Probab., 37, 1, 143-188 (2009) · Zbl 1179.60070 · doi:10.1214/08-AOP399
[73] Peterson, Jonathon; Samorodnitsky, Gennady, Weak quenched limiting distributions for transient one-dimensional random walk in a random environment, Ann. Inst. Henri Poincar\'e Probab. Stat., 49, 3, 722-752 (2013) · Zbl 1277.60188 · doi:10.1214/11-AIHP474
[74] Petrov, V. V., Sums of independent random variables, x+346 pp. (1975), Springer-Verlag, New York-Heidelberg · Zbl 0322.60042
[75] Peres, Yuval; Zeitouni, Ofer, A central limit theorem for biased random walks on Galton-Watson trees, Probab. Theory Related Fields, 140, 3-4, 595-629 (2008) · Zbl 1141.60073 · doi:10.1007/s00440-007-0077-y
[76] Shen, Lian, Asymptotic properties of certain anisotropic walks in random media, Ann. Appl. Probab., 12, 2, 477-510 (2002) · Zbl 1016.60092 · doi:10.1214/aoap/1026915612
[77] Sina{\u \i }, Ya. G., The limit behavior of a one-dimensional random walk in a random environment, Teor. Veroyatnost. i Primenen., 27, 2, 247-258 (1982) · Zbl 0497.60065
[78] Solomon, Fred, Random walks in a random environment, Ann. Probability, 3, 1-31 (1975) · Zbl 0305.60029
[79] Sidoravicius, Vladas; Sznitman, Alain-Sol, Quenched invariance principles for walks on clusters of percolation or among random conductances, Probab. Theory Related Fields, 129, 2, 219-244 (2004) · Zbl 1070.60090 · doi:10.1007/s00440-004-0336-0
[80] Sznitman, Alain-Sol, On the anisotropic walk on the supercritical percolation cluster, Comm. Math. Phys., 240, 1-2, 123-148 (2003) · Zbl 1087.82011 · doi:10.1007/s00220-003-0896-3
[81] Sznitman, Alain-Sol, Random motions in random media. Mathematical statistical physics, 219-242 (2006), Elsevier B. V., Amsterdam · Zbl 1411.60151 · doi:10.1016/S0924-8099(06)80041-7
[82] Sznitman, Alain-Sol, Topics in random walks in random environment. School and Conference on Probability Theory, ICTP Lect. Notes, XVII, 203-266 (electronic) (2004), Abdus Salam Int. Cent. Theoret. Phys., Trieste · Zbl 1060.60102
[83] Sznitman, Alain-Sol; Zerner, Martin, A law of large numbers for random walks in random environment, Ann. Probab., 27, 4, 1851-1869 (1999) · Zbl 0965.60100 · doi:10.1214/aop/1022874818
[84] Whitt, Ward, Stochastic-process limits, Springer Series in Operations Research, xxiv+602 pp. (2002), Springer-Verlag, New York · Zbl 0993.60001
[85] Zeitouni, Ofer, Random walks in random environment. Lectures on probability theory and statistics, Lecture Notes in Math. 1837, 189-312 (2004), Springer, Berlin · Zbl 1060.60103 · doi:10.1007/978-3-540-39874-5\_2
[86] Zindy, O., Scaling limit and aging for directed trap models, Markov Process. Related Fields, 15, 1, 31-50 (2009) · Zbl 1177.60077
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.