Associated Graph of Markov Chain Tree Implies Reversibility

Question

I wish to show the following claim.

Associate a graph with a Markov process${}^1$ by letting $(j,k)$ be an edge if $q(j,k) > 0$ or $q(k,j) > 0$. Show that if the graph associated with a stationary Markov process is a tree, then the process is reversible.

A proof of this is given here (Proposition 1.6) or here (Lemma 1.5). Unfortunately, I don't completely follow the proofs. I understand the basics, eg that removing an edge from a tree disconnects it. However, I don't understand why this then reduces full balance for $j$ (or $k$) down to detailed balance for the pair $(j,k)$. There's no mention of stationarity in the proof -- I image that this is the understanding part that I'm missing...

---

${}^1$ by 'Markov process' I mean a continuous-time Markov chain on a countable state space

Answer 1

Let us consider discrete-time -- the continuous-case follows similarly. Define $$ Q(A,B) = \sum_{x \in A} \sum_{y \in B} \pi(x) p(x,y). $$ One can show using only stationarity (see, eg, Lemma 1.4), for any set $S$, that $$ Q(S,S^c) = Q(S^c,S). $$ This does not require reversiblity.

Now let us consider our problem. Take $i$ and $j$ with $(i,j)$ an edge. Let $S$ be the set of all vertices 'on one side of $j$', along with $j$, ie the set of all vertices that are connected to $j$ not using the edge $(i,j)$. Then the equality $$ Q(S,S^c) = Q(S^c,S) $$ does reduce to the detailed balance equation for $i$ and $j$.

---

This is fairly straightfoward, but I do believe that it isn't adequately described in the linked answers -- indeed, one says to take $S$ to be $j$, which isn't what one wants to do (or, at least, I can't see how to do it using that). Hopefully this answer can be a reference for those with a similar issue to what I had!

Answer 2

Let $\{X_t:t\geqslant0\}$ be the CTMC on state space $E=\{1,2,\ldots,n\}$. It is clear that $\{X_t\}$ is irreducible as trees are connected graphs, and so there exists a unique stationary distribution $\pi$ (as the state space is finite). Let $Q$ be the generator of $\{X_t\}$ and let $i,j\in E$. Assume that $\mathbb P(X_t=j)=\pi_j$, so that the process is stationary.

If $i=j$ then trivially $\pi_iQ_{ii}=\pi_iQ_{ii}$. If $Q_{ij}=0$ then $\pi_iQ_{ij}=\pi_jQ_{ji}=0$ (since $Q_{ij}>0\iff Q_{ji}>0$). If $Q_{ij}>0$, consider the cut formed by removing edge $\{i,j\}$ from the graph - let $i\in A$ and $j\in A^c$. Because the graph is a tree, the detailed balance equation $$ \sum_{k\in A}\sum_{\ell\in A^c}\pi_kQ_{k\ell} = \sum_{k\in A^c}\sum_{\ell\in A}\pi_kQ_{k\ell} $$ reduces to $$ \pi_i Q_{ij} = \pi_jQ_{ji}, $$ and so it follows that $\{X_t\}$ is reversible.