Is a reversible and a time-reversible Markov chain the same thing?

413 Views Asked by At

I am suspecting this is not the case.

This source says that "all reversible MArkov chains can be interpreted as random walks on graphs"

On the other hand a time reversible MArkov chain is defined as one for which, is $\pi$ is the stationary distribution,

$$\pi _i P_{ij} = \pi _j P_{ji} \ \forall i,j$$

And intuitively, I am tinking that since the hitting time from a vertex s to a vertex t is not symmetric, then we do not have time reveribility. I believe that the stationary distribution for asimple random walk on a graph has $\pi_i = deg(i)/n\bar{d}$ so it is not the uniform distribution.

Any clarification would be very appreciated.

1

There are 1 best solutions below

3
On BEST ANSWER

These uses of "reversible" and "time-reversible" really are the same.

The condition $\pi_i P_{ij} = \pi_j P_{ji}$ holds for all random walks on graphs. It does not imply that $\pi$ is the uniform distribution (and in fact, you should see that $\pi_i \ne \pi_j$ whenever $P_{ij} \ne P_{ji}$). It also does not imply that hitting times should be symmetric, though it does imply that $$H(i,j) + H(j,k) + H(k,i) = H(i,k) + H(k,j) + H(j,i).$$ The stationary distribution $\pi_i = \frac{\deg(i)}{2m}$ satisfies the reversibility condition simply because $P_{ij} = \frac1{\deg(i)}$, and so $\pi_i P_{ij} = \frac1{2m}$ for all $i$ and $j$.


However, reversible Markov chains are not quite the same as random walks on graphs. They are the same as random walks on weighted graphs. Here, each edge $ij$ has a weight $w_{ij}=w_{ji}$; let $w_i = \sum_j w_{ij}$, and let $w = \sum_i w_i$. The weighted random walk goes from $i$ to $j$ with probability $\frac{w_{ij}}{w_i}$ if there is an edge between $i$ and $j$, and the stationary distribution is $\pi_i = \frac{w_i}{w}$. When the weights are $1$ for every edge, we get back to ordinary random walks.

To see that this is true, take any reversible Markov chain, and take the graph whose vertices are the states of the Markov chain, letting $w_{ij} = \pi_i P_{ij} = \pi_j P_{ji}$. You will see that this random walk behaves exactly like the original Markov chain.