1
$\begingroup$

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)$.
Improve this question
$\endgroup$
13
  • 3
    $\begingroup$ From a big O point of view, the naive approach is already linear in the length of the output. So it is just as quick as simply writing down the output, and you can't expect to improve on that (unless you want the output in some sort of compressed format). $\endgroup$
    – Nate Eldredge
    Commented Aug 15, 2017 at 21:25
  • $\begingroup$ I'm not sure what exactly your generalization is asking: what is the "transformation" you want? If $\pi_1$ should be the distribution after $n$ steps, then you are asking about efficient ways to compute $\pi_0 P^n$ where $P$ is the transition matrix. One typical approach is to try to diagonalize $P$. $\endgroup$
    – Nate Eldredge
    Commented Aug 15, 2017 at 21:27
  • $\begingroup$ @NateEldredge Thanks for your useful comments. Concerning second question (the generalization), and your comment thereupon, it's not even clear to me why there should exist an natural number $n$ such that $\pi_1 = \pi_0 P^n$, unless $\pi_0$ and $\pi_1$ are pure (i.e all their mass is concentrated on a single state, say $x$ and $y$ respectively), in which case we're back to the first part of the question. $\endgroup$
    – dohmatob
    Commented Aug 16, 2017 at 8:31
  • 1
    $\begingroup$ Reading again, is the question something like this: "Given two distributions $\pi_0, \pi_1$, find a stopping time $T$ such that when the chain is started in distribution $\pi_0$, the distribution of $X_T$ is $\pi_1$; then find a method to sample $(X_0, X_1, \dots, X_T)$?" Where $T$ should be "not too large" and it should be reasonably efficient to determine when the stopping time is reached. $\endgroup$
    – Nate Eldredge
    Commented Aug 16, 2017 at 15:14
  • 2
    $\begingroup$ @dohmatob, you can get this easily. Simply choose a state $y$ independently from the distribution $\pi_1$ and stop the chain when it first hits $y$. $\endgroup$
    – Ori Gurel-Gurevich
    Commented Aug 17, 2017 at 10:15

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ The problem is not stated rigorously enough, but shouldn't an "optimal" solution produce an empty path if $\pi_0 = \pi_1$? $\endgroup$
    – Mateusz Kwaśnicki
    Commented Aug 17, 2017 at 12:29
  • $\begingroup$ Oops!, you're absolutely right. Thanks! It seems the sub-optimality stems from the fact that the sampling of $x$ and $y$ is done independently of one-another. I'll probably need to sample $(x,y) \sim \gamma$ were $\gamma$ is chosen to have minimal cost (will have to define an appropriate cost function $(s', s) \mapsto c(s,s')$) such that its 1st and 2nd marginals equal $\pi_0$ and $\pi_1$ respectively. Maybe I can take this cost $c(s,s')$ to be the "time" between states $s$ and $s'$. I'll try to think look into this offline. Things are beginning to look like optimal transport in disguise. $\endgroup$
    – dohmatob
    Commented Aug 17, 2017 at 13:26
  • $\begingroup$ @MateuszKwaśnicki I've re-stated the question more rigorously. $\endgroup$
    – dohmatob
    Commented Aug 17, 2017 at 13:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .