2
$\begingroup$

Suppose that $M$ is a time-homogeneous (and, for simplicity, stationary) Markov chain on $d$ states, which induces the probability measure $P$ on paths of length $n$. I seek a Markov chain $M'$ on $d'<d$ states whose induced distribution $P'$ on paths of length $n$ minimizes $\epsilon:=||P-P'||_1$. What is known about the optimal relations between $d,d',n,\epsilon$?

Update: As Bill Bradley notes below, we'll need some conditions on $M$, such as ergodicity, for anything nontrivial to be possible at all.

Update II: As pointed out elsewhere, an earthmover-type distance (such as Wasserstein) probably makes more sense than TV on distributions over different domains.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I'm guessing you might want to add "aperiodic" to your list of assumptions? Suppose $d$ is prime and consider a (periodic) Markov chain that cycles between $d$ states in order (1->2->3...); if you try to model this with $d'<d$ states things will go poorly. $\endgroup$
    – Bill Bradley
    Commented Oct 23 at 11:15
  • $\begingroup$ @BillBradley great point, will amend! $\endgroup$
    – Aryeh Kontorovich
    Commented Oct 23 at 11:19
  • $\begingroup$ it's not clear what is meant by earth-mover distance here, you might get more answers if question was a bit more precise. Other than that things like higher order cheeger inequalities (ie for multicuts) seem relevant $\endgroup$
    – alesia
    Commented Oct 23 at 16:25

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .