Next: Reversibility; Estimates for the Up: Ergodicity and Stationarity Previous: Stationary Initial Distributions   Contents

### Direct and Iterative Computation Methods

First we show how the stationary initial distribution of the Markov chain can be computed based on methods from linear algebra in case the transition matrix does not exhibit a particularly nice structure (but is quasi-positive) and if the number of states is reasonably small.

Theorem 2.12
• Let the transition matrix of the Markov chain be quasi-positive.
• Then the matrix is invertible and the uniquely determined probability solution of the matrix equation is given by

 (73)

where and all entries of the matrix are euqal to .

Proof

• In order to prove that the matrix is invertible we show that the only solution of the equation

 (74)

is given by .
• As satisfies the equation we obtain

 (75)

• Thus (74) implies

i.e.

 (76)

• On the other hand, clearly and hence as a consequence of (76)

 and (77)

• Taking into account (74) this implies and, equivalently, .
• Thus, we also have for all .
• Furthermore, Theorem 2.4 implies ,
• where denotes the matrix consisting of the identical (row) vectors .
• In other words: For we have

i.e.  for all .
• As the right hand sides of these equations do not depend on we can conclude for some constant .
• Moreover, as a consequence of (77),

and hence , i.e. .
• Thus, the matrix is invertible.
• Finally, (75) implies

and, equivalently,

Remarks

• Given a larger number of states the numerical computation of the inverse matrix in (73) can cause difficulties.
• In this case it is often more convenient to solve the matrix equation iteratively.
• If the transition matrix is quasi-positive and hence one can start by setting and solving the modified equation

 (78)

where and , .
• The probability function desired originally is given by

• When solving the modified matrix equation (78) we use the facts of being invertible and that there is an expansion of as a power series, which is a consequence of the following two lemmata.

Lemma 2.4
• Let be an matrix such that for .
• Then the matrix is invertible and for all

 (79)

Proof

• Obviously for all
 (80)

• Furthermore, the matrix is invertible for sufficiently large as by hypothesis .
• Consequently, for sufficiently large we have
 0

• This implies and hence is invertible.
• The assertion (79) now follows from (80).

Lemma 2.5
• Let the stochastic matrix be quasi-positive and let be the matrix introduced in .

• Then, for , the matrix is invertible, and

 (81)

Proof

• Because of Lemma 2.4 it suffices to show that .
• As is quasi-positive by hypothesis there is a natural number such that

• Furthermore,

and thus for all ; .
• Writing as for some and we obtain

• This yields

Remarks

• As a consequence of Lemma 2.5 the solution of the equation (78), i.e. , is given by

 (82)

thus allowing an iterative solution of .
• Notice that we start the iteration with as initial value later setting for all .
• Thus, (82) can thus be rewritten as

 (83)

and can be used as an approximation for if is sufficiently large.

Next: Reversibility; Estimates for the Up: Ergodicity and Stationarity Previous: Stationary Initial Distributions   Contents
Ursa Pantle 2006-07-20