TY - JOUR

T1 - Randomly biased walks on subcritical trees

AU - Ben Arous, Gérard

AU - Hammond, Alan

N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.

PY - 2012/11

Y1 - 2012/11

N2 - As a model of trapping by biased motion in random structure, we study the time taken for a biased random walk to return to the root of a subcritical Galton-Watson tree. We do so for trees in which these biases are randomly chosen, independently for distinct edges, according to a law that satisfies a logarithmic nonlattice condition. The mean return time of the walk is in essence given by the total conductance of the tree. We determine the asymptotic decay of this total conductance, finding it to have a pure power-law decay. In the case of the conductance associated to a single vertex at maximal depth in the tree, this asymptotic decay may be analyzed by the classical defective renewal theorem, due to the nonlattice edge-bias assumption. However, the derivation of the decay for total conductance requires computing an additional constant multiple outside the power law that allows for the contribution of all vertices close to the base of the tree. This computation entails a detailed study of a convenient decomposition of the tree under conditioning on the tree having high total conductance. As such, our principal conclusion may be viewed as a development of renewal theory in the context of random environments. For randomly biased random walks on a supercritical Galton-Watson tree with positive extinction probability, our main results may be regarded as a description of the slowdown mechanism caused by the presence of subcritical trees adjacent to the backbone that may act as traps that detain the walker. Indeed, this conclusion is exploited in a sequel by the second author to obtain a stable limiting law for walker displacement in such a tree.

AB - As a model of trapping by biased motion in random structure, we study the time taken for a biased random walk to return to the root of a subcritical Galton-Watson tree. We do so for trees in which these biases are randomly chosen, independently for distinct edges, according to a law that satisfies a logarithmic nonlattice condition. The mean return time of the walk is in essence given by the total conductance of the tree. We determine the asymptotic decay of this total conductance, finding it to have a pure power-law decay. In the case of the conductance associated to a single vertex at maximal depth in the tree, this asymptotic decay may be analyzed by the classical defective renewal theorem, due to the nonlattice edge-bias assumption. However, the derivation of the decay for total conductance requires computing an additional constant multiple outside the power law that allows for the contribution of all vertices close to the base of the tree. This computation entails a detailed study of a convenient decomposition of the tree under conditioning on the tree having high total conductance. As such, our principal conclusion may be viewed as a development of renewal theory in the context of random environments. For randomly biased random walks on a supercritical Galton-Watson tree with positive extinction probability, our main results may be regarded as a description of the slowdown mechanism caused by the presence of subcritical trees adjacent to the backbone that may act as traps that detain the walker. Indeed, this conclusion is exploited in a sequel by the second author to obtain a stable limiting law for walker displacement in such a tree.

UR - http://www.scopus.com/inward/record.url?scp=84865543401&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84865543401&partnerID=8YFLogxK

U2 - 10.1002/cpa.21416

DO - 10.1002/cpa.21416

M3 - Article

AN - SCOPUS:84865543401

VL - 65

SP - 1481

EP - 1527

JO - Communications on Pure and Applied Mathematics

JF - Communications on Pure and Applied Mathematics

SN - 0010-3640

IS - 11

ER -