In a previous question, given an ergodic Markov chain, I'm interesting in sampling as short a path as possible with prescribed distributions for its endpoints. In a comment, I propose that the solution to this problem would be optimal transport with cost-function given by the *commute time distance* of the chain. I'm opening this new question to try and explore the OT connection better.

# Precise statement of the problem

Consider an ergodic Markov chain with state space $S$. Let $\pi_0$ and $\pi_1$ be two distributions on $S$. Let $\Gamma(\pi_0,\pi_1)$ be the coupling polytope of joint distributions on $S \times S$ with marginals $\pi_0$ and $\pi_1$ respectively. For example, if the state space $S$ is finite, then this is just the set of all nonnegative matrices with row sum $\pi_0$ and column sum $\pi_1$. Since the *commute time distance* (i.e the average time it takes to move from one state to another and back) defines a distance on $S$, it follows that the mapping

$$\Delta(\pi_0, \pi_1) := \operatorname{minimize}_{\gamma \in \Gamma(\pi_0,\pi_1)}\mathbb E_{(x,y) \sim \gamma}[\operatorname{CommuteTimeDistance}(x,y)],$$ defines a distance between distributions on $S$.

# Question

Is there an efficient way to compute such a distance ?

# Poorman's solution

In finite dimensions, it should be possible to use Sinkhorn iterations to solve an entropy regularized version of the above problem (this appears to be the SOTA method for solving large scale OT problems). I was wondering whether we can do better. That is, maybe a more "analytic" way to go about the problem.

# Euclidean embedding

This paper shows that if the state space $S$ is finite, say has $n$ elements, then it can be embedded into a euclidean space of dimension $\le n - 1$ via the mean commute time as follows. Let $L = U\Lambda U^T$ be the eigen-decomposition of Laplacian of the chain (note that $L$ is positive semi-definite). Finally, for $i \in S= \{1,2,\ldots,n\}$, let $e_i$ be the $i$th unit vector in $\mathbb R^n$ and set $\psi_i := U{\Lambda^\dagger}^{1/2}e_i$. Then

$$\operatorname{CommuteTimeDistance}(i,j) = \|\psi_i - \psi_j\|_2^2. $$

1more comment