2
$\begingroup$

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.

2 Answers 2

3

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.

2

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$).