Chapter 3 FINITE-STATE MARKOV CHAINS 3.1 Introduction The counting processes {N (t); t > 0} described in Section 2.1.1 have the property that N (t) changes at discrete instants of time, but is deﬁned for all real t > 0. The Markov chains to be discussed in this chapter are stochastic processes deﬁned only at integer values of time, n = 0, 1, . . . . At each integer time n ≥ 0, there is an integer-valued random variable (rv) Xn , called the state at time n, and the process is the family of rv’s {Xn ; n ≥ 0}. We refer to these processes as integer-time processes. An integer-time process {Xn ; n ≥ 0} can also be viewed as a process {X(t); t ≥ 0} deﬁned for all real t by taking X(t) = Xn for n ≤ t < n + 1, but since changes occur only at integer times, it is usually simpler to view the process only at those integer times. In general, for Markov chains, the set of possible values for each rv Xn is a countable set S. If S is countably inﬁnite, it is usually taken to be S = {0, 1, 2, . . . }, whereas if S is ﬁnite, it is usually taken to be S = {1, . . . , M}. In this chapter (except for Theorems 3.2.2 and 3.2.3), we restrict attention to the case in which S is ﬁnite, i.e., processes whose sample functions are sequences of integers, each between 1 and M. There is no special signiﬁcance to using integer labels for states, and no compelling reason to include 0 for the countably inﬁnite case and not for the ﬁnite case. For the countably inﬁnite case, the most common applications come from queueing theory, where the state often represents the number of waiting customers, which might be zero. For the ﬁnite case, we often use vectors and matrices, where positive integer labels simplify the notation. In some examples, it will be more convenient to use more illustrative labels for states. Deﬁnition 3.1.1. A Markov chain is an integer-time process, {Xn , n ≥ 0} for which the sample values for each rv Xn , n ≥ 1, lie in a countable set S and depend on the past only through the most recent rv Xn−1 . More speciﬁcally, for all positive integers n, and for all i, j, k, . . . , m in S, Pr{Xn =j | Xn−1 =i, Xn−2 =k, . . . , X0 =m} = Pr{Xn =j | Xn−1 =i} . (3.1) CHAPTER 3. FINITE-STATE MARKOV CHAINS Furthermore, Pr{Xn =j | Xn−1 =i} depends only on i and j (not n) and is denoted by Pr{Xn =j | Xn−1 =i} = Pij . (3.2) The initial state X0 has an arbitrary probability distribution. A ﬁnite-state Markov chain is a Markov chain in which S is ﬁnite. Equations such as (3.1) are often easier to read if they are abbreviated as Pr{Xn | Xn−1 , Xn−2 , . . . , X0 } = Pr{Xn | Xn−1 } . This abbreviation means that equality holds for all sample values of each of the rv’s. i.e., it means the same thing as (3.1). The rv Xn is called the state of the chain at time n. The possible values for the state at time n, namely {1, . . . , M} or {0, 1, . . . } are also generally called states, usually without too much confusion. Thus Pij is the probability of going to state j given that the previous state is i; the new state, given the previous state, is independent of all earlier states. The use of the word state here conforms to the usual idea of the state of a system — the state at a given time summarizes everything about the past that is relevant to the future. Deﬁnition 3.1.1 is used by some people as the deﬁnition of a homogeneous Markov chain. For them, Markov chains include more general cases where the transition probabilities can vary with n. Thus they replace (3.1) and (3.2) by Pr{Xn =j | Xn−1 =i, Xn−2 =k, . . . , X0 =m} = Pr{Xn =j | Xn−1 =i} = Pij (n). (3.3) We will call a process that obeys (3.3), with a dependence on n, a non-homogeneous Markov chain. We will discuss only the homogeneous case, with no dependence on n, and thus restrict the deﬁnition to that case. Not much of general interest can be said about non homogeneous chains.1 An initial probability distribution for X0 , combined with the transition probabilities {Pij } (or {Pij (n)} for the non-homogeneous case), deﬁne the probabilities for all events in the Markov chain. Markov chains can be used to model an enormous variety of physical phenomena and can be used to approximate many other kinds of stochastic processes such as the following example: Example 3.1.1. Consider an integer process {Zn ; n ≥ 0} where the Zn are ﬁnite integervalued rv’s as in a Markov chain, but each Zn depends probabilistically on the previous k rv’s, Zn−1 , Zn−2 , . . . , Zn−k . In other words, using abbreviated notation, Pr{Zn | Zn−1 , Zn−2 , . . . , Z0 } = Pr{Zn | Zn−1 , . . . Zn−k } . (3.4) 1 On the other hand, we frequently ﬁnd situations where a small set of rv’s, say W, X, Y, Z satisfy the Markov condition that Pr{Z | Y, X, W } = Pr{Z | Y } and Pr{Y | X, W } = Pr{Y | X} but where the condi tional distributions Pr{Z | Y } and Pr{Y | X} are unrelated. In other words, Markov chains imply homoge niety here, whereas the Markov condition does not. 3.2. CLASSIFICATION OF STATES We now show how to view the condition on the right side of (3.4), i.e., (Zn−1 , Zn−2 , . . . , Zn−k ) as the state of the process at time n − 1. We can rewrite (3.4) as Pr{Zn , Zn−1 , . . . , Zn−k+1 | Zn−1 , . . . , Z0 } = Pr{Zn , . . . , Zn−k+1 | Zn−1 , . . . Zn−k } , since, for each side of the equation, any given set of values for Zn−1 , . . . , Zn−k+1 on the right side of the conditioning sign speciﬁes those values on the left side. Thus if we deﬁne Xn−1 = (Zn−1 , . . . , Zn−k ) for each n, this simpliﬁes to Pr{Xn | Xn−1 , . . . , Xk−1 } = Pr{Xn | Xn−1 } . We see that by expanding the state space to include k-tuples of the rv’s Zn , we have converted the k dependence over time to a unit dependence over time, i.e., a Markov process is deﬁned using the expanded state space. Note that in this new Markov chain, the initial state is Xk−1 = (Zk−1 , . . . , Z0 ), so one might want to shift the time axis to start with X0 . Markov chains are often described by a directed graph (see Figure 3.1 a). In this graphical representation, there is one node for each state and a directed arc for each non-zero transition probability. IfPij = 0, then the arc from node i to node j is omitted, so the diﬀerence between zero and non-zero transition probabilities stands out clearly in the graph. The classiﬁcation of states, as discussed in Section 3.2, is determined by the set of transitions with non-zero probabilities, and thus the graphical representation is ideal for that topic. A ﬁnite-state Markov chain is also often described by a matrix [P ] (see Figure 3.1 b). If the chain has M states, then [P ] is an M by M matrix with elements Pij . The matrix representation is ideally suited for studying algebraic and computational issues. ❦   ✟ ✯2 ② ✟ ✟ ✟ ✟ ☛ ✟✟ P12 ✘ ✿ 1❦ ✡ ✘ ❍  ❍❍ P44 P11 ❍❍ P41 ❍❍ ✎ 4❦ P23 P32 P45 a) Graphical P63  ③ ❦  3✛ 6❦ ✡ ✡ P65 ✡ ✡ ✡ P55 ✟ ✢✘ ✡ ✘ ✲ 5❦  ②  ✠    [P ] =   P11 P12 P21 P22 .. .. . . P61 P62 · · · P16 · · · P26 .. .. .. .. ... . · · · P66      b) Matrix Figure 3.1: Graphical and Matrix Representation of a 6 state Markov Chain; a directed arc from i to j is included in the graph if and only if (iﬀ) Pij > 0. 3.2 Classiﬁcation of states This section, except where indicated otherwise, applies to Markov chains with both ﬁnite and countable state spaces. We start with several deﬁnitions. CHAPTER 3. FINITE-STATE MARKOV CHAINS Deﬁnition 3.2.1. An (n-step) walk is an ordered string of nodes, (i0 , i1 , . . . in ), n ≥ 1, in which there is a directed arc from im−1 to im for each m, 1 ≤ m ≤ n. A path is a walk in which no nodes are repeated. A cycle is a walk in which the ﬁrst and last nodes are the same and no other node is repeated. Note that a walk can start and end on the same node, whereas a path cannot. Also the number of steps in a walk can be arbitrarily large, whereas a path can have at most M − 1 steps and a cycle at most M steps for a ﬁnite-state Markov chain with |S| = M. Deﬁnition 3.2.2. A state j is accessible from i (abbreviated as i → j) if there is a walk in the graph from i to j. For example, in Figure 3.1(a), there is a walk from node 1 to node 3 (passing through node 2), so state 3 is accessible from 1. There is no walk from node 5 to 3, so state 3 is not accessible from 5. State 2 is accessible from itself, but state 6 is not accessible from itself. To see the probabilistic meaning of accessibility, suppose that a walk i0 , i1 , . . . in exists from node i0 to in . Then, conditional on X0 = i0 , there is a positive probability, Pi0 i1 , that X1 = i1 , and consequently (since Pi1 i2 > 0), there is a positive probability that X2 = i2 . Continuing this argument, there is a positive probability that Xn = in , so that Pr{Xn =in | X0 =i0 } > 0. Similarly, if Pr{Xn =in | X0 =i0 } > 0, then an n-step walk from i0 to in must exist. Summarizing, i → j if and only if (iﬀ) Pr{Xn =j | X0 =i} > 0 for some n ≥ 1. We denote Pr{Xn =j | X0 =i} by Pijn . Thus, for n ≥ 1, Pijn > 0 if and only if the graph has an n step walk from i to j (perhaps visiting the same node more than once). For 2 =P P n the example in Figure 3.1(a), P13 12 23 > 0. On the other hand, P53 = 0 for all n ≥ 1. An important relation that we use often in what follows is that if there is an n-step walk from state i to j and an m-step walk from state j to k, then there is a walk of m + n steps from i to k. Thus Pijn > 0 and Pm jk > 0 imply Pn+m > 0. ik (3.5) This also shows that i → j and j → k imply i → k. (3.6) Deﬁnition 3.2.3. Two distinct states i and j communicate (abbreviated i ↔ j) if i is accessible from j and j is accessible from i. An important fact about communicating states is that if i ↔ j and m ↔ j then i ↔ m. To see this, note that i ↔ j and m ↔ j imply that i → j and j → m, so that i → m. Similarly, m → i, so i ↔ m. Deﬁnition 3.2.4. A class C of states is a non-empty set of states such that each i ∈ C communicates with every other state j ∈ C and communicates with no j ∈ / C. For the example of Figure 3.1(a), {2, 3} is one class of states, {1}, {4}, {5}, and {6} are the other classes. Note that state 6 does not communicate with any other state, and is not even accessible from itself, but the set consisting of {6} alone is still a class. The entire set of states in a given Markov chain is partitioned into one or more disjoint classes in this way. 3.2. CLASSIFICATION OF STATES Deﬁnition 3.2.5. For ﬁnite-state Markov chains, a recurrent state is a state i that is accessible from all states that are accessible from i (i is recurrent if i → j implies that j → i). A transient state is a state that is not recurrent. Recurrent and transient states for Markov chains with a countably-inﬁnite state space will be deﬁned in Chapter 5. According to the deﬁnition, a state i in a ﬁnite-state Markov chain is recurrent if there is no possibility of going to a state j from which there can be no return. As we shall see later, if a Markov chain ever enters a recurrent state, it returns to that state eventually with probability 1, and thus keeps returning inﬁnitely often (in fact, this property serves as the deﬁnition of recurrence for Markov chains without the ﬁnite-state restriction). A state i is transient if there is some j that is accessible from i but from which there is no possible return. Each time the system returns to i, there is a possibility of going to j; eventually this possibility will occur with no further returns to i. Theorem 3.2.1. For ﬁnite-state Markov chains, either all states in a class are transient or all are recurrent.2 Proof: Assume that state i is transient (i.e., for some j, i → j but j 6→ i) and suppose that i and m are in the same class (i.e., i ↔ m). Then m → i and i → j, so m → j. Now if j → m, then the walk from j to m could be extended to i; this is a contradiction, and therefore there is no walk from j to m, and m is transient. Since we have just shown that all nodes in a class are transient if any are, it follows that the states in a class are either all recurrent or all transient. For the example of Figure 3.1(a), {2, 3} and {5} are recurrent classes and the other classes are transient. In terms of the graph of a Markov chain, a class is transient if there are any directed arcs going from a node in the class to a node outside the class. Every ﬁnite-state Markov chain must have at least one recurrent class of states (see Exercise 3.2), and can have arbitrarily many additional classes of recurrent states and transient states. States can also be classiﬁed according to their periods (see Figure 3.2). For X0 = 2 in Figure 3.2(a), Xn must be 2 or 4 for n even and 1 or 3 for n odd. On the other hand, if X0 is 1 or 3, then Xn is 2 or 4 for n odd and 1 or 3 for n even. Thus the eﬀect of the starting state never dies out. Figure 3.2(b) illustrates another example in which the memory of the starting state never dies out. The states in both of these Markov chains are said to be periodic with period 2. Another example of periodic states are states 2 and 3 in Figure 3.1(a). Deﬁnition 3.2.6. The period of a state i, denoted d(i), is the greatest common divisor (gcd) of those values of n for which Piin > 0. If the period is 1, the state is aperiodic, and if the period is 2 or more, the state is periodic. 2 As shown in Chapter 5, this theorem is also true for Markov chains with a countably inﬁnite state space, but the proof given here is inadequate. Also recurrent classes with a countably inﬁnite state space are further classiﬁed into either positive-recurrent or null-recurrent, a distinction that does not appear in the ﬁnite-state case. CHAPTER 3. FINITE-STATE MARKOV CHAINS 1❧ ②  ✄✗ ③ ❧  2 ✄✎ 4❧ ②  ✎✄ ③ ❧  3 ✄✗ (a) ✒ ° ° 7❧ 8❧ ✲ 9❧ ❅ ■ ❅ ❧ 6✛ 1❧ ❅ ✒ ❅ ° ❘ ❧ ❅ ❘ ❧ ❅ ° 4 2 ° ❅ ° ■ ✠ ° ✠ ° ❅ ❧ 5❧ 3 (b) Figure 3.2: Periodic Markov Chains n > 0 for n = 2, 4, 6, . . . . Thus d(1), the period of state 1, For example, in Figure 3.2(a), P11 is two. Similarly, d(i) = 2 for the other states in Figure 3.2(a). For Figure 3.2(b), we have n > 0 for n = 4, 8, 10, 12, . . . ; thus d(1) = 2, and it can be seen that d(i) = 2 for all the P11 states. These examples suggest the following theorem. Theorem 3.2.2. For any Markov chain (with either a ﬁnite or countably inﬁnite number of states), all states in the same class have the same period. Proof: Let i and j be any distinct pair of states in a class C. Then i ↔ j and there is some r such that Pijr > 0 and some s such that Pjis > 0. Since there is a walk of length r + s going from i to j and back to i, r + s must be divisible by d(i). Let t be any integer such t > 0. Since there is a walk of length r + t + s from i o j, then back to j, and then that Pjj to i, r + t + s is divisible by d(i), and thus t is divisible by d(i). Since this is true for any t t > 0, d(j) is divisible by d(i). Reversing the roles of i and j, d(i) is divisible such that Pjj by d(j), so d(i) = d(j). Since the states in a class C all have the same period and are either all recurrent or all transient, we refer to C itself as having the period of its states and as being recurrent or transient. Similarly if a Markov chain has a single class of states, we refer to the chain as having the corresponding period. Theorem 3.2.3. If a recurrent class C in a ﬁnite-state Markov chain has period d, then the states in C can be partitioned into d subsets, S1 , S2 , . . . , Sd , in such a way that all transitions from S1 go to S2 , all from S2 go to S3 , and so forth up to Sm−1 to Sm . Finally, all transitions from Sm go to S1 . Proof: See Figure 3.3 for an illustration of the theorem. For a given state in C, say state 1, deﬁne the sets S1 , . . . , Sd by nd+m Sm = {j : P1j > 0 for some n ≥ 0}; 1 ≤ m ≤ d. (3.7) For each j ∈ C, we ﬁrst show that there is one and only one value of m such that j ∈ Sm . Since 1 ↔ j, there is some r for which P1rj > 0 and some s for which Pjs1 > 0. Thus there is a walk from 1 to 1 (through j) of length r + s, so r + s is divisible by d. For the given r, 3.2. CLASSIFICATION OF STATES let m, 1 ≤ m ≤ d, satisfy r = m + nd, where n is an integer. From (3.7), j ∈ Sm . Now let 0 r0 be any other integer such that P1rj > 0. Then r0 + s is also divisible by d, so that r0 − r is divisible by d. Thus r0 = m + n0 d for some integer n0 and that same m. Since r0 is any 0 integer such that P1rj > 0, j is in Sm for only that one value of m. Since j is arbitrary, this shows that the sets Sm are disjoint and partition C. Finally, suppose j ∈ Sm and Pjk > 0. Given a walk of length r = nd + m from state 1 to j, there is a walk of length nd + m + 1 from state 1 to k. It follows that if m < d, then k ∈ Sm+1 and if m = d, then k ∈ S1 , completing the proof. ❣ ❣ PP ❍ PP ❑❆❆ ❍ ✻ S2 ❍ ❍ ❣P P P P ❆ ❍ PP P  ❍❍ P ③ P❣ q PP  S1 ❆ ❇▼❇ P ❍ P ❆❇ PP ❍❍ PP ❍ ❆❇ PP❍ S3 ❆❇ P❍ Pq ❍ ❥❣ P ❆❇ ❣✮ ✏ ✏ ✛ Figure 3.3: Structure of a periodic Markov chain with d = 3. Note that transitions only go from one subset Sm to the next subset Sm+1 (or from Sd to S1 ). We have seen that each class of states (for a ﬁnite-state chain) can be classiﬁed both in terms of its period and in terms of whether or not it is recurrent. The most important case is that in which a class is both recurrent and aperiodic. Deﬁnition 3.2.7. For a ﬁnite-state Markov chain, an ergodic class of states is a class that is both recurrent and aperiodic3 . A Markov chain consisting entirely of one ergodic class is called an ergodic chain. We shall see later that these chains have the desirable property that Pijn becomes indepen dent of the starting state i as n → 1. The next theorem establishes the ﬁrst part of this by showing that Pijn > 0 for all i and j when n is suﬃciently large. A guided proof is given in Exercise 3.5. Theorem 3.2.4. For an ergodic M state Markov chain, Pijm > 0 for all i, j, and all m ≥ (M − 1)2 + 1. Figure 3.4 illustrates a situation where the bound (M − 1)2 + 1 is met with equality. Note that there is one cycle of length M − 1 and the single node not on this cycle, node 1, is the unique starting node at which the bound is met with equality. 3 For Markov chains with a countably inﬁnite state space, ergodic means that the states are positiverecurrent and aperiodic (see Chapter 5, Section 5.1). CHAPTER 3. FINITE-STATE MARKOV CHAINS ✓✏ ✓✏ ✲ 6 ✒✑ ❅ ❅ ✓✏ ❘ ❅ ✒✑ ✒ ° ° ✓✏ ° 5 ✒✑ ■ ❅ ❅ ❅✓✏ 3 ✛ ✒✑ ✒✑ ° ° ✓✏ ❄° ✠ 4 1 ✒✑ 2 Figure 3.4: An ergodic chain with M = 6 states in which Pijm > 0 for all m > (M − 1)2 (M−1)2 and all i, j but P11 = 0 The ﬁgure also illustrates that an M state Markov chain must have a cycle with M − 1 or fewer nodes. To see this, note that an ergodic chain must have cycles, since each node must have a walk to itself, and subcycles of repeated nodes can be omitted from that walk, converting it into a cycle. Such a cycle might have M nodes, but a chain with only an M node cycle would be periodic. Thus some nodes must be on smaller cycles, such as the cycle of length 5 in the ﬁgure. 3.3 The matrix representation The matrix [P ] of transition probabilities of a Markov chain is called a stochastic matrix; that is, a stochastic matrix is a square matrix of nonnegative terms in which the elements in each row sum to 1. We ﬁrst consider the n step transition probabilities Pijn in terms of [P]. The probability, starting in state i, of going to state j in two steps is the sum over k of the probability of going ﬁrst to k and then to j. Using the Markov condition in (3.1), Pij2 = M X Pik Pkj . k=1 It can be seen that this is just the ij term of the product of the matrix [P ] with itself; denoting [P ][P ] as [P 2 ], this means that Pij2 is the (i, j) element of the matrix [P 2 ]. Similarly, Pijn is the ij element of the nth power of the matrix [P ]. Since [P m+n ] = [P m ][P n ], this means that Pijm+n = M X m n Pik Pkj . (3.8) k=1 This is known as the Chapman-Kolmogorov equation. An eﬃcient approach to compute [P n ] (and thus Pijn ) for large n, is to multiply [P ]2 by [P ]2 , then [P ]4 by [P ]4 and so forth. Then [P ], [P 2 ], [P 4 ], . . . can be multiplied as needed to get [P n ]. 3.3. THE MATRIX REPRESENTATION 3.3.1 Steady state and [P n ] for large n The matrix [P n ] (i.e., the matrix of transition probabilities raised to the nth power) is im portant for a number of reasons. The i, j element of this matrix is Pijn = Pr{Xn =j | X0 =i}. If memory of the past dies out with increasing n, then we would expect the dependence of Pijn on both n and i to disappear as n → 1. This means, ﬁrst, that [P n ] should converge to a limit as n → 1, and, second, that for each column j, the elements in that column, n , P n , . . . , P n should all tend toward the same value, say π , as n → 1. If this type P1j j 2j Mj of convergence occurs, (and we later determine the circumstances under which it occurs), then Pijn → πj and each row of the limiting matrix will be (π1 , . . . , πM ), i.e., each row is the same as each other row. P n If we now look at the equation Pijn+1 = k Pik Pkj , and Passume the above type of convergence as n → 1, then the limiting equation becomes πj = πk Pkj . In vector form, this equation is π = π [P ]. We will do this more carefully later, but what it says is that if Pijn approaches a limit denoted πj as n → 1, then π = (π1 , . . . , πM ) satisﬁes π = π [P ]. If nothing else, it is easier to solve the linear equations π = π [P ] than to multiply [P ] by itself an inﬁnite number of times. Deﬁnition 3.3.1. A steady-state vector (or a steady-state distribution) for an M state Markov chain with transition matrix [P ] is a row vector π that satisﬁes X π = π [P ] ; where πi = 1 and πi ≥ 0 , 1 ≤ i ≤ M. (3.9) i If π satisﬁes (3.9), then the last half of the equation says that it must be a probability vector. If π is taken as the initial PMF of the chain at time 0, then that PMF is maintained forever. That is, post-multiplyng both sides of (3.9) by [P ], we get π [P ] = π [P 2 ], and iterating this, π = π [P 2 ] = π [P 3 ] = · · · for all n. It is important to recognize that we have shown that if [P n ] converges to a matrix all of whose rows are π , then π is a steady-state vector, i.e., it satisﬁes (3.9). However, ﬁnding a π that satisﬁes (3.9) does not imply that [P n ] converges as n → 1. For the example of Figure 3.1, it can be seen that if we choose π2 = π3 = 1/2 with πi = 0 otherwise, then π is a steady-state vector. Reasoning more physically, we see that if the chain is in either state 2 or 3, it simply oscillates between those states for all time. If it starts at time 0 being in states 2 or 3 with equal probability, then it persists forever being in states 2 or 3 with equal probability. Although this choice of π satisﬁes the deﬁnition in (3.9) and also is a steady-state distribution in the sense of not changing over time, it is not a very satisfying form of steady state, and almost seems to be concealing the fact that we are dealing with a simple oscillation between states. This example raises one of a number of questions that should be answered concerning steady-state distributions and the convergence of [P n ]: 1. Under what conditions does π = π [P ] have a probability vector solution? 2. Under what conditions does π = π [P ] have a unique probability vector solution? CHAPTER 3. FINITE-STATE MARKOV CHAINS 3. Under what conditions does each row of [P n ] converge to a probability vector solution of π = π [P ]? We ﬁrst give the answers to these questions for ﬁnite-state Markov chains and then derive them. First, (3.9) always has a solution (although this is not necessarily true for inﬁnitestate chains). The answers to the second and third questions are simpliﬁed if we use the following deﬁnition: Deﬁnition 3.3.2. A unichain is a ﬁnite-state Markov chain that contains a single recurrent class plus, perhaps, some transient states. An ergodic unichain is a unichain for which the recurrent class is ergodic. A unichain, as we shall see, is the natural generalization of a recurrent chain to allow for some initial transient behavior without disturbing the long term aymptotic behavior of the underlying recurrent chain. The answer to the second question above is that the solution to (3.9) is unique if and only if [P] is the transition matrix of a unichain. If there are c recurrent classes, then (3.9) has c linearly independent solutions, each nonzero only over the elements of the corresponding recurrent class. For the third question, each row of [P n ] converges to the unique solution of (3.9) if and only if [P] is the transition matrix of an ergodic unichain. If there are multiple recurrent classes, and each one is aperiodic, then [P n ] still converges, but to a matrix with non-identical rows. If the Markov chain has one or more periodic recurrent classes, then [P n ] does not converge. We ﬁrst look at these answers from the standpoint of the transition matrices of ﬁnite-state Markov chains, and then proceed in Chapter 5 to look at the more general problem of Markov chains with a countably inﬁnite number of states. There we use renewal theory to answer these same questions (and to discover the diﬀerences that occur for inﬁnite-state Markov chains). The matrix approach is useful computationally and also has the advantage of telling us something about rates of convergence. The approach using renewal theory is very simple (given an understanding of renewal processes), but is more abstract. In answering the above questions (plus a few more) for ﬁnite-state Markov chains, it is simplest to ﬁrst consider the third question,4 i.e., the convergence of [P n ]. The simplest approach to this, for each column j of [P n ], is to study the diﬀerence between the largest and smallest element of that column and how this diﬀerence changes with n. The following almost trivial lemma starts this study, and is valid for all ﬁnite-state Markov chains. Lemma 3.3.1. Let [P ] be the transition matrix of a ﬁnite-state Markov chain and let [P n ] be the nth power of [P ] i.e., the matrix of nth order transition probabilities, Pijn . Then for each state j and each integer n ≥ 1 max Pijn+1 ≤ max P`nj i 4 ` min Pijn+1 ≥ min P`nj . i ` (3.10) One might naively try to show that a steady-state vector exists by ﬁrst noting that each row of P sums to 1. The column vector e = (1, 1, . . . , 1)T then satisﬁes the eigenvector equation e = [P ]e. Thus there must also be a left eigenvector satisfying π [P ] = π . The problem here is showing that π is real and non-negative. 3.3. THE MATRIX REPRESENTATION Discussion The lemma says that for each column j, the largest of the elementsis nonincreasing with n and the smallest of the elements is non-decreasing with n. The elements in a column that form the maximum and minimum can change with n, but the range covered by those elements is nested in n, either shrinking or staying the same as n → 1. Proof: For each i, j, n, we use the Chapman-Kolmogorov equation, (3.8), followed by the n ≤ max P n , to see that fact that Pkj ` `j Pijn+1 = X k n Pik Pkj ≤ X Pik max P`nj = max P`jn . ` k ` (3.11) Since this holds for all states i, and thus for the maximizing i, the ﬁrst half of (3.10) follows. The second half of (3.10) is the same, with minima replacing maxima, i.e., Pijn+1 = X k n Pik Pkj ≥ X Pik min P`nj = min P`nj . ` k ` (3.12) For some Markov chains, the maximizing elements in each column decrease with n and reach a limit equal to the increasing sequence of minimizing elements. For these chains, [P n ] converges to a matrix where each column is constant, i.e., the type of convergence discussed above. For others, the maximizing elements converge at some value strictly above the limit of the minimizing elements, Then [P n ] does not converge to a matrix where each column is constant, and might not converge at all since the location of the maximizing and minimizing elements in each column can vary with n. The following three subsections establish the above kind of convergence (and a number of subsidiary results) for three cases of increasing complexity. The ﬁrst assumes that Pij > 0 for all i, j. This is denoted as [P ] > 0 and is not of great interest in its own right, but provides a needed step for the other cases. The second case is where the Markov chain is ergodic, and the third is where the Markov chain is an ergodic unichain. 3.3.2 Steady state assuming [P ] > 0 Lemma 3.3.2. Let the transition matrix of a ﬁnite-state Markov chain satisfy [P ] > 0 (i.e., Pij > 0 for all i, j), and let α = mini,j Pij . Then for all states j and all n ≥ 1: max Pijn+1 i − min Pijn+1 i µ ∂ n n ≤ max P`j − min P`j (1 − 2α). ` µ ∂ n n max P`j − min P`j ≤ (1 − 2α)n . ` ` ` lim max P`nj = n→1 ` lim min P`nj > 0. n→1 ` (3.13) (3.14) (3.15) Discussion: Since Pij > 0 for all i, j, we must have α > 0. Thus the theorem says that for each j, the elements Pijn in column j of [P n ] approach equality over both i and n as CHAPTER 3. FINITE-STATE MARKOV CHAINS n → 1, i.e., the state at time n becomes independent of the state at time 0 as n → 1. The approach is exponential in n. Proof: We ﬁrst slightly tighten the inequality in (3.11). For a given j and n, let `min be a value of ` that minimizes P`nj . Then Pijn+1 = X n Pik Pkj k ≤ X Pik max P`nj + Pi`min min P`nj k=` 6 min ` ` µ ∂ n n n = max P`j − Pi`min max P`j − min P`j ` ` ` µ ∂ n n n ≤ max P`j − α max P`j − min P`j , ` ` ` where in the third step, we added and subtracted Pi`min min` P`nj to the right hand side, and in the fourth step, we used α ≤ Pi`min in conjuction with the fact that the term in parentheses must be nonnegative. Repeating the same argument with the roles of max and min reversed, µ ∂ n+1 n n n Pij ≥ min P`j + α max P`j − min P`j . ` ` ` The upper bound above applies to maxi Pijn+1 and the lower bound to mini Pijn+1 . Thus, subtracting the lower bound from the upper bound, we get (3.13). Finally, note that min P`j ≥ α > 0 ` max P`j ≤ 1 − α. ` Thus max` P`j − min` P`j ≤ 1 − 2α. Using this as the base for iterating (3.13) over n, we get (3.14). This, in conjuction with (3.10), shows not only that the limits in (3.10) exist and are positive and equal, but that the limits are approached exponentially in n. 3.3.3 Ergodic Markov chains Lemma 3.3.2 extends quite easily to arbitrary ergodic ﬁnite-state Markov chains. The key to this comes from Theorem 3.2.4, which shows that if [P ] is the matrix for an M state ergodic Markov chain, then the matrix [P h ] is positive for any h ≥ (M − 1)2 − 1. Thus, choosing h = (M − 1)2 − 1, we can apply Lemma 3.3.2 to [P h ] > 0. For each integer ∫ ≥ 1, ≥ ¥ h(∫+1) h(∫+1) h∫ h∫ max Pij − min Pij ≤ max Pmj − min Pmj (1 − 2β) (3.16) m m i i ≥ ¥ h∫ h∫ max Pmj − min Pmj ≤ (1 − 2β)∫ m m h∫ lim max Pmj = ∫→1 m h∫ lim min Pmj > 0, ∫→1 m (3.17) 3.3. THE MATRIX REPRESENTATION where β = mini,j Pijh . Lemma 3.3.1 states that maxi Pijn+1 is nondecreasing in n, so that the limit on the left in (3.17) can be replaced with a limit in n. Similarly, the limit on the right can be replaced with a limit on n, getting ≥ ¥ n n max Pmj − min Pmj ≤ (1 − 2β)bn/hc (3.18) m m n lim max Pmj = n→1 m n lim min Pmj > 0. n→1 m (3.19) Now deﬁne π > 0 by n n πj = lim max Pmj = lim min Pmj > 0. n→1 m n→1 m (3.20) Since πj lies between the minimum and maximum Pijn for each n, Ø n Ø ØPij − πj Ø ≤ (1 − 2β)bn/hc . In the limit, then, lim Pijn = πj n→1 for each i, j. (3.21) (3.22) This says that the matrix [P n ] has a limit as n → 1 and the i, j term of that matrix is πj for all i, j. In other words, each row of this limiting matrix is the same and is the vector π . This is represented most compactly by π lim [P n ] = eπ n→1 where e = (1, 1, . . . , 1)T . (3.23) The following theorem5 summarizes these results and adds one small additional result. Theorem 3.3.1. Let [P ] be the matrix of an ergodic ﬁnite-state Markov chain. Then there is a unique steady-state vector π , that vector is positive and satisﬁes (3.22) and (3.23). The convergence in n is exponential, satisfying (3.18). Proof: We need to show that π as deﬁned in (3.20) is the unique steady-state vector. Let µ be any steady state vector, i.e., any probability vector solution to µ [P ] = µ . Then µ must satisfy µ = µ [P n ] for all n > 1. Going to the limit, π = π. µ = µ lim [P n ] = µ eπ n→1 Thus π is a steady state vector and is unique 3.3.4 Ergodic Unichains Understanding how Pijn approaches a limit as n → 1 for ergodic unichains is a straight forward extension of the results in Section 3.3.3, but the details require a little care. Let T denote the set of transient states (which might contain several transient classes), and CHAPTER 3. FINITE-STATE MARKOV CHAINS    [PT ] [P ] =   [0]  P1,t+1 [PT R ] =  · · · Pt,t+1 [PT R ]    [PR ] ··· ··· ... where  P1,t+r  ··· Pt,t+r  P11 [PT ] =  · · · Pt1  Pt+1,t+1 [PR ] =  · · · Pt+r,t+1 ··· ··· ...  P1t ···  Ptt ··· ··· ...  Pt+r,t+1  ··· Pt+r,t+r Figure 3.5: The transition matrix of a unichain. The block of zeroes in the lower left corresponds to the absence of transitions from recurrent to transient states. assume the states of T are numbered 1, 2, . . . , t. Let R denote the recurrent class, assumed to be numbered t+1, . . . , t+r (see Figure 3.5). If i and j are both recurrent states, then there is no possibility of leaving the recurrent class in going from i to j. Assuming this class to be ergodic, the transition matrix [PR ] as shown in Figure 3.5 has been analyzed in Section 3.3.3. If the initial state is a transient state, then eventually the recurrent class is entered, and eventually after that, the distribution approaches steady state within the recurrent class. This suggests (and we next show) that there is a steady-state vector π for [P ] itself such that πj = 0 for j ∈ T and πj is as given in Section 3.3.3 for each j ∈ R. Initially we will show that Pijn converges to 0 for i, j ∈ T . The exact nature of how and when the recurrent class is entered starting in a transient state is an interesting problem in its own right, and is discussed more later. For now, a crude bound will suﬃce. For each transient state, there must a walk to some recurrent state, and since there are only t transient states, there must be some such path P of length at most t. Each such path has positive probability, and thus for each i ∈ T , j∈R Pijt > 0. It follows that for each i ∈ T , P t j∈T Pij < 1. Let ∞ < 1 be the maximum of these probabilities over i ∈ T , i.e., ∞ = max i∈T X Pijt < 1. j∈T Lemma 3.3.3. Let [P ] be a unichain with a set T of t transient states. Then max `∈T 5 X j∈T P`nj ≤ ∞ bn/tc . (3.24) This is essentially the Frobenius theorem for non-negative irreducible matrices, specialized to Markov chains. A non-negative matrix [P ] is irreducible if its graph (containing an edge from node i to j if Pij > 0) is the graph of a recurrent Markov chain. There is no constraint that each row of [P ] sums to 1. The proof of the Frobenius theorem requires some fairly intricate analysis and seems to be far more complex than the simple proof here for Markov chains. A proof of the general Frobenius theorem can be found in [10]. 3.3. THE MATRIX REPRESENTATION Proof: For each integer multiple ∫t of t and each i ∈ T , X X X X X (∫+1)t X t ∫t t ≤ = Pij Pik Pkj ≤ Pik max P`∫t ∞ max P`j∫t . j j∈T j ∈T k∈T k∈T `∈T j ∈T `∈T j ∈T Recognizing that this applies to all i ∈ T , and thus to the maximum over i, we can iterate this equation, getting X P`j∫t ≤ ∞ ∫ . max `∈T j∈T Since this maximum is nonincreasing in n, (3.24) follows. We now proceed to the case where the initial state is i ∈ T and the ﬁnal state is j ∈ R. Let m = bn/2c. For each i ∈ T and j ∈ R, the Chapman-Kolmogorov equation, says that X X m n−m m n−m Pijn = Pik Pkj + Pik Pkj . k∈T k∈R Let πj be the steady-state probability of state j ∈ R in the recurrent Markov chain with n . Then for each i ∈ T , states R, i.e., πj = limn→1 Pkj Ø Ø ØX ≥ ¥ X ≥ ¥Ø Ø Ø n Ø n−m n−m m m ØPij − πj Ø = ØØ Pik Pkj − πj + Pik Pkj − πj Ø Ø Ø k∈T k∈R Ø Ø Ø Ø X X Ø Ø m Ø n−m m Ø n−m ≤ Pik Pik ØPkj − πj Ø + ØPkj − πj Ø k∈T ≤ X m Pik + k∈T bm/tc ≤ ∞ X k∈R k∈R Ø Ø Ø m Ø n−m Pik ØPkj − πj Ø + (1 − 2β)b(n−m)/hc , (3.25) (3.26) where the ﬁrst step upper bounded the absolute value of a sum by the sum of the absolute values. In the last step, (3.24) was used in the ﬁrst half of (3.25) and (3.21) (with h = (r − 1)2 − 1 and β = mini,j ∈R Pijh > 0) was used in the second half. This is summarized in the following theorem. Theorem 3.3.2. Let [P ] be the matrix of an ergodic ﬁnite-state unichain. Then limn→1 [P n ] = π where e = (1, 1, . . . , 1)T and π is the steady-state vector of the recurrent class of states, eπ expanded by 0’s for each transient state of the unichain. The convergence is exponential in n for all i, j. 3.3.5 Arbitrary ﬁnite-state Markov chains The asymptotic behavior of [P n ] as n → 1 for arbitrary ﬁnite-state Markov chains can mostly be deduced from the ergodic unichain case by simple extensions and common sense. First consider the case of m > 1 aperiodic classes plus a set of transient states. If the initial state is in the ∑th of the recurrent classes, say R∑ then the chain remains in R∑ and there CHAPTER 3. FINITE-STATE MARKOV CHAINS is a unique ﬁnite-state vector π ∑ that is non-zero only in R∑ that can be found by viewing class ∑ in isolation. If the initial state i is transient, then, for each R∑ , there is a certain probability that R∑ is eventually reached, and once it is reached there is no exit, so the steady state over that recurrent class is approached. The question of ﬁnding the probability of entering each recurrent class from a given transient class will be discussed in the next section. Next consider a recurrent Markov chain that is periodic with period d. The dth order transition probability matrix, [P d ], is then constrained by the fact that Pijd = 0 for all j not in the same periodic subset as i. In other words, [P d ] is the matrix of a chain with d recurrent classes. We will obtain greater facility in working with this in the next section when eigenvalues and eigenvectors are discussed. 3.4 The eigenvalues and eigenvectors of stochastic matrices For ergodic unichains, the previous section showed that the dependence of a state on the distant past disappears with increasing n, i.e., Pijn → πj . In this section we look more carefully at the eigenvalues and eigenvectors of [P ] to sharpen our understanding of how fast [P n ] converges for ergodic unichains and what happens for other ﬁnite-state Markov chains. 6 Deﬁnition 3.4.1. The P row vector π is a left eigenvector of [P ] of eigenvalue ∏ if π 6= 0 π , i.e., i πi Pij = ∏πj for all j. The column vector ∫ is a right eigenvector and π [P ] = ∏π P of eigenvalue ∏ if ∫ 6= 0 and [P ]∫∫ = ∏∫∫ , i.e., j Pij ∫j = ∏∫i for all i. We showed that a stochastic matrix always has an eigenvalue ∏ = 1, and that for an ergodic unichain, there is a unique steady-state vector π that is a left eigenvector with ∏ = 1 and (within a scale factor) a unique right eigenvector e = (1, . . . , 1)T . In this section we look at the other eigenvalues and eigenvectors and also look at Markov chains other than ergodic unichains. We start by limiting the number of states to M = 2. This provides insight without requiring much linear algebra. After that, the general case with arbitrary M < 1 is analyzed. 3.4.1 Eigenvalues and eigenvectors for M = 2 states The eigenvalues and eigenvectors can be found by elementary (but slightly tedious) algebra. The left and right eigenvector equations can be written out as π1 P11 + π2 P21 = ∏π1 (left) π1 P12 + π2 P22 = ∏π2 6 P11 ∫1 + P12 ∫2 = ∏∫1 (right). P21 ∫1 + P22 ∫2 = ∏∫2 (3.27) Students of linear algebra usually work primarily with right eigenvectors (and in abstract linear algebra often ignore matrices and concrete M-tuples altogether). Here a more concrete view is desirable because of the direct connection of [P n ] with transition probabilities. Also, although left eigenvectors could be converted to right eigenvectors by taking the transpose of [P ], this would be awkward when Markov chains with rewards are considered and both row and column vectors play important roles. 3.4. THE EIGENVALUES AND EIGENVECTORS OF STOCHASTIC MATRICES 119 Each set of equations have a non-zero solution if and only if the matrix [P − ∏I], where [I] is the identity matrix, is singular (i.e., there must be a non-zero ∫ for which [P − ∏I]∫∫ = 0 ). Thus ∏ must be such that the determinant of [P − ∏I], namely (P11 − ∏)(P22 − ∏) − P12 P21 , is equal to 0. Solving this quadratic equation in ∏, we ﬁnd that ∏ has two solutions, ∏1 = 1 ∏2 = 1 − P12 − P21 . Assuming initially that P12 and P21 are not both 0, the solution for the left and right eigenvectors, π (1) and ∫ (1) , of ∏1 and π (2) and ∫ (2) of ∏2 , are given by (1) π1 = (2) π1 = P21 P12 +P21 1 (1) π2 = (2) π2 = (1) P12 P12 +P21 ∫1 = (2) ∫1 −1 (1) 1 ∫2 = P12 P12 +P21 = (2) ∫2 = 1 . −P21 P12 +P21 (1) (1) These solutions contain arbitrary normalization factors. That for π (1) = (π1 , π2 ) has been chosen so that π (1) is a steady-state vector (i.e., the components sum to 1). The solutions have also been normalized so that π i∫ i = 1 for i = 1, 2. Now deﬁne    ∏1 0  [Λ] =   0 ∏2 and   [U ] =  (1) ∫1 (2) ∫1 (1) ∫2 (2) ∫2   , i.e., [U ] is a matrix whose columns are the eigenvectors ∫ (1) and ∫ (2) . Then the two right eigenvector equations in (3.27) can be combined compactly as [P ][U ] = [U ][Λ]. It turns out (for the given normalization of the eigenvectors) that the inverse of [U ] is just the matrix whose rows are the left eigenvectors of [P ] (this can be veriﬁed by noting that π 1∫ 2 = π 2∫ 1 = 0. We then see that [P ] = [U ][Λ][U ]−1 and consequently [P n ] = [U ][Λ]n [U ]−1 . Multiplying this out, we get   [P n ] =  π1 + π2 ∏n2 π2 − π2 ∏2n π1 − π1 ∏n2 π2 + π1 ∏n2   , (3.28) where π = (π1 , π2 ) is the steady state vector π (1) . Recalling that ∏2 = 1 − P12 − P21 , we see that |∏2 | ≤ 1. There are 2 trivial cases where |∏2 | = 1. In the ﬁrst, P12 = P21 = 0, so that [P ] is just the identity matrix. The Markov chain then has 2 recurrent states and stays forever where it starts. In the other trivial case, P12 = P21 = 1. Then ∏2 = −1 so that [P n ] alternates between the identity matrix for n even and [P ] for n odd. In all other π. cases, |∏2 | < 1 and [P n ] approaches the steady state matrix limn→1 [P n ] = eπ π . Each term What we have learned from this is the exact way in which [P n ] approaches eπ n n in [P ] approaches the steady state value exponentially in n as ∏2 . Thus, in place of the upper bound in (3.21), we have an exact expression, which in this case is simpler than the bound. As we see shortly, this result is representative of the general case, but the simplicity is lost. CHAPTER 3. FINITE-STATE MARKOV CHAINS 3.4.2 Eigenvalues and eigenvectors for M > 2 states For the general case of a stochastic matrix, we start with the fact that the set of eigenvalues is given by the set of (possibly complex) values of ∏ that satisfy the determinant equation det[P − ∏I] = 0. Since det[P − ∏I] is a polynomial of degree M in ∏, this equation has M roots (i.e., M eigenvalues), not all of which need be distinct.7 Case with M distinct eigenvalues: We start with the simplest case in which the M eigenvalues, say ∏1 , . . . , ∏M , are all distinct. The matrix [P − ∏i I] is singular for each i, so there must be a right eigenvector ∫ (i) and a left eigenvector π (i) for each eigenvalue ∏i . The right eigenvectors span M dimensional space and thus the matrix U with columns (∫∫ (1) , . . . , ∫ (M) ) is nonsingular. The left eigenvectors, if normalized to satisfy π (i)∫ (i) = 1 for each i, then turn out to be the rows of [U −1 ] (see Exercise 3.11). As in the two state case, we can then express [P n ] as [P n ] = [U −1 )[Λn ][U ], (3.29) where Λ is the diagonal matrix with terms ∏1 , . . . , ∏M . If Λ is broken into the sum of M diagonal matrices,8 each with only a single nonzero element, then (see Exercise 3.11) [P n ] can be expressed as n [P ] = M X ∏ni ∫ (i)π (i) . (3.30) i=1 Note that this is the same form as (3.28), where in (3.28), the eigenvalue ∏1 = 1 simply appears as the value 1. We have seen that there is always one eigenvalue that is 1, with an accompanying steady-state vector π as a left eigenvector and the unit vector e = (1, . . . , 1)T as a right eigenvector. The other eigenvalues and eigenvectors can be Øcomplex, but it is Ø n Ø Ø almost self evident from the fact that [P ] is a stochastic matrix that ∏i ≤ 1. A simple guided proof of this is given in Exercise 3.12. π for ergodic unichains. This We have seen that limn→1 [P n ] = eπ Ø Ø implies that all terms except i = 1 in (3.30) die out with n, which further implies that Ø∏i Ø < 1 for all eigenvalues except ∏ = 1. In this case, we see that the rate at which [P n ] approaches steady state is given by the second largest eigenvalue in magnitude, i.e., maxi:|∏i |<1 |∏i |. If a recurrent chain is periodic with period d, it turns out that there are d eigenvalues of magnitude 1, and these are uniformly spaced around the unit circle in the complex plane. Exercise 3.19 contains a guided proof of this. Case with repeated eigenvalues and M linearly independent eigenvectors: If some of the M eigenvalues of [P ] are not distinct, the question arises as to how many linearly independent left (or right) eigenvectors exist for an eigenvalue ∏i of multiplicity m, i.e., a ∏i that is an mth order root of det[P − ∏I]. Perhaps the ugliest part of linear algebra is the fact that an eigenvalue of multiplicity m need not have m linearly independent eigenvectors. 7 Readers with little exposure to linear algebra can either accept the linear algebra results in this section (without a great deal of lost insight) or can ﬁnd them in Strang [19] or many other linear algebra texts. 8 If 0 is one of the M eigenvalues, then only M − 1 such matrices are required. 3.4. THE EIGENVALUES AND EIGENVECTORS OF STOCHASTIC MATRICES 121 An example of a very simple Markov chain with M = 3 but only two linearly independent eigenvectors is given in Exercise 3.14. These eigenvectors do not span M-space, and thus the expansion in (3.30) cannot be used. Before looking at this ugly case, we look at the case where the right eigenvectors, say, span the space, i.e., where each distinct eigenvalue has a number of linearly independent eigenvectors equal to its multiplicity. We can again form a matrix [U ] whose columns are the M linearly independent right eigenvectors, and again [U −1 ] is a matrix whose rows are the corresponding left eigenvectors of [P ]. We then get (3.30) again. Thus, so long as the eigenvectors span the space, the asymptotic expression for the limiting transition probabilities can be found in the same way. The most important situation where these repeated eigenvalues make a major diﬀerence is for Markov chains with ∑ > 1 recurrent classes. In this case, ∑ is the multiplicity of the eigenvalue 1. It is easy to see that there are ∑ diﬀerent steady-state vectors. The steadystate vector for recurrent class `, 1 ≤ ` ≤ ∑, is strictly positive for each state of the `th recurrent class and is zero for all other states. The eigenvalues for [P ] in this case can be found by ﬁnding the eigenvalues separately for each recurrent class. If class j contains rj states, then rj of the eigenvalues (counting repetitions) of [P ] are the eigenvalues of the rj by rj matrix for the states in that recurrent class. Thus the rate of convergence of [P n ] within that submatrix is determined by the second largest eigenvalue (in magnitude) in that class. What this means is that this general theory using eigenvalues says exactly what common sense says: if there are ∑ recurrent classes, look at each one separately, since they have nothing to do with each other. This also lets us see that for any recurrent class that is aperiodic, all the other eigenvalues for that class are strictly less than 1 in magnitude. The situation is less obvious if there are ∑ recurrent classes plus a set of t transient states. All but t of the eigenvalues (counting repetitions) are associated with the recurrent classes, and the remaining t eigenvalues are the eigenvalues of the t by t matrix, say [Pt ], between the transient states. Each of these t eigenvalues are strictly less than 1 (as seen in Section 3.3.4) and neither these eigenvalues nor their eigenvectors depend on the transition probabilities from the transient to recurrent states. The left eigenvectors for the recurrent classes also do not depend on these transient to recurrent states. The right eigenvector for ∏ = 1 for each recurrent class R` is very interesting however. It’s value is 1 for each state in R` , is 0 for each state in the other recurrent classes, and is equal to limn→1 Pr{Xn ∈ R` | X0 = i} for each transient state i (see Exercise 3.13). The Jordan form case: As mentioned before, there are cases in which one or more eigenvalues of [P ] are repeated (as roots of det[P − ∏I]) but where the number of linearly independent right eigenvectors for a given eigenvalue is less than the multiplicity of that eigenvalue. In this case, there are not enough eigenvectors to span the space, so there is no M by M matrix whose columns are linearly independent eigenvectors. Thus [P ] can not be expressed as [U −1 ][Λ][U ] where Λ is the diagonal matrix of the eigenvalues, repeated according to their multiplicity. The Jordan form is the cure for this unfortunate situation. The Jordan form for a given CHAPTER 3. FINITE-STATE MARKOV CHAINS [P ] is the following modiﬁcation of the diagonal matrix of eigenvalues: we start with the diagonal matrix of eigenvalues, with the repeated eigenvalues as neighboring elements. Then for each missing eigenvector for a given eigenvalue, a 1 is placed immediately to the right and above a neighboring pair of appearances of that eigenvalue, as seen by example9 below:   ∏1 1 0 0 0  0 ∏1 0 0 0   [J] =   0 0 ∏2 1 0  . 0 0 0 ∏2 1 0 0 0 0 ∏2 There is a theorem in linear algebra that says that an invertible matrix [U ] exists and a Jordan form exists such that [P ] = [U −1 ][J][U ]. The major value to us of this result is that it makes it relatively easy to calculate [J]n for large n (see Exercise 3.15). This exercise also shows that for all stochastic matrices, each eigenvalue of magnitude 1 has precisely one associated eigenvector. This is usually expressed by the statement that all the eigenvalues of magnitude 1 are simple, meaning that their multiplicity equals their number of linearly independent eigenvectors. Finally the exercise shows that [P n ] for an aperiodic recurrent chain converges as a polynomial10 in n times ∏ns where ∏s is the eigenvalue of largest magnitude less than 1. The most important results of this section on eigenvalues and eigenvectors can be summa rized in the following theorem. Theorem 3.4.1. The transition matrix of a ﬁnite state unichain has a single eigenvalue ∏ = 1 with an accompanying left eigenvector π satisfying (3.9) and a left eigenvector e = (1, 1, . . . , 1)T . The other eigenvalues ∏i all satisfy |∏i | ≤ 1. The inequality is strict unless the unichain is periodic, say with period d, and then there are d eigenvalues of magnitude 1 spaced equally around the unit circle. If the unichain is ergodic, then [P n ] converges to π with an error in each term bounded by a ﬁxed polynomial in n times |∏s |n , steady state eπ where ∏s is the eignevalue of largest magnitude less than 1. Arbitrary Markov chains can be split into their recurrent classes, and this theorem can be applied separately to each class. 3.5 Markov chains with rewards Suppose that each state i in a Markov chain is associated with a reward, ri . As the Markov chain proceeds from state to state, there is an associated sequence of rewards that are not independent, but are related by the statistics of the Markov chain. The concept of a reward in each state11 is quite graphic for modeling corporate proﬁts or portfolio performance, and 9 See Strang [19], for example, for a more complete description of how to construct a Jordan form This polynomial is equal to 1 if these eigenvalues are simple. 11 Occasionally it is more natural to associate rewards with transitions rather than states. If rij denotes a reward associatedPwith a transition from i to j and Pij denotes the corresponding transition probability, then deﬁning ri = j Pij rij essentially simpliﬁes these transition rewards to rewards over the initial state for the transition. These transition rewards are ignored here, since the details add complexity to a topic that is complex enough for a ﬁrst treatment. 10 3.5. MARKOV CHAINS WITH REWARDS is also useful for studying queueing delay, the time until some given state is entered, and many other phenomena. The reward ri associated with a state could equally well be veiwed as a cost or any given real-valued function of the state. In Section 3.6, we study dynamic programming and Markov decision theory. These topics include a “decision maker,” “policy maker,” or “control” that modify both the transition probabilities and the rewards at each trial of the ‘Markov chain.’ The decision maker at tempts to maximize the expected reward, but is typically faced with compromising between immediate reward and the longer-term reward arising from the choice of transition proba bilities that lead to ‘high reward’ states. This is a much more challenging problem than the current study of Markov chains with rewards, but a thorough understanding of the current problem provides the machinery to understand Markov decision theory also. The steady-state expected reward per unit time, P assuming a single recurrent class of states, is deﬁned to be the gain, expressed as g = i πi ri where πi is the steady-state probability of being in state i. 3.5.1 Examples of Markov chains with rewards The following examples demonstrate that it is important to understand the transient be havior of rewards as well as the long-term averages. This transient behavior will turn out to be even more important when we study Markov decision theory and dynamic programming. Example 3.5.1 (Expected ﬁrst-passage time). First-passage times, i.e., the number of steps taken in going from one given state, say i, to another, say 1, are frequently of interest for Markov chains, and here we solve for the expected value of this random variable. Since the ﬁrst-passage time is independent of the transitions after the ﬁrst entry to state 1, we can modify the chain to convert the ﬁnal state, say state 1, into a trapping state (a trapping state i is a state from which there is no exit, i.e., for which Pii = 1). That is, we modify P11 to 1 and P1j to 0 for all j = 6 1. We leave Pij unchanged for all i = 6 1 and all j (see Figure 3.6). This modiﬁcation of the chain will not change the probability of any sequence of states up to the point that state 1 is ﬁrst entered. ✙ ✟ ✘ 1♥ ✿ ❍  ♥ ✯ 2 ❍ ✟  ✄✗ ✎✄ ✙ ❥ ♥ ❍ ✟ 4 ❥ 3♥ ❍  ✯ ② ✟ 2♥  ✚ ❍ ✚ ✄✗ ✚ ❂ ❍ 3♥ ❥ ✘ 1♥  ✿ ✯ ② ✟  ⑥  ✄✎ ✟  ♥ ✙ 4 Figure 3.6: The conversion of a recurrent Markov chain with M = 4 into a chain for which state 1 is a trapping state, i.e., the outgoing arcs from node 1 have been removed. Let vi be the expected number of steps to ﬁrst reach state 1 starting in state i = 6 1. This number of steps includes the ﬁrst step plus the expected number of remaining steps to reach state 1 starting from whatever state is entered next (if state 1 is the next state entered, this CHAPTER 3. FINITE-STATE MARKOV CHAINS remaining number is 0). Thus, for the chain in Figure 3.6, we have the equations v2 = 1 + P23 v3 + P24 v4 . v3 = 1 + P32 v2 + P33 v3 + P34 v4 . v4 = 1 + P42 v2 + P43 v3 . For an arbitrary chain of M states where 1 is a trapping state and all other states are transient, this set of equations becomes X vi = 1 + Pij vj ; i = 6 1. (3.31) j=1 6 If we deﬁne ri = 1 for i 6= 1 and ri = 0 for i = 1, then ri is a unit reward for not yet entering the trapping state, and vi is the expected aggregate reward before entering the trapping state. Thus by taking r1 = 0, the reward ceases upon entering the trapping state, and vi is the expected transient reward, i.e., the expected ﬁrst-passage time from state i to state 1. Note that in this example, rewards occur only in transient states. Since transient states P have zero steady-state probabilities, the steady-state gain per unit time, g = i πi ri , is 0. If we deﬁne v1 = 0, then (3.31), along with v1 = 0, has the vector form v = r + [P ]v ; v1 = 0. (3.32) For a Markov chain with M states, (3.31) is a set of M − 1 equations in the M − 1 variables v2 to vM . The equation v = r + [P ]v is a set of M linear equations, of which the ﬁrst is the vacuous equation v1 = 0 + v1 , and, with v1 = 0, the last M − 1 correspond to (3.31). It is not hard to show that (3.32) has a unique solution for v under the condition that states 2 to M are all transient and 1 is a trapping state, but we prove this later, in Theorem 3.5.1, under more general circumstances. Example 3.5.2. Assume that a Markov chain has M states, {0, 1, . . . , M − 1}, and that the state represents the number of customers in an integer-time queueing system. Suppose we wish to ﬁnd the expected sum of the customer waiting times, starting with i customers in the system at some given time t and ending at the ﬁrst instant when the system becomes idle. That is, for each of the i customers in the system at time t, the waiting time is counted from t until that customer exits the system. For each new customer entering before the system next becomes idle, the waiting time is counted from entry to exit. When we discuss Little’s theorem in Section 4.5.4, it will be seen that this sum of waiting times is equal to the sum over τ of the state Xτ at time τ , taken from τ = t to the ﬁrst subsequent time the system is empty. As in the previous example, we modify the Markov chain to make state 0 a trapping state and assume the other states are then all transient. We take ri = i as the “reward” in state i, and vi as the expected aggregate reward until the trapping state is entered. Using the same reasoning as in the previous example, vi is equal to the immediate reward ri =Pi plus the expected aggregate reward from whatever state is entered next. Thus vi = ri + j≥1 Pij vj . With v0 = 0, this is v = r + [P ]v . This has a unique solution for v , as will be shown later in Theorem 3.5.1. This same analysis is valid for any choice of reward ri for each transient state i; the reward in the trapping state must be 0 so as to keep the expected aggregate reward ﬁnite. 3.5. MARKOV CHAINS WITH REWARDS In the above examples, the Markov chain is converted into a trapping state with zero gain, and thus the expected reward is a transient phenomena with no reward after entering the trapping state. We now look at the more general case of a unichain. In this more general case, there can be some gain per unit time, along with some transient expected reward depending on the initial state. We ﬁrst look at the aggregate gain over a ﬁnite number of time units, thus providing a clean way of going to the limit. Example 3.5.3. The example in Figure 3.7 provides some intuitive appreciation for the general problem. Note that the chain tends to persist in whatever state it is in. Thus if the chain starts in state 2, not only is an immediate reward of 1 achieved, but there is a high probability of additional unit rewards on many successive transitions. Thus the aggregate value of starting in state 2 is considerably more than the immediate reward of 1. On the other hand, we see from symmetry that the gain per unit time, over a long time period, must be one half. ✿ 1♥ ✘ ②  0.99 r1 =0 0.01 0.01 ③ ♥  2  ② 0.99 r2 =1 Figure 3.7: Markov chain with rewards and nonzero steady-state gain. 3.5.2 The expected aggregate reward over multiple transitions Returning to the general case, let Xm be the state at time m and let Rm = R(Xm ) be the reward at that m, i.e., if the sample value of Xm is i, then ri is the sample value of Rm . Conditional on Xm = i, the aggregate expected reward vi (n) over n trials from Xm to Xm+n−1 is vi (n) = E [R(Xm ) + R(Xm+1 ) + · · · + R(Xm+n−1 ) | Xm = i] X X = ri + Pij rj + · · · + Pijn−1 rj . j j This expression does not depend on the starting time m because of the homogeneity of the Markov chain. Since it gives the expected reward for each initial state i, it can be combined into the following vector expression v (n) = (v1 (n), v2 (n), . . . , vM (n))T , v (n) = r + [P ]r + · · · + [P n−1 ]r = n−1 X [P h ]r , (3.33) h=0 where r = (r1 , . . . , rM )T and P 0 is the identity matrix. Now assume that the Markov π and limn→1 [P ]n r = eπ π r = ge chain is an ergodic unichain. Then limn→1 [P ]n = eπ where g = π r is the steady-state reward per unit time. If g 6= 0, then v (n) changes by approximately ge for each unit increase in n, so v (n) does not have a limit as n → 1. As shown below, however, v (n) − nge does have a limit, given by lim (v (n) − nge) = lim n→1 n→1 n−1 X h=0 π ]r . [P h − eπ (3.34) CHAPTER 3. FINITE-STATE MARKOV CHAINS To see that this limit exists, note from (3.26) that ≤ > 0 canPbe chosen small enough that h Pijn − πj = o(exp(−n≤)) for all states i, j and all n ≥ 1. Thus 1 h=n (Pij − πj ) = o(exp(−n≤)) also. This shows that the limits on each side of (3.34) must exist for an ergodic unichain. The limit in (3.34) is a vector over the states of the Markov chain. This vector gives the asymptotic relative expected advantage of starting the chain in one state relative to another. This is an important quantity in both the next section and the remainder of this one. It is called the relative-gain vector and denoted by w , w = = n−1 X π ]r [P h − eπ (3.35) lim (v (n) − nge) . (3.36) lim n→1 h=0 n→1 Note from (3.36) that if g > 0, then nge increases linearly with n and and v (n) must asymptotically increase linearly with n. Thus the relative-gain vector w becomes small relative to both nge and v (n) for large n. As we will see, w is still important, particularly in the next section on Markov decisions. We can get some feel for w and how vi (n) − nπi converges to wi from Example 3.5.3 (as described in Figure 3.7). Since this chain has only two states, [P n ] and vi (n) can be calculated easily from (3.28). The result is tabulated in Figure 3.8, and it is seen numerically that w = (−25, +25)T . The rather signiﬁcant advantage of starting in state 2 rather than 1, however, requires hundreds of transitions before the gain is fully apparent. n 1 2 4 10 40 100 400 π v (n) 0.5 1 2 5 20 50 200 v1 (n) 0 0.01 0.0592 0.4268 6.1425 28.3155 175.007 v2 (n) 1 1.99 3.9408 9.5732 33.8575 71.6845 224.9923 Figure 3.8: The expected aggregate reward, as a function of starting state and stage, for the example of ﬁgure 3.7. Note that w = (−25, +25)T , but the convergence is quite slow. This example also shows that it is somewhat inconvenient to calculate w from (3.35), and this inconvenience grows rapidly with the number of states. Fortunately, as shown in the following theorem, w can also be calculated simply by solving a set of linear equations. Theorem 3.5.1. Let [P ] be the transition matrix for an ergodic unichain. Then the relativegain vector w given in (3.35) satisﬁes the following linear vector equation. w + ge = [P ]w + r and π w = 0. (3.37) Furthermore (3.37) has a unique solution if [P ] is the transition matrix for a unichain (either ergodic or periodic). 3.5. MARKOV CHAINS WITH REWARDS Discussion: For an ergodic unichain, the interpretation of w as an asymptotic relative gain comes from (3.35) and (3.36). For a periodic unichain, (3.37) still has a unique solution, but (3.35) no longer converges, so the solution to (3.37) no longer has a clean interpretation as an asymptotic limit of relative gain. This solution is still called a relative-gain vector, and can be interpreted as an asymptotic relative gain over a period, but the important thing is that this equation has a unique solution for arbitrary unichains. Deﬁnition 3.5.1. The relative-gain vector w of a unichain is the unique vector that satis ﬁes (3.37). Proof: Premultiplying both sides of (3.35) by [P ], [P ]w = = = lim n→1 n−1 X h=0 π ]r [P h+1 − eπ n X π ]r lim [P h − eπ n→1 h=1 √ n ! X π ]r − [P 0 − eπ π ]r lim [P h − eπ n→1 h=0 0 π r = w − r + ge. = w − [P ]r + eπ Rearranging terms, we get (3.37). For a unichain, the eigenvalue 1 of [P ] has multiplicity 1, and the existence and uniqueness of the solution to (3.37) is then a simple result in linear algebra (see Exercise 3.23). The above manipulations conceal the intuitive nature of (3.37). To see the intuition, consider the ﬁrst-passage-time example again. Since all states are transient except state 1, π1 = 1. Since r1 = 0, we see that the steady-state gain is g = 0. Also, in the more general model of the theorem, vi (n) is the expected reward over n transitions starting in state i, which for the ﬁrst-passage-time example is the expected number of transient states visited up to the nth transition. In other words, the quantity vi in the ﬁrst-passage-time example is limn→1 vi (n). This means that the v in (3.32) is the same as w here, and it is seen that the formulas are the same with g set to 0 in (3.37). The reason that the derivation of aggregate reward was so simple for ﬁrst-passage time is that there was no steady-state gain in that example, and thus no need to separate the gain per transition g from the relative gain w between starting states. One way to apply the intuition of the g = 0 case to the general case is as follows: given a reward vector r , ﬁnd the steady-state gain g = π r , and then deﬁne a modiﬁed reward vector r 0 = r − ge. Changing the reward vector from r to r 0 in this way does not change w , but the modiﬁed limiting aggregate gain, say v 0 (n) then has a limit, which is in fact w . The intuitive derivation used in (3.32) again gives us w = [P ]w + r 0 . This is equivalent to (3.37) since r 0 = r − ge. There are many generalizations of the ﬁrst-passage-time example in which the reward in each recurrent state of a unichain is 0. Thus reward is accumulated only until a recurrent CHAPTER 3. FINITE-STATE MARKOV CHAINS state is entered. The following corollary provides a monotonicity result about the relativegain vector for these circumstances that might seem obvious12 . Thus we simply state it and give a guided proof in Exercise 3.25. Corollary 3.5.1. Let [P ] be the transition matrix of a unichain with the recurrent class R. Let r ≥ 0 be a reward vector for [P ] with ri = 0 for i ∈ R. Then the relative-gain vector w satisﬁes w ≥ 0 with wi = 0 for i ∈ R and wi > 0 for ri > 0. Furthermore, if r0 and r00 are diﬀerent reward vectors for [P ] and r0 ≥ r00 with ri0 = ri00 for i ∈ R, then w0 ≥ w00 with wi0 = wi00 for i ∈ R and wi0 > wi00 for ri0 > ri00 . 3.5.3 The expected aggregate reward with an additional ﬁnal reward Frequently when a reward is aggregated over n transitions of a Markov chain, it is appro priate to assign some added reward, say ui , as a function of the ﬁnal state i. For example, it might be particularly advantageous to end in some particular state. Also, if we wish to view the aggregate reward over n + ` transitions as the reward over the ﬁrst n transitions plus that over the following ` transitions, we can model the expected reward over the ﬁnal ` transitions as a ﬁnal reward at the end of the ﬁrst n transitions. Note that this ﬁnal expected reward depends only on the state at the end of the ﬁrst n transitions. As before, let R(Xm+h ) be the reward at time m + h for 0 ≤ h ≤ n − 1 and U (Xm+n ) be the ﬁnal reward at time m + n, where U (X) = ui for X = i. Let vi (n, u) be the expected reward from time m to m + n, using the reward r from time m to m + n − 1 and using the ﬁnal reward u at time m+n. The expected reward is then the following simple modiﬁcation of (3.33): v (n, u) = r + [P ]r + · · · + [P n−1 n ]r + [P ]u = n−1 X [P h ]r + [P n ]u. (3.38) h=0 This simpliﬁes considerably if u is taken to be the relative-gain vector w . Theorem 3.5.2. Let [P ] be the transition matrix of a unichain and let w be the corre sponding relative-gain vector. Then for each n ≥ 1, v(n, w) = nge + w. (3.39) Also, for an arbitrary ﬁnal reward vector u, v(n, u) = nge + w + [P n ](u − w). (3.40) Discussion: An important special case of (3.40) arises from setting the ﬁnal reward u to 0, thus yielding the following expression for v (n): v (n) = nge + w − [P n ]w . 12 (3.41) An obvious counterexample if we omit the condition ri = 0 for i ∈ R is given by Figure 3.7 where r = (0, 1)T and w = (−25, 25)T . 3.6. MARKOV DECISION THEORY AND DYNAMIC PROGRAMMING π . Since π w = 0 by deﬁnition of w , the limit of For an ergodic unichain, limn→1 [P n ] = eπ (3.41) as n → 1 is lim (v (n) − nge) = w , n→1 which agrees with (3.36). The advantage of (3.41) over (3.36) is that it provides an explicit expression for v (n) for each n and also that it continues to hold for a periodic unichain. Proof: For n = 1, we see from (3.38) that v (1, w ) = r + [P ]w = ge + w , so the theorem is satisﬁed for n = 1. For n > 1, v (n, w ) = = = n−1 X [P h ]r + [P n ]w h=0 n−2 X [P h ]r + [P n−1 ] (r + [P ]w ) h=0 n−2 X [P h ]r + [P n−1 ] (g e + w ) h=0 = v (n−1, w ) + ge. Using induction, this implies (3.39). To establish (3.40), note from (3.38) that v (n, u) − v (n, w ) = [P n ](u − w ). Then (3.40) follows by using (3.39) for the value of v (n, w ). 3.6 Markov decision theory and dynamic programming In the previous section, we analyzed the behavior of a Markov chain with rewards. In this section, we consider a much more elaborate structure in which a decision maker can choose among various possible rewards and transition probabilities. In place of the reward ri and the transition probabilities {Pij ; 1 ≤ j ≤ M} associated with a given state i, there is a choice (1) (2) (K ) between some number Ki of diﬀerent rewards, say ri , ri , . . . , ri i and a corresponding (1) (2) choice between Ki diﬀerent sets of transition probabilities, say {Pij ; 1 ≤ j ≤ M}, {Pij , 1 ≤ (K ) j ≤ M}, . . . {Pij i ; 1 ≤ j ≤ M}. At each time m, a decision maker, given Xm = i, selects one of the Ki possible choices for state i. Note that if decision k is chosen in state i, then (k) (k) the reward is ri and the transition probabilities from i are {Pij ; 1 ≤ j ≤ M}; it is not (k) (k) permissable to choose ri for one k and {Pij ; 1 ≤ j ≤ M} for another k. We also assume that if decision k is selected at time m, the probability of entering state j at time m + 1 is (k) Pij , independent of earlier states and decisions. CHAPTER 3. FINITE-STATE MARKOV CHAINS Figure 3.9 shows an example of this situation in which the decision maker can choose be tween two possible decisions in state 2 (K2 = 2), and has no freedom of choice in state 1 (K1 = 1). This ﬁgure illustrates the familiar tradeoﬀ between instant gratiﬁcation (alter native 2) and long term gratiﬁcation (alternative 1). ✿ 1♥ ✘  ② 0.99 r1 =0 0.01 0.01 ③ ♥  2  ② 0.99 (1) r2 =1 Decision 1 ✿ 1♥ ✘ ②  0.99 r1 =0 0.01 1 ③ ♥  2 (2) r2 =50 Decision 2 Figure 3.9: A Markov decision problem with two alternatives in state 2. The set of rules used by the decision maker in selecting an alternative at each time is called a policy. We want to consider the expected aggregate reward over n steps of the “Markov chain” as a function of the policy used by the decision maker. If for each state i, the policy uses the same decision, say ki , at each occurrence of i, then that policy (k ) corresponds to a homogeneous Markov chain with transition probabilities Pij i . We denote the matrix of these transition probabilities as [P k ], where k = (k1 , . . . , kM ). Such a policy, i.e., mapping each state i into a ﬁxed decision ki , independent of time and past, is called a stationary policy. The aggregate gain for any such stationary policy was found in the previous section. Since both rewards and transition probabilities depend only on the state and the corresponding decision, and not on time, one feels intuitively that stationary policies make a certain amount of sense over a long period of time. On the other hand, if we look at the example of Figure 3.9, it is clear that decision 2 is the best choice in state 2 at the nth of n trials, but it is less obvious what to do at earlier trials. In what follows, we ﬁrst derive the optimal policy for maximizing expected aggregate reward over an arbitrary number n of trials, say at times m to m + n − 1. We shall see that the decision at time m + h, 0 ≤ h < n, for the optimal policy can in fact depend on h and n (but not m). It turns out to simplify matters considerably if we include a ﬁnal reward {ui ; 1 ≤ i ≤ M} at time m + n. This ﬁnal reward u is considered as a ﬁxed vector, to be chosen as appropriate, rather than as part of the choice of policy. This optimized strategy, as a function of the number of steps n and the ﬁnal reward u, is called an optimal dynamic policy for that u. This policy is found from the dynamic programming algorithm, which, as we shall see, is conceptually very simple. We then go on to ﬁnd the relationship between optimal dynamic policies and optimal stationary policies. We shall ﬁnd that, under fairly general conditions, each has the same long-term gain per trial. 3.6.1 Dynamic programming algorithm As in our development of Markov chains with rewards, we consider the expected aggregate reward over n time periods, say m to m + n − 1, with a ﬁnal reward at time m + n. First consider the optimal decision with n = 1. Given Xm = i, a decision k is made with (k) (k) immediate reward ri . With probability Pij the next state Xm+1 is state j and the ﬁnal 3.6. MARKOV DECISION THEORY AND DYNAMIC PROGRAMMING reward is then uj . The expected aggregate reward over times m and m + 1, maximized over the decision k, is then X (k) (k) vi∗ (1, u) = max{ri + Pij uj }. (3.42) k j Being explicit about the maximizing decision k0 , (3.42) becomes (k0 ) vi∗ (1, u) = ri + X (k0 ) for k0 such that Pij uj j (k0 ) ri + X j (k0 ) (k) Pij uj = max{ri k + X j (k) Pij uj }. (3.43) Note that a decision is made only at time m, but that there are two rewards, one at time m and the other, the ﬁnal reward, at time m+1. We use the notation vi∗ (n, u) to represent the maximum expected aggregate reward from times m to m + n starting at Xm = i. Decisions (with the reward vector r ) are made at the n times m to m + n − 1, and this is followed by a ﬁnal reward vector u (without any decision) at time m + n. It often simpliﬁes notation to deﬁne the vector of maximal expected aggregate rewards ∗ v ∗ (n, u) = (v1∗ (n, u), v2∗ (n, u), . . . , vM (1, u))T . With this notation, (3.42) and (3.43) become kM T where k = (k1 , . . . , kM )T , r k = (r1k1 , . . . , rM ) . v ∗ (1, u) = max{r k + [P k ]u} k 0 0 0 v ∗ (1, u) = r k + [P k ]u 0 where r k + [P k ]u = max r k + [P k ]u. k (3.44) (3.45) Now consider vi∗ (2, u), i.e., the maximal expected aggregate reward starting at Xm = i with decisions made at times m and m + 1 and a ﬁnal reward at time m + 2. The key to dynamic programming is that an optimal decision at time m + 1 can be selected based only on the state j at time m + 1; this decision (given Xm+1 = j) is optimal independent of the decision at time m. That is, whatever decision is made at time the maximal ≥ m, P ¥ expected (k) (k) reward at times m + 1 and m + 2, given Xm+1 = j, is maxk rj + ` Pj ` u` . Note that this maximum is vj∗ (1, u), as found in (3.42). Using this optimized decision at time m + 1, it is seen that if Xm = i and decision k is made P (k) at time m, then the sum of expected rewards at times m + 1 and m + 2 is j Pij vj∗ (1, u). Adding the expected reward at time m and maximizing over decisions at time m, ≥ ¥ X (k) (k) vi∗ (2, u) = max ri + Pij vj∗ (1, u) . (3.46) k j In other words, the maximum aggregate gain over times m to m + 2 (using the ﬁnal reward u at m + 2) is the maximum over choices at time m of the sum of the reward at m plus the CHAPTER 3. FINITE-STATE MARKOV CHAINS maximum aggregate expected reward for m + 1 and m + 2. The simple expression of (3.46) results from the fact that the maximization over the choice at time m + 1 depends on the state at m + 1 but, given that state, is independent of the policy chosen at time m. This same argument can be used for all larger numbers of trials. To ﬁnd the maximum expected aggregate reward from time m to m + n, we ﬁrst ﬁnd the maximum expected aggregate reward from m + 1 to m + n, conditional on Xm+1 = j for each state j. This is the same as the maximum expected aggregate reward from time m to m + n − 1, which is vj∗ (n − 1, u). This gives us the general expression for n ≥ 2, ≥ ¥ X (k) (k) vi∗ (n, u) = max ri + Pij vj∗ (n − 1, u) . (3.47) j k We can also write this in vector form as ≥ ¥ v ∗ (n, u) = max r k + [P k ]v ∗ (n − 1, u) . k (3.48) Here k is a set (or vector) of decisions, k = (k1 , k2 , . . . , kM )T , where ki is the decision for (k ) state i. [P k ] denotes a matrix whose (i, j) element is Pij i , and r k denotes a vector whose (k ) ith element is ri i . The maximization over k in (3.48) is really M separate and independent maximizations, one for each state, i.e., (3.48) is simply a vector form of (3.47). Another frequently useful way to rewrite (3.48) is as follows: 0 0 v ∗ (n, u) = r k + [P k ]v ∗ (n−1, u) for k 0 such that ≥ ¥ 0 0 r k + [P k ]v ∗ (n−1, u) = max r k + [P k ]v ∗ (n−1, u) . k (3.49) If k 0 satisﬁes (3.49), then k 0 is an optimal decision at an arbitrary time m given, ﬁrst, that the objective is to maximize the aggregate gain from time m to m + n, second, that optimal decisions for this objective are to be made at times m + 1 to m + n − 1, and, third, that u is the ﬁnal reward vector at m + n. In the same way, v ∗ (n, u) is the maximum expected reward over this ﬁnite sequence of n decisions from m to m + n − 1 with the ﬁnal reward u at m + n. Note that (3.47), (3.48), and (3.49) are valid with no restrictions (such as recurrent or aperiodic states) on the possible transition probabilities [P k ]. These equations are also valid in principle if the size of the state space is inﬁnite. However, the optimization for each n can then depend on an inﬁnite number of optimizations at n − 1, which is often infeasible. The dynamic programming algorithm is just the calculation of (3.47), (3.48), or (3.49), performed iteratively for n = 1, 2, 3, . . . . The development of this algorithm, as a systematic tool for solving this class of problems, is due to Bellman [Bel57]. Note that the algorithm is independent of the starting time m; the parameter n, usually referred to as stage n, is the number of decisions over which the aggregate gain is being optimized. This algorithm yields the optimal dynamic policy for any ﬁxed ﬁnal reward vector u and any given number of trials. Along with the calculation of v ∗ (n, u) for each n, the algorithm also yields the optimal decision at each stage (under the assumption that the optimal policy is to be used for each lower numbered stage, i.e., for each later trial of the process). 3.6. MARKOV DECISION THEORY AND DYNAMIC PROGRAMMING The surprising simplicity of the algorithm is due to the Markov property. That is, vi∗ (n, u) is the aggregate present and future reward conditional on the present state. Since it is conditioned on the present state, it is independent of the past (i.e., how the process arrived at state i from previous transitions and choices). Although dynamic programming is computationally straightforward and convenient13 , the asymptotic behavior of v ∗ (n, u) as n → 1 is not evident from the algorithm. After working out some simple examples, we look at the general question of asymptotic behavior. Example 3.6.1. Consider Figure 3.9, repeated below, with the ﬁnal rewards u2 = u1 = 0. ✘ 1♥ ✿  ② 0.99 r1 =0 0.01 0.01 ③ ♥  2 ②  ✘ 1♥ ✿  ② 0.99 0.99 (1) r2 =1 r1 =0 0.01 1 ③ ♥  2 (2) r2 =50 Since r1 = 0 and u1 = u2 = 0, the aggregate gain in state 1 at stage 1 is X v1∗ (1, u) = r1 + P1j uj = 0. j (1) Similarly, since policy 1 has an immediate reward r2 = 1 in state 2, and policy 2 has an (2) immediate reward r2 = 50, Ωh X (1) i h (2) X (2) iæ (1) ∗ v2 (1, u) = max r2 + P2j uj , r2 + P2j uj = max{1, 50} = 50. j j We can now go on to stage 2, using the results above for vj∗ (1, u). From (3.46), v1∗ (2, u) = r1 + P11 v1∗ (1, u) + P12 v2∗ (1, u) = P12 v2∗ (1, u) = 0.5 Ωh i h iæ X (1) (1) (2) (2) ∗ ∗ ∗ v2 (2, u) = max r2 + P2j vj (1, u) , r2 + P21 v1 (1, u) j n o (1) = max [1 + P22 v2∗ (1, u)], 50 = max{50.5, 50} = 50.5. Thus for two trials, decision 1 is optimal in state 2 for the ﬁrst trial (stage 2), and decision 2 is optimal in state 2 for the second trial (stage 1). What is happening is that the choice of decision 2 at stage 1 has made it very proﬁtable to be in state 2 at stage 1. Thus if the chain is in state 2 at stage 2, it is preferable to choose decision 1 (i.e., the small unit gain) at stage 2 with the corresponding high probability of remaining in state 2 at stage 1. Continuing this computation for larger n, one ﬁnds that v1∗ (n, u) = n/2 and v2∗ (n, u) = 50 + n/2. The optimum dynamic policy (for u = 0) is decision 2 for stage 1 (i.e., for the last decision to be made) and decision 1 for all stages n > 1 (i.e., for all decisions before the last). This example also illustrates that the maximization of expected gain is not necessarily what is most desirable in all applications. For example, risk-averse people might well prefer decision 2 at the next to ﬁnal decision (stage 2). This guarantees a reward of 50, rather than taking a small chance of losing that reward. 13 Unfortunately, many dynamic programming problems of interest have enormous numbers of states and possible choices of decision (the so called curse of dimensionality), and thus, even though the equations are simple, the computational requirements might be beyond the range of practical feasibility. CHAPTER 3. FINITE-STATE MARKOV CHAINS Example 3.6.2 (Shortest Path Problems). The problem of ﬁnding the shortest paths between nodes in a directed graph arises in many situations, from routing in communication networks to calculating the time to complete complex tasks. The problem is quite similar to the expected ﬁrst-passage time of example 3.5.1. In that problem, arcs in a directed graph were selected according to a probability distribution, whereas here decisions must be made about which arcs to take. Although this is not a probabilistic problem, the decisions can be posed as choosing a given arc with probability one, thus viewing the problem as a special case of dynamic programming. Consider ﬁnding the shortest path from each node in a directed graph to some particular node, say node 1 (see Figure 3.10). Each arc (except the special arc (1, 1)) has a positive link length associated with it that might reﬂect physical distance or an arbitrary type of cost. The special arc (1, 1) has 0 link length. The length of a path is the sum of the lengths of the arcs on that path. In terms of dynamic programming, a policy is a choice of arc out of each node (state). Here we want to minimize cost (i.e., path length) rather than maximizing reward, so we simply replace the maximum in the dynamic programming algorithm with a minimum (or, if one wishes, all costs can be replaced with negative rewards). 2♥ ❍ 2  ✚ 4✚ ✄✗ 0 ✚ ❂ ❥ 3♥ ❍ ② ✿ 1♥ ✘ ✟  ✯  ⑥  ✄✎ ✟  ♥ ✙ 4 4 Figure 3.10: A shortest path problem. The arcs are marked with their lengths. Un marked arcs have unit length. We start the dynamic programming algorithm with a ﬁnal cost vector that is 0 for node 1 and inﬁnite for all other nodes. In stage 1, the minimal cost decision for node (state) 2 is arc (2, 1) with a cost equal to 4. The minimal cost decision for node 4 is (4, 1) with unit cost. The cost from node 3 (at stage 1) is inﬁnite whichever decision is made. The stage 1 costs are then v1∗ (1, u) = 0, v2∗ (1, u) = 4, v3∗ (1, u) = 1, v4∗ (1, u) = 1. In stage 2, the cost v3∗ (2, u), for example, is h v3∗ (2, u) = min 2 + v2∗ (1, u), The set of costs at stage 2 are v1∗ (2, u) = 0, v2∗ (2, u) = 2, i 4 + v4∗ (1, u) = 5. v3∗ (2, u) = 5, v4∗ (2, u) = 1. The decision at stage 2 is for node 2 to go to 4, node 3 to 4, and 4 to 1. At stage 3, node 3 switches to node 2, reducing its path length to 4, and nodes 2 and 4 are unchanged. Further iterations yield no change, and the resulting policy is also the optimal stationary policy. 3.6. MARKOV DECISION THEORY AND DYNAMIC PROGRAMMING The above results at each stage n can be interpreted as the shortest paths constrained to at most n hops. As n is increased, this constraint is successively relaxed, reaching the true shortest paths in less than M stages. It can be seen without too much diﬃculty that these ﬁnal aggregate costs (path lengths) also result no matter what ﬁnal cost vector u (with u1 = 0) is used. This is a useful feature for many types of networks where link lengths change very slowly with time and a shortest path algorithm is desired that can track the corresponding changes in the shortest paths. 3.6.2 Optimal stationary policies In Example 3.6.1, we saw that there was a ﬁnal transient (at stage 1) in which decision 1 was taken, and in all other stages, decision 2 was taken. Thus, the optimal dynamic policy consisted of a long-term stationary policy, followed by a transient period (for a single stage in this case) over which a diﬀerent policy was used. It turns out that this ﬁnal transient can be avoided by choosing an appropriate ﬁnal reward vector u for the dynamic programming algorithm. If one has very good intuition, one would guess that the appropriate choice of ﬁnal reward u is the relative-gain vector w associated with the long-term optimal policy. It seems reasonable to expect this same type of behavior for typical but more complex Markov decision problems. In order to understand this, we start by considering an arbitrary 0 ) and denote the transition matrix of the associated stationary policy k 0 = (k10 , . . . , kM 0 Markov chain as [P k ]. We assume that he associated Markov chain is a unichain, or, abbrevating terminology, that k 0 is a unichain. Let w 0 be the unique relative-gain vector for k 0 . We then ﬁnd some necessary conditions for k 0 to be the optimal dynamic policy at each stage using w 0 as the ﬁnal reward vector. First, from (3.45) k 0 is an optimal dynamic decision (with the ﬁnal reward vector w 0 for 0 [P k ]) at stage 1 if 0 0 r k + [P k ]w 0 = max{r k + [P k ]w 0 }. k (3.50) Note that this is more than a simple statement that k 0 can be found by maximizing r k + [P k ]w 0 over k . It also involves the fact that w 0 is the relative-gain vector for k 0 , so there is no immediately obvious way to ﬁnd a k 0 that satisﬁes (3.50), and no a priori assurance that this equation even has a solution. The following theorem, however, says that this is the only condition required to ensure that k 0 is the optimal dynamic policy at every stage (again using w 0 as the ﬁnal reward vector). Theorem 3.6.1. Assume that (3.50) is satisﬁed for some policy k0 where the Markov chain for k0 is a unichain and w0 is the relative-gain vector of k0 . Then the optimal dynamic policy, using w0 as the ﬁnal reward vector, is the stationary policy k0 . Furthermore the optimal gain at each stage n is given by v∗ (n, w0 ) = w0 + ng 0 e, 0 where g 0 = π 0 rk and π 0 is the steady-state vector for k0 . (3.51) CHAPTER 3. FINITE-STATE MARKOV CHAINS Proof: We have seen from (3.45) that k 0 is an optimal dynamic decision at stage 1. Also, since w 0 is the relative-gain vector for k 0 , Theorem 3.5.2 asserts that if decision k 0 is used at each stage, then the aggregate gain satisﬁes v (n, w 0 ) = ng 0 e + w 0 . Since k 0 is optimal at stage 1, it follows that (3.51) is satisﬁed for n = 1. We now use induction on n, with n = 1 as a basis, to verify (3.51) and the optimality of this same k 0 at each stage n. Thus, assume that (3.51) is satisﬁed for n. Then, from (3.48), v ∗ (n + 1, w 0 ) = max{r k + [P k ]v ∗ (n, w 0 )} k n o = max r k + [P k ]{w 0 + ng 0 e} k 0 = ng e + max{r k + [P k ]w 0 } = ng 0 e + r k k0 0 0 + [P k ]w 0 } 0 = (n + 1)g e + w . (3.52) (3.53) (3.54) (3.55) (3.56) Eqn (3.53) follows from the inductive hypothesis of (3.51), (3.54) follows because [P k ]e = e for all k , (3.55) follows from (3.50), and (3.56) follows from the deﬁnition of w 0 as the relative-gain vector for k 0 . This veriﬁes (3.51) for n + 1. Also, since k 0 maximizes (3.54), it also maximizes (3.52), showing that k 0 is the optimal dynamic decision at stage n + 1. This completes the inductive step. Since our major interest in stationary policies is to help understand the relationship between the optimal dynamic policy and stationary policies, we deﬁne an optimal stationary policy as follows: Deﬁnition 3.6.1. A unichain stationary policy k0 is optimal if the optimal dynamic policy with w0 as the ﬁnal reward uses k0 at each stage. This deﬁnition side-steps several important issues. First, we might be interested in dynamic programming for some other ﬁnal reward vector. Is it possible that dynamic programming performs much better in some sense with a diﬀerent ﬁnal reward vector. Is it possible that there is another stationary policy, especially one with a larger gain per stage? We answer these questions later and ﬁnd that stationary policies that are optimal according to the deﬁnition do have maximal gain per stage compared with dynamic policies with arbitrary ﬁnal reward vectors. From Theorem 3.6.1, we see that if there is a policy k 0 which is a unichain with relative-gain vector w 0 , and if that k 0 is a solution to (3.50), then k 0 is an optimal stationary policy. It is easy to imagine Markov decision models for which each policy corresponds to a Markov chain with multiple recurrent classes. There are many special cases of such situations, and their detailed study is inappropriate in an introductory treatment. The essential problem with such models is that it is possible to get into various sets of states from which there is no exit, no matter what decisions are used. These sets might have diﬀerent gains, so that there is no meaningful overall gain per stage. We avoid these situations by a modeling assumption called inherent reachability, which assumes, for each pair (i, j) of states, that there is some decision vector k containing a path from i to j. 3.6. MARKOV DECISION THEORY AND DYNAMIC PROGRAMMING The concept of inherent reachability is a little tricky, since it does not say the same k can be used for all pairs of states (i.e., that there is some k for which the Markov chain is recurrent). As shown in Exercise 3.31, however, inherent reachability does imply that for any state j, there is a k for which j is accessible from all other states. As we have seen a number of times, this implies that the Markov chain for k is a unichain in which j is a recurrent state. Any desired model can be modiﬁed to satisfy inherent reachability by creating some new decisions with very large negative rewards; these allow for such paths but very much dis courage them. This will allow us to construct optimal unichain policies, but also to use the appearance of these large negative rewards to signal that there was something questionable in the original model. 3.6.3 Policy improvement and the seach for optimal stationary policies The general idea of policy improvement is to start with an arbitrary unichain stationary policy k 0 with a relative gain vector w 0 (as given by (3.37)). We assume inherent reachability throughout this section, so such unichains must exist. We then check whether (3.50), is satisﬁed, and if so, we know from Theorem 3.6.1 that k 0 is an optimal stationary policy. If not, we ﬁnd another stationary policy k that is ‘better’ than k 0 in a sense to be described later. Unfortunately, the ‘better’ policy that we ﬁnd might not be a unichain, so it will also be necessary to convert this new policy into an equally ‘good’ unichain policy. This is where the assumption of of inherent reachability is needed. The algorithm then iteratively ﬁnds better and better unichain stationary policies, until eventually one of them satisﬁes (3.50) and is thus optimal. We now state the policy-improvement algorithm for inherently reachable Markov decision problems. This algorithm is a generalization of Howard’s policy-improvement algorithm, [How60]. Policy-improvement Algorithm 1. Choose an arbitrary unichain policy k 0 0 0 2. For policy k 0 , calculate w 0 and g 0 from w 0 + g 0 e = r k + [P k ]w 0 and π 0 w 0 = 0 0 0 3. If r k + [P k ]w 0 = maxk {r k + [P k ]w 0 }, then stop; k 0 is optimal. P (k0 ) P (k ) (k0 ) (k ) 4. Otherwise, choose ` and k` so that r` ` + j P`j ` wj0 < r` ` + j P`j ` wj0 . For i = 6 `, 0 let ki = ki . 5. If k = (k1 , . . . kM ) is not a unichain, then let R be the recurrent class in k that contains state `, and let k̃ be a unichain policy for which k̃i = ki for each i ∈ R. Alternatively, if k is already a unichain, let k̃ = k . 6. Update k 0 to the value of k̃ and return to step 2. P (k0 ) (k0 ) If the stopping test in step 3 fails, there must be an ` and k` for which r` ` + j P`j ` wj0 < P (k ) (k ) r` ` + j P`j ` wj0 . Thus step 4 can always be executed if the algorithm does not stop in CHAPTER 3. FINITE-STATE MARKOV CHAINS step 3, and since the decision is changed only for the single state `, the resulting policy k satisﬁes 0 0 r k + [pk ]w 0 ≤ r k + [P k ]w 0 with strict inequality for component `. (3.57) The next three lemmas consider the diﬀerent cases for the state ` whose decision is changed in step 4 of the algorithm. Taken together, they show that each iteration of the algorithm either increases the gain per stage or keeps the gain per stage constant while increasing the relative gain vector. After proving these lemmas, we return to show that the algorithm must converge and explain the sense in which the resulting stationary algorithm is optimal. For each of the lemmas, let k 0 be the decision vector in step 1 of a given iteration of the policy improvement algorithm and assume that the Markov chain for k 0 is a unichain. Let g 0 , w 0 , and R0 respectively be the gain per stage, the relative gain vector, and the recurrent set of states for k 0 . Assume that the stopping condition in step 3 is not satisﬁed and that ` denotes the state whose decision is changed. Let k` be the new decision in step 4 and let k be the new decision vector. Lemma 3.6.1. Assume that ` ∈ R0 . Then the Markov chain for k is a unichain and ` is recurrent in k. The gain per stage g for k satisﬁes g > g 0 . Proof: The Markov chain for k is the same as that for k 0 except for the transitions out of state `. Thus every path into ` in k 0 is still a path into ` in k . Since ` is recurrent in the unichain k 0 , it is accessible from all states in k 0 and thus in k . It follows (see Exercise 3.3) 0 0 that ` is recurrent in k and k is a unichain. Since r k + [P k ]w 0 = w 0 + g 0 e (see (3.37)), we can rewrite (3.57) as w 0 + g 0 e ≤ r k + [P k ]w 0 with strict inequality for component `. (3.58) Premultiplying both sides of (3.58) by the steady-state vector π of the Markov chain k and using the fact that ` is recurent and thus π` > 0, π w 0 + g 0 < π r k + π [P k ]w 0 . Since π [P k ] = π , this simpliﬁes to g0 < π r k . (3.59) The gain per stage g for k is π r k , so we have g 0 < g. Lemma 3.6.2. Assume that ` ∈ / R0 (i.e., ` is transient in k0 ) and that the states of R0 are not accessible from ` in k. Then k is not a unichain and ` is recurrent in k. A decision vector k̃ exists that is a unichain for which k̃i = ki for i ∈ R, and its gain per stage g̃ satisﬁes g̃ > g. Proof: Since ` ∈ / R0 , the transition probabilities from the states of R0 are unchanged in going from k 0 to k . Thus the set of states accessible from R0 remains unchanged, and R0 is a recurrent set of k . Since R0 is not accessible from `, there must be another recurrent 3.6. MARKOV DECISION THEORY AND DYNAMIC PROGRAMMING set, R, in k , and thus k is not a unichain. The states accessible from R no longer include R0 , and since ` is the only state whose transition probabilities have changed, all states in R have paths to ` in k . It follows that ` ∈ R. Now let π be the steady-state vector for R in the Markov chain for k . Since π` > 0, (3.58) and (3.59) are still valid for this situation. Let k̃ be a decision vector for which k̃i = ki for each i ∈ R. Using inherent reachability, we can also choose k̃i for each i ∈ / R so that ` is reachable from i (see Exercise 3.31). Thus k̃ is a unichain with the recurrent class R. Since k̃ has the same transition probabilities and rewards in R as k , we see that g̃ = πr k and thus g̃ > g 0 . The ﬁnal lemma now includes all cases not in Lemmas 3.6.1 and 3.6.2 Lemma 3.6.3. Assume that ` ∈ / R0 and that R0 is accessible from ` in k. Then k is a unichain with the same recurrent set R0 as k0 . The gain per stage g is equal to g 0 and the relative-gain vector w of k satisﬁes w0 ≤ w with w`0 < w` and wi0 = wi for i ∈ R0 . (3.60) Proof: Since k 0 is a unichain, k 0 contains a path from each state to R0 . If such a path does not go through state `, then k also contains that path. If such a path does go through `, then that path can be replaced in k by the same path to ` followed by a path in k from ` to R0 . Thus R0 is accessible from all states in k . Since the states accessible from R0 are unchanged from k 0 to k , k is still a unichain with the recurrent set R0 and state ` is still transient. If we write out the deﬁning equation (3.37) for w 0 component by component, we get k0 wi0 + g 0 = ri i + X k0 Piji wj0 . (3.61) j k0 Consider the set of these equations for which i ∈ R0 . Since Piji = 0 for all transient j in k 0 , these are the same relative-gain equations as for the Markov chain restricted to R0 . Therefore w 0 is uniquely deﬁned for i ∈ R0i by this restricted set of equations. These equations are not changed in going from k 0 to k , so it follows that wi = wi0 for i ∈ R0 . We have also seen that the steady-state vector π 0 is determined solely by the transition probabilities in the recurrent class, so π 0 is unchanged from k 0 to k , and g = g 0 . Finally, consider the diﬀerence between the relative-gain equations for k 0 in 3.61 and those for k . Since g 0 = g, ¥ X≥ k k0 k0 wi − wi0 = riki − ri i + Piji wj − Piji wj0 . (3.62) j For all i = 6 `, this simpliﬁes to wi − wi0 = X j Pijki (wj − wj0 ). (3.63) CHAPTER 3. FINITE-STATE MARKOV CHAINS For i = `, (3.62) can be rewritten as w` − w`0 = X j  k0 P`kj` (wj − wj0 ) + r`k` − r` `  ¥ X≥ k k0 + P`j` wj0 − P`j` wj0  . (3.64) j The quantity in brackets must be positive because of step 4 of the algorithm, and we denote it as r̂` − r̂`0 . If we also deﬁne r̂i = r̂i0 for i 6= `, then we can apply the last part of Corollary 3.5.1 (using r̂ and r̂ 0 as reward vectors) to conclude that w ≥ w 0 with w` > w`0 . We now see that each iteration of the algorithm either increases the gain per stage or holds the gain per stage the same and increases the relative-gain vector w . Thus the sequence of policies found by the algorithm can never repeat. Since there are a ﬁnite number of stationary policies, the algorithm must eventually terminate at step 3. This means that the optimal dynamic policy using the ﬁnal reward vector w 0 for the terminating decision vector k 0 must in fact be the stationary policy k 0 . The question now arises whether the optimal dynamic policy using some other ﬁnal reward vector can be substantially better than that using w 0 . The answer is quite simple and is developed in Exercise 3.30. It is shown there that if u and u 0 are arbitrary ﬁnal reward vectors used on the dynamic programming algorithm, then v ∗ (n, u) and v ∗ (n, u 0 ) are related by v ∗ (n, u) ≤ v ∗ (n, u 0 ) + αe, where α = maxi (ui − u0i ). Using w 0 for u 0 , it is seen that the gain per stage of dynamic programming, with any ﬁnal reward vector, is at most the gain g 0 of the stationary policy at the termination of the policy-improvement algorithm. The above results are summarized in the following theorem. Theorem 3.6.2. For any inherently reachable ﬁnite-state Markov decision problem, the policy-improvement algorithm terminates with a stationary policy k0 that is the same as the solution to the dynamic programming algorithm using w0 as the ﬁnal reward vector. The gain per stage g 0 of this stationary policy maximizes the gain per stage over all stationary policies and over all ﬁnal-reward vectors for the dynamic programming algorithm. One remaining issue is the question whether the relative-gain vector found by the policyimprovement algorithm is in any sense optimal. The example in Figure 3.11 illustrates two diﬀerent solutions terminating the policy-improvement algorithm. They each have the same gain (as guaranteed by Theorem 3.6.2) but their relative-gain vectors are not ordered. In many applications such as variations on the shortest path problem, the interesting issue is what happens before the recurrent class is entered, and there is often only one recurrent class and one set of decisions within that class of interest. The following corollary shows that in this case, the relative-gain vector for the stationary policy that terminates the algorithm is maximal not only among the policies visited by the algorithm but among all policies with the same recurrent class and the same decisions within that class. The proof is almost the same as that of Lemma 3.6.3 and is carried out in Exercise 3.33. 3.7. SUMMARY (2) ✿ 1♥ ✘  ② r1 = − 20 (1) P11 =1 (1) r1 =0 (2) P12 = 1 (1) P21 = 1 (2) ③ ♥  2  ② r2 =1 (1) r2 =2 (2) P23 = 1 (1) P32 = 1 (2) ③ ♥  3  ② r2 = − 20 (2) P33 = 1 (1) r2 =0 Figure 3.11: A Markov decision problem in which there are two unichain decision vectors (one left-going, and the other right-going). For each, (3.50) is satisﬁed and the gain per stage is 0. The dynamic programming algorithm (with no ﬁnal reward) is stationary but has two recurrent classes, one of which is {3}, using decision 2 and the other of which is {1, 2}, using decision 1 in each state. Corollary 3.6.1. Assume the policy improvement algorithm terminates with the recurrent class R0 , the decision vector k0 , and the relative-gain vector w0 . Then for any stationary policy that has the recurrent class R0 and a decision vector k satisfying ki = ki0 for all i ∈ R0 , the relative gain vector w satisﬁes w ≤ w0 . 3.7 Summary This chapter has developed the basic results about ﬁnite-state Markov chains. It was shown that the states of any ﬁnite-state chain can be partitioned into classes, where each class is either transient or recurrent, and each class is periodic or aperiodic. If a recurrent class is periodic of period d, then the states in that class can be partitioned into d subsets where each subset has transitions only into the next subset. The transition probabilities in the Markov chain can be represented as a matrix [P ], and the n-step transition probabilities are given by the matrix product [P n ]. If the chain is ergodic, i.e., one aperiodic recurrent class, then the limit of the n-step transition probabilities become independent of the initial state, i.e., limn→1 Pijn = πj where π = (π1 , . . . , πM ) is called the steady-state probability. Thus the limiting value of [P n ] is an M by M matrix whose rows π are all the same, i.e., the P limiting matrix is the P product eπ . The steady state probabilities are uniquely speciﬁed by j πi Pij = πj and i πi = 1. That unique solution must satisfy πi > 0 for all i. The same result holds (see Theorem 3.3.2) for aperidodic unichains with the exception that πi = 0 for all transient states. The eigenvalues and eigenvectors of [P ] are useful in many ways, but in particular provide precise results about how Pijn approaches πj with increasing n. An eigenvalue equal to 1 always exists, and its multiplicity is equal to the number of recurrent classes. For each recurrent class, there is a left eigenvector π of eigenvalue 1. It is the steady-state vector for the given recurrent class. If a recurrent class is periodic with period d, then there are d corresponding eigenvalues of magnitude 1 uniformly spaced around the unit circle. The left eigenvector corresponding to each is nonzero only on that periodic recurrent class. All other eigenvalues of [P ] are less than 1 in magnitude. If the eigenvectors of the entire set of eigenvalues span M dimensional space, then [P n ] can be represented by (3.30) which shows explicitly how steady state is approached for aperiodic recurrent classes of states. If the eigenvectors do not span M-space, then (3.30) can be replaced by a Jordan form. CHAPTER 3. FINITE-STATE MARKOV CHAINS For an arbitrary ﬁnite-state Markov chain, if the initial state is transient, then the Markov chain will eventually enter a recurrent state, and the probability that this takes more than n steps approaches zero geometrically in n; Exercise 3.18 shows how to ﬁnd the probability that each recurrent class is entered. Given an entry into a particular recurrent class, the results about recurrent chains can be used to analyze the behavior within that class. The results about Markov chains were extended to Markov chains with rewards. The use of reward functions (or cost functions) provides a systematic way to approach a large class of problems ranging from ﬁrst-passage times to dynamic programming. For unichains, the key result here is Theorem 3.5.2, which provides both an exact expression and an asymptotic expression for the expected aggregate reward over n stages. Markov chains with rewards and multiple recurrent classes are best handled by considering the individual recurrent classes separately. Finally, the results on Markov chains with rewards were used to understand Markov deci sion theory. The Bellman dynamic programming algorithm was developed, and the policy improvement algorithm was discussed and analyzed. Theorem 3.6.2 demonstrated the re lationship between the optimal dynamic policy and the optimal stationary policy. This section provided only an introduction to dynamic programming and omitted all discussion of discounting (in which future gain is considered worth less than present gain because of interest rates). The development was also restricted to ﬁnite-state spaces. For a review of vectors, matrices, and linear algebra, see any introductory text on linear algebra such as Strang [19]. For further reading on Markov decision theory and dynamic programming, see Bertsekas, [3]. Bellman [1] is of historic interest and quite readable.

Finite-State Markov Chains

Related Documents

Recommended Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock