THE UNIVERSITY OF WESTERN ONTARIO LONDON ONTARIO

Time-homogeneous Markov chains with nite state space in discrete time 1 Theory The following is a distillation of the material in C inlar (1975). Let (Ω;F;P) be a probability space, let X = f1; 2; : : : ; Ng be a nite set and let Xt(!) be a stochastic process in discrete time such that Xt(!) 2 X for all t = 0; 1; 2: : : and all! 2 Ω. Suppose there is an N N matrix P (called the prob-ability transition matrix or PTM of the process) such that for all i; j 2 X and all t = 0; 1; 2; : : : we have P[Xt+1 = ijXt = j] = Pi;j: Then we call the processXt a time-homogeneous Markov chain with nite state space in discrete time. Evidently the matrix P has non-negative entries and its columns sum to 1. We call such a matrix a stochastic matrix. 1 De nition 1 Let P be a stochastic matrix. It is said to be irreducible if for every pair i; j 2 X there is an n 1 such that (P n)i;j> 0. De nition 2 Let P be an N N stochastic matrix and let 1 i N. The set of return times for state i is dened via R(i) = fn 2 N: n> 0 & (P n)i;i> 0g: De nition 3 Let P be an N N stochastic matrix, let 1 i N and let R(i) be the set of return times for state i. Then the period of state i is dened via p(i) = gcdR(i) where gcd stands for \greatest common divisor". De nition 4 An N N stochastic matrix P is called aperiodic if p(i) = 1 for each i = 1; 2; : : : ; N. Proposition 1 Each of the following two statements is equivalent to the statement that P is irreducible and aperiodic. 1. P n is irreducible for each n 1. 2. There is an n such that all entries of P n are strictly positive. Theorem 1 (Perron-Frobenius) Let P be an irreducible stochastic matrix. Then 1 is an eigenvalue for P and the associated eigenspace S is one-dimensional. There exists a 2 S = fx 2 RN: Px = xg such that all entries of are strictly positive. There is a unique 2 S such that ∑Ni=1 i = 1 and its entries are strictly positive. We call this the stationary probability measure associated with P. If P is also aperiodic, then all the other eigenvalues of P satisfy jj < 1