Report

CSE 531: Performance Analysis of Systems Lecture 4: DTMC Anshul Gandhi 1307, CS building [email protected] [email protected] 1 Definitions Stochastic Process: A Stochastic Process in discrete time, t ∈ N = {1, 2, …}, is a sequence of RVs, {X0, X1, …}, denoted by X = {Xn, n ≥ 1}. Here, Xn is state of the process at time n. Markov chain: A Stochastic Process, X = {Xn, n ≥ 1}, is called a Markov chain if, ∀states {j, i, i0, i1, …}, Pr[Xn+1 = j | Xn = i, Xn-1 = in-1, Xn-2 = in-2, …, X0 = i0] = Pr[Xn+1 = j | Xn = i] (Markovian property) = Pij (Stationary) Markovian property: The conditional distribution of future state (Xn+1) given past states ({X0, X1, …, Xn-1}), and present state (Xn), is independent of past states and depends only on present state.