Skip to main content
1 of 4
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

Factorization of Markov chain as product of smaller chains

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 ?

dohmatob
  • 6.9k
  • 1
  • 18
  • 76