Consider a discrete-time Markov chain on $n$ states $S = \{1,2,\ldots,n\}$, with transition dynamics

$$ \mathbf{x}^{(t+1)} = \mathbf{P} \mathbf{x}^{(t)},$$

where $\mathbf{P}$ is the transition matrix, a stochastic matrix (nonnegative entries and unit column sums). We are interested in the possibility of decomposing this chain into a product of 2 chains on two disjoint subject sets of states $A,B \subseteq S$ (of approx same size), so that $\mathbf{P} = \mathbf{P}_A \otimes \mathbf{P}_B$, i.e

$$\mathbf{x}_A^{(t+1)} = \mathbf{P}_A \mathbf{x}_A^{(t)},\text{ and }\mathbf{x}_B^{(t+1)} = \mathbf{P}_B \mathbf{x}_B^{(t)}, $$

where $\mathbf{P}_A$ and $\mathbf{P}_B$ are stochastic matrices on $\#A$ and $\#B$ states resp. When we can produce such a factorization, we shall say that the original chain is reducible (index $r = 1$), otherwise it is irreducible (index $r = 0$).

Question: I wish to extend / relax this reducibility index $r$ to a general scenario and get a float $r(\mathbf{P}) \in [0, 1]$ which measures how well $\mathbf{P}$ can be approximated by a product of $\mathbf{P}_A \otimes \mathbf{P}_B$ of smaller chains. Is there anything in literature (maybe linear algebra ?) that can shed light on this ?

Consider a discrete-time Markov chain on $n$ states $S = \{1,2,\ldots,n\}$, with transition dynamics

$$ \mathbf{x}^{(t+1)} = \mathbf{P} \mathbf{x}^{(t)},$$

where $\mathbf{P}$ is the transition matrix, a stochastic matrix (nonnegative entries and unit column sums). We are interested in the possibility of decomposing this chain into a product of 2 chains on two disjoint subject sets of states $A,B \subseteq S$ (of approx same size), with dynamics $\mathbf{P}_A$ and $\mathbf{P}_B$ resp. so that

$$\mathbf{x}_A^{(t+1)} = \mathbf{P}_A \mathbf{x}_A^{(t)},\text{ and }\mathbf{x}_B^{(t+1)} = \mathbf{P}_B \mathbf{x}_B^{(t)}, $$

where $\mathbf{P}_A$ and $\mathbf{P}_B$ are stochastic matrices on $\#A$ and $\#B$ states resp. When we can produce such a factorization, we shall say that the original chain is splittable (index $r = 1$), otherwise it is irreducible (index $r = 0$).

Question: I wish to extend / relax this split index $r$ to a general scenario and get a float $r(\mathbf{P}) \in [0, 1]$ which measures how well / bad the original chain can be approximated can be factored into smaller chains. Is there anything in literature (maybe linear algebra ?, graph theory ?) that can shed light on this ?

Consder a discrete-time Markov chain on $n$ states $S = \{1,2,\ldots,n\}$, with transition dynamics

$$ \mathbf{x}^{(t+1)} = \mathbf{P} \mathbf{x}^{(t)},$$

where $\mathbf{P}$ is the transition matrix, a stochastic matrix (nonnegative entries and unit column sums). We are interested in the possibility of decomposing this chain into a product of 2 chains on two disjoint subject sets of states $A,B \subseteq S$ (of approx same size), so that $\mathbf{P} = \mathbf{P}_A \otimes \mathbf{P}_B$, i.e

$$\mathbf{x}_A^{(t+1)} = \mathbf{P}_A \mathbf{x}_A^{(t)},\text{ and }\mathbf{x}_B^{(t+1)} = \mathbf{P}_B \mathbf{x}_B^{(t)}, $$

where $\mathbf{P}_A$ and $\mathbf{P}_B$ are stochastic matrices on $\#A$ and $\#B$ states resp. When we can produce such a factorization, we shall say that the original chain is reducible (index $r = 1$), otherwise it is irreducible (index $r = 0$).

Question: I wish to extend / relax this reducibility index $r$ to a general scenario and get a float $r(\mathbf{P}) \in [0, 1]$ which measures how well $\mathbf{P}$ can be approximated by a product of $\mathbf{P}_A \otimes \mathbf{P}_B$ of smaller chains. Is there anything in literature (maybe linear algebra ?) that can shed light on this ?

Consider a discrete-time Markov chain on $n$ states $S = \{1,2,\ldots,n\}$, with transition dynamics

$$ \mathbf{x}^{(t+1)} = \mathbf{P} \mathbf{x}^{(t)},$$

where $\mathbf{P}$ is the transition matrix, a stochastic matrix (nonnegative entries and unit column sums). We are interested in the possibility of decomposing this chain into a product of 2 chains on two disjoint subject sets of states $A,B \subseteq S$ (of approx same size), so that $\mathbf{P} = \mathbf{P}_A \otimes \mathbf{P}_B$, i.e

$$\mathbf{x}_A^{(t+1)} = \mathbf{P}_A \mathbf{x}_A^{(t)},\text{ and }\mathbf{x}_B^{(t+1)} = \mathbf{P}_B \mathbf{x}_B^{(t)}, $$

where $\mathbf{P}_A$ and $\mathbf{P}_B$ are stochastic matrices on $\#A$ and $\#B$ states resp. When we can produce such a factorization, we shall say that the original chain is reducible (index $r = 1$), otherwise it is irreducible (index $r = 0$).

Question: I wish to extend / relax this reducibility index $r$ to a general scenario and get a float $r(\mathbf{P}) \in [0, 1]$ which measures how well $\mathbf{P}$ can be approximated by a product of $\mathbf{P}_A \otimes \mathbf{P}_B$ of smaller chains. Is there anything in literature (maybe linear algebra ?) that can shed light on this ?