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­cesses can be used for understanding other kinds of processes. In Section 5.1, the first-passage-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 \ref{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 probabilities independent of the starting state.

We found that the major complications that result from countable state spaces are, first, different 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 buffer 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 \ref{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 reversible 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 \(p_{0}>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 offspring 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 that in an M/M/1 queue

For further reading on Markov chains with countably-infinite state spaces, see [8], [16], or [22]. Feller [8] is particularly complete, but Ross [16] and Wolff [22] are somewhat more accessible. Harris, [12] is the standard reference on branching processes and Kelly, [13] is the standard reference on reversibility. The material on round-robin systems is from [24] and is generalized there.