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.