1
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I see, so random walks on graphs are reversible since they satisfy the reversibility condition. In general reverisble Markov chains are representable as random walks on weighted graphs, and the random walks on graphs are those for which we may take unit weight for each edge. $\endgroup$
    – Meep
    May 2, 2022 at 21:36
  • $\begingroup$ Just to be clear, the above seems not to depend on the type of random walk? Like simple vs lazy? $\endgroup$
    – Meep
    May 2, 2022 at 21:37
  • $\begingroup$ A lazy random walk on a graph is just a random walk on a graph with appropriately-weighted loops at each vertex. $\endgroup$ May 2, 2022 at 22:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .