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)⎦ ⎤ .

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2009 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.