Countable-State Markov Chains

Chapter 5 COUNTABLE-STATE MARKOV CHAINS 5.1 Introduction and classification of states Markov chains with a countably-infinite state space (more briefly, countable-state Markov chains) exhibit some types of behavior not possible for chains with a finite state space. With the exception of the first example to follow and the section on branching processes, we label the states by the nonnegative integers. This is appropriate when modeling things such as the number of customers in a queue, and causes no loss of generality in other cases. The following two examples give some insight into the new issues posed by countable state spaces. Example 5.1.1. Consider the familiar Bernoulli process {Sn = X1 + · · · Xn ; n 1} where {Xn ; n 1} is an IID binary sequence with pX (1) = p and pX ( 1) = (1 p) = q. The sequence {Sn ; n 1} is a sequence of integer random variables (rv’s ) where Sn = Sn 1 + 1 with probability p and Sn = Sn 1 1 with probability q. This sequence can be modeled by the Markov chain in Figure 5.1. ... q n 2X y p q=1 z n X 1X y p p q z n X 0 y X p q z n X 1 X y p q X n z 2 ... Figure 5.1: A Markov chain with a countable state space modeling a Bernoulli process. If p > 1/2, then as time n increases, the state Xn becomes large with high probability, i.e., limn!1 Pr{Xn j} = 1 for each integer j. Similarly, for p < 1/2, the state becomes highly negative. Using the notation of Markov chains, P0nj is the probability of being in state j at the end of the nth transition, conditional on starting in state 0. The final state j is the number of positive transitions k less the number of negative transitions n k, i.e., j = 2k n. Thus, 5.1. INTRODUCTION AND CLASSIFICATION OF STATES using the binomial formula, ✓ ◆ n k n n P0j = p q k k where k = j+n ; 2 j + n even. (5.1) All states in this Markov chain communicate with all other states, and are thus in the same class. The formula makes it clear that this class, i.e., the entire set of states in the Markov chain, is periodic with period 2. For n even, the state is even and for n odd, the state is odd. What is more important than the periodicity, however, is what happens to the state prob­ abilities for large n. As we saw in (1.88) while proving the central limit theorem for the binomial case, P0nj 1 ⇠ p exp 2⇡npq  (k np)2 2pqn where k = j+n ; 2 j + n even. (5.2) In other words, P0nj , as a function of j, looks like a quantized form of the Gaussian density for large n. The significant terms of that distribution are close to k = np, i.e., to j = n(2p 1). For p > 1/2, the state increases with increasing n. Its distribution is centered at n(2p 1), p but the distribution is also spreading out as n. For p < 1/2, the state similarly decreases and spreads out. The most interesting case is p = 1/2, where the distribution remains p centered at 0, but due to the spreading, the PMF approaches 0 as 1/ n for all j. For this example, then, the probability of each state approaches zero as n ! 1, and this holds for all choices of p, 0 < p < 1. If we attempt to define a steady-state probability as 0 for each state, then these probabilities do not sum to 1, so they cannot be viewed as a steady-state distribution. Thus, for countable-state Markov chains, the notions of recurrence and steady-state probabilities will have to be modified from that with finitestate Markov chains. The same type of situation occurs whenever {Sn ; n 1} is a sequence of sums of arbitrary IID integer-valued rv’s. Most countable-state Markov chains that are useful in applications are quite di↵erent from Example 5.1.1, and instead are quite similar to finite-state Markov chains. The following example bears a close resemblance to Example 5.1.1, but at the same time is a countablestate Markov chain that will keep reappearing in a large number of contexts. It is a special case of a birth-death process, which we study in Section 5.2. Example 5.1.2. Figure 5.2 is similar to Figure 5.1 except that the negative states have been eliminated. A sequence of IID binary rv’s {Xn ; n 1}, with pX (1) = p and pX ( 1) = q = 1 p, controls the state transitions. Now, however, Sn = max(0, Sn 1 + Xn , so that Sn is a nonnegative rv. All states again communicate, and because of the self transition at state 0, the chain is aperiodic. For p > 1/2, transitions to the right occur with higher frequency than transitions to the left. Thus, reasoning heuristically, we expect the state Sn at time n to drift to the right with increasing n. Given S0 = 0, the probability P0nj of being in state j at time n, should then tend to zero for any fixed j with increasing n. As in Example 5.1.1, we see that a CHAPTER 5. COUNTABLE-STATE MARKOV CHAINS q ⇠ 0n : y X p q=1 p z n X 1 y X p q z n X 2 y X p q z n X 3 y X p q z n X 4 ... Figure 5.2: A Markov chain with a countable state space. If p > 1/2, then as time n increases, the state Xn becomes large with high probability, i.e., limn!1 Pr{Xn 1 for each integer j. j} = steady state does not exist. In more poetic terms, the state wanders o↵ into the wild blue yonder. One way to understand this chain better is to look at what happens if the chain is truncated The truncation of Figure 5.2 to k states is analyzed in Exercise 3.9. The solution there defines ⇢ = p/q and shows that if ⇢ 6= 1, then ⇡i = (1 ⇢)⇢i /(1 ⇢k ) for each i, 0  i < k. For ⇢ = 1, ⇡i = 1/k for each i. For ⇢ < 1, the limiting behavior as k ! 1 is ⇡i = (1 ⇢)⇢i . Thus for ⇢ < 1 ( p < 1/2), the steady state probabilities for the truncated Markov chain approaches a limit which we later interpret as the steady state probabilities for the untruncated chain. For ⇢ > 1 (p > 1/2), on the other hand, the steady-state probabilities for the truncated case are geometrically decreasing from the right, and the states with significant probability keep moving to the right as k increases. Although the probability of each fixed state j approaches 0 as k increases, the truncated chain never resembles the untruncated chain. Perhaps the most interesting case is that where p = 1/2. The nth order transition proba­ bilities, P0nj can be calculated exactly for this case (see Exercise 5.3) and are very similar to those of Example 5.1.1. In particular, 8 > n n > > for j 0, (j + n) even > (j+n)/2 2 > < n P0j = (5.3) > > > > > n n : for j 0, (j + n) odd (j+n+1)/2 2 r  2 2 j ⇠ exp for j 0. (5.4) ⇡n 2n n for large n is approximated by the positive side of a quantized Gaussian We see that P0j distribution. It looks like the positive side of the PMF of (5.1) except that it is no longer p periodic. For large n, P0nj is concentrated in a region of width n around j = 0, and the p PMF goes to 0 as 1/ n for each j as n ! 1. Fortunately, the strange behavior of Figure 5.2 when p q is not typical of the Markov chains of interest for most applications. For typical countable-state Markov chains, a steady state does exist, and the steady-state probabilities of all but a finite number of states (the number depending on the chain and the application) can almost be ignored for numerical calculations. 5.1. INTRODUCTION AND CLASSIFICATION OF STATES 5.1.1 Using renewal theory to classify and analyze Markov chains The matrix approach used to analyze finite-state Markov chains does not generalize easily to the countable-state case. Fortunately, renewal theory is ideally suited for this purpose, especially for analyzing the long term behavior of countable-state Markov chains. We must first revise the definition of recurrent states. The definition for finite-state Markov chains does not apply here, and we will see that, under the new definition, the Markov chain in Figure 5.2 is recurrent for p  1/2 and transient for p > 1/2. For p = 1/2, the chain is called null-recurrent, as explained later. In general, we will find that for a recurrent state j, the sequence of subsequent entries to state j, conditional on starting in j, forms a renewal process. The renewal theorems then specify the time-average relative-frequency of state j, the limiting probability of j with increasing time and a number of other relations. We also want to understand the sequence of epochs at which one state, say j, is entered, conditional on starting the chain at some other state, say i. We will see that, subject to the classification of states i and j, this gives rise to a delayed renewal process. In preparing to study these renewal processes and delayed renewal process, we need to understand the inter-renewal intervals. The probability mass functions (PMF’s) of these intervals are called first-passage-time probabilities in the notation of Markov chains. Definition 5.1.1. The first-passage-time probability, fij (n), of a Markov chain is the prob­ ability, conditional on X0 = i, that the first subsequent entry to state j occurs at discrete epoch n. That is, fij (1) = Pij and for n 2, fij (n) = Pr{Xn =j, Xn 1 6=j, Xn 2 6=j, . . . , X1 6=j|X0 =i} . (5.5) The distinction between fij (n) and Pijn = Pr{Xn = j|X0 = i} is that fij (n) is the probability that the first entry to j (after time 0) occurs at time n, whereas Pijn is the probability that any entry to j occurs at time n, both conditional on starting in state i at time 0. The definition in (5.5) also applies for j = i; fii (n) is thus the probability, given X0 = i, that the first occurrence of state i after time 0 occurs at time n. Since the transition probabilities are independent of time, fkj (n 1) is also the probability, given X1 = k, that the first subsequent occurrence of state j occurs at time n. Thus we can calculate fij (n) from the iterative relations X fij (n) = Pik fkj (n 1); n > 1; fij (1) = Pij . (5.6) k=j 6 Note that the sum excludes k = j, since Pij fjj (n 1) is the probability that state j occurs first at epoch at epoch n. Note also from the Chapman-Kolmogorov equation P 1 andn next 1 n that Pij = k Pik Pkj . In other words, the only di↵erence between the iterative expressions to calculate fij (n) and Pijn is the exclusion of k = j in the expression for fij (n). With this iterative approach, the first-passage-time probabilities fij (n) for a given n must be calculated for all i before proceeding to calculate them for the next larger value of n. This also gives us fjj (n), although fjj (n) is not used in the iteration. CHAPTER 5. COUNTABLE-STATE MARKOV CHAINS Let Fij (n), for n 1, be the probability, given X0 = i, that state j occurs at some time between 1 and n inclusive. Thus, Fij (n) = n X fij (m). (5.7) m=1 For each i, j, Fij (n) is non-decreasing in n and (since it is a probability) is upper bounded by 1. Thus Fij (1) (i.e., limn!1 Fij (n)) must exist, and is the probability, given X0 = i, that state j will ever occur. If Fij (1) = 1, then, given X0 = i, it is certain (with probability 1) that the chain will eventually enter state j. In this case, we can define a random variable (rv) Tij , conditional on X0 = i, as the first-passage time from i to j. Then fij (n) is the PMF of Tij and Fij (n) is the distribution function of Tij . If Fij (1) < 1, then Tij is a defective rv, since, with some non-zero probability, there is no first-passage to j. Defective rv’s are not considered to be rv’s (in the theorems here or elsewhere), but they do have many of the properties of rv’s. The first-passage time Tjj from a state j back to itself is of particular importance. It has the PMF fjj (n) and the distribution function Fjj (n). It is a rv (as opposed to a defective rv) if Fjj (1) = 1, i.e., if the state eventually returns to state j with probability 1 given that it starts in state j. This leads to the definition of recurrence. Definition 5.1.2. A state j in a countable-state Markov chain is recurrent if Fjj (1) = 1. It is transient if Fjj (1) < 1. Thus each state j in a countable-state Markov chain is either recurrent or transient, and is recurrent if and only if an eventual return to j (conditional on X0 = j) occurs with probability 1. Equivalently, j is recurrent if and only if Tjj , the time of first return to j, is a rv. Note that for the special case of finite-state Markov chains, this definition is consistent with the one in Chapter 3. For a countably-infinite state space, however, the earlier definition is not adequate. An example is provided by the case p > 1/2 in Figure 5.2. Here i and j communicate for all states i and j, but it is intuitively obvious (and shown in Exercise 5.2, and further explained in Section 5.2) that each state is transient. If the initial state X0 of a Markov chain is a recurrent state j, then Tjj is the integer time of the first recurrence of state j. At that recurrence, the Markov chain is in the same state j as it started in, and the discrete interval from Tjj to the next occurrence of state j, say Tjj,2 has the same distribution as Tjj and is clearly independent of Tjj . Similarly, the sequence of successive recurrence intervals, Tjj , Tjj,2 , Tjj,3 , . . . is a sequence of IID rv’s. This sequence of recurrence intervals1 is then the sequence of inter-renewal intervals of a renewal process, where each renewal interval has the distribution of Tjj . These inter-renewal intervals have the PMF fjj (n) and the distribution function Fjj (n). Since results about Markov chains depend very heavily on whether states are recurrent or transient, we will look carefully at the probabilities Fij (n). Substituting (5.6) into (5.7), we 1 Note that in Chapter 4 the inter-renewal intervals were denoted X1 , X2 , . . . , whereas here X0 , X1 , . . . , is the sequence of states in the Markov chain and Tjj , Tjj,2 , . . . , is the sequence of inter-renewal intervals. 5.1. INTRODUCTION AND CLASSIFICATION OF STATES obtain Fij (n) = Pij + X Pik Fkj (n 1); n > 1; Fij (1) = Pij . (5.8) k=j 6 P To understand the expression P Pij + k6=j Pik Fkj (n 1), note P that the first term, Pij , is fij (1) and the second term, k6=j Pik Fkj (n 1), is equal to n`=2 fij (`). We have seen that Fij (n) P is non-decreasing in n and upper bounded by 1, so the limit Fij (1) must exist. Similarly, k=j PikP Fkj (n 1) is non-decreasing in n and upper bounded by 1, 6 so it also has a limit, equal to k=j Pik Fkj (1). Thus 6 Fij (1) = Pij + X Pik Fkj (1). (5.9) k=j 6 For any given j, (5.9) can be viewed as a set of linear equations in the variables Fij (1) for each state i. There is not always a unique solution to this set of equations. In fact, the set of equations X xij = Pij + Pik xkj ; all states i (5.10) k=j 6 always has a solution in which xij = 1 for all i. If state j is transient, however, there is another solution in which xij is the true value of Fij (1) and Fjj (1) < 1. Exercise 5.1 shows that if (5.10) is satisfied by a set of nonnegative numbers {xij ; 1  i  J}, then Fij (1)  xij for each i. We have defined a state j to be recurrent if Fjj (1) = 1 and have seen that if j is recurrent, then the returns to state j, given X0 = j form a renewal process. All of the results of renewal theory can then be applied to the random sequence of integer times at which j is entered. The main results from renewal theory that we need are stated in the following lemma. Lemma 5.1.1. Let {Njj (t); t 0} be the counting process for occurrences of state j up to time t in a Markov chain with X0 = j. The following conditions are then equivalent. 1. state j is recurrent. 2. limt!1 Njj (t) = 1 with probability 1. 3. limt!1 E [Njj (t)] = 1. P n = 1. 4. limt!1 1nt Pjj Proof: First assume that j is recurrent, i.e., that Fjj (1) = 1. This implies that the interrenewal times between occurrences of j are IID rv’s, and consequently {Njj (t); t 1} is a renewal counting process. Recall from Lemma 4.3.1 of Chapter 4 that, whether or not the expected inter-renewal time E [Tjj ] is finite, limt!1 Njj (t) = 1 with probability 1 and limt!1 E [Njj (t)] = 1. CHAPTER 5. COUNTABLE-STATE MARKOV CHAINS Next assume that state j is transient. In this case, the inter-renewal time Tjj is not a rv, so {Njj (t); t 0} is not a renewal process. An eventual return to state j occurs only with probability Fjj (1) < 1, and, since subsequent returns are independent, the total number of returns to state j is a geometric rv with mean Fjj (1)/[1 Fjj (1)]. Thus the total number of returns is finite with probability 1 and the expected total number of returns is finite. This establishes the first three equivalences. n , the probability of a transition to state j at integer time n, is equal Finally, note that Pjj to the expectation of a transition to j at integer time n (i.e., a single transition occurs n and 0 occurs otherwise). Since N (t) is the sum of the number of with probability Pjj jj transitions to j over times 1 to t, we have X n E [Njj (t)] = Pjj , 1nt which establishes the final equivalence. Our next objective is to show that all states in the same class as a recurrent state are also recurrent. Recall that two states are in the same class if they communicate, i.e., each has a path to the other. For finite-state Markov chains, the fact that either all states in the same class are recurrent or all transient was relatively obvious, but for countable-state Markov chains, the definition of recurrence has been changed and the above fact is no longer obvious. Lemma 5.1.2. If state j is recurrent and states i and j are in the same class, i.e., i and j communicate, then state i is also recurrent. P n = 1. Since j and i comProof: From Lemma 5.1.1, state j satisfies limt!1 1nt Pjj municate, there are integers m and k such that Pijm > 0 and Pjik > 0. For every walk from state j to j in n steps, there is a corresponding walk from i to i in m + n + k steps, going from i to j in m steps, j to j in n steps, and j back to i in k steps. Thus Piim+n+k 1 X n=1 Piin n k Pijm Pjj Pji 1 X n=1 Piim+n+k Pijm Pjik 1 X n=1 n Pjj = 1. Thus, from Lemma 5.1.1, i is recurrent, completing the proof. Since each state in a Markov chain is either recurrent or transient, and since, if one state in a class is recurrent, all states in that class are recurrent, we see that if one state in a class is transient, they all are. Thus we can refer to each class as being recurrent or transient. This result shows that Theorem 3.2.1 also applies to countable-state Markov chains. We state this theorem separately here to be specific. Theorem 5.1.1. For a countable-state Markov chain, either all states in a class are tran­ sient or all are recurrent. We next look at the delayed counting process {Nij (n); n 1}. If this is a delayed renewal counting process, then we can use delayed renewal processes to study whether the e↵ect of 5.1. INTRODUCTION AND CLASSIFICATION OF STATES the initial state eventually dies out. If state j is recurrent, we know that {Njj (n); n 1} is a renewal counting process. In addition, in order for {Nij (n); n 1} to be a delayed renewal counting process, it is necessary for the first-passage time to be a rv, i.e., for Fij (1) to be 1. Lemma 5.1.3. Let states i and j be in the same recurrent class. Then Fij (1) = 1. Proof: Since i is recurrent, the number of visits to i by time t, given X0 = i, is a renewal counting process Nii (t). There is a path from i to j, say of probability ↵ > 0. Thus the probability that the first return to i occurs before visiting j is at most 1 ↵. The probability that the second return occurs before visiting j is thus at most (1 ↵)2 and the probability that the nth occurs without visiting j is at most (1 ↵)n . Since i is visited infinitely often with probability 1 as n ! 1, the probability that j is never visited is 0. Thus Fij (1) = 1. Lemma 5.1.4. Let {Nij (t); t 0} be the counting process for transitions into state j up to time t for a Markov chain given X0 = i = 6 j. Then if i and j are in the same recurrent class, {Nij (t); t 0} is a delayed renewal process. Proof: From Lemma 5.1.3, Tij , the time until the first transition into j, is a rv. Also Tjj is a rv by definition of recurrence, and subsequent intervals between occurrences of state j are IID, completing the proof. If Fij (1) = 1, we have seen that the first-passage time from i to j is a rv, i.e., is finite with probability 1. In this case, the mean time T ij to first enter state j starting from state i is of interest. Since Tij is a nonnegative random variable, its expectation is the integral of its complementary distribution function, T ij = 1 + 1 X (1 Fij (n)). (5.11) n=1 It is possible to have Fij (1) = 1 but T ij = 1. As will be shown in Section 5.2, the chain in Figure 5.2 satisfies Fij (1) = 1 and T ij < 1 for p < 1/2 and Fij (1) = 1 and T ij = 1 for p = 1/2. As discussed before, Fij (1) < 1 for p > 1/2. This leads us to the following definition. Definition 5.1.3. A state j in a countable-state Markov chain is positive-recurrent if Fjj (1) = 1 and T jj < 1. It is null-recurrent if Fjj (1) = 1 and T jj = 1. Each state of a Markov chain is thus classified as one of the following three types — positiverecurrent, null-recurrent, or transient. For the example of Figure 5.2, null-recurrence lies on a boundary between positive-recurrence and transience, and this is often a good way to look at null-recurrence. Part f) of Exercise 6.3 illustrates another type of situation in which null-recurrence can occur. Assume that state j is recurrent and consider the renewal process {Njj (t); t 0}. The limiting theorems for renewal processes can be applied directly. From the strong law for CHAPTER 5. COUNTABLE-STATE MARKOV CHAINS renewal processes, Theorem 4.3.1, lim Njj (t)/t = 1/T jj t!1 with probability 1. (5.12) From the elementary renewal theorem, Theorem 4.6.1, lim E [Njj (t)/t] = 1/T jj . t!1 (5.13) Equations (5.12) and (5.13) are valid whether j is positive-recurrent or null-recurrent. Next we apply Blackwell’s theorem to {Njj (t); t 0}. Recall that the period of a given state j in a Markov chain (whether the chain has a countable or finite number of states) is n > 0. If this period the greatest common divisor of the set of integers n > 0 such that Pjj is d, then {Njj (t); t 0} is arithmetic with span (i.e., renewals occur only at times that are multiples of ). From Blackwell’s theorem in the arithmetic form of (4.61), lim Pr{Xn = j | X0 = j} = /T jj . n!1 (5.14) If state j is aperiodic (i.e., = 1), this says that limn!1 Pr{Xn = j | X0 = j} = 1/T jj . Equations (5.12) and (5.13) suggest that 1/T jj has some of the properties associated with a steady-state probability of state j, and (5.14) strengthens this if j is aperiodic. For a Markov chain consisting of a single class of states, all positive-recurrent, we will strengthen this association further in Theorem 5.1.4 by showing that there is a unique P steady-state distribution, {⇡ , j 0} such that ⇡ = 1/T for all j and such that ⇡ = j j jj j i ⇡i Pij for P all j 0 and j ⇡j = 1. The following theorem starts this development by showing that (5.12-5.14) are independent of the starting state. Theorem 5.1.2. Let j be a recurrent state in a Markov chain and let i be any state in the same class as j. Given X0 = i, let Nij (t) be the number of transitions into state j by time t and let T jj be the expected recurrence time of state j (either finite or infinite). Then lim Nij (t)/t = 1/T jj t!1 with probability 1 lim E [Nij (t)/t] = 1/T jj . t!1 (5.15) (5.16) If j is also aperiodic, then lim Pr{Xn = j | X0 = i} = 1/T jj . n!1 (5.17) Proof: Since i and j are recurrent and in the same class, Lemma 5.1.4 asserts that {Nij (t); t 0} is a delayed renewal process for j 6= i. Thus (5.15) and (5.16) follow from Theorems 4.8.1 and 4.8.2 of Chapter 4. If j is aperiodic, then {Nij (t); t 0} is a delayed renewal process for which the inter-renewal intervals Tjj have span 1 and Tij has an integer span. Thus, (5.17) follows from Blackwell’s theorem for delayed renewal processes, Theorem 4.8.3. For i = j, (5.15-5.17) follow from (5.12-5.14), completing the proof. Theorem 5.1.3. All states in the same class of a Markov chain are of the same type — either all positive-recurrent, all null-recurrent, or all transient. 5.1. INTRODUCTION AND CLASSIFICATION OF STATES Proof: Let j be a recurrent state. From Theorem 5.1.1, all states in a class are recurrent or all are transient. Next suppose that j is positive-recurrent, so that 1/T jj > 0. Let i be in the same class as j, and consider the renewal-reward process on {Njj (t); t 0} for which R(t) = 1 whenever the process is in state i (i.e., if Xn = i, then R(t) = 1 for n  t < n + 1). The reward is 0 whenever the process is in some state other than i. Let E [Rn ] be the expected reward in an inter-renewal interval; this must be positive since i is accessible from j. From the strong law for renewal-reward processes, Theorem 4.4.1, Z t 1 E [Rn ] lim R(⌧ )d⌧ = with probability 1. t!1 t T jj 0 The term on the left is the time-average number of transitions into state i, given X0 = j, and this is 1/T ii from (5.15). Since E [Rn ] > 0 and T jj < 1, we have 1/T ii > 0, so i is positive-recurrent. Thus if one state is positive-recurrent, the entire class is, completing the proof. If all of the states in a Markov chain are in a null-recurrent class, then 1/T jj = 0 for each state, and one might think of 1/T jj = 0 as a “steady-state” probability for j in the sense that 0 is both the time-average rate of occurrence of j and the limiting probability of j. However, these “probabilities” do not add up to 1, so a steady-state probability distribution does not exist. This appears rather paradoxical at first, but the example of Figure 5.2, with p = 1/2 will help to clarify the situation. As time n increases (starting in state i, say), the random variable Xn spreads out over more and more states around i,P and thus is less likely n to be in each individual state. For Peachn j, limn!1 Pij (n) = 0. Thus, j {limn!1 Pij } = 0. On the other hand, for every n, j Pij = 1. This is one of those unusual examples where a limit and a sum cannot be interchanged. In Chapter 3, we defined the steady-state distribution of a finite-state Markov chain as a probability vector ⇡ that satisfies ⇡ = ⇡ [P ]. Here we define {⇡i ; i 0} in the same way, as a set of numbers that satisfy X X ⇡j = ⇡i Pij for all j; ⇡j 0 for all j; ⇡j = 1. (5.18) i j Suppose that a set of numbers {⇡i ; i 0} satisfying (5.18) is chosen as the initial probability distribution for a Markov chain, i.e., if Pr{X0 = i} = ⇡i for all i. Then Pr{X1 = j} = P ⇡ P = ⇡ 0. The i ij j for all j, and, by induction, Pr{Xn = j} = ⇡j for all j and all n i fact that Pr{Xn = j} = ⇡j for all j motivates the definition of steady-state distribution above. Theorem 5.1.2 showed that 1/T jj is a ‘steady-state’ probability for state j, both in a time-average and a limiting ensemble-average sense. The following theorem brings these ideas together. An irreducible Markov chain is a Markov chain in which all pairs of states communicate. For finite-state chains, irreducibility implied a single class of recurrent states, whereas for countably infinite chains, an irreducible chain is a single class that can be transient, null-recurrent, or positive-recurrent. Theorem 5.1.4. Assume an irreducible Markov chain with transition probabilities {Pij }. If (5.18) has a solution, then the solution is unique, ⇡i = 1/T ii > 0 for all i 0, and the states are positive-recurrent. Also, if the states are positive-recurrent then (5.18) has a solution. CHAPTER 5. COUNTABLE-STATE MARKOV CHAINS Proof*: Let {⇡j ; j 0} satisfy (5.18) and be the initial distribution of the Markov chain, i.e., Pr{X0 =j} = ⇡j , j 0. Then, as shown above, Pr{Xn =j} = ⇡j for all n 0, j 0. Let Ñj (t) be the number of occurrences of any given state j from time 1 to t. Equating Pr{Xn =j} to the expectation of an occurrence of j at time n, we have, h i X (1/t)E Ñj (t) = (1/t) Pr{Xn =j} = ⇡j for all integers t 1. 1nt Conditioning this on the possible starting states i, and using the counting processes {Nij (t); t 0} defined earlier, h i X ej (t) = ⇡j = (1/t)E N ⇡i E [Nij (t)/t] for all integer t 1. (5.19) i For any given state i, let Tij be the time of the first occurrence of state j given X0 = i. Then if Tij < 1, we have Nij (t)  Nij (Tij + t). Thus, for all t 1, E [Nij (t)]  E [Nij (Tij + t)] = 1 + E [Njj (t)] . (5.20) The last step follows since the process is in state j at time Tij , and the expected number of occurrences of state j in the next t steps is E [Njj (t)]. Substituting (5.20) in (5.19) for each i, ⇡j  1/t + E [NP jj (t)/t)]. Taking the limit as t ! 1 and using (5.16), ⇡j  limt!1 E [Njj (t)/t]. Since i ⇡i = 1, there is at least one value of j for which ⇡j > 0, and for this j, limt!1 E [Njj (t)/t] > 0, and consequently limt!1 E [Njj (t)] = 1. Thus, from Lemma 5.1.1, state j is recurrent, and from Theorem 5.1.2, j is positive-recurrent. From Theorem 5.1.3, all states are then positive-recurrent. For any j and any integer M , (5.19) implies that X ⇡j ⇡i E [Nij (t)/t] for all t. (5.21) iM From Theorem 5.1.2, P limt!1 E [Nij (t)/t] = 1/T jj for all i. Substituting this into (5.21), we get ⇡j 1/T jj iM ⇡i . Since M is arbitrary, ⇡j 1/T jj . Since we already showed that ⇡j  limt!1 E [Njj (t)/t] = 1/T jj , we have ⇡j = 1/T jj for all j. This shows both that ⇡j > 0 for all j and that the solution to (5.18) is unique. Exercise 5.5 completes the proof by showing that if the states are positive-recurrent, then choosing ⇡j = 1/T jj for all j satisfies (5.18). In practice, it is usually easy to see whether a chain is irreducible. We shall also see by a number of examples that the steady-state distribution can often be calculated from (5.18). Theorem 5.1.4 then says that the calculated distribution is unique and that its existence guarantees that the chain is positive recurrent. Example 5.1.3. Age of a renewal process: Consider a renewal process {N (t); t > 0} in which the inter-renewal random variables {Wn ; n 1} are arithmetic with span 1. We will use a Markov chain to model the age of this process (see Figure 5.3). The probability that a renewal occurs at a particular integer time depends on the past only through the integer time back to the last renewal. The state of the Markov chain during a unit interval 5.1. INTRODUCTION AND CLASSIFICATION OF STATES ⇠ 0n : y X Y H P01 P00 P10 z n X 1 X n z 2 P12 P20 X n z 3 P23 P30 P34 P40 z n X 4 ... Figure 5.3: A Markov chain model of the age of a renewal process. will be taken as the age of the renewal process at the beginning of the interval. Thus, each unit of time, the age either increases by one or a renewal occurs and the age decreases to 0 (i.e., if a renewal occurs at time t, the age at time t is 0). Pr{W > n} is the probability that an inter-renewal interval lasts for more than n time units. We assume that Pr{W > 0} = 1, so that each renewal interval lasts at least one time unit. The probability Pn,0 in the Markov chain is the probability that a renewal interval has duration n + 1, given that the interval exceeds n. Thus, for example, P00 is the probability that the renewal interval is equal to 1. Pn,n+1 is 1 Pn,0 , which is Pr{W > n + 1} /Pr{W > n}. We can then solve for the steady state probabilities in the chain: for n > 0, ⇡n = ⇡n 1 Pn 1,n = ⇡n 2 Pn 2,n 1 Pn 1,n = ⇡0 P0,1 P1,2 . . . Pn 1,n . The first equality above results from the fact that state n, for n > 0 can be entered only from state n 1. The subsequent equalities come from substituting in the same expression for ⇡n 1 , then pn 2 , and so forth. ⇡n = ⇡0 Pr{W > 1} Pr{W > 2} Pr{W > n} ... = ⇡0 Pr{W > n} . Pr{W > 0} Pr{W > 1} Pr{W > n 1} (5.22) We have cancelled out all the cross terms above and used the fact that Pr{W > 0} = 1. Another way to see that ⇡n = ⇡0 Pr{W > n} is to observe that state 0 occurs exactly once in each inter-renewal interval; state n occurs exactly once in those inter-renewal intervals of duration n or more. Since the steady-state probabilities must sum to 1, (5.22) can be solved for ⇡0 as ⇡0 = P1 n=0 1 1 = . Pr{W > n} E [W ] (5.23) The second equality follows by expressing E [W ] as the integral of the complementary distri­ bution function of W . Combining this with (5.22), the steady-state probabilities for n 0 are ⇡n = Pr{W > n} . E [W ] (5.24) In terms of the renewal process, ⇡n is the probability that, at some large integer time, the age of the process will be n. Note that if the age of the process at an integer time is n, then the age increases toward n + 1 at the next integer time, at which point it either drops CHAPTER 5. COUNTABLE-STATE MARKOV CHAINS to 0 or continues to rise. Thus ⇡n can be interpreted as the fraction of time that the age of the process is between n and n + 1. Recall from (4.28) (and the fact that residual life and age are equally R n distributed) that the distribution function of the time-average age is given by FZ (n) = 0 Pr{W > w} dw/E [W ]. Thus, the probability that the age is between n and n+1 is FZ (n+1) FZ (n). Since W is an integer random variable, this is Pr{W > n} /E [W ] in agreement with our result here. The analysis here gives a new, and intuitively satisfying, explanation of why the age of a renewal process is so di↵erent from the inter-renewal time. The Markov chain shows the ever increasing loops that give rise to large expected age when the inter-renewal time is heavy tailed (i.e., has a distribution function that goes to 0 slowly with increasing time). These loops can be associated with the isosceles triangles of Figure 4.7. The advantage here is that we can associate the states with steady-state probabilities if the chain is recurrent. Even when the Markov chain is null-recurrent (i.e., the associated renewal process has infinite expected age), it seems easier to visualize the phenomenon of infinite expected age. 5.2 Birth-death Markov chains A birth-death Markov chain is a Markov chain in which the state space is the set of nonneg­ ative integers; for all i 0, the transition probabilities satisfy Pi,i+1 > 0 and Pi+1,i > 0, and for all |i j| > 1, Pij = 0 (see Figure 5.4). A transition from state i to i + 1 is regarded as a birth and one from i + 1 to i as a death. Thus the restriction on the transition probabilities means that only one birth or death can occur in one unit of time. Many applications of birth-death processes arise in queueing theory, where the state is the number of customers, births are customer arrivals, and deaths are customer departures. The restriction to only one arrival or departure at a time seems rather peculiar, but usually such a chain is a finely sampled approximation to a continuous-time process, and the time increments are then small enough that multiple arrivals or departures in a time increment are unlikely and can be ignored in the limit. ⇠ 0n : y X O p0 q1 z n X 1 y X O p1 q2 z n X 2 y X O p2 q3 z n X 3 X y O 1 p3 p3 q4 X n z 4 ... O q3 Figure 5.4: Birth-death Markov chain. We denote Pi,i+1 by pi and Pi,i 1 by qi . Thus Pii = 1 pi qi . There is an easy way to find the steady-state probabilities of these birth-death chains. In any sample function of the process, note that the number of transitions from state i to i + 1 di↵ers by at most 1 from the number of transitions from i + 1 to i. If the process starts to the left of i and ends to the right, then one more i ! i + 1 transition occurs than i + 1 ! i, etc. Thus if we visualize a renewal-reward process with renewals on occurrences of state i and unit reward on transitions from state i to i + 1, the limiting time-average number of transitions per unit time is ⇡i pi . Similarly, the limiting time-average number of transitions per unit time from 5.3. REVERSIBLE MARKOV CHAINS i + 1 to i is ⇡i+1 qi+1 . Since these two must be equal in the limit, ⇡i pi = ⇡i+1 qi+1 for i 0. (5.25) The intuition in (5.25) is simply that the rate at which downward transitions occur from i + 1 to i must equal the rate of upward transitions. Since this result is very important, both here and in our later study of continuous-time birth-death processes, we show that (5.25) also results from using the steady-state equations in (5.18): ⇡i = pi 1 ⇡i 1 ⇡0 = (1 + (1 pi qi )⇡i + qi+1 ⇡i+1 ; i>0 p0 )⇡0 + q1 ⇡1 . (5.26) (5.27) From (5.27), p0 ⇡0 = q1 ⇡1 . To see that (5.25) is satisfied for i > 0, we use induction on i, with i = 0 as the base. Thus assume, for a given i, that pi 1 ⇡i 1 = qi ⇡i . Substituting this in (5.26), we get pi ⇡i = qi+1 ⇡i+1 , thus completing the inductive proof. It is convenient to define ⇢i as pi /qi+1 . Then we have ⇡i+1 = ⇢i ⇡i , and iterating this, ⇡i = ⇡0 i 1 Y ⇢j ; ⇡0 = j=0 1+ P1 1 i=1 Qi 1 j=0 ⇢j . (5.28) P Q If i 1 0j 0 and all sufficiently large j, then this sum of products will converge and the states will be positive-recurrent. For the simple birth-death process of Figure 5.2, if we define ⇢ = q/p, then ⇢j = ⇢ for all j. For ⇢ < 1, (5.28) simplifies to ⇡i = ⇡o ⇢i for all i 0, ⇡0 = 1 ⇢, and thus ⇡i = (1 ⇢)⇢i for i 0. Exercise 5.2 shows how to find Fij (1) for all i, j in the case where ⇢ 1. We have seen that the simple birth-death chain of Figure 5.2 is transient if ⇢ > 1. This is not necessarily so in the case where self-transitions exist, but the chain is still either transient or null-recurrent. An example of this will arise in Exercise 6.3. 5.3 Reversible Markov chains Many important Markov chains have the property that, in steady state, the sequence of states looked at backwards in time, i.e.,. . . Xn+1 , Xn , Xn 1 , . . . , has the same probabilistic structure as the sequence of states running forward in time. This equivalence between the forward chain and backward chain leads to a number of results that are intuitively quite surprising and that are quite difficult to derive without using this equivalence. We shall study these results here and then extend them in Chapter 6 to Markov processes with a discrete state space. This set of ideas, and its use in queueing and queueing networks, has been an active area of queueing research over many years . It leads to many simple results for systems that initially look very complex. We only scratch the surface here and refer the interested reader to [13] for a more comprehensive treatment. Before going into reversibility, we describe the backward chain for an arbitrary Markov chain. CHAPTER 5. COUNTABLE-STATE MARKOV CHAINS The defining characteristic of a Markov chain {Xn ; n Pr{Xn+1 | Xn , Xn 1, . . . 0} is that for all n 0, , X0 } = Pr{Xn+1 | Xn } . (5.29) For homogeneous chains, which we have been assuming throughout, Pr{Xn+1 = j | Xn = i} = Pij , independent of n. For any k > 1, we can extend (5.29) to get Pr{Xn+k , Xn+k 1, . . . = Pr{Xn+k | Xn+k , Xn+1 | Xn , Xn = Pr{Xn+k , Xn+k 1 } Pr{Xn+k 1 1, . . . 1, . . . , X0 } | Xn+k , Xn+1 | Xn } . 2 } . . . Pr{Xn+1 | Xn } By letting A+ be any event defined on the states Xn+1 to Xn+k and letting A event defined on X0 to Xn 1 , this can be written more succinctly as Pr A+ | Xn , A = Pr A+ | Xn . (5.30) be any (5.31) This says that, given state Xn , any future event A+ is statistically independent of any past event A . This result, namely that past and future are independent given the present state, is equivalent to (5.29) for defining a Markov chain, but it has the advantage of showing the symmetry between past and future. This symmetry is best brought out by multiplying both sides of (5.31) by Pr{A | Xn }, obtaining2 Pr A+ , A | Xn = Pr A+ | Xn Pr A | Xn . (5.32) This symmetric form says that, conditional on the current state, the past and future states are statistically independent. Dividing both sides by Pr{A+ | Xn } then yields Pr A | Xn , A+ = Pr A | Xn . By letting A be Xn 1 (5.33) and A+ be Xn+1 , Xn+2 , . . . , Xn+k , this becomes Pr{Xn 1 | Xn , Xn+1 , . . . , Xn+k } = Pr{Xn 1 | Xn } . This is the equivalent form to (5.29) for the backward chain, and says that the backward chain is also a Markov chain. By Bayes’ law, Pr{Xn 1 | Xn } can be evaluated as Pr{Xn 1 | Xn } = Pr{Xn | Xn 1 } Pr{Xn Pr{Xn } 1} . (5.34) Since the distribution of Xn can vary with n, Pr{Xn 1 | Xn } can also depend on n. Thus the backward Markov chain is not necessarily homogeneous. This should not be surprising, since the forward chain was defined with some arbitrary distribution for the initial state at time 0. This initial distribution was not relevant for equations (5.29) to (5.31), but as soon as Pr{A | Xn } was introduced, the initial state implicitly became a part of each equation and destroyed the symmetry between past and future. For a chain in steady state, however, Pr{Xn = j} = Pr{Xn 1 = j} = ⇡j for all j, and we have Pr{Xn 2 1 = j | Xn = i} = Pji ⇡j /⇡i . (5.35) Much more broadly, any 3 events, say A , X0 , A+ are said to be Markov if Pr A+ | X0 A = Pr A+ | X0 , and this implies the more symmetric form Pr A A+ | X0 ) = Pr A | X0 Pr A+ | X0 . 5.3. REVERSIBLE MARKOV CHAINS Thus the backward chain is homogeneous if the forward chain is in steady state. For a chain with steady-state probabilities {⇡i ; i 0}, we define the backward transition probabilities Pij⇤ as ⇡i Pij⇤ = ⇡j Pji . (5.36) From (5.34), the backward transition probability Pij⇤ , for a Markov chain in steady state, is then equal to Pr{Xn 1 = j | Xn = i}, the probability that the previous state is j given that the current state is i. Now consider a new Markov chain with transition probabilities {Pij⇤ }. Over some segment of time for which both this new chain and the old chain are in steady state, the set of states generated by the new chain is statistically indistinguishable from the backward running sequence of states from the original chain. It is somewhat simpler, in talking about forward and backward running chains, however, to visualize Markov chains running in steady state from t = 1 to t = +1. If one is uncomfortable with this, one can also visualize starting the Markov chain at some very negative time with the initial distribution equal to the steady-state distribution. Definition 5.3.1. A Markov chain that has steady-state probabilities {⇡i ; i versible if Pij = ⇡j Pji /⇡i for all i, j, i.e., if Pij⇤ = Pij for all i, j. 0} is re­ Thus the chain is reversible if, in steady state, the backward running sequence of states is statistically indistinguishable from the forward running sequence. Comparing (5.36) with the steady-state equations (5.25) that we derived for birth-death chains, we have the important theorem: Theorem 5.3.1. Every birth-death chain with a steady-state probability distribution is re­ versible. We saw that for birth-death chains, the equation ⇡i Pij = ⇡j Pji (which only had to be consid­ ered for |i j|  1) provided a very simple way of calculating the steady-state probabilities. Unfortunately, it appears that we must first calculate the steady-state probabilities in order to show that a chain is reversible. The following simple theorem gives us a convenient escape from this dilemma. Theorem 5.3.2. Assume that an irreducible Markov chain has transition probabilities {Pij }. Suppose {⇡i } is a set of positive numbers summing to 1 and satisfying ⇡i Pij = ⇡j Pji ; then, first, {⇡i ; i is reversible. all i, j. (5.37) 0} is the steady-state distribution for the chain, and, second, the chain Proof: Given a solution to (5.37) for all i and j, we can sum this equation over i for each j. X X ⇡i Pij = ⇡j Pji = ⇡j . (5.38) i i CHAPTER 5. COUNTABLE-STATE MARKOV CHAINS P Thus the solution to (5.37), along with the constraints ⇡i > 0, i ⇡i = 1, satisfies the steady-state equations, (5.18), and, from Theorem 5.1.4, this is the unique steady-state distribution. Since (5.37) is satisfied, the chain is also reversible. It is often possible, sometimes by using an educated guess, to find a solution to (5.37). If this is successful, then we are assured both that the chain is reversible and that the actual steady-state probabilities have been found. Note that the theorem applies to periodic chains as well as to aperiodic chains. If the chain is periodic, then the steady-state probabilities have to be interpreted as average values over the period, but from Theorem 5.1.4 shows that (5.38) still has a unique solution (assuming an irreducible chain). On the other hand, for a chain with period d > 1, there are d subclasses of states and the sequence {Xn } must rotate between these classes in a fixed order. For this same order to be followed in the backward chain, the only possibility is d = 2. Thus periodic chains with periods other than 2 cannot be reversible. There are several simple tests that can be used to show that some given irreducible chain is not reversible. First, the steady-state probabilities must satisfy ⇡i > 0 for all i, and thus, if Pij > 0 but Pji = 0 for some i, j, then (5.37) cannot be satisfied and the chain is not reversible. Second, consider any set of three states, i, j, k. If Pji Pik Pkj is unequal to Pjk Pki Pij then the chain cannot be reversible. To see this, note that (5.37) requires that ⇡i = ⇡j Pji /Pij = ⇡k Pki /Pik . Thus, ⇡j Pji Pik = ⇡k Pki Pij . Equation (5.37) also requires that ⇡j Pjk = ⇡k Pkj . Taking the ratio of these equations, we see that Pji Pik Pkj = Pjk Pki Pij . Thus if this equation is not satisfied, the chain cannot be reversible. In retrospect, this result is not surprising. What it says is that for any cycle of three states, the probability of three transitions going around the cycle in one direction must be the same as the probability of going around the cycle in the opposite (and therefore backwards) direction. It is also true (see [16] for a proof), that a necessary and sufficient condition for a chain to be reversible is that the product of transition probabilities around any cycle of arbitrary length must be the same as the product of transition probabilities going around the cycle in the opposite direction. This doesn’t seem to be a widely useful way to demonstrate reversibility. There is another result, generalizing Theorem 5.3.2, for finding the steady-state probabilities of an arbitrary Markov chain and simultaneously finding the transition probabilities of the backward chain. Theorem 5.3.3. Assume that an irreducible Markov chain has transition probabilities {Pij }. Suppose {⇡i } is a set of positive numbers summing to 1 and that {Pij⇤ } is a set of transition probabilities satisfying ⇡i Pij = ⇡j Pji⇤ ; all i, j. (5.39) Then {⇡i } is the steady-state distribution and {Pij⇤ } is the set of transition probabilities for the backward chain. 5.4. THE M/M/1 SAMPLE-TIME MARKOV CHAIN Proof: Summing (5.39) over i, we get the steady-state equations for the Markov chain, so the fact that the given {⇡i } satisfy these equations asserts that they are the steady-state probabilities. Equation (5.39) then asserts that {Pij⇤ } is the set of transition probabilities for the backward chain. The following two sections illustrate some important applications of reversibility. 5.4 The M/M/1 sample-time Markov chain The M/M/1 Markov chain is a sampled-time model of the M/M/1 queueing system. Recall that the M/M/1 queue has Poisson arrivals at some rate and IID exponentially distributed service times at some rate µ. We assume throughout this section that < µ (this is required to make the states positive-recurrent). For some given small increment of time , we visualize observing the state of the system at the sample times n . As indicated in Figure 5.5, the probability of an arrival in the interval from (n 1) to n is modeled as , independent of the state of the chain at time (n 1) and thus independent of all prior arrivals and departures. Thus the arrival process, viewed as arrivals in subsequent intervals of duration , is Bernoulli, thus approximating the Poisson arrivals. This is a sampled-time approximation to the Poisson arrival process of rate for a continuous-time M/M/1 queue. 0n X y O µ z n X 1 y X O µ z n X 2 y X O µ z n X 3 y X O µ z n X 4 ... O Figure 5.5: Sampled-time approximation to M/M/1 queue for time increment . When the system is non-empty (i.e., the state of the chain is one or more), the probability of a departure in the interval (n 1) to n is µ , thus modelling the exponential service times. When the system is empty, of course, departures cannot occur. Note that in our sampled-time model, there can be at most one arrival or departure in an interval (n 1) to n . As in the Poisson process, the probability of more than one arrival, more than one departure, or both an arrival and a departure in an increment is of order 2 for the actual continuous-time M/M/1 system being modeled. Thus, for very small, we expect the sampled-time model to be relatively good. At any rate, we can now analyze the model with no further approximations. Since this chain is a birth-death chain, we can use (5.28) to determine the steady-state probabilities; they are ⇡i = ⇡0 ⇢i ; ⇢ = /µ < 1. Setting the sum of the ⇡i to 1, we find that ⇡0 = 1 ⇡i = (1 ⇢)⇢i ; ⇢, so all i 0. (5.40) CHAPTER 5. COUNTABLE-STATE MARKOV CHAINS Thus the steady-state probabilities exist and the chain is a birth-death chain, so from Theorem 5.3.1, it is reversible. We now exploit the consequences of reversibility to find some rather surprising results about the M/M/1 chain in steady state. Figure 5.6 illustrates a sample path of arrivals and departures for the chain. To avoid the confusion associated with the backward chain evolving backward in time, we refer to the original chain as the chain moving to the right and to the backward chain as the chain moving to the left. There are two types of correspondence between the right-moving and the left-moving chain: 1. The left-moving chain has the same Markov chain description as the right-moving chain, and thus can be viewed as an M/M/1 chain in its own right. We still label the sampled-time intervals from left to right, however, so that the left-moving chain makes transitions from Xn+1 to Xn to Xn 1 . Thus, for example, if Xn = i and Xn 1 = i + 1, the left-moving chain has an arrival in the interval from n to (n 1) . 2. Each sample function . . . xn 1 , xn , xn+1 . . . of the right-moving chain corresponds to the same sample function . . . xn+1 , xn , xn 1 . . . of the left-moving chain, where Xn 1 = xn 1 is to the left of Xn = xn for both chains. With this correspondence, an arrival to the right-moving chain in the interval (n 1) to n is a departure from the leftmoving chain in the interval n to (n 1) , and a departure from the right-moving chain is an arrival to the left-moving chain. Using this correspondence, each event in the left-moving chain corresponds to some event in the right-moving chain. In each of the properties of the M/M/1 chain to be derived below, a property of the leftmoving chain is developed through correspondence 1 above, and then that property is translated into a property of the right-moving chain by correspondence 2. Property 1: Since the arrival process of the right-moving chain is Bernoulli, the arrival process of the left-moving chain is also Bernoulli (by correspondence 1). Looking at a sample function xn+1 , xn , xn 1 of the left-moving chain (i.e., using correspondence 2), an arrival in the interval n to (n 1) of the left-moving chain is a departure in the interval (n 1) to n of the right-moving chain. Since the arrivals in successive increments of the left-moving chain are independent and have probability in each increment , we conclude that departures in the right-moving chain are similarly Bernoulli. The fact that the departure process is Bernoulli with departure probability in each increment is surprising. Note that the probability of a departure in the interval (n ,n ] is µ conditional on Xn 1 1 and is 0 conditional on Xn 1 = 0. Since Pr{Xn 1 1} = 1 Pr{Xn 1 = 0} = ⇢, we see that the unconditional probability of a departure in the interval (n , n ] is ⇢µ = as asserted above. The fact that successive departures are independent is much harder to derive without using reversibility (see exercise 5.13). Property 2: In the original (right-moving) chain, arrivals in the time increments after n are independent of Xn . Thus, for the left-moving chain, arrivals in time increments to the left of n are independent of the state of the chain at n . From the correspondence between sample paths, however, a left chain arrival is a right chain departure, so that for the right-moving chain, departures in the time increments prior to n are independent of Xn , which is equivalent to saying that the state Xn is independent of the prior departures. 5.4. THE M/M/1 SAMPLE-TIME MARKOV CHAIN r r r r r r r r r r r r r r H HH Hr r r r r r r Arrivals r r r r r r - r Departures r HH H State r HH HH Hr r H HH HArrivals rH rH HDepartures H H HHr Hr r Figure 5.6: Sample function of M/M/1 chain over a busy period and corresponding arrivals and departures for right and left-moving chains. Arrivals and departures are viewed as occurring between the sample times, and an arrival in the left-moving chain between time n and (n + 1) corresponds to a departure in the right-moving chain between (n + 1) and n . This means that if one observes the departures prior to time n , one obtains no information about the state of the chain at n . This is again a surprising result. To make it seem more plausible, note that an unusually large number of departures in an interval from (n m) to n indicates that a large number of customers were probably in the system at time (n m) , but it doesn’t appear to say much (and in fact it says exactly nothing) about the number remaining at n . The following theorem summarizes these results. Theorem 5.4.1 (Burke’s theorem for sampled-time). Given an M/M/1 Markov chain in steady state with < µ, a) the departure process is Bernoulli, b) the state Xn at any time n is independent of departures prior to n . The proof of Burke’s theorem above did not use the fact that the departure probability is the same for all states except state 0. Thus these results remain valid for any birth-death chain with Bernoulli arrivals that are independent of the current state (i.e., for which Pi,i+1 = for all i 0). One important example of such a chain is the sampled time approximation to an M/M/m queue. Here there are m servers, and the probability of departure from state i in an increment is µi for i  m and µm for i > m. For the states to be recurrent, and thus for a steady state to exist, must be less than µm. Subject to this restriction, properties a) and b) above are valid for sampled-time M/M/m queues. CHAPTER 5. COUNTABLE-STATE MARKOV CHAINS 5.5 Branching processes Branching processes provide a simple model for studying the population of various types of individuals from one generation to the next. The individuals could be photons in a photo­ multiplier, particles in a cloud chamber, micro-organisms, insects, or branches in a data structure. Let Xn be the number of individuals in generation n of some population. Each of these Xn individuals, independently of each other, produces a random number of o↵spring, and these o↵spring collectively make up generation n + 1. More precisely, a branching process is a Markov chain in which the state Xn at time n models the number of individuals in generation n. Denote the individuals of generation n as {1, 2, ..., Xn } and let Yk,n be the number of o↵spring of individual k. The random variables Yk,n are defined to be IID over k and n, with a PMF pj = Pr{Yk,n = j}. The state at time n + 1, namely the number of individuals in generation n + 1, is Xn+1 = Xn X Yk,n . (5.41) k=1 Assume a given distribution (perhaps deterministic) for the initial state X0 . The transition probability, Pij = Pr{Xn+1 = j | Xn = i}, is just the probability that Y1,n +Y2,n +· · ·+Yi,n = j. The zero state (i e., the state in which there are no individuals) is a trapping state (i.e., P00 = 1) since no future o↵spring can arise in this case. One of the most important issues about a branching process is the probability that the population dies out eventually. Naturally, if p0 (the probability that an individual has no o↵spring) is zero, then each generation must be at least as large as the generation before, and the population cannot die out unless X0 = 0. We assume in what follows that p0 > 0 and X0 > 0. Recall that Fij (n) was defined as the probability, given X0 = i, that state j is entered between times 1 and n. From (5.8), this satisfies the iterative relation X Fij (n) = Pij + Pik Fkj (n 1), n > 1; Fij (1) = Pij . (5.42) k6=j The probability that the process dies out by time n or before, given X0 = i, is thus Fi0 (n). For the nth generation to die out, starting with an initial population of i individuals, the descendants of each of those i individuals must die out. Since each individual generates descendants independently, we have Fi0 (n) = [F10 (n)]i for all i and n. Because of this relationship, it is sufficient to find F10 (n), which can be determined from (5.42). Observe that P1k is just pk , the probability that an individual will have k o↵spring. Thus, (5.42) becomes 1 1 X X F10 (n) = p0 + pk [F10 (n 1)]k = pk [F10 (n 1)]k . (5.43) k=1 P k=0 Let h(z) = k pk be the z transform of the number of an individual’s o↵spring. Then (5.43) can be written as zk F10 (n) = h(F10 (n 1)). (5.44) 5.5. BRANCHING PROCESSES This iteration starts with F10 (1) = p0 . Figure 5.7 shows a graphical construction for eval­ uating F10 (n). Having found F10 (n) as an ordinate on the graph for a given value of n, we find the same value as an abscissa by drawing a horizontal line over to the straight line of slope 1; we then draw a vertical line back to the curve h(z) to find h(F10 (n)) = F10 (n + 1). 1 F10 (1) 1 h((z) h z) p0 F10 (2) F10 (1) F10 (3) F10 (3) F10 (2) h(z) p0 F10 (1) F10 (1) (a) z (b) Figure 5.7: Graphical construction to find the probability that a population dies out. Here F10 (n) is the probability that a population starting with one member at generation 0 dies out by generation n or before. Thus F10 (1) is the probability that the population ever dies out. For the two subfigures shown, it can be seen that F10 (1) is equal to the smallest root of the equation h(z) z = 0. We next show that these two figures are representative of all possibilities. Since h(z) is a z transform, we know P that h(1) = 1, so that z = 1 is one root of h(z) z = 0. Also, h0 (1) = Y , where Y = k kpk is the expected number of an individual’s o↵spring. If Y > 1, as in Figure 5.7a, then h(z) z is negative for z slightly smaller than 1. Also, for z = 0, h(z) z = h(0) = p0 > 0. Since h00 (z) 0, there is exactly one root of h(z) z = 0 for 0 < z < 1, and that root is equal to F10 (1). By the same type of analysis, it can be seen that if Y  1, as in Figure 5.7b, then there is no root of h(z) z = 0 for z < 1, and F10 (1) = 1. As we saw earlier, Fi0 (1) = [F10 (1)]i , so that for any initial population size, there is a probability strictly between 0 and 1 that successive generations eventually die out for Y > 1, and probability 1 that successive generations eventually die out for Y  1. Since state 0 is accessible from all i, but F0i (1) = 0, it follows from Lemma 5.1.3 that all states other than state 0 are transient. We next evaluate the expected number of individuals in a given generation. Conditional on Xn 1 = i, (5.41) shows that the expected value of Xn is iY . Taking the expectation over Xn 1 , we have E [Xn ] = Y E [Xn 1] . (5.45) Iterating this equation, we get n E [Xn ] = Y E [X0 ] . (5.46) Thus, if Y > 1, the expected number of individuals in a generation increases exponentially with n, and Y gives the rate of growth. Physical processes do not grow exponentially CHAPTER 5. COUNTABLE-STATE MARKOV CHAINS forever, so branching processes are appropriate models of such physical processes only over some finite range of population. Even more important, the model here assumes that the number of o↵spring of a single member is independent of the total population, which is highly questionable in many areas of population growth. The advantage of an oversimplified model such as this is that it explains what would happen under these idealized conditions, thus providing insight into how the model should be changed for more realistic scenarios. It is important to realize that, for branching processes, the mean number of individuals is not a good measure of the actual number of individuals. For Y = 1 and X0 = 1, the expected number of individuals in each generation is 1, but the probability that Xn = 0 approaches 1 with increasing n; this means that as n gets large, the nth generation contains a large number of individuals with a very small probability and contains no individuals with a very large probability. For Y > 1, we have just seen that there is a positive probability that the population dies out, but the expected number is growing exponentially. A surprising result, which is derived from the theory of martingales in Chapter 7, is that n if X0 = 1 and Y > 1, then the sequence of random variables Xn /Y has a limit with probability 1. This limit is a random variable; it has the value 0 with probability F10 (1), and has larger values with some given distribution. Intuitively, for large n, Xn is either 0 or very large. If it is very large, it tends to grow in an orderly way, increasing by a multiple of Y in each subsequent generation. 5.6 Round-robin and processor sharing Typical queueing systems have one or more servers who each serve customers in FCFS order, serving one customer completely while other customers wait. These typical systems have larger average delay than necessary. For example, if two customers with service requirements of 10 and 1 units respectively are waiting when a single server becomes empty, then serving the first before the second results in departures at times 10 and 11, for an average delay of 10.5. Serving the customers in the opposite order results in departures at times 1 and 11, for an average delay of 6. Supermarkets have recognized this for years and have special express checkout lines for customers with small service requirements. Giving priority to customers with small service requirements, however, has some disadvan­ tages; first, customers with high service requirements can feel discriminated against, and second, it is not always possible to determine the service requirements of customers before they are served. The following alternative to priorities is popular both in the computer and data network industries. When a processor in a computer system has many jobs to accom­ plish, it often serves these jobs on a time-shared basis, spending a small increment of time on one, then the next, and so forth. In data networks, particularly high-speed networks, messages are broken into small fixed-length packets, and then the packets from di↵erent messages can be transmitted on an alternating basis between messages. A round-robin service system is a system in which, if there are m customers in the system, say c1 , c2 , . . . , cm , then c1 is served for an incremental interval , followed by c2 being served for an interval , and so forth up to cm . After cm is served for an interval , the server returns and starts serving c1 for an interval again. Thus the customers are served in a 5.6. ROUND-ROBIN AND PROCESSOR SHARING cyclic, or “round-robin” order, each getting a small increment of service on each visit from the server. When a customer’s service is completed, the customer leaves the system, m is reduced, and the server continues rotating through the now reduced cycle as before. When a new customer arrives, m is increased and the new customer must be inserted into the cycle of existing customers in a way to be discussed later. Processor sharing is the limit of round-robin service as the increment goes to zero. Thus, with processor sharing, if m customers are in the system, all are being served simultaneously, but each is being served at 1/m times the basic server rate. For the example of two customers with service requirement 1 and 10, each customer is initially served at rate 1/2, so one customer departs at time 2. At that time, the remaining customer is served at rate 1 and departs at time 11. For round-robin service with an increment of 1, the customer with unit service requirement departs at either time 1 or 2, depending on the initial order of service. With other increments of service, the results are slightly di↵erent. We first analyze round-robin service and then go to the processor-sharing limit as ! 0. As the above example suggests, the results are somewhat cleaner in the limiting case, but more realistic in the round-robin case. Round robin provides a good example of the use of backward transition probabilities to find the steady-state distribution of a Markov chain. The techniques used here are quite similar to those used in the next chapter to analyze queueing networks. Assume a Bernoulli arrival process in which the probability of an arrival in an interval is . Assume that the ith arriving customer has a service requirement Wi . The random variables Wi , i 1, are IID and independent of the arrival epochs. Thus, in terms of the arrival process and the service requirements, this is the same as an M/G/1 queue (see Section 4.5.5), but with M/G/1 queues, the server serves each customer completely before going on to the next customer. We shall find that the round-robin service here avoids the “slow truck e↵ect” identified with the M/G/1 queue. For simplicity, assume that Wi is arithmetic with span , taking on only values that are positive integer multiples of . Let f (j) = Pr{Wi = j } , j 1 and let F (j) = Pr{Wi > j }. Note that if a customer has already received j increments of service, then the probability that that customer will depart after 1 more increment is f (j + 1)/F (j). This probability of departure on the next service increment after the j th is denoted by g(j) = f (j + 1)/F (j); j 1. (5.47) The state s of a round-robin system can be expressed as the number, m, of customers in the system, along with an ordered listing of how many service increments each of those m customers have received, i.e., s = (m, z1 , z2 , . . . , zm ), (5.48) where z1 is the amount of service already received by the customer at the front of the queue, z2 is the service already received by the next customer in order, etc. In the special case of an idle queue, s = (0), which we denote as . Given that the state Xn at time n is s = 6 follows: , the state Xn+1 at time n + evolves as CHAPTER 5. COUNTABLE-STATE MARKOV CHAINS • A new arrival enters with probability and is placed at the front of the queue; • The customer at the front of the queue receives an increment of service; • The customer departs if service is complete. • Otherwise, the customer goes to the back of the queue It can be seen that the state transition depends, first, on whether a new arrival occurs (an event of probability ), and, second, on whether a departure occurs. If no arrival and no departure occurs, then the queue simply rotates. The new state is s 0 = r(s), where the rotation operator r(s) is defined by r(s) = (m, z2 , . . . , zm , z1 + 1). If a departure but no arrival occurs, then the customer at the front of the queue receives its last unit of service and departs. The new state is s 0 = (s), where the departure operator (s) is defined by (s) = (m 1, z2 , . . . , zm ). If an arrival occurs, the new customer receives one unit of service and goes to the back of the queue if more than one unit of service is required. In this case, the new state is s 0 = a(s) where the arrival operator a(s) is defined by a(s) = (m + 1, z1 , z2 , . . . , zm , 1). If only one unit of service is required by a new arrival, the arrival departs and s 0 = s. In the special case of an empty queue, s = , the state is unchanged if either no arrival occurs or an arrival requiring one increment of service arrives. Otherwise, the new state is s = (1, 1), i.e., the one customer in the system has received one increment of service. We next find the probability of each transition for s = 6 . The probability of no arrival is 1 . Given no arrival, and given a non-empty system, s 6= , the probability of a departure is g(z1 ) = f (z1 + 1)/F (z1 ), i e., the probability that one more increment of service allows the customer at the front of the queue to depart. Thus the probability of a departure is (1 )g(z1 ) and the probability of a rotation is (1 )[1 g(z1 )]. Finally, the probability of an arrival is , and given an arrival, the new arrival will leave the system after one unit of service with probability g(0) = f (1). Thus the probability of an arrival and no departure is [1 f (1)] and the probability of an unchanged system is f (1). To summarize, for s 6= , Ps,r(s) = (1 )[1 Ps,d(s) = (1 )g(z1 ); d(s) = (m f (1)]; a(s) = (m + 1, z1 , z2 , . . . , zm , 1) Ps,a(s) = Ps,s = [1 g(z1 )]; r(s) = (m, z2 , . . . , zm , z1 + 1) 1, z2 , . . . , zm ) f (1). For the special case of the idle state, P (5.49) , = (1 )+ f (1) and P ,(1,1) = (1 f (1)). We now find the steady-state distribution for this Markov chain by looking at the back­ ward Markov chain. We will hypothesize backward transition probabilities, and then use Theorem 5.3.3 to verify that the hypothesis is correct. Consider the backward transitions corresponding to each of the forward transitions in (5.49). A rotation in forward time causes the elements z1 , . . . , zm in the state s = (m, z1 , . . . , zm ) to rotate left, and the left most element (corresponding to the front of the queue) is incremented while rotating to the right end. The backward transition from r(s) to s corresponds to the elements z2 , . . . , zm , z1 + 1 5.6. ROUND-ROBIN AND PROCESSOR SHARING rotating to the right, with the right most element being decremented while rotating to the left end. If we view the transitions in backward time as a kind of round-robin system, we see that the rotation is in the opposite direction from the forward time system. In the backward time system, we view the numbers z1 , . . . , zm in the state as the remaining service required before the corresponding customers can depart. Thus, these numbers de­ crease in the backward moving system. Also, since the customer rotation in the backward moving system is opposite to that in the forward moving system, zm is the remaining service of the customer at the front of the queue, and z1 is the remaining service of the customer at the back of the queue. We also view departures in forward time as arrivals in backward time. Thus the backward transition from d(s) = (m 1, z2 , . . . , zm ) to s = (m, z1 , . . . , zm ) corresponds to an arrival requiring z1 + 1 units of service; the arrival goes to the front of the queue, receives one increment of service, and then goes to the back of the queue with z1 increments of remaining service. The nicest thing we could now hope for is that the arrivals in backward time are Bernoulli. This is a reasonable hypothesis to make, partly because it is plausible, and partly because it is easy to check via Theorem 5.3.3. Fortunately, we shall find that it is valid. According to ⇤ this hypothesis, the backward transition probability Pr(s),s is given by 1 ; that is, given that Xn+1 is r(s) = (m, z2 , . . . , zm , z1 +1), and given that there is no arrival in the backward system at time (n + 1) , then the only possible state at time n is s = (m, z1 , . . . , zn ). Next consider a backward transition from d(s) = (m 1, z2 , . . . , zn ) to s = (m, z1 , z2 , . . . , zm ). This corresponds to an arrival in the backward moving system; the arrival requires z1 + 1 increments of service, one of which is provided immediately, leaving the arrival at the back of the queue with z1 required increments of service remaining. The probability of this transition is Pd⇤(s),s = f (z1 + 1). Calculating the other backward transitions in the same way, the hypothesized backward transition probabilities are given by Pr⇤(s),s Pa⇤(s),s = 1 Pd⇤(s),s = = 1 Ps⇤,s = f (z1 + 1) f (1). (5.50) One should view (5.50) as an hypothesis for the backward transition probabilities. The arguments leading up to (5.50) are simply motivation for this hypothesis. If the hypothesis is correct, we can combine (5.49) and (5.50) to express the steady-state equations of Theorem 5.3.3 (for s = 6 f ) as ⇤ ⇡s Ps,r(s) = ⇡r(s) Pr(s),s ; (1 )[1 ⇡d(s) Pd⇤(s),s ; ⇤ ⇡a(s) Pa(s),s ; ⇤ ⇡s Ps ,s ; (1 )g(z1 )⇡s = f (z1 + 1)⇡d(s) (5.52) f (1)]⇡s = (1 )⇡a(s) (5.53) ⇡s Ps,d(s) = ⇡s Ps,a(s) = ⇡s Ps,s = [1 f (1)⇡s = g(z1 )]⇡s = (1 f (1)⇡s . )⇡r(s) (5.51) (5.54) We next show that (5.52), applied repeatedly, will allow us to solve for ⇡s (if is small enough for the states to be positive recurrent). Verifying that the solution also satisfies (5.51) and (5.53), will then verify the hypothesis. Since f (z1 + 1)/g(z1 ) is F (z1 ) from (5.47), we have ⇡s = 1 F (z1 )⇡d(s) . (5.55) CHAPTER 5. COUNTABLE-STATE MARKOV CHAINS For m > 1, d(s) = (m 1, z2 , . . . , zm ), so we can apply (5.55) to ⇡d(s) , and substitute the result back into (5.55), yielding !2 ⇡s = F (z1 )F (z2 )⇡d(d(s)) , 1 (5.56) where d(d(s)) = (m 2, z3 , . . . , zm ). Applying (5.55) repeatedly to ⇡d(d(s)) , ⇡d(d(d(s))) , and so forth, we eventually get 1 !m 0 m Y @ ⇡s = F (zj )A ⇡ . (5.57) 1 j=1 Before this can be accepted as a steady-state distribution, we must verify that it satisfies (5.51) and (5.53). The left hand side of (5.51) is (1 )[1 g(z1 )]⇡s , and, from (5.47), 1 g(z1 ) = [F (z1 ) f (z1 + 1)]/F (z1 ) = F (z1 + 1)/(z1 ). Thus using (5.57), the left side of (5.51) is 1 1 !m 0 m !m 0 m Y Y F (z1 +1) @ @ F (zj )A ⇡ = (1 (1 ) ) F (zj )A F (z1 +1)⇡ . 1 1 F (z1 ) j=1 j=2 This is equal to (1 )⇡r(s) , verifying (5.51). Equation (5.53) is verified in the same way. We now have to find P whether there is a solution for pf such that these probabilities sum to 1. First define Pm = z1 , . . . , zm ⇡(m, z1 , . . . , zm ). This is the probability of m customers in the system. Whenever a new customer enters the system, it receives one increment of service immediately, so each zi 1. Using the hypothesized solution in (5.57), 1 !m 0 m 1 Y X @ Pm = F (i)A ⇡ . (5.58) 1 j=1 i=1 Since F (i) = Pr{W > i }, since W is arithmetic with span , and since the mean of a nonnegative random variable is the integral of its complementary distribution function, we have 1 X F (i) = E [W ] i=1 Pm = Defining ⇢ = [ /(1 )]{E [W ] 1 (5.59) !m ⇣ E [W ] ⌘m ⇡ . }, we see Pm = ⇢m ⇡ . If ⇢ < 1, then ⇡ = 1 Pm = (1 ⇢)⇢m ; m 0. (5.60) ⇢, and (5.61) The condition r < 1 is required for the states to be positive-recurrent. The expected P number of customers in the system for a round-robin queue is m mPm = ⇢/(1 ⇢), and using Little’s theorem, Theorem 4.5.3, the expected delay is ⇢/[ (1 ⇢)]. In using Little’s 5.7. SUMMARY theorem here, however, we are viewing the time a customer spends in the system as starting when the number m in the state increases; that is, if a customer arrives at time n , it goes to the front of the queue and receives one increment of service, and then, assuming it needs more than one increment, the number m in the state increases at time (n + 1) . Thus the actual expected delay, including the original d when the customer is being served but not counted in the state, is + ⇢/[ (1 ⇢)]. The relation between ⇢ and E [W ] is shown in Figure 5.8, and it is seen that ⇢ < 1 for E [W ] < 1. The extreme case where = E [W ] is the case for which each customer requires exactly one unit of service. Since at most one customer can arrive per time incre­ ment, the state always remains at s = , and the delay is , i.e., the original increment of service received when a customer arrives. 1 ⇢ E [W ] 1 Figure 5.8: ⇢ as a function of E [W ] for given . Note that (5.61) is the same as the distribution of customers in the system for the M/M/1 Markov chain in (5.40), except for the anomaly in the definition of ⇢ here. We then have the surprising result that if round-robin queueing is used rather than FCFS, then the dis­ tribution of the number of customers in the system is approximately the same as that for an M/M/1 queue. In other words, the slow truck e↵ect associated with the M/G/1 queue has been eliminated. Another remarkable feature of round-robin systems is that one can also calculate the ex­ pected delay for a customer conditional on the required service of that customer. This is done in Exercise 5.16, and it is found that the expected delay is linear in the required service. Next we look at processor sharing by going to the limit as ! 0. We first eliminate the assumption that the service requirement distribution is arithmetic with span . Assume that the server always spends an increment of time on the customer at the front of the queue, and if service is finished before the interval of length ends, the server is idle until the next sample time. The analysis of the steady-state distribution above P is still valid if 1 we define F (j) = Pr{W > j }, and f (j) = F (j) F (j + 1). In this case i=1 F (i) lies between E [W ] and E [W ]. As ! 0, ⇢ = E [W ], and distribution of time in the system becomes identical to that of the M/M/1 system. 5.7 Summary This chapter extended the finite-state Markov chain results of Chapter 3 to the case of countably-infinite state spaces. It also provided an excellent example of how renewal pro­ CHAPTER 5. COUNTABLE-STATE MARKOV CHAINS cesses can be used for understanding other kinds of processes. In Section 5.1, the firstpassage-time random variables were used to construct renewal processes with renewals on successive transitions to a given state. These renewal processes were used to rederive the basic properties of Markov chains using renewal theory as opposed to the algebraic PerronFrobenius approach of Chapter 3. The central result of this was Theorem 5.1.4, which showed that, for an irreducible chain, the states are positive-recurrent if and only if the steady-state equations, (5.18), have a solution. Also if (5.18) has a solution, it is positive and unique. We also showed that these steady-state probabilities are, with probability 1, time-averages for sample paths, and that, for an ergodic chain, they are limiting probabili­ ties independent of the starting state. We found that the major complications that result from countable state spaces are, first, di↵erent kinds of transient behavior, and second, the possibility of null-recurrent states. For finite-state Markov chains, a state is transient only if it can reach some other state from which it can’t return. For countably infinite chains, there is also the case, as in Figure 5.2 for p > 1/2, where the state just wanders away, never to return. Null recurrence is a limiting situation where the state wanders away and returns with probability 1, but with an infinite expected time. There is not much engineering significance to null recurrence; it is highly sensitive to modeling details over the entire infinite set of states. One usually uses countably infinite chains to simplify models; for example, if a bu↵er is very large and we don’t expect it to overflow, we assume it is infinite. Finding out, then, that the chain is transient or null-recurrent simply means that the modeling assumption is not very good. We next studied birth-death Markov chains and reversibility. Birth-death chains are widely used in queueing theory as sample time approximations for systems with Poisson arrivals and various generalizations of exponentially distributed service times. Equation (5.28) gives their steady-state probabilities if positive-recurrent, and shows the conditions under which they are positive-recurrent. We showed that these chains are reversible if they are positiverecurrent. Theorems 5.3.2 and 5.3.3 provides a simple way to find the steady-state distribution of re­ versible chains and also of chains where the backward chain behavior could be hypothesized or deduced. We used reversibility to show that M/M/1 and M/M/m Markov chains satisfy Burke’s theorem for sampled-time — namely that the departure process is Bernoulli, and that the state at any time is independent of departures before that time. Branching processes were introduced in Section 5.5 as a model to study the growth of various kinds of elements that reproduce. In general, for these models (assuming p0 > 0), there is one trapping state and all other states are transient. Figure 5.7 showed how to find the probability that the trapping state is entered by the nth generation, and also the probability that it is entered eventually. If the expected number of o↵spring of an element is at most 1, then the population dies out with probability 1, and otherwise, the population dies out with some given probability q, and grows without bound with probability 1 q. Round-robin queueing was then used as a more complex example of how to use the backward process to deduce the steady-state distribution of a rather complicated Markov chain; this also gave us added insight into the behavior of queueing systems and allowed us to show that, in the processor-sharing limit, the distribution of number of customers is the same as