On the transience of processes defined on Galton-Watson trees. (English) Zbl 1104.60048

Summary: We introduce a simple technique for proving the transience of certain processes defined on the random tree \({\mathcal G}\) generated by a supercritical branching process. We prove the transience for once-reinforced random walks on \({\mathcal G}\), that is, a generalization of a result of R. Durrett, H. Kesten and V. Limic [Probab. Theory Relat. Fields 122, No. 4, 567–592 (2002; Zbl 0995.60042)]. Moreover, we give a new proof for the transience of a family of biased random walks defined on \({\mathcal G}\). Other proofs of this fact can be found in [R. Pemantle, Ann. Probab. 16, No. 3, 1229–1241 (1988; Zbl 0648.60077) and R. Lyons, ibid. 18, No. 3, 931–958 (1990; Zbl 0714.60089)] as part of more general results. A similar technique is applied to a vertex-reinforced jump process. A by-product of our result is that this process is transient on the 3-ary tree. B. Davis and S. Volkov [Probab. Theory Relat. Fields 128, No. 1, 42–62 (2004; Zbl 1048.60062)] proved that a vertex-reinforced jump process defined on the \(b\)-ary tree is transient if \(b\geq 4\) and recurrent if \(b=1\). The case \(b=2\) is still open.


60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
60G50 Sums of independent random variables; random walks
60J75 Jump processes (MSC2010)
Full Text: DOI arXiv


[1] Collevecchio, A. (2005). Limit theorems for vertex-reinforced jump processes on certain trees. Unpublished manuscript. · Zbl 1189.60170
[2] Collevecchio, A. (2006). Limit theorems for reinforced random walks on certain trees. Probab. Theory Related Fields . · Zbl 1109.60027
[3] Coppersmith, D. and Diaconis, P. (1987). Random walks with reinforcement. Unpublished manuscript.
[4] Dai, J. J. (2005). A once edge-reinforced random walk on a Galton–Watson tree is transient. Statist. Probab. Lett. 73 115–124. · Zbl 1078.60033
[5] Davis, B. (1990). Reinforced random walk. Probab. Theory Related Fields 84 203–229. · Zbl 0665.60077
[6] Davis, B. (1999). Reinforced and perturbed random walks. In Random Walks (P. Révész and B. Tóth, eds.) 9 113–126. Bolyai Soc. Math. Studies, Budapest. · Zbl 0953.60028
[7] Davis, B. and Volkov, S. (2002). Continuous time vertex-reinforced jump processes. Probab. Theory Related Fields 84 281–300. · Zbl 1009.60027
[8] Davis, B. and Volkov, S. (2004). Vertex-reinforced jump process on trees and finite graphs. Probab. Theory Related Fields 128 42–62. · Zbl 1048.60062
[9] Diaconis, P. and Rolles, S. W. W. (2006). Bayesian analysis for reversible Markov chains. Ann. Statist. 34 . · Zbl 1118.62085
[10] Durrett, R., Kesten, H. and Limic, V. (2002). Once reinforced random walk. Probab. Theory Related Fields 122 567–592. · Zbl 0995.60042
[11] Lyons, R. (1990). Random walks and percolation on trees. Ann. Probab. 18 931–958. · Zbl 0714.60089
[12] Lyons, R. and Pemantle, R. (1992). Random walk in a random environment and first-passage percolation on trees. Ann. Probab. 20 125–136. · Zbl 0751.60066
[13] Lyons, R., Pemantle, R. and Peres, Y. (1996). Biased random walks on Galton–Watson trees. Probab. Theory Related Fields 106 249–264. · Zbl 0859.60076
[14] Muliere, P., Secchi, P. and Walker, S. G. (2000). Urn schemes and reinforced random walks. Stochastic Process. Appl. 88 59–78. · Zbl 1045.62006
[15] Othmer, H. and Stevens, A. (1997). Aggregation, blowup, and collapse: The ABCs of taxis and reinforced random walk. SIAM J. Appl. Math. 57 1044–1081. JSTOR: · Zbl 0990.35128
[16] Pemantle, R. (1988). Phase transition in reinforced random walks and rwre on trees. Ann. Probab. 16 1229–1241. · Zbl 0648.60077
[17] Pemantle, R. (2001). Random processes with reinforcement. Preprint. Available at www.math.upenn.edu/ pemantle/papers/Papers.html.
[18] Pemantle, R. (1992). Vertex-reinforced random walk. Probab. Theory Related Fields 92 117–136. · Zbl 0741.60029
[19] Pemantle, R. and Peres, Y. (1996). On which graphs are all random walks in random environments transient? In Random Discrete Structures (R. Pemantle and Y. Peres, eds.) 207–211. Springer, New York. · Zbl 0846.60095
[20] Pemantle, R. and Stacey, A. M. (2001). The branching random walk and contact process on Galton–Watson and nonhomogeneous trees. Ann. Probab. 29 1563–1590. · Zbl 1013.60078
[21] Pemantle, R. and Volkov, S. (1999). Vertex-reinforced random walks on \(\mathbbZ\) have finite range. Ann. Probab. 27 1368–1388. · Zbl 0960.60041
[22] Rolles, S. W. W. (2003). How edge-reinforced random walk arises naturally. Probab. Theory Related Fields 126 243–260. · Zbl 1029.60089
[23] Rolles, S. W. W. (2006). On the recurrence of edge-reinforced random walks on \( \mathbbZ\times G\). Probab. Theory Related Fields . · Zbl 1206.82045
[24] Sellke, T. (1994). Reinforced random walk on the \(d\)-dimensional integer lattice. Technical Report 94–26, Dept. Statistics, Purdue Univ. · Zbl 1154.82011
[25] Volkov, S. (2001). Vertex-reinforced random walk on arbitrary graphs. Ann. Probab. 29 66–91. · Zbl 1031.60089
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.