Markov chains diagram - what are the numbers above arrows?

783 Views Asked by At

Most if not all articles describe the numbers above arrows as probabilities of a transition in that direction, such as this one, or this one. But here, for example, something really weird is happening.

enter image description here

Certainly $\lambda$ and $\mu$ are not probabilities (as they are greater than $1$). If so, they I'd say it's not a Markov Chain diagram because these numbers are not probabilities. Then what is it? I'm just reading some articles about queueing theory and it looks like that most of the time, for some reason.

Materials that introduce to this topic are very welcome, as well as an intuitive, straightforward explanation of what's going on here.

2

There are 2 best solutions below

1
On

As Robert Israel and Ian suggested, this is a continuous-time Markov chain, and those are rates, not probabilities.

It should be emphasized that "rate" here has a specific technical meaning that is not necessarily equivalent to the usual everyday meaning. For instance, suppose we had a continuous-time Markov chain with two states, $0$ and $1$, a single transition from $0$ to $1$ with rate $\lambda$, and a deterministic initial state of $0$. (That is, the system begins in state $0$ with probability one.)

That rate of $\lambda$ does not mean that the probability of being in state $0$ is $1$ at time $0$, $1-\lambda$ at time $1$, $1-2\lambda$ at time $2$, etc. Rather, it means that the probability of being in state $0$ is governed by the following differential equation:

$$ \frac{d}{dt} P_0(t) = -\lambda P_0(t) $$

That is, in any infinitesimal period of time $dt$, the probability of moving from state $0$ to state $1$ is given by $\lambda P_0(t) dt$. That is what is meant by the state transition rate. It is analogous to the state transition probability in a discrete-time Markov chain, in that it is conditioned on the system being in state $0$ (or wherever the transition starts from) at that particular time; that is (in the discrete case)

$$ P_0(t+1)-P_0(t) = -p_{01} P_0(t) $$

where $p_{01}$ is the state transition probability from $0$ to $1$.

The reason why rates can exceed $1$, while probabilities cannot, stems from what happens when you try to extrapolate from a discrete-time Markov chain to a continuous-time Markov chain. Consider a two-state ($0$ and $1$ again) discrete-time Markov chain in which transitions happen once per second, and a system transitions from state $0$ to state $1$ with probability $1/2$. Then the system takes an average of $2$ seconds to move from state $0$ to state $1$.

Suppose one wanted to convert that into a continuous-time process. One might naively try to approximate a continuous-time Markov chain by successively halving the time interval between transitions, from one second to a half-second to a quarter-second and so on, while maintaining the average time to transition at $2$ seconds. The problem is that if you do so, in the limit, you have a transition from state $0$ to itself with probability $1$, and a transition from state $0$ to state $1$ with probability $0$.

However, we can save the situation by realizing that although the probability of a transition from state $0$ to state $1$ vanishes to $0$ as the time interval vanishes to $0$, those two quantities vanish in direct proportion to one another (if we maintain the average time to transition at $2$ seconds). In fact, we find that if we set the infinitesimal probability of transition $p_{01}$ equal to half the infinitesimal time interval $dt$, we preserve the $2$ second average transition time, and then

$$ P_0(t+dt)-P_0(t) = -\frac{dt}{2} P_0(t) $$

or (with a modicum of abuse of notation)

$$ \frac{d}{dt} P_0(t) = -\frac{1}{2} P_0(t) $$

That is, here, the rate $\lambda = 1/2$. Note that the expected transition time $2$ seconds is equal to $1/\lambda$. This is no coincidence. In general, with constant-rate transitions, the mean time to transition is equal to the reciprocal of the transition rate. That means, among other things, that if the mean transition time is less than one time unit, the transition rate is greater than one per that time unit. For instance, a mean transition rate of $2$ per second corresponds to a mean transition time of $1/2$ second.

I emphasize "per that time unit" because the state transition rate, unlike the state transition probability, is not dimensionless. It has a dimension of inverse time, in line with its interpretation as a transition probability per unit time. If we were to use milliseconds instead of seconds as our time unit, that transition rate of $2$ per second becomes one of $1/500$ per millisecond. And that's equal to a transition rate of $604800$ per fortnight. Those are obviously consistent with one another, despite the disparate numerical values.

0
On

This may be a helpful way of thinking of it. Suppose you have $n$ independent "exponential alarm clocks", i.e. the time until clock #$j$ rings is an exponential random variable with a given rate $r_j > 0$ (and thus expected value $1/r_j$). You wait until the first clock rings, and if it is clock $j$ that rings you go into state #$j$. This will be a continuous-time Markov chain with rates $r_j$ for each transition $i \to j$.

To make this into a fully general (finite) continuous-time Markov chain, allow the rates of the clocks to depend on which state you are in, and also allow these rates to be $0$ (a clock with a rate of $0$ never rings).