Reversible Markov Chain on graph Could someone help me with this exercise?
Let $(X_n)$ be a random walk on a network G and let $x$ and $y$ be two vertices in $G$. Let $\mathscr{P}$ be a path from $x$ to $y$ and $\mathscr{P}\text{ '}$ be its reversal (from $y$ to $x$). Show that $$\mathbb{P}_x\big[(X_n;n<\tau_y)=\mathscr{P} \text{ }| \text{ } \tau_y<\tau_x^+ \big] = \mathbb{P}_y\big[(X_n;n<\tau_x)=\mathscr{P} \text{ ' }| \text{ } \tau_x<\tau_y^+ \big],$$
where $\tau_w$ denotes the first time the random walk visits $w$ and $\tau_w^+$ denotes the first time after $0$ that the random walk visits $w$ and $\mathbb{P}_u$ denotes the law of random walk started at $u$.
I know that this says that paths between two states that don't return to the starting point and stop at the first visit to the endpoint have the same distribution in both directions of time but how do I show the equality?
Any help would be great!
 A: Let the path $\mathscr P$ consist of vertices $v_0, v_1, \dots, v_k$ with $v_0 = x$ and $v_k = y$.
Note that we have:
$$\mathbb{P}_x\big[(X_n;n\le \tau_y)=\mathscr{P} \mid \tau_y<\tau_x^+ \big] = \frac{\mathbb{P}_x\big[(X_0,X_1,\dots,X_k)=\mathscr{P}\big]}{\mathbb{P}_x\big[\tau_y<\tau_x^+ \big]}.$$
(By default, the top probability would have an "and $\tau_y < \tau_x^+$" in it, but if we are following the path $\mathscr P$ to the end, we already know that $\tau_y < \tau_x^+$.)
Moreover, we can compute the probability that we follow $\mathscr P$ exactly: it is $$\prod_{i=0}^{k-1} \frac{1}{\deg v_i} = \deg y \prod_{i=0}^{k} \frac{1}{\deg v_i}.$$
The same logic applies to following the reversal of $\mathscr P$ starting from $y$, so we seek to prove
$$\frac{\deg y \prod_{i=0}^{k} \frac{1}{\deg v_i}}{\mathbb{P}_x\big[\tau_y<\tau_x^+ \big]} = \frac{\deg x \prod_{i=0}^{k} \frac{1}{\deg v_i}}{\mathbb{P}_y\big[\tau_x<\tau_y^+ \big]}$$ which is equivalent (after we cancel like terms) to showing that $$\mathbb{P}_x\big[\tau_y<\tau_x^+ \big] \cdot \deg x = \mathbb{P}_y\big[\tau_x<\tau_y^+ \big] \cdot \deg y.$$
We could stop here by appealing to a standard result in the electric networks interpretation of random walks: $\mathbb{P}_x\big[\tau_y<\tau_x^+ \big] \cdot \deg x$ is the effective conductance between $x$ and $y$, and effective conductance is symmetric. But this might be unsatisfying, so let me take a different approach.
Note that in the limiting distribution $\pi$, we have $\pi_x = \frac{\deg x}{2|E|}$. (This is still true for the time-average distribution even if $G$ is bipartite.) So it suffices to show that $\mathbb{P}_x\big[\tau_y<\tau_x^+ \big] \cdot \pi_x = \mathbb{P}_y\big[\tau_x<\tau_y^+ \big] \cdot \pi_y$.
Now imagine the Markov chain with just two states $X$ and $Y$, and transitions as follows:


*

*If we're in state $X$, take a random walk in $G$ starting from $x$ until it either reaches $y$ or returns to $x$. If this random walk reaches $y$, transition to state $Y$; otherwise, stay in state $X$.

*If we're in state $Y$, take a random walk in $G$ starting from $y$ until it either reaches $x$ or returns to $y$. If this random walk reaches $x$, transition to state $X$; otherwise, stay in state $Y$.


In this Markov chain, the transition probabilities are precisely $P_{X\to Y} = \mathbb{P}_x\big[\tau_y<\tau_x^+ \big]$ and $P_{Y\to X} = \mathbb{P}_y\big[\tau_x<\tau_y^+ \big]$. It's easy to solve a two-state Markov chain: the limiting distribution is $$\left(\frac{P_{Y \to X}}{P_{X\to Y} + P_{Y \to X}}, \frac{P_{X \to Y}}{P_{X\to Y} + P_{Y \to X}}\right).$$
But it should also be clear that the limiting distribution of this Markov chain corresponds to the limiting distribution of the original random walk on $G$: in fact, the Markov chain is just the random walk with all states other than $x$ and $y$ dropped from it. So the Markov chain should have limiting distribution $$\left(\frac{\pi_x}{\pi_x + \pi_y}, \frac{\pi_y}{\pi_x + \pi_y}\right).$$
Setting these equal, we conclude that $\pi_x P_{X \to Y} = \pi_y P_{Y \to X}$, which is equivalent to the statement we wanted to prove.
