Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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.

share|improve this question

migrated from math.stackexchange.com Feb 20 '13 at 15:20

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

1  
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
show 1 more comment

1 Answer 1

You might want to look in to sparse matrix representations for the transition matrix. These are methods of storing a matrix with lots of zero elements in way that take less space.

share|improve this answer
    
I have initially imprecisely stated the problem -- it is about finding patterns in a Markov chain given by a transition matrix, and not about storing the matrix in a compact form (although the latter might be a positive side effect). –  arataj Feb 18 '13 at 15:28
    
Ok. I do not have any very good idea. Obviously your "typical" transition matrix will not have any meaningful pattern and its description in the form of rules will be as complex as looking at the transition matrix. On the other hand the matrices appearing in your applications might be untypical. But exactly what patterns they might have would depend crucially on where they come from I guess. Looking at the transition diagram of the Markov chain might be somewhat better than staring at the transition matrix however. –  Johan Feb 19 '13 at 12:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.