Discrete-Time Markov Chains

Description Definition Examples References

Description: Markov Chain models can be obtained from SMP by putting restrictions on the stochastic clock that ensure �memoryless� property of Markov chains. Discrete-time Markov chains has a constraint that events occur at discrete time instances only and the �memoryless� property is expressed as follows: P[Xk+1=x k+1| X k=x k, X k-1=x k-1, �, X 0=x o]=P[Xk+1=x k+1| X k=x k] Strictly speaking here we are defining homogeneous Markov chains where transition probabilities are independent of time. Formal Definition: A Discrete-Time Markov Chain model is 3-tuple ����������������������� (X, p, p0 ) where X � is a countable� set of states p(x�, x) � is a state transition probability, defined for all x, x� ∈X, reflecting probability of going from state x to state x�, described by a probability matrix P . p0(x) � is the pmf P[X0=x], x∈X, of the initial state X0. Examples: References: K.Kant, Introduction to computer system performance evaluation, McGraw-Hill, 1992. C. G. Cassandras, S. Lafortune, Introduction to Discrete Event Systems, Kluwer, 1999.