"Inverting" a Markov chain transition matrix into a weighted, undirected graph

Question

Suppose I have some normalized transition matrix $P$ for a Markov chain, and suppose I know a priori that there exists a weighted, undirected graph $G$ for which a random walk on $G$ would have the same transition probabilities as $P$. How would I go about deriving $G$ from $P$ (up to a constant factor on edge weights)?

Answer 1

You can find an explanation of what's going on here in Chapter 9 of Markov Chains and Mixing Times by Levin, Wilmer, Peres, which is available online.

Briefly, we can say the following: such a weighted graph exists if and only if the Markov chain is reversible. If the Markov chain has a unique stationary distribution $\pi$, then reversibility is equivalent to the detailed balance equation $$ \pi(x)P(x,y) = \pi(y) P(y,x) $$ holding for all states $x,y$.

With that said, one valid weighting is to take $\pi(x) \cdot P(x,y)$ to be the weight for the edge $xy$.