5
$\begingroup$

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 ?

$\endgroup$
3
  • $\begingroup$ It sounds as though you might be asking whether the original transition matrix can be approximated as a tensor product of two stochastic matrices. I guess whether such an approximation is useful would depend on the kind of question you want to apply it to. $\endgroup$ Mar 13 '17 at 16:26
  • $\begingroup$ 1. What is $\otimes$ here? The Kronecker product? If so, the condition $A,B\subseteq S$ seems weird. Maybe you mean $\oplus$? Please clarify. For instance, if you specified dimensions it would solve a lot of doubts. 2. Do not use the word irreducible -- it already means something else in Markov chains. $\endgroup$ Mar 13 '17 at 19:29
  • $\begingroup$ Sorry for the confusion. I've fixed the post to remove sources of misunderstanding. $\endgroup$
    – dohmatob
    Mar 13 '17 at 19:41
3
$\begingroup$

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

$\endgroup$
0
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks. I'd taught of the Fiedler eigenvalue of the weighted graph associated with my Markov chain, but for some reason, declined it thinking it would be a very loose measure of this "splittability". Maybe not, after all. Thanks for the suggestion. $\endgroup$
    – dohmatob
    Mar 15 '17 at 2:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.