1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you explain why you don't think the example works in your question? $\endgroup$ – Paul Plummer Nov 13 '19 at 22:15
  • $\begingroup$ Also do you agree that the example has branching number 1? (I have not looked at the formal definitions but if your "intuition definition" is accurate that should be the case) $\endgroup$ – Paul Plummer Nov 13 '19 at 22:22
  • $\begingroup$ Yes, the branching number of the example is $1$. However, the simple random walk on it is recurrent. To see that, consider the correct example I posted as answer below. Instead of adding $n$ nodes in a row, more than $2^n$ nodes would be added (if I understand correctly). The very last formula will then not give a finite sum anymore (because $n$ has to be replaced with $2^n$). However, the correct example is of course almost the same. $\endgroup$ – M_F Nov 13 '19 at 23:15
  • 1
    $\begingroup$ I think you misunderstood the example given in the other answer. They are adding a bunch of leaves (or one ended rays if you don't want leaves) to bring the average down, but random walks can't be recurrent if the original graph wasn't recurrent. $\endgroup$ – Paul Plummer Nov 13 '19 at 23:26
  • $\begingroup$ Possibly, I'm not quite sure. The infinite trees which are considered in the book do not have leaves ("For the purposes of this chapter, we do not allow the possibility of leaves, that is, vertices without children", page 2, Section 1.2). I therefore assumed that he meant adding paths with nodes which have only one child. However, now that you've pointed out the other interpretation, I guess it's much more likely that this was the intended meaning... I just didn't see it. (even though the phrase "adding generations" sounds wrong to me in this context) $\endgroup$ – M_F Nov 13 '19 at 23:42
0
$\begingroup$

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.

Modifying the binary tree

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.

    Finite energy flow

    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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.