Let a random walk on a graph $G=(V,E)$ be characterized by the transition matrix $P$.
The usual discrete random walk process is: \begin{equation} p^{t+1}= p^{t} P, \end{equation} where $p^{t}$ is a probability distribution over the graph vertices at time $t$.
Under assumptions that the random walk be ergodic, i.e., reversible and aperiodic, there exists a unique stationary distribution $\pi$ checking: \begin{equation} \pi= \pi P\;,\quad p^{t}\xrightarrow{\ \ t\to\infty\ \ } \pi. \end{equation}
Aperiodicity is achieved provided the graph is not bipartite, or $P$ has all its eigenvalues $>-1$.
Reversibility is the property that the time-reverse random walk has the same transition matrix: \begin{equation} \pi_i P_{ij} = \pi_j P_{ji}. \end{equation}
It is then rather easy to check if the aperiodicity property is achieved.
But how do you check that your random walk is reversible? Is there a simple criteria which does not require to know $\pi$?
