FIRST-PASSAGE PERCOLATION ON TREES'

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. 1. Introduction. A random walk on a tree (by which we always mean an infinite, locally finite tree) is a Markov chain whose state space is the vertex set of the tree and for which the only allowable transitions are between neighboring vertices. We assume throughout that all transition probabilities are nonzero. For a fixed tree, the transition probabilities may be taken as random variables, in which case the resulting mixture of Markov chains is called random walk in a random environment (RWRE). The first theorem proved in this paper is conceptually the upper bound of two previous results obtained by the authors (separately) about RWRE on trees. The notation necessary to describe this is as follows. Choose an arbitrary vertex as the root and let o- be any other vertex. Let 5f denote the first vertex on the shortest path from o- to the root. If o- is at distance at least 2 from the root, define AO as the transition probability from 0f to rf divided by the transition probability from Or to 0r. We assume the following uniformity in our random environment: All but finitely many of the random variables AO, are identically distributed. (Since the values of A, are determined by the transition probabilities in a way that depends on the choice of root, it may appear that whether this condition is satisfied depends on the choice of root, but actually a different choice of root changes only finitely many of the A 's.) Let A denote a random variable with this common distribution. By the zero-one law, a RWRE is a.s. transient or a.s. recurrent. We shall determine the phase transition boundary; we do not know in general when the cases on the boundary are transient or recurrent, but examples indicate that