Factorization of a Markov chain as the product of smaller chains

Question

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 ?

Answer 1

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".

Answer 2

What you need is a definition of graph connectivity for undirected graphs. One can try to generalize the idea of Fiedler vector from directed graphs: if the second-to-last singular value of $I-P$ is zero, then the matrix is "splittable", otherwise it is not. For instance, you can use the ratio $\sigma_{n-1}/\sigma_1$ as a measure of connectivity.

If you have already a candidate approximate splitting into two blocks $\begin{bmatrix}P_{11} & P_{12} \\ P_{21} & P_{22}\end{bmatrix}$, another simple performance measure is $\frac{\|P_{12}\|+\|P_{21}\|}{\|P_{11}\|+\|P_{12}\|+\|P_{21}\|+\|P_{22}\|}$, which also makes sense as "distance from the closest splittable matrix".