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.