Let $T$ be a tree with countably many nodes so that each node has $n$ neighbors. Let a Markov chain be defined by starting at some random vertex of $T$ and then move by traveling to any of the $n$ neighbour nodes at each step with probability $1/n$. For which values of $n$ is the chain transient?
Thoughts: I would intuitively have thought that this Markov chain was never transient since the number of nodes is countable, and therefore we should almost surely visit any given node an infinite number of times. Obviously this is not how it works though. Can someone show me how to proceed with calculations (I don't need an exact answer, just a method)?
I claim that the random walk on $T$ is recurrent if $n\leq 2$ and transient if $n \geq 3$. The easiest and most standard way to prove this is to use the comment above by Ian to reduce the problem to an easier problem about Markov Chains on $\Bbb N$. A standard approach to the theory of recurrence and transience can be found starting on page 75 here.
However, I would like to outline a different approach to prove the transience part of the statement for $n \geq 3$. This approach uses harmonic functions and martingales. Namely, we will reduce the problem of proving transience to finding a nonconstant bounded harmonic function on $T$.
Definition: A function $f:T \to \Bbb R$ is harmonic if its value at every node is equal its average value over all neighboring nodes, i.e, $\;f(v)=\frac{1}{n}\sum_{w \sim v} f(w)$.
Lemma: If the random walk on $T$ is recurrent, then every bounded harmonic function from $T \to \Bbb R$ is constant.
Proof: Let $X_n$ denote the random walk on $T$ starting from some arbitrary base vertex $x_0$, and let $f:T \to \Bbb R$ be some bounded harmonic function. Then $f(X_n)$ is a bounded martingale (this is straightforward). Let $x \in T$ be an arbitrary vertex, and let $\tau_x$ denote the first hitting time of $x$ by $X_n$. By recurrence $\tau_x<\infty$. Since bounded martingales are uniformly integrable, the optional stopping theorem tells us that $f(x) = \Bbb E[f(X_{\tau_x})]=\Bbb E[f(X_0)] = f(x_0)$. Thus $f$ is constant. $\Box$
Proof of Transience for $n \geq 3$: Let $T_3=T$ be our tree of degree $3$. Let $B_2$ denote an infinite binary tree. Then $B_2$ embeds into $T_3$ in a straightforward way, so it suffices to show the existence of a nonconstant bounded harmonic function from $B_2 \to \Bbb R$. For $v \in B_2$ we define $|v|$ to be the height of $v$ below the root vertex. We also define $\sigma(v) \in \{-1,1\}$ to be the sign of $v$, which is defined to be $1$ if $v$ is on the left half of $B_2$ and $-1$ if $v$ is on the right half of $B_2$ (the root vertex has no sign). Then we define our nonconstant bounded harmonic function from $B_2 \to [-1,1]$ by sending $v \mapsto \sigma(v) \cdot (1-2^{-|v|})$. It is easily checked that this function is harmonic. This gives transience on $T_3$, and by an easy embedding argument and induction we get transience on $T_n$ for $n \geq 3$. $\Box$