2004/04/02 by Robin Pemantle, Russell Lyons
Mathematics · #math.PR #msc:60J15 #msc:60K35 #msc:82A43
published as Ann. Probab., 20, 125 - 136 (1992) · 11 pages
arxiv created 2004/04/02 · arxiv updated 2009/12/01
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.