Abstract

The following paper, first written in 1974, was never published other than as part of an internal research series. Its lack of publication is certainly unrelated to the merits of the paper since the paper is of current importance by virtue of its relation to relaxation time. This chapter provides a systematic discussion of the approach of a finite Markov chain to ergodicity by proving the monotonicity of an important set of norms, each a measure of ergodicity whether or not time reversibility is present. The paper is of particular interest because the discussion of the relaxation time of a finite Markov chain (Keilson 1979) has only been clean for time reversible chains, a small subset of the chains of interest. This restriction is not present here. Indeed, a new relaxation time quoted quantifies the relaxation time for all finite ergodic chains (cf. the discussion of Q₁(t) below Eq. (7)). This relaxation time was developed by J. Keilson with A. Roy in his thesis (Roy 1996).

Introduction

Let be a finite homogeneous Markov chain in continuous time on the state space , which is irreducible and hence ergodic.

Let be the state probability vector at time t with . Let be the ergodic vector .

Consider the norm function with probability weights ,

1

defined for arbitrary probability vectors supported on N. Of interest are the related functions of time

2

and

3

The functions are vector norms on , and then describes a time dependent norm function. The function has related properties.

It will be shown (cf. Theorem 1) that is strictly decreasing in t for , and strictly increasing in t for when , that is, when the chain is not stationary. When for all t. A similar monotonicity of with t is demonstrated in Theorem 2. We note that lim for all α as . In particular,

4

and

5

where (cf. Kullback (1968), Renyi (1970))

6

is the divergence of the distribution from the distribution , an entity closely related to entropy and other concepts in information theory. The monotonicity of and for arbitrary chains has been known (Renyi 1970).

A value of α of special interest corresponding to weighted quadratic distance is , for which

7

and this is strictly decreasing in t if the chain is not stationary.

In the time reversible case, the monotonicity of Eq. (7) is well known (see Keilson 1979; and Kendall 1959). Indeed, for this case, the quadratic distance to ergodicity

8

is strictly decreasing by virtue of the symmetry of and its associated spectral representation (cf. Keilson 1979). That and are monotone decreasing for all ergodic chains is striking. The function decreases strictly to zero for every finite nonstationary homogeneous ergodic chain.

The monotonicity of the distance to ergodicity (8) does not appear to extend easily to the full family and .

It is shown in Roy (1996, Remark 3.2.2) that for any ergodic chain and initial distribution,

9

where is the smallest of the positive real singular values of (cf. Amir-Moez and Fass (1961)). When the chain is reversible in time, this agrees with the known result (Keilson 1979). Consequently, is a natural extension of the relaxation time for time reversible ergodic chains to all ergodic chains.

The distance and the relaxation time also play a role in the covariance function of any stationary ergodic chain . Here (cf. Keilson 1979),

where

Since f may be made positive by adding a constant without altering R_f(τ), it follows that is of the form needed for Eq. (8) and that Eq. (9) is then relevant. One then has from the Schwartz inequality

10

Note that for the Frobenius norm of ,

and this is strictly decreasing in time. This follows from Eq. (7) with , weighting by , and summation over m. Indeed,

and

When ,

11

is a decreasing function of t, and

12

is an increasing function of t.

Some Basic Lemmas

Lemma 1. For , let

13

Then for all real α and all ,

14

with equality if and only if .

Proof.

Consequently, . Moreover, strict inequality holds for .

Lemma 2. Let be a doubly conservative matrix, that is,

Then, for all real and all

15

and

16

Moreover, equality holds if and only if whenever .

Proof. Let . Then form simple algebra with :

17

By taking , Eq. (17) yields

18

Lemma 2 then follows from Lemma 1.

Remark 1. Note that for special value ,

for all real , because

and the last two terms are zero.

The Main Result

Theorem 1. For a finite ergodic chain in continuous time, let

If the chain is not stationary, is a strictly decreasing function of t on when and a strictly increasing function of t on when .

Proof. Since is differentiable, is also differentiable. Then for

19

Let be the transition matrix for the chain , so that where is the infinitesimal generator of the chain. Let . Then is doubly conservative in the sense of Lemma 2. Let . Then

20

The expression for is a property of ergodic chains in continuous time. By Lemma 2, the expression (20) is always nonpositive for . From (19) it follows that is nonpositive for , and nonnegative for . It attains the value 0 iff implies . For chains with positive transition rates between all pairs of states, this is possible only if for all n, that is, if the chain is stationary. The result then follows for all ergodic chains. When ,

with equality iff the chain is stationary.

Similar monotonicity properties hold for the family . From (2) and (3) we have

21

When or and have the same monotonicity properties with t. When increases when decreases. When , we have , which for nonstationary chains is strictly positive for any by virtue of Eq. (20) and Lemma 1. This yields the following theorem.

Theorem 2. Under the conditions of Theorem 1, is strictly decreasing in t for , strictly increasing in t for , and .

Ergodic Chains in Discrete Time

The results of the previous section apply also to discrete time finite Markov chains with the strict monotonicity replaced by weak monotonicity. Since the state probabilities can be zero, we will restrict ourselves to the case only. In keeping with this convention, p log p will be defined to be zero whenever .

Theorem 3a. Let . For a finite ergodic Markov chain, the sequence is a nonincreasing sequence.

Theorem 3b. If the elements of the one-step transition matrix are positive and the chain is not stationary, then is strictly monotone in t.

The details of the proofs are similar to that for the continuous time case and are somewhat tedious. They will not be given here.

References

1. Amir-Moez, A.R., and Fass, A.I. (1961). Elements of Linear Spaces. Ann Arbor, MI: Edwards Bros.
2. Keilson, J. (1979). Markov Chain Models—Rarity and Exponentiality. New York: Springer-Verlag, Applied Mathematical Sciences Series 28.
3. Kendall, D.G. (1959). “Unitary Dilations of Markov Transition Operators and the Corresponding Integral Representations for Transition Probability Matrices” (edited by U. Grenander), Probability and Statistics. Stockholm: Almqvist and Wiksell.
4. Kullback, S. (1968). Information Theory and Statistics. New York: Dover Publications Inc.
5. Renyi, A. (1970). Foundations of Probability, San Francisco: Holden-Day.
6. Roy, A. (1996). Transient Analysis of Queuing Systems, Ph.D. Thesis. Ann Arbor, MI: University of Rochester. This is available from UMI, Ann Arbor.