9
$\begingroup$

I'm currently reading some papers about Markov chain lumping and I'm failing to see the difference between a Markov chain and a plain directed weighted graph.

For example in the article Optimal state-space lumping in Markov chains they provide the following definition of a CTMC (continuous time Markov chain):

We consider a finite CTMC $(\mathcal{S}, Q)$ with state space $\mathcal{S} = \{x_1, x_2, \ldots, x_n\}$ by a transition rate matrix $Q: \mathcal{S} \times \mathcal{S} \to \mathbb{R}^+$.

They don't mention the Markov property at all, and, in fact, if the weight on the edges represents a probability I believe the Markov property trivially holds since the probability depends only on the current state of the chain and not the path that lead to it.

In an other article On Relational Properties of Lumpability Markov chains are defined similarly:

A Markov chain $M$ will be represented as a triplet $(S, P, \pi)$ where $S$ is the finite set of states of $M$, $P$ the transition probability matrix indicating the probability of getting from one state to another, and $\pi$ is the initial probability distribution representing the likelyhood for the system to start in a certain state.

Again, no mention of past or future or independence.

There's a third paper Simple O(m logn) Time Markov Chain Lumping where they not only never state that the weights on the edges are probabilities, but they even say:

In many applications, the values $W(s, s')$ are non-negative. We do not make this assumption, however, because there are also applications where $W(s, s)$ is deliberately chosen as $-W(s, S \setminus \{s\})$, making it usually negative.

Moreover, it's stated that lumping should be a way to reduce the number of states while maintaining the Markov property (by aggregating "equivalent" state into a bigger state). Yet, to me, it looks like it's simply summing probabilities and it shouldn't even guarantee that the resulting peobabilities of the transitions to/from the aggregated states are in the range $[0,1]$. What does the lumping actually preserve then?

So, there are two possibilities that I see:

  • I didn't understand what a Markov chain is, or
  • The use of the term Markov chain in those papers is bogus

Could someone clarify the situation?

It really looks like there are different communities using that term and they mean widely different things. From these 3 articles that I'm considering it looks like the Markov property is either trivial or useless, while looking at a different kind of papers it looks fundamental.

$\endgroup$
  • $\begingroup$ There are tons of textbooks and resources on the Internet that explain (a) what a Markov chain is and (b) what the precise mathematical definition is. We expect you to do a significant amount of research and self-study before asking. So, have you consulted any of those resources? What did you find there? P.S. I would guess that papers in the literature would assume you know the definition of a Markov chain, and those sentences wouldn't necessarily be intended as a precise formal definition of a Markov chain, but rather merely to establish the notation they use when talking about one. $\endgroup$ – D.W. Mar 24 '15 at 9:23
  • $\begingroup$ Past or future or independence are properties that follow, iirc. There should be some restrictions on the weight, though; maybe some things can stay implicit, e.g. assigning missing outgoing weight to an edge that leads to a sink state (cf. different DFA definitions). $\endgroup$ – Raphael Mar 24 '15 at 9:51
  • 4
    $\begingroup$ @D.W. Yes I did. What I found is that the notion of Markov chain in textbook seem to have nothing to do with it's concept as used in such papers. This is exactly why I'm asking this. $\endgroup$ – Bakuriu Mar 24 '15 at 10:19
  • 4
    $\begingroup$ Again, there's a third possibility. I think the mistake you are making is to interpret the statement in those papers as a definition of a Markov chain. I'd guess that is probably not the intent of those statements. I'd guess the authors assume you are already familiar with the definition of a Markov chain, and are just trying to establish some notation (there are multiple kinds of notation you can use for the same concept). So, take another look from that viewpoint and see if you find anything that contradicts it in the papers (if you find any, add it to the question). $\endgroup$ – D.W. Mar 24 '15 at 11:30
  • 4
    $\begingroup$ @D.W. It seems like the OP did decent research and structured his question acceptably. Yes we can use google to learn. But have you noticed how highly ranked SE sites are in google? Its because we condense information into (usually) single, well defined questions. The collaborative efforts of our community create very rich and valuable content that is, many times, more useful than the pages and pages of info out there resulting in more efficient learning. $\endgroup$ – BAR Mar 24 '15 at 15:46
10
$\begingroup$

A Continuous-time Markov Chain can be represented as a directed graph with constant non-negative edge weights. An equivalent representation of the constant edge-weights of a directed graph with $N$ nodes is as an $N \times N$ matrix. The Markov property (that the future states depend only on the current state) is implicit in the constant edge weights (or constant entries in the matrix). Implicit means implied by. Mathematicians use it as a euphemism meaning, "you should prove it yourself."

But the first paper defines a notation consistent with a Continuous-time Markov Chain, sometimes called a Markov Process, while the second paper defines a notation consistent with a Discrete-time Markov Chain. They say

$P$ is the transition probability matrix indicating the probability of getting from one state to another, and $\pi$ is the initial probability distribution representing the likelihood for the system to start in a certain state. [emphasis added]

They are assuming that the matrix is constant over time (thus implying the Markov property). Implicit in the term probability is the fact that each constant is in range $[0,1]$, that the entries in every column of $P$ sum to $1$, and that the sum of the entries in $\pi$ sum to $1$.

I can't read the third paper, it is paywalled. If the entries in every column of the matrix are required to sum to 1 then they are probabilities and they are talking about Discrete-time Markov Chains. If the entries in every column can sum to an arbitrary number then the entries represent rates not probabilities and they are talking about Continuous-time Markov Chains.

Continuous-time Markov Chains are not the same as Discrete-time Markov Chains. In a Continuous-time Markov Chain the edge weights do not represent probabilities, but rather transition rates. The edge weights must be non-negative, but can be arbitrarily large, and the weights of the out-edges can sum to any non-negative number. The sum is not required to be $1$.

With both Continous-time and Discrete-time Markov Chains the Markov property is implied by the constant edge weights (or equivalently the constant entries in the transition matrix.)

$\endgroup$
8
$\begingroup$

Markov Chains come in two flavors: continuous time and discrete time.

Both continuous time markov chains (CTMC) and discrete time markov chains (DTMC) are represented as directed weighted graphs.

For DTMC's the transitions always take one unit of "time." As a result, there is no choice for what your weight on an arc should be-- you put the probability of going to "j" given that you're at "i."

For CTMC's, the transition time between any two states is necessarily given by an exponential random variable. This is the key difference between CTMC's and DTMC's: DTMC's always have unit transition time. CTMC's have random transition time.

For a CTMC, the convention is generally to put weights on an arc according to the rate of the exponential random variable going from the source to the destination. That is- the convention is to put rates on the arcs, not probabilities.

Negative Rates

Although all the CTMC's that I recall were represented with positive rates on the edges, negative rates do come up in CTMC analysis.

Say we're standing at state A, which is connected to B, C, and D as below.

A --> B (the rate into A from B is negative) A --> C (the rate into A from C is negative) D --> A (the rate into A from D is positive)

This is likely not quite what your paper is referring to; I bring it up to show that negative weights aren't necessarily ridiculous if someone was working with a suitable convention.

Markov Property

For DTMC's- you're right. The markov property is satisfied trivially. For CTMC's, the markov property is satisfied because the transitions are given by exponential random variables (which are "memoryless"). If the transitions were not given by exponential random variables (say instead they were uniform), then we would be talking about "Semi-Markov Chains" or "Semi-Markov Processes."

$\endgroup$
  • $\begingroup$ Thanks for the clarification about the exponential being memoryless. It makes sense. I double checked the third article and they do explicitly say that they do not assume the weights to be non-negative, because there's a peculiar definition of $W(s, s)$ (the rate of a state into itself) which is usually defined to be $-W(s, S \setminus \{s\})$ (i.e. minus the sum of rates of $s$ to all other states) which makes it, almost always, negative. $\endgroup$ – Bakuriu Mar 24 '15 at 16:30
  • $\begingroup$ The last paper is quite mysterious to me because they don't use Markov chain terminology through most of the paper. It's possible that they solve a more general problem even though the motivation is Markov chains. That said, $W(s,s) = -W(s, S\setminus \{s\})$ is consistent with working with the Laplace operator (or rather its negation..for some reason). $\endgroup$ – Sasho Nikolov Mar 25 '15 at 1:43

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.