DiscreteTimeMarkovChain.ppt

Discrete time Markov Chain G.U. Hwang Next Generation Communication Networks Lab. Department of Mathematical Sciences KAIST Definition The sequence of R.V.s X0, X1, X2, ? with a countable state space S is said to be a discrete time Markov chain (DTMC) if it satisfies the Markov Property: for any ik 2 S, k=0,1,?,n-1 and i, j 2 S. Time homogeneous DTMC : P{Xn+1 = j | Xn = i} is independent of n. Transition Probability Matrices One step transition probability matrix P P = (pij) where pij = P{Xn+1 = j | Xn = i } The matrix P is nonnegative and stochastic, i.e., pij ? 0 and ?j2 S pij = 1 n step transition probability matrix P(n) = (p(n)ij) pij(n) = P{Xn = j | X0 = i} For a DTMC, the initial distribution and the matrix P uniquely determine the future behavior of the DTMC because Example: A general random walk Let Xi be i.i.d. R.V.s with P{X1 = j} = aj, j=0,1,?. Let S0 = 0, Sn = ?k=1n Xk. Then {Sn, n? 1} is a DTMC because Chapman - Kolmogorovs equation Chapman - Kolmogorovs theorem pij(n+m) = ?k2 S pik(n) pkj(m) proof: Using the chapman-Kolmogorov’s theorem we get i.e., the n-th power of the one step transition matrix P is, in fact, the n step transition matrix. Example Find the distribution of X4 where {Xn} (Xn2 S = {1,2}) forms a DTMC with initial distribution P{X0 = 1}=1 and one step transition probability P as follows: sol: Analysis of a DTMC When a communication system can be modeled by a DTMC with P and S = {0,1,2}, what happens? The stationary probabilities The state space S ={0,1, ?} The stationary probability vector (distribution) ? a row vector ? = (?0, ?1, ?) is called a stationary probability vector of a DTMC with transition matrix P if it satisfies Does the stationary distribution always exist? Does the stationary distribution always exist? The key question: When does the stationary vector exist? to answer the question, we need to classify DTMCs according to its probabilistic properties as irreducibility recurrence positive recurren