# Transition matrix to a compact set of rules

I would like to ask you about methods of converting a discrete time Markov chain, represented by a fully known transition matrix, into a relatively small set of transition rules.

For example, let there be a transition matrix:

$$\left(\begin{array}{cccc} 1-m & m & 0 & 0 \\ u & 1-u-m & m & 0 \\ 0 & u & 1-u-m & m \\ 0 & 0 & u & 1-u \\ \end{array}\right)$$

where a coordinate (either a row or column one) represents tha value of a state vector, containing only a single element, e. g. a queue size $q$, which can be $0 \ldots 3$. A row number expresses the current state, and a column number expresses the next state. So, e.g. for $q=3$, there is a probability $u$, that the next state will be $q=2$, and a probability $1-u$ of staying in the same state.

The method I ask about, on basis of that matrix, would be able to find out these two transition rules:

$$\begin{array}{c} q > 0 \rightarrow \mathrm{prob}(u): \,\, q' = q - 1 \\ q < 3 \rightarrow \mathrm{prob}(m): \,\, q' = q + 1 \\ \end{array}$$

to describe that matrix.

This could ease to see the patterns in a Markov chain given by, often directly hardly readable, transition matrix.

## migrated from math.stackexchange.comFeb 20 '13 at 15:20

This question came from our site for people studying math at any level and professionals in related fields.

• How do you define a transition matrix? It seems that when you are in state 3 there is a probability of transiting to no state at all. – Johan Feb 18 '13 at 13:35
• I don't understand your notation for the rules you list (the display starting with $q > 0$). – Nate Eldredge Feb 18 '13 at 13:43
• @Johan, the transition matrix is now described in more detail. – arataj Feb 18 '13 at 15:20
• @NateEldredge, the first rule says: for all states where $q > 0$, there is a probability $u$ that the next state (that is, the one after the next time step) will have $q$ decreased by 1, and also a probability $1-u$, that the vector state won't change. – arataj Feb 18 '13 at 15:24
• @NateEldredge, I can't already edit the above comment, but it is wrong about staying in the same state -- the probability, that the vector state won't change, is 1-(probabilities given in all relevant rules), so e.g. for $q > 0 \land q < 3$, the system would stay in the same state with a probability $1 - u - m$. – arataj Feb 18 '13 at 15:33