Given an ergodic Markov chain and 2 states $x$ and $y$, how may one algorithmically sample a path (of finite length) $x =: s\_0 \rightarrow s\_1 \rightarrow \ldots \rightarrow s\_T = y$ between $x$ and $y$ ?


**Poorman's solution:** Let $N$ be the transition operator for the chain.
Then the process $s\_{t + 1} \sim N(s|s\_t)$, started at $s\_0 = x$ eventually hits $y$ in finite time. This gives us a path between $x$ and $y$. Is there a better solution (i.e which converges faster) ?


**Generalization:** Given two distributions $\pi\_0$ and $\pi\_1$ on the states, prescribe a procedure for sampling a path $x =: s\_0 \rightarrow s\_1 \rightarrow \ldots \rightarrow s\_T = y$, such that


* $x$ is distributed according to $\pi\_0$;
* $y$ is distributed according to $\pi\_1$;
* the length $T$ of the path is minimal.


**N.B.:**


* If $\pi\_0 := \delta\_x$ and $\pi\_1 = \delta\_y$, then this problem reduces to the first part, i.e it demands just the sampling of a random path between $x$ and $y$
* If $\pi\_0 = \pi\_1$, then the computed path should be empty (i.e $T = 0)$.



How to sample a path between 2 states in a Markov chain
As observed by a MO user (Nate Eldredge), the naive solution that I provided alongside the question is essentially optimal as it's linear in the length of the chain.


**Solving the generalization:**
As observed by another user (Ori Gurel-Gurevich), the following simple procedure solves the second part of the question (concerning the generalization):


* Sample an initial state $x \sim \pi\_0$.
* Sample a final state $y \sim \pi\_1$.
* Sample a path $x =:s\_0 \rightarrow s\_1 \rightarrow \ldots \rightarrow s\_T =y$. This is precisely the first part of the problem.


**N.B.:** As another MO user (Mateusz Kwaśnicki) has remarked, the above solution is far from optimal. For example, it doesn't return an empty path in case $\pi\_0 = \pi\_1$.




---


As I wrote in the comments section for this answer, the generalized problem smells like optimal transport. Below, I'll try elaborate what I mean.


**Conjecture:**
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$. Let $\gamma^\* \in \Gamma(\pi\_0,\pi\_1)$ be a solution to the following linear-programming problem


$$\operatorname{minimize}\_{\gamma \in \Gamma(\pi\_0,\pi\_1)}\mathbb E\_{(x,y) \sim \gamma}[\operatorname{CommuteTimeDistance}(x,y)].$$
Then the following procedure solves our "general" sampling problem optimally.


* Sample a couple $(x,y) \sim \gamma^\*$.
* Sample a path $x =:s\_0 \rightarrow s\_1 \rightarrow \ldots \rightarrow s\_T =y$.


The following observations about the above procedure are immediate


* It reduces to the simple case in case $\pi\_0$ and $\pi\_1$ are Dirac masses.
* It avoids the issue raised above, i.e it outputs and empty path when $\pi\_0 = \pi\_1$.


Follow up
=========


The above claim is being addressed in a separate question [here](https://mathoverflow.net/q/279257/78539).


