Randomly biased walks on subcritical trees

Gérard Ben Arous, Alan Hammond

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1481-1527
Number of pages47
JournalCommunications on Pure and Applied Mathematics
Volume65
Issue number11
DOIs
StatePublished - Nov 2012

ASJC Scopus subject areas

  • Mathematics(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Randomly biased walks on subcritical trees'. Together they form a unique fingerprint.

  • Cite this