4
$\begingroup$

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. $$

Improve this question
$\endgroup$
6
  • $\begingroup$ An even less "analytic" solution: The OT problem is a linear program and there are a several methods that are tuned OT problems. Hence you may try any LP solver or look for special solver for transport problems. (Of course, all in finite dimensions, but my bet is that there is no analytical way.) $\endgroup$
    – Dirk
    Commented Aug 21, 2017 at 19:34
  • $\begingroup$ @Dirk please see the last part of the question (naive solution). As I already mentioned there, there are indeed "fast" numerical methods to solve (approximations to ) this problem (e.g Sinkhorn iterations, etc.) with which I'm familiar. I should mention that solving OT exactly (the linear programming problem) is out of hand when the dimensions is above a few hundreds. $\endgroup$
    – dohmatob
    Commented Aug 21, 2017 at 20:28
  • 1
    $\begingroup$ The following work discusses the continuous-analog (Benamou-Brenier style) optimal transport on graphs/markov chains :Maas, Jan. "Gradient flows of the entropy for finite Markov chains." Journal of Functional Analysis 261.8 (2011): 2250-2292. $\endgroup$
    – Piyush Grover
    Commented Aug 21, 2017 at 21:06
  • 1
    $\begingroup$ Also see: Solomon, Justin, et al. "Continuous-flow graph transportation distances." arXiv preprint arXiv:1603.06927 (2016). $\endgroup$
    – Piyush Grover
    Commented Aug 21, 2017 at 21:13
  • $\begingroup$ Well, you asked for efficiency, and tailored LP solvers for OT problems should be the fastest methods around for S up to a few thousand. Besides that, there is fast growing body of literature on analysis and numerics of OT problems. $\endgroup$
    – Dirk
    Commented Aug 22, 2017 at 5:32

0

Reset to default

You must log in to answer this question.