In recent years, probability on trees and networks is studied by more people. The simplest model is random walks. It is a corner stone for advanced studies. There are now some efficient criteria to determine if a random walk is recurrent or transient. The simple random walk on tree T is transient if the branching number br(T) > 1. H. Kesten et al proved that the simple random walk on the infinite open cluster in the Bernoulli bond percolation in Z^d is transient for d ³ 3.

Transient random walks are further studied by examining the speed lim_n |X_n|/n (if it exists), while X_n is the position of the walker after n movements from the initial vertex O, and |X_n| is the graphic distance from O to X_n. For the lambda biased random walk on Galton-Watson trees, R. Lyons, R. Pemantle and Y. Peres proved the existence of the speed and conjectured that the speed is bounded above by (m - l) / (m +l). Here m is the average branching number of Galton-Watson trees. In verifying this conjecture, we also obtained a lower bound of the speed. That is lim_n |X_n|/n ³ (m¢- l) / (m¢+ l), while m¢ is the harmonic mean of branching numbers of Galton-Watson trees. In most cases, it is more difficult to establish a lower bound. So it is still the best estimate so far. The upper bound, on the other hand, has been improved by B. Virag in 1998. Y. Peres provided a lower bound on the branching number br(T) if the speed of simple random walk is positive.

In 1959 H. Kesten proved the following three statements are equivalent for the simple random walk on a Cayley graph: (1) the Cheeger constant is positive; (2). liminf_n |X_n|/n is positive; and (3) lim_n (P( X_n = O) )^1/n < 1. Translation invariance of a Cayley graph is essential in the proof. Benjamini, Lyons and Schramm further conjectured that liminf_n|X_n|/n is positive in general graphs if the so-called anchored constant is positive.

The Bernoulli bond percolation may be viewed as a random perturbation of a graph. We like to find out which property is invariant under this perturbation. The previous result by Kesten et al is a beautiful result of this type. It is then natural to find out if the statement that speed of a random walk is zero is invariant under this perturbation. The difficult part of verification is to examine those graphs that their Cheeger constant is zero but their ball volume grows exponentially as the radius grows. G₁ and G₂ are examples of this type. The simple random walk on G₁ or G₂ is transient and the speed is zero. Y. Peres and I proved that the speed is zero for a simple random walk on an infinite open cluster of the Bernoulli bond percolation on G₁ or G₂.