Key Ideas

We limit our discussion to a simple case: the regular Markov chains. These Markov chains visit states in a countable set. When it reaches a state, it stays there for an exponentially distributed random time (called the state holding time) with a mean that depends only on the state. The Markov chain then jumps out of state with transition probabilities that depend only on the current state. Given the current state, the state holding time, the next state, and the evolution of the Markov chain prior to hitting the current state are independent. The Markov chain is regular if jumps do not accumulate, i.e., if it makes only finitely many jumps in finite time. We explain this construction and we give some examples. We then sate some results about the stationary distribution.

Definition

A random process X = {X(t), t Î Â} is a continuous-time Markov chain on the countable set S with generator (or rate matrix) Q = [q(i, j), i, j Î S] if

P[X(t + e) = j | X(t) = i, X(s), s £ t] = 1{i = j} + q(i, j)e + o(e), i, j Î S.

Here, Q is a matrix with nonnegative off-diagonal elements, finite nonpositive diagonal elements, and row sums equal to zero. Such a matrix is called a rate matrix. The formula says (if you can read between the symbols) that given X(t), the future and the past are independent.

One represents the rate matrix by a state transition diagram that shows the states; an arrow from i to j marked with q(i, j) shows the transition rate between these states. No arrow is drawn when the transition rate is zero.

Construction (regular case)

Let Q be a rate matrix. Define the process X = {X(t), t ³ 0} as follow. Start by choosing X(0) according to some distribution in S. When X reaches a state i (and when it starts in that state), it stays there for some exponentially distributed time with mean 1/q(i) where q(i) = - q(i, i). When it leaves state i, the process jumps to state j ¹ i with probability q(i, j)/q(i). The evolution of X then continues as before. A picture illustrates this construction:

This construction defines a process on the positive real line if the jumps do not accumulate, which we assume here. It takes a simple argument to show that this construction corresponds to the definition.

Examples

The example [1] corresponds to a Poisson process with rate l.

The following example [2] corresponds to a Poisson process with rate l.

The following example [3] corresponds to a reflected difference between two Poisson processes. (See Applications.)

Stationary Distribution

The classification results are similar to the discrete time case. An irreducible Markov chain (can reach every state from every other state) is either null recurrent, positive recurrent, or transient (defined as in discrete time). The positive recurrent Markov chains have a unique invariant distribution, the others do not have any. Also, a distribution p is invariant if and only if it solves the balance equations:

pQ = 0.

For instance, [3] is transient if r = l/m > 1; it is null recurrent if r = 1; it is positive recurrent if r < 1 and then its invariant distribution is

p(n) = (1 – r) rⁿ, n = 0, 1, 2, ….

Time-Reversibility

A stationary irreducible Markov chain is time-reversible if and only if p satisfies the detailed balance equations:

p(i)q(i, j) = p(j)q(j, i) for all i, j Î S.

For instance, [3] is time-reversible.

Jean Walrand – January 2000 --- INDEX