Continuous Time Markov Chains

Description

Definition

Examples

References

 

 

 

Description:

Markov Chain models can be obtained from SMP  by making the stochastic clock Poisson. This ensures that interevent times are exponentially distributed and this in turn gives rise to the “memoryless” property of Markov chains– the amount of time spent in a current state has no importance.

 

For Continuous-Time MC the “memoryless” property can be expressed as follows:

 

P[X(tk+1)=x k+1| X(t k)=x k, X(t k-1)=x k-1, …, X(t 0)=x o] = P[X(tk+1)=x k+1| X(t k)=x k]

 

Strictly speaking here we are defining homogeneous Markov chains where transition probabilities are independent of time.

Formal Definition:

A Markov Chain model is a 3-tuple

                        (X, q, p0 )

where

X – is a countable  set of states

q(x’, x) – state transition rates, defined for all x, x’ ∈X, reflecting probability of going from state x to state x’, described by transition rate matrix Q .

p0(x) – is the pmf P[X0=x], x∈X, of the initial state X0.

Examples:

References:

  1. K.Kant, Introduction to computer system performance evaluation, McGraw-Hill, 1992.
  2. C. G. Cassandras, S. Lafortune,  Introduction to Discrete Event Systems, Kluwer, 1999.