How to sample a path between 2 states in a Markov chain 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)$.

 A: 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.
