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

8more comments