Chapter 10

Markov Processes

10.1 Regular Markov Matrices

The existence of the Jordan form is the basis for the proof of limit theorems for certainkinds of matrices called Markov matrices.

Definition 10.1.1 An n × n matrix A = (aij) , is a Markov matrix if aij ≥ 0 for all i, jand ∑

i

aij = 1.

It may also be called a stochastic matrix or a transition matrix. A Markov or stochasticmatrix is called regular if some power of A has all entries strictly positive. A vector v ∈ Rn,is a steady state if Av = v.

Lemma 10.1.2 The property of being a stochastic matrix is preserved by taking products.It is also true if the sum is of the form

∑j aij = 1.

Proof: Suppose the sum over a row equals 1 for A and B. Then letting the entries bedenoted by (aij) and (bij) respectively and the entries of AB by (cij),∑

i

cij =∑i

∑k

aikbkj =∑k

∑i

aikbkj =∑k

bkj = 1

It is obvious that when the product is taken, if each aij , bij ≥ 0, then the same will betrue of sums of products of these numbers. Similar reasoning works for the assumption that∑

j aij = 1. ■The following theorem is convenient for showing the existence of limits.

Theorem 10.1.3 Let A be a real p× p matrix having the properties

1. aij ≥ 0

2. Either∑p

i=1 aij = 1 or∑p

j=1 aij = 1.

3. The distinct eigenvalues of A are {1, λ2, . . . , λm} where each |λj | < 1.

Then limn→∞An = A∞ exists in the sense that limn→∞ anij = a∞ij , the ijth entry A∞.

Here anij denotes the ijth entry of An. Also, if λ = 1 has algebraic multiplicity r, thenthe Jordan block corresponding to λ = 1 is just the r × r identity.

Proof. By the existence of the Jordan form for A, it follows that there exists an invertiblematrix P such that

P−1AP =

I +N

Jr2 (λ2). . .

Jrm (λm)

 = J

where I is r × r for r the multiplicity of the eigenvalue 1 and N is a nilpotent matrix forwhich Nr = 0. I will show that because of Condition 2, N = 0.

First of all,Jri (λi) = λiI +Ni

263