¿Cambia la distribución de estado estacionario de una cadena de Markov al minimizarla?

Question

Digamos que tengo esta cadena de Markov Entonces realizo una bisimulación sobre ella, donde encuentro la mayor relación entre los estados de la cadena de Markov. Finalmente puedo construir un cociente/minimización de la bisimulación (creo que esto es similar a una minimización DFA) donde la cadena de Markov se ha vuelto significativamente más pequeña. Todo esto es bueno.

Lo que estoy especulando es si la distribución del estado estacionario realmente cambia. Si lo hace, ¿cómo se relaciona con la distribución de estado estacionario original de la cadena de Markov no minimizada?

Parece que no puedo entenderlo. Tienes nuevos estados donde cada uno contiene un grupo de estados. Pero la probabilidad seguiría siendo la misma, sólo tienes menos estados en la matriz de transición de probabilidad. ¿No es así?

Answer 1

En primer lugar, es posible que el tema de la bisimulación no resulte familiar a los demás, por lo que le animo a que proporcione algunas referencias, especialmente cuando hable de procesos estocásticos bisimilares. Creo que estará relacionado con la noción probabilística de lumpability .

Ahora bien, la bisimulación es una relación entre dos sistemas: dos cadenas de Markov pueden ser bisimilares si tienen la misma estructura de etiquetado/salida, pero diferentes espacios de estado -de hecho, nuestra principal esperanza es que podamos encontrar una cadena de Markov bimilar sobre un espacio de estado más pequeño. Por ejemplo, empezamos con una cadena de Markov $C$ con $n$ estados y construir una cadena de Markov bisimilar $\bar C$ con $m<n$ estados. Sus distribuciones invariantes no pueden ser las mismas por la sencilla razón de que una distribución invariante de $C$ satisface $\pi\in \Delta_n$ mientras que $\bar\pi \in \Delta_m$ , donde $$ \Delta_i:=\{p\in\Bbb R^n_+:p\cdot \mathbf 1 = 1\} $$ es el $i$ -de probabilidad simplex. Sin embargo, es una cuestión interesante si $\bar\pi$ puede obtenerse de $\pi$ de forma sencilla.

Bien, dejemos $X$ sea el espacio de estados de $C$ y $\bar X$ sea el espacio de estados de $\bar C$ y que $p$ y $\bar p$ sean las correspondientes matrices estocásticas. Sea $f:X\to \bar X$ denotan el mapa de abstracción, es decir, para todo $x\in X$ y $\bar y\in \bar X$ sostiene que $$ \bar p(\bar y|f(x)) = \sum_{y\in f^{-1}(\bar y)}p(y|x). $$ Dejemos que $\pi$ sea cualquier distribución invariante de $p$ que es para todos $y\in X$ $$ \sum_{x\in X} p(y|x)\pi(x) = \pi(y). $$ Denote $\bar\pi := f_*\pi$ es decir $\bar\pi(\bar y) := \sum_{y\in f^{-1}(\bar y)}\pi(y)$ . Tenemos $$ \begin{align} \sum_{\bar X\in \bar X}\bar p(\bar y|\bar x)\bar\pi(\bar x) &= \sum_{\bar x\in \bar X}\sum_{x\in f^{-1}(\bar x)}\bar p(\bar y|\bar x)\pi(x) = \sum_{x\in X}\bar p(\bar y|f(x))\pi(x) \\ &= \sum_{x\in X}\sum_{y\in f^{-1}(\bar y)}p(y|x)\pi(x) = \sum_{y\in f^{-1}(\bar y)}\sum_{x\in X}p(y|x)\pi(x) \\ &= \sum_{y\in f^{-1}(\bar y)}\pi(y) = \bar\pi(\bar y). \end{align} $$