Short Version:
I'm reading Probability on Trees and Networks and I am currently struggling with Exercise 3.4 (page number 80 / page 97 in the PDF) which asks "For simple random walk on $T$ to be transient, is it necessary that $\operatorname{br} T > 1$?". The hint says to consider spherically symmetric trees. Of course, an infinite spherically symmetric tree $T$ with branching number $\operatorname{br} T = 1$ would be the tree where every node has exactly one child ($=$ a root with an infinite line of nodes attached). The simple random walk on this graph is recurrent, so $\operatorname{br} T \geq 1 \nRightarrow \textrm{transient}$. Hence, we need $\operatorname{br} T > 1$ to infer transience.
My question is about the other direction: does transience imply $\operatorname{br} T > 1$? Or is there an infinite tree with $\operatorname{br} T = 1$ which has a transient simple random walk?
Another way to phrase this question is: does it hold that $$\operatorname{br} T = 1 \iff \textrm{simple random walk on } T \textrm{ is recurrent}$$
(if this holds, then transience would imply $\operatorname{br} T > 1$; the direction $\impliedby$ is clear since $\operatorname{br} T > 1 \implies \textrm{transient}$)
In summary, I'm looking for either of these two:
- either an example of an infinite tree $T$ with $\operatorname{br} T = 1$ and a transient simple random walk
- or a proof that $\operatorname{br} T = 1$ implies recurrence
Long Version:
Let $T$ be a locally finite infinite rooted tree (infinitely many nodes, but every node has only finitely many neighbors). The branching number $\operatorname{br} T$ is not completely straightforward to define, but it measures something like the average number of children of a node. In the book mentioned above, there is a good definition in Section 1.2 (page number 2 / page 19 in the PDF). Consider a simple random walk (taking every edge with equal probability) starting at the root.
The random walk is transient if the probability of never returning to the root is positive, and recurrent otherwise. The branching number $\operatorname{br} T$ is closely connected to recurrence and transience, see Section 1.4, Theorem 1.7 in the book (page number 7, page 24 in the PDF). This theorem also implies that $\operatorname{br} T > 1 \implies \textrm{transient}$ for simple random walks. The case $\operatorname{br} T = 1$ for simple random walks is not covered by the theorem, however. My question above is exactly about that case.
In this question, 1. bullet point, almost the same question was asked. The answer, however, is not correct in my opinion. A simple random walk on the modified binary tree given in the answer is recurrent, and not transient, as claimed in the answer (I'm quite confident that this is correct, but feel free to leave a comment if you think it is transient). There was only this one reply to that question, so I'm still looking for a correct answer.
Best Answer
Counterexample to $\operatorname{br} T = 1 \iff T \textrm{ recurrent}$:
This counterexample uses the following notation: $T$ is a locally finite infinite tree with root $o$, i.e. the number of vertices is infinite but the degree of every node is finite. All considered random walks are simple random walks starting at the root, i.e. random walks which take each edge with equal probability. The random walk is recurrent if it returns to the root with probability $1$ (and hence returns to the root infinitely often almost surely), and transient if it only returns to the root with probability $< 1$, i.e. the probability of never returning is positive.
The branching number $\operatorname{br} T$ of a tree $T$ is defined as in 1, page 80 / Equation 3.4. A spherically symmetric tree is a tree such that every node at distance $n$ from the root has the same number of children. By 1, page 4 / Exercise 1.2, it holds that $\operatorname{br} T = \operatorname{gr} T$ (if the latter exists) for every spherically symmetric tree where $\operatorname{gr} T$ is the growth rate given by $\operatorname{gr} T := \lim_{n\to\infty} \left|T_n\right|^{\frac{1}{n}}$ with $T_n$ being the set of vertices at distance $n$ from the root.
In the following, random walk will be used for simple random walk. As it depends entirely on the tree $T$ whether the simple random walk is recurrent or transient, the formulation $T$ is recurrent or transient will be used, meaning that the simple random walk on $T$ starting at the root is recurrent or transient.
It holds that $\operatorname{br} T = 1 \impliedby T \textrm{ recurrent}$. See 1, Theorem 3.5. However, $\operatorname{br} T = 1 \implies T \textrm{ recurrent}$ is wrong, as the following example shows:
Consider the infinte binary tree. Let $T_n$ as above. Then, replace every edge exiting $T_n$ with a chain of $n$ nodes. See Figure 1: at every level $T_n$ of the original binary tree, linearly many (exactly $n$) generations with only one child per node are added, indicated in blue.
From now on, call this tree $T$ ($T$ is on the right in Figure 1). Claim: $\operatorname{br} T = 1$ and the random walk on $T$ is transient.
Proof: First, $\operatorname{br} T = 1$ is shown, followed by the proof of transience.
$T$ is spherically symmetric, so $\operatorname{br} T = \operatorname{gr} T = \lim_{n\to\infty} \left|T_n\right|^{\frac{1}{n}}$. It holds that \begin{align*} \left|T_n\right| = 2^k \textrm{ for } \frac{k\left(k-1\right)}{2} < n \leq \frac{k\left(k+1\right)}{2} \end{align*} This can be seen easily: $2^k$ is the number of nodes on level $k$ in the original binary tree. Adding first $1$, then $2$, then $3$, and so on nodes in between the levels, $2^k$ is now the number of nodes for all levels between $1 + 2 + \ldots + k - 1 = \frac{k\left(k-1\right)}{2}$ (exclusive) and $1 + 2 + \ldots + k = \frac{k\left(k+1\right)}{2}$ (inclusive), also see Figure 1.
This implies, selecting the appropriate $k$: \begin{align*} \sqrt[k+1]{4} = \left(2^k\right)^{\frac{2}{k\left(k+1\right)}} \leq \left|T_n\right|^{\frac{1}{n}} < \left(2^k\right)^{\frac{2}{k\left(k-1\right)}} = \sqrt[k-1]{4} \end{align*} Both sides converge to $1$ for $k \to \infty$, and as $k \to \infty$ for $n \to \infty$, we conclude $\operatorname{gr} T = \lim_{n\to\infty} \left|T_n\right|^{\frac{1}{n}} = 1$.
To show that $T$ is transient, we use the following Theorem 11 from 2 / Theorem 2.11 from 1 (these two theorems are the same): the random walk on $T$ is transient if, and only if, the tree admits a finite energy source flow.
A flow is a map $f: E \to \left[0, \infty\right)$ with the set of edges $E$ (outward-oriented) of $T$, such that the incoming flow at every node (except from the root) from its parent is the same as the sum of the outgoing flows to its children. The energy of the flow is defined as $\sum_{e \in E} f\left(e\right)^2$.
Hence, it suffices to show the existence of such an $f$ for the considered $T$ with finite energy. Define $f$ as follows: for the edges exiting the root, set $f\left(e\right) = \frac{1}{2}$. Then, whenever a node has two children, split the flow equally among them. See Figure 2: the flow $f$ is indicated in blue for selected edges.
It remains to calculate the energy of the flow. This is simple: there are exactly $2^n \cdot n$ edges with a flow of $\frac{1}{2^n}$, also see Figure 2 again. It then follows that $\sum_{e \in E} f\left(e\right)^2 = \sum_{n = 1}^\infty 2^n \cdot n \cdot \left(\frac{1}{2^n}\right)^2$ which is convergent by the root test. In fact, $\sum_{n = 1}^\infty 2^n \cdot n \cdot \left(\frac{1}{2^n}\right)^2 = 2$. Hence, the energy of $f$ is finite and we can conclude that $T$ is transient.