Miranda Holmes-Cerfon                                            Applied Stochastic Analysis, Spring 2019
                        Lecture 2: Markov Chains (I)
                        Readings Strongly recommended:
                           • Grimmett and Stirzaker (2001) 6.1, 6.4-6.6
                        Optional:
                           • Hayes (2013) for a lively history and gentle introduction to Markov chains.
                           • Koralov and Sinai (2010) 5.1-5.5, pp.67-78 (more mathematical)
                        Acanonical reference on Markov chains is Norris (1997).
                        WewillbeginbydiscussingMarkovchains. InLectures2&3wewilldiscussdiscrete-timeMarkovchains,
                        and Lecture 4 will cover continuous-time Markov chains.
                        2.1   Setup and definitions
                        Weconsider a discrete-time, discrete space stochastic process which we write as X(t) = X , for t = 0,1,....
                                                                                                                  t
                        ThestatespaceSisdiscrete,i.e. finiteorcountable,sowecanletitbeasetofintegers,asinS={1,2,...,N}
                        or S = {1,2,...}.
                        Definition. The process X(t) = X ,X ,X ,... is a discrete-time Markov chain if it satisfies the Markov
                                                           0   1  2
                        property:
                                            P(X     =s|X =x ,X =x ,...,X =x )=P(X                =s|X =x ).                     (1)
                                                n+1       0    0  1     1      n    n        n+1       n    n
                        Thequantities P(X     =j|X =i)arecalledthetransition probabilities. In general the transition probabili-
                                          n+1       n
                        ties are functions of i, j,n. It is convenient to write them as
                                                               p (n)=P(X        =j|X =i).                                       (2)
                                                                i j         n+1       n
                        Definition. The transition matrix at time n is the matrix P(n) = (pij(n)), i.e. the (i, j)th element of P(n) is
                        pij(n).1 The transition matrix satisfies:
                          (i) pij(n) ≥ 0   ∀i, j  (the entries are non-negative)
                          (ii) ∑ p (n)=1 ∀i        (the rows sum to 1)
                                j i j
                        Anymatrixthatsatisfies(i), (ii) above is called a stochastic matrix. Hence, the transition matrix is a stochas-
                        tic matrix.
                        Exercise 2.1. Show that the transition probabilities satisfy (i), (ii) above.
                        Exercise 2.2. Show that if X(t) is a discrete-time Markov chain, then
                                              P(X =s|X =x ,X =x ,...,X =x )=P(X =s|X =x ),
                                                 n       0    0  1     1      m     m        n      m     m
                        for any 0 ≤ m