Random Walk in a Random Environment and First-Passage Percolation on Trees Export

@article{citeulike:2468971, abstract = {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.}, author = {Lyons, Russell and Pemantle, Robin}, citeulike-article-id = {2468971}, citeulike-linkout-0 = {http://www.jstor.org/stable/2244549}, journal = {The Annals of Probability}, keywords = {branching\_processes, random\_walks}, number = {1}, pages = {125--136}, posted-at = {2008-03-05 02:49:54}, priority = {2}, title = {Random Walk in a Random Environment and First-Passage Percolation on Trees}, url = {http://www.jstor.org/stable/2244549}, volume = {20}, year = {1992} }

TY - JOUR ID - citeulike:2468971 L3 - citeulike-article-id:2468971 N2 - 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. IS - 1 JF - The Annals of Probability EP - 136 TI - Random Walk in a Random Environment and First-Passage Percolation on Trees VL - 20 SP - 125 KW - branching_processes KW - random_walks AU - Lyons, Russell AU - Pemantle, Robin PY - 1992/// UR - http://www.jstor.org/stable/2244549 ER -