16 1. INTRODUCTION TO FINITE MARKOV CHAINS 1.7. Classifying the States of a Markov Chain* We will occasionally need to study chains which are not irreducible—see, for instance, Sections 2.1, 2.2 and 2.4. In this section we describe a way to classify the states of a Markov chain. This classification clarifies what can occur when irreducibility fails. Let P be the transition matrix of a Markov chain on a finite state space Ω. Given x, y Ω, we say that y is accessible from x and write x y if there exists an r 0 such that P r(x, y) 0. That is, x y if it is possible for the chain to move from x to y in a finite number of steps. Note that if x y and y z, then x z. A state x is called essential if for all y such that x y it is also true that y x. A state x is inessential if it is not essential. We say that x communicates with y and write x y if and only if x y and y x. The equivalence classes under are called communicating classes. For x Ω, the communicating class of x is denoted by [x]. Observe that when P is irreducible, all the states of the chain lie in a single communicating class. Lemma 1.23. If x is an essential state and x y, then y is essential. Proof. If y z, then x z. Therefore, because x is essential, z x, whence z y. It follows directly from the above lemma that the states in a single communi- cating class are either all essential or all inessential. We can therefore classify the communicating classes as either essential or inessential. If [x] = {x} and x is inessential, then once the chain leaves x, it never returns. If [x] = {x} and x is essential, then the chain never leaves x once it first visits x such states are called absorbing. Lemma 1.24. Every finite chain has at least one essential class. Proof. Define inductively a sequence (y0, y1, . . .) as follows: Fix an arbitrary initial state y0. For k 1, given (y0, . . . , yk−1), if yk−1 is essential, stop. Otherwise, find yk such that yk−1 yk but yk yk−1. There can be no repeated states in this sequence, because if j k and yk yj , then yk yk−1, a contradiction. Since the state space is finite and the sequence cannot repeat elements, it must eventually terminate in an essential state. Note that a transition matrix P restricted to an essential class [x] is stochastic. That is, y∈[x] P (x, y) = 1, since P (x, z) = 0 for z [x]. Proposition 1.25. If π is stationary for the finite transition matrix P , then π(y0) = 0 for all inessential states y0. Proof. Let C be an essential communicating class. Then πP (C) = z∈C (πP )(z) = z∈C y∈C π(y)P (y, z) + y∈C π(y)P (y, z)⎦ .
Previous Page Next Page