I am wondering the validity and the procedure to condense/group several states into one in markov chain, namely, if it is possible, how to transform the state vector and the transition matrix? Many thanks.
What's the procedure to condense several states into one in Markov chain?
2 Answers
To generalize slightly the result mentioned by mjqxxxx, assume that one groups the original states $S_i$ into classes $C_a$. Hence the collection of classes $(C_a)$ is a partition of the state space and each class can be reduced to one state, or not. Then a sufficient condition for the resulting process to still be Markov is that the function $\varphi$ defined, for every state $S$ and class $C$, by the formula $ \varphi(S,C)=\sum_{T\in C}P(S\to T) $ depends on the state $S$ through its class only. In other words, one asks that, for every classes $C$ and $D$ and every states $S$ and S' in $C$, \varphi(S,D)=\varphi(S',D). Note that the condition is always true if every class is reduced to one state, and that it is also true if there is only one class.
Caveat: if this condition is not met, it can nevertheless happen that the resulting process is Markov for some, but not all, initial conditions.
If all the transition probabilities out of a set of states ${\cal S} = \{S_1, S_2, ... S_n\}$ are equal (that is, $P(S_i\rightarrow T)=P(S_j\rightarrow T)$ for all $i$ and $j$ and for all states $T \notin {\cal S}$), then those states may be consolidated into a single new state $S^{\prime}$ without affecting the dynamics. The state vector will no longer record the individual probabilities of the states in ${\cal S}$, but at any time $P(S^{\prime})$ will be equal to $\sum_i P(S_i)$ in the original model. The transition probabilities into the new state should be $P(T \rightarrow S^{\prime}) = \sum_i P(T \rightarrow S_i)$ for $T \notin {\cal S}$; the transition probabilities out of the new state should be $P(S^{\prime} \rightarrow T) = P(S_i \rightarrow T)$ for $T \notin {\cal S}$ (this is independent of the choice of $S_i$); and the probability for remaining in the new state should be $P(S^{\prime} \rightarrow S^{\prime}) = \sum_j P(S_i \rightarrow S_j)$ (again independent of the choice of $S_i$).