Chapter 4FINITE-STATE MARKOVCHAINS4.1 IntroductionThe 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 defined for all real t > 0. The Markov chainsto be discussed in this chapter are stochastic processes defined only at integer values oftime, 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}. Werefer to these processes as integer-time processes. An integer-time process {Xn; n  0} canalso be viewed as a process {X(t); t  0} defined for all real t by taking X(t) = Xnforn  t < n + 1, but since changes occur only at integer times, it is usually simpler to viewthe process only at those integer times.In general, for Markov chains, the set of possible values for each rv Xnis a countable set S.If S is countably infinite, it is usually taken to be S = {0, 1, 2, . . . }, whereas if S is finite,it is usually taken to be S = {1, . . . , M}. In this chapter (except for Theorems 4.2.2 and4.2.3), we restrict attention to the case in which S is finite, i.e., processes whose samplefunctions are sequences of integers, each between 1 and M. There is no special significanceto using integer labels for states, and no compelling reason to include 0 for the countablyinfinite case and not for the finite case. For the countably infinite case, the most commonapplications come from queueing theory, where the state often represents the number ofwaiting customers, which might be zero. For the finite case, we often use vectors andmatrices, where positive integer labels simplify the notation. In some examples, it will bemore convenient to use more illustrative labels for states.Definition 4.1.1. A Markov chain is an integer-time process, {Xn, n  0} for which thesample values for each rv Xn, n  1, lie in a countable set S and depend on the past onlythrough the most recent rv Xn1. More specifically, for all positive integers n, and for allchoices of i, j, k, . . . , ` in S,Pr{Xn=j | Xn1=i, Xn2=k, . . . , X0=`} = Pr{Xn=j | Xn1=i} (4.1)1624.1. INTRODUCTION 163for all conditioning events Xn1=i, Xn2=k, . . . , X0=` of positive probability. Furthermore,Pr{Xn=j | Xn1=i} depends only on i and j (not n) and is denoted byPr{Xn=j | Xn1=i} = Pij. (4.2)The initial state X0has an arbitrary probability distribution. A finite-state Markov chainis a Markov chain in which S is finite.Equations such as (4.1) are often easier to read if they are abbreviated asPr{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 (4.1).The rv Xnis called the state of the chain at time n. The possible values for the state attime n, namely {1, . . . , M} or {0, 1, . . . } are also generally called states, usually withouttoo much confusion. Thus Pijis the probability of going to state j given that the previousstate is i; the new state, given the previous state, is independent of all earlier states. Theuse of the word state here conforms to the usual idea of the state of a system — the stateat a given time summarizes everything about the past that is relevant to the future.Definition 4.1.1 is used by some people as the definition of a homogeneous Markov chain.For them, Markov chains include more general cases where the transition probabilities canvary with n. Thus they replace (4.1) and (4.2) byPr{Xn=j | Xn1=i, Xn2=k, . . . , X0=`} = Pr{Xn=j | Xn1=i} = Pij(n). (4.3)We will call a process that obeys (4.3), with a dependence on n, a non-homogeneous Markovchain. We will discuss only the homogeneous case, with no dependence on n, and thusrestrict the definition to that case. Not much of general interest can be said about non-homogeneous chains.1An initial probability distribution for X0, combined with the transition probabilities {Pij}(or {Pij(n)} for the non-homogeneous case), define the probabilities for all events in theMarkov chain.Markov chains can be used to model an enormous variety of physical phenomena and can beused to approximate many other kinds of stochastic processes such as the following example:Example 4.1.1. Consider an integer-time process {Zn; n  0} where the Znare finiteinteger-valued rv’s as in a Markov chain, but each Zndepends probabilistically on theprevious m rv’s, Zn1, Zn2, . . . , Znm. In other words, using abbreviated notation,Pr{Zn| Zn1, Zn2, . . . , Z0}= Pr{Zn| Zn1, . . . Znm}. (4.4)1On the other hand, we frequently find situations where a small set of rv’s, say W, X, Y, Z satisfy theMarkov condition that Pr{Z | Y, X, W } = Pr{Z | Y } and Pr{Y | X, W } = Pr{Y | X} but where the condi-tional probability Pr{Z=j | Y =i} is not necessarily the same as Pr{Y =j | X=i}. In other words, Markovchains imply homogeneity here, whereas the Markov condition do es not.164 CHAPTER 4. FINITE-STATE MARKOV CHAINSWe now show how to view the condition on the right side of (4.4), i.e., (Zn1, Zn2, . . . , Znm)as the state of the process at time n  1. We can rewrite (4.4) asPr{Zn, Zn1, . . . , Znm+1| Zn1, . . . , Z0}= Pr{Zn, . . . , Znm+1| Zn1, . . . Znm},since, for each side of the equation, any given set of values for Zn1, . . . , Znm+1on theright side of the conditioning sign specifies those values on the left side. Thus if we defineXn1= (Zn1, . . . , Znm) for each n, this simplifies toPr{Xn| Xn1, . . . , Xm1} = Pr{Xn| Xn1} .We see that by expanding the state space to include m-tuples of the rv’s Zn, we haveconverted the m dependence over time to a unit dependence over time, i.e., a Markovprocess is defined using the expanded state space.Note that in this new Markov chain, the initial state is Xm1= (Zm1, . . . , Z0), so onemight want to shift the time axis to start with X0.Markov chains are often described by a directed graph (see Figure 4.1 a). In this graphicalrepresentation, there is one node for each state and a directed arc for each non-zero transitionprobability. If Pij= 0, then the arc from node i to node j is omitted, so the di↵erencebetween zero and non-zero transition probabilities stands out clearly in the graph. Theclassification of states, as discussed in Section 4.2, is determined by the set of transitionswith non-zero probabilities, and thus the graphical