We show that the transience or recurrence of a random walk in certain random environments on an arbitrary infinite locally finite tree is determined by the branching number of the tree, which is a measure of the average number of branches per vertex. This generalizes and unifies previous work of the authors. It also shows that the point of phase transition for edge-reinforced random walk is likewise determined by the branching number of the tree. Finally, we show that the branching number determines the rate of first-passage percolation on trees, also known as the first-birth problem. Our techniques depend on quasi-Bernoulli percolation and large deviation results.
Publié le : 1992-01-14
Classification:
Trees,
random walk,
random environment,
first-passage percolation,
first birth,
random networks,
60J15,
60K35,
82A43
@article{1176989920,
author = {Lyons, Russell and Pemantle, Robin},
title = {Random Walk in a Random Environment and First-Passage Percolation on Trees},
journal = {Ann. Probab.},
volume = {20},
number = {4},
year = {1992},
pages = { 125-136},
language = {en},
url = {http://dml.mathdoc.fr/item/1176989920}
}
Lyons, Russell; Pemantle, Robin. Random Walk in a Random Environment and First-Passage Percolation on Trees. Ann. Probab., Tome 20 (1992) no. 4, pp. 125-136. http://gdmltest.u-ga.fr/item/1176989920/