Scaling limit of linearly edge-reinforced random walks on critical Galton-Watson trees. (English) Zbl 1514.60054

Andriopoulos, George; Archer, Eleanor

Electron. J. Probab. 28, Paper No. 9, 64 p. (2023).

The authors prove an invariance principle for linearly edge reinforced random walks on \(\gamma\)-stable critical Galton-Watson trees, where \(\gamma\in (1,2]\) and where the edge joining \(x\) to its parent has rescaled initial weight \(d(O, x)^{\alpha}\) for some \(\alpha\leq 1\). This corresponds to the recurrent regime of initial weights.
The authors then establish fine asymptotics for the limit process. In the transient regime, an upper bound on the random walk displacement in the discrete setting is done, showing that the edge reinforced random walk never has positive speed, even when the initial edge weights are strongly biased away from the root.

Reviewer: Pavel Stoynov (Sofia)

MSC:

60G50	Sums of independent random variables; random walks
60F17	Functional limit theorems; invariance principles
60K37	Processes in random environments
60K50	Anomalous diffusion models (subdiffusion, superdiffusion, continuous-time random walks, etc.)
60J60	Diffusion processes
60J80	Branching processes (Galton-Watson, birth-and-death, etc.)

Keywords:

diffusion in random environment; Dirichlet distribution; Galton-Watson trees; random walk in random environment; reinforced random walks; slow movement

References:

[1]	R. Abraham, J-F. Delmas, and P. Hoscheit, A note on the Gromov-Hausdorff-Prokhorov distance between (locally) compact metric measure spaces, Electron. J. Probab. 18(14) (2013), 1-21. · Zbl 1285.60004
[2]	E. Aidékon, Transient random walks in random environment on a galton-watson tree, Probability Theory and Related Fields 142 (2008), 525-559. · Zbl 1146.60078
[3]	J. Akahori, A. Collevecchio, and M. Takei, Phase transitions for edge-reinforced random walks on the half-line, Electronic Communications in Probability 24 (2019). · Zbl 1488.60224
[4]	D. Aldous, Asymptotic fringe distributions for general families of random trees, Ann. Appl. Probab. 1 (1991), no. 2, 228-266. · Zbl 0733.60016
[5]	D. Aldous, The continuum random tree. I, Ann. Probab. 19 (1991), no. 1, 1-28. · Zbl 0722.60013
[6]	D. Aldous, The continuum random tree. II. An overview, Stochastic analysis (Durham, 1990), London Math. Soc. Lecture Note Ser., vol. 167, Cambridge Univ. Press, Cambridge, 1991, pp. 23-70. · Zbl 0791.60008
[7]	D. Aldous, The continuum random tree. III, Ann. Probab. 21 (1993), no. 1, 248-289. · Zbl 0791.60009 · doi:10.1214/aop/1176989404
[8]	G. Andriopoulos, Invariance principles for random walks in random environment on trees, Electron. J. Probab. 26 (2021), Paper No. 115, 38. · Zbl 1476.60065
[9]	E. Archer, Infinite stable looptrees, Electronic Journal of Probability 25 (2020). · Zbl 1445.60032
[10]	E Archer, Random walks on decorated Galton-Watson trees, arXiv preprint 2011.07266 (2020).
[11]	S. Athreya, M. Eckhoff, and A. Winter, Brownian motion on \[ \mathbb{R} -trees \], Transactions of the American Mathematical Society 365 (2013), no. 6, 3115-3150. · Zbl 1278.60009
[12]	S. Athreya, W. Löhr, and A. Winter, The gap between gromov-vague and gromov-hausdorff-vague topology, Stochastic Processes and their Applications 126 (2016), no. 9, 2527-2553. · Zbl 1384.60016
[13]	S. Athreya, W. Löhr, and A. Winter, Invariance principle for variable speed random walks on trees, Ann. Probab. 45 (2017), no. 2, 625-667. · Zbl 1388.60120
[14]	S. Bacallado, Bayesian analysis of variable-order, reversible Markov chains, Ann. Statist. 39 (2011), no. 2, 838-864. · Zbl 1215.62083
[15]	S. Bacallado, J. Chodera, and V. Pande, Bayesian comparison of markov models of molecular dynamics with detailed balance constraint, The Journal of chemical physics 131 (2009), no. 4, 07B622.
[16]	S. Bacallado, V. Pande, S. Favaro, and L. Trippa, Bayesian regularization of the length of memory in reversible sequences, J. R. Stat. Soc. Ser. B. Stat. Methodol. 78 (2016), no. 4, 933-946. · Zbl 1414.62084
[17]	S. Bacallado, C. Sabot, and P. Tarrès, The*-edge-reinforced random walk, arXiv preprint 2102.08984 (2021).
[18]	M. Barlow, Diffusions on fractals, Lectures on probability theory and statistics (Saint-Flour, 1995), Lecture Notes in Math., vol. 1690, Springer, Berlin, 1998, pp. 1-121. · Zbl 0916.60069
[19]	M. Barlow and T. Kumagai, Random walk on the incipient infinite cluster on trees, Illinois J. Math. 50 (2006), no. 1-4, 33-65. · Zbl 1110.60090
[20]	R. Bass and K. Burdzy, Stochastic bifurcation models, Ann. Probab. 27 (1999), no. 1, 50-108. · Zbl 0943.60087
[21]	J. Bertoin, An extension of Pitman’s theorem for spectrally positive Lévy processes, Ann. Probab. 20 (1992), no. 3, 1464-1483. · Zbl 0760.60068
[22]	J. Bertoin, Lévy processes, Cambridge Tracts in Mathematics, vol. 121, Cambridge University Press, Cambridge, 1996. · Zbl 0861.60003
[23]	P. Billingsley, Convergence of probability measures, second ed., Wiley Series in Probability and Statistics: Probability and Statistics, John Wiley & Sons, Inc., New York, 1999, A Wiley-Interscience Publication. · Zbl 0944.60003
[24]	N. Bingham, C. Goldie, and J. Teugels, Regular variation, Encyclopedia of Mathematics and its Applications, vol. 27, Cambridge University Press, Cambridge, 1989. · Zbl 0667.26003
[25]	T. Brox, A one-dimensional diffusion process in a Wiener medium, Ann. Probab. 14 (1986), no. 4, 1206-1218. · Zbl 0608.60072
[26]	D. Burago, Y. Burago, and S. Ivanov, A course in metric geometry, Graduate Studies in Mathematics, vol. 33, American Mathematical Society, Providence, RI, 2001. · Zbl 0981.51016
[27]	P. Carmona, The mean velocity of a brownian motion in a random lévy potential, The Annals of Probability (1997), 1774-1788. · Zbl 0903.60065
[28]	A. Collevecchio, Limit theorems for reinforced random walks on certain trees, Probab. Theory Related Fields 136 (2006), no. 1, 81-101. · Zbl 1109.60027
[29]	D. Coppersmith and P. Diaconis, Random walk with reinforcement, Unpublished manuscript (1986).
[30]	D. Croydon, An introduction to stochastic processes associated with resistance forms and their scaling limits, RIMS Kokyuroku 2030, no. 1 (2017).
[31]	D. Croydon, Scaling limits of stochastic processes associated with resistance forms, Ann. Inst. Henri Poincaré Probab. Stat. 54 (2018), no. 4, 1939-1968. · Zbl 1417.60067
[32]	D. Croydon and T. Kumagai, Random walks on galton-watson trees with infinite variance offspring distribution conditioned to survive, Electronic Journal of Probability 13 (2008), 1419-1441. · Zbl 1191.60121
[33]	N. Curien and I. Kortchemski, Random stable looptrees, Electron. J. Probab. 19(108) (2014), 1-35. · Zbl 1307.60061
[34]	B. Davis and S. Volkov, Continuous time vertex-reinforced jump processes, Probability theory and related fields 123 (2002), no. 2, 281-300. · Zbl 1009.60027
[35]	P. Diaconis and D. Freedman, de finetti’s theorem for markov chains, The Annals of Probability (1980), 115-130. · Zbl 0426.60064
[36]	P. Diaconis and S. Rolles, Bayesian analysis for reversible Markov chains, Ann. Statist. 34 (2006), no. 3, 1270-1292. · Zbl 1118.62085
[37]	T. Duquesne, A limit theorem for the contour process of conditioned Galton-Watson trees, Ann. Probab. 31 (2003), no. 2, 996-1027. · Zbl 1025.60017
[38]	T. Duquesne, A limit theorem for the contour process of conditioned Galton-Watson trees, Ann. Probab. 31 (2003), no. 2, 996-1027. · Zbl 1025.60017
[39]	T. Duquesne, Continuum random trees and branching processes with immigration, Stochastic Process. Appl. 119 (2009), no. 1, 99-129. · Zbl 1161.60028
[40]	T. Duquesne and J-F. Le Gall, Random trees, Lévy processes and spatial branching processes, Astérisque (2002), no. 281, vi+147. · Zbl 1037.60074
[41]	T. Duquesne and J-F. Le Gall, Probabilistic and fractal aspects of Lévy trees, Probab. Theory Related Fields 131 (2005), no. 4, 553-603. · Zbl 1070.60076
[42]	T. Duquesne and J-F. Le Gall, The Hausdorff measure of stable trees, ALEA Lat. Am. J. Probab. Math. Stat. 1 (2006), 393-415. · Zbl 1128.60072
[43]	T. Duquesne and G. Wang, Exceptionally small balls in stable trees, arXiv preprint 1111.3465 (2011).
[44]	S. Evans, J. Pitman, and A. Winter, Rayleigh processes, real trees, and root growth with re-grafting, Probab. Theory Related Fields 134 (2006), no. 1, 81-126. · Zbl 1086.60050
[45]	C. Goldschmidt and B. Haas, Behavior near the extinction time in self-similar fragmentations. I. The stable case, Ann. Inst. Henri Poincaré Probab. Stat. 46 (2010), no. 2, 338-368. · Zbl 1214.60012
[46]	P. Hall and C. Heyde, Martingale limit theory and its application, Academic press, 2014.
[47]	S. Janson and J-F. Marckert, Convergence of discrete snakes, J. Theoret. Probab. 18 (2005), no. 3, 615-647. · Zbl 1084.60049
[48]	H. Kesten, The limit distribution of Sinaĭ’s random walk in random environment, Phys. A 138 (1986), no. 1-2, 299-309. · Zbl 0666.60065
[49]	H. Kesten, Subdiffusive behavior of random walk on a random cluster, Ann. Inst. H. Poincaré Probab. Statist. 22 (1986), no. 4, 425-487. · Zbl 0632.60106
[50]	I. Kortchemski, Sub-exponential tail bounds for conditioned stable Bienaymé-Galton-Watson trees, Probability Theory and Related Fields 168 (2017), no. 1, 1-40. · Zbl 1374.60167
[51]	I. Kortchemski and L. Richier, Condensation in critical Cauchy Bienaymé-Galton-Watson trees, The Annals of Applied Probability 29 (2019), no. 3, 1837-1877. · Zbl 1427.60178
[52]	T. Kumagai, Heat kernel estimates and parabolic Harnack inequalities on graphs and resistance forms, Publ. Res. Inst. Math. Sci. 40 (2004), no. 3, 793-818. · Zbl 1067.60070
[53]	J-F. Le Gall, Random real trees, Ann. Fac. Sci. Toulouse Math. (6) 15 (2006), no. 1, 35-62. · Zbl 1129.60047
[54]	J-F. Le Gall and Y. Le Jan, Branching processes in Lévy processes: the exploration process, Ann. Probab. 26 (1998), no. 1, 213-252. · Zbl 0948.60071
[55]	D. Levin, Y. Peres, and E. Wilmer, Markov chains and mixing times, American Mathematical Society, Providence, RI, 2017, Second edition of [MR2466937], With contributions by Elizabeth L. Wilmer, With a chapter on “Coupling from the past” by James G. Propp and David B. Wilson. · Zbl 1390.60001
[56]	T. Lupu, C. Sabot, and P. Tarrès, Fine mesh limit of the vrjp in dimension one and bass-burdzy flow, Probability Theory and Related Fields 177 (2020), no. 1, 55-90. · Zbl 1434.60215
[57]	C. Marzouk, Scaling limits of discrete snakes with stable branching, Annales de l’Institut Henri Poincaré, Probabilités et Statistiques 56 (2020), no. 1, 502-523. · Zbl 1434.60248
[58]	Pertti Mattila, Geometry of sets and measures in Euclidean spaces, Cambridge Studies in Advanced Mathematics, vol. 44, Cambridge University Press, Cambridge, 1995, Fractals and rectifiability. · Zbl 0819.28004
[59]	F. Merkl and S. Rolles, A random environment for linearly edge-reinforced random walks on infinite graphs, Probability theory and related fields 138 (2007), no. 1-2, 157-176. · Zbl 1116.60060
[60]	J. Neveu, Arbres et processus de Galton-Watson, Ann. Inst. H. Poincaré Probab. Statist. 22 (1986), no. 2, 199-207. · Zbl 0601.60082
[61]	C. Pacheco, From the sinai’s walk to the brox diffusion using bilinear forms, arXiv preprint 1605.02826 (2016).
[62]	R. Pemantle, Phase transition in reinforced random walk and RWRE on trees, Ann. Probab. 16 (1988), no. 3, 1229-1241. · Zbl 0648.60077
[63]	J. Pitman, Combinatorial stochastic processes: Ecole d’eté de probabilités de saint-flour xxxii-2002, Springer, 2006. · Zbl 1103.60004
[64]	C. Sabot and P. Tarrès, Edge-reinforced random walk, vertex-reinforced jump process and the supersymmetric hyperbolic sigma model, J. Eur. Math. Soc. (JEMS) 17 (2015), no. 9, 2353-2378. · Zbl 1331.60185
[65]	C. Sabot and L. Tournier, Random walks in Dirichlet environment: an overview, Ann. Fac. Sci. Toulouse Math. (6) 26 (2017), no. 2, 463-509. · Zbl 1369.60074
[66]	P. Seignourel, Discrete schemes for processes in random media, Probability theory and related fields 118 (2000), no. 3, 293-322. · Zbl 0968.60100
[67]	Y. Sinaĭ, The limit behavior of a one-dimensional random walk in a random environment, Teor. Veroyatnost. i Primenen. 27 (1982), no. 2, 247-258. · Zbl 0497.60065
[68]	R. Slack, A branching process with mean one and possibly infinite variance, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 9 (1968), 139-145. · Zbl 0164.47002
[69]	M. Takei, Almost sure behavior of linearly edge-reinforced random walks on the half-line, Electron. J. Probab. 26 (2021), Paper No. 104, 18. · Zbl 1474.60125
[70]	M. Takeshima, Behavior of 1-dimensional reinforced random walk, Osaka Journal of Mathematics 37 (2000), no. 2, 355-372. · Zbl 0962.60017
[71]	P. Tetali, Random walks and the effective resistance of networks, J. Theoret. Probab. 4 (1991), no. 1, 101-109. · Zbl 0722.60070
[72]	A. van der Vaart and J. Wellner, Weak convergence and empirical processes, Springer Series in Statistics, Springer-Verlag, New York, 1996, With applications to statistics. · Zbl 0862.60002