Random walks on regular trees

Question

An infinite $d$-regular tree is a graph where every vertex has degree $d$ and there are no cycles. Suppose we define a standard random walk $X_n$ on such a tree. Is the claim that $X_n$ is transient for $d \ge 3$ true? If so, how can I prove that?

I do know for a fact that random walks are transient on $\mathbb{Z}^d$ with $d \ge 3$. Can we use this somehow to prove the claim?

Answer 1

The claim is true. The proof is similar to the proof for Z^d. The key idea is that on an infinite regular tree, there are many paths that diverge from the current location of the walk. This means the walk can "get lost" and move far away from the origin, leading to transience. To make this precise, consider the following:

Let d_n be the distance from the origin after n steps. For any n, there are at least d choices for the (n+1)st step that increase d_n. By the branching property, this will be true no matter where the walk is, so d_n will tend to infinity almost surely.

So you can mimic the proof for Z^d by showing that the walk can always increase its distance from the origin, leading to transience. The branching property of the tree is what enables this, analogous to the many neighboring sites available on Z^d. Hope this helps!

Answer 2

This is more of an extended hint/spoiler than a complete answer but it should get you where you need to go.

First, designate the starting node as the root of the tree. Next, observe that nodes that are the same distance from the root are essentially equivalent for our purposes. Thus, we can model a random walk on the tree as a random walk on a set of states $\{s_0,s_1,s_2, \ldots\}$ with probability $p_{i,j}$ of transiting from state $s_i$ to $s_j$ as follows:$$ p_{0,1} = 1 \\ p_{i,i-1} = 1/d ,\quad \mbox{for } i\geq 1\\ p_{i,i+1} = 1-1/d,\quad \mbox{for } i\geq 1$$From here, you can apply the usual textbook techniques to determine that this Markov process is transient. There does not appear to be any need to appeal to $\mathbb{Z}^d$.

tl;dr: a random walk on an infinite tree of degree $d$ is transient not via analogy to $\mathbb{Z}^d$ but via analogy to a biased random walk on $\mathbb{N}$.

Answer 3

There are many proofs of transience. I took the question as challenging us to write down the most elementary proof.

Call the starting vertex $x_0$. The walk can only return to $x_0$ after an even number of steps. We first bound the number $\Psi_{2n}$ of paths of length $2n$ from $x_0$ to itself:

Let $v_n$ be a vertex at distance $2n$ from $x_0$. At each of the first $2n$ steps, there is one option for the walk to move closer to $v_n$ and there are $d-1$ options to move further from $v_n$.

For a path from $x_0$ to return to $x_0$, the number of steps moving closer to $v_n$ must equal the number of steps moving further. Thus $$\Psi_{2n} \le {2n \choose n} (d-1)^n \le 2^{2n} (d-1)^n\,,$$ where the binomial factor comes from choosing in which of the $2n$ steps the walk will move closer to $v_n$. Therefore $$\mathbb P_{x_0}(X_{2n}=x_0) =\frac{\Psi_{2n}}{d^{2n}} \le \left(\frac{4(d-1)}{d^2}\right)^n \,.$$ Since the RHS is summable in $n$, the random walk is transient.