Skip to main content
MathOverflow

Return to Question

added 165 characters in body
Source Link
Aryeh Kontorovich
Aryeh Kontorovich
  • 6.5k
  • 32
  • 51

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.

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.

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.

added 142 characters in body
Source Link
Aryeh Kontorovich
Aryeh Kontorovich
  • 6.5k
  • 32
  • 51

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.

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$?

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.

Source Link
Aryeh Kontorovich
Aryeh Kontorovich
  • 6.5k
  • 32
  • 51

dimensionality reduction of Markov chains

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$?