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 ?



Factorization of a Markov chain as the product of smaller chains
In dynamical systems, there is a concept of "almost-invariance", which generalizes invariance of a set, under the action of dynamics. The analogy is roughly the following:


If you create a markov chain on $S$ from the given dynamics $F$, then if the chain is reducible (into $A$ and $B$), it just implies that sets $A$ and $B$ are invariant under the dynamics. This is detected e.g. if the second largest eigenvalue of the Markov matrix is 1.


If $\lambda\_2<1$, the almost-invariance of a $\textbf{set}$ $C$ can be quantified by defining a scalar 


$\rho(C)=\dfrac{m(F^{-1}(C)\cap C)}{m(C)}$, where $m$ is a lebesgue measure. Now, one can formulate an optimization problem to divide the set S into two sets A and B, such that the result minimizes 


$r=\max (\rho(A),\rho(B))$. This metric might be closest thing to the number you are looking for. 


This problem is NP-hard, however several heuristics give good results. 
See: Froyland, Gary. "Statistically optimal almost-invariant sets." Physica D: Nonlinear Phenomena 200.3 (2005): 205-219.


This problem is also studied in graph theory community under "graph partitioning".


