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.

- 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

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

is given by .- As
satisfies the equation
we
obtain

- Thus (74) implies

- As
satisfies the equation
we
obtain
- On the other hand, clearly
and hence
as a consequence of (76)

- 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
- As the right hand sides of these equations do not depend on we can conclude for some constant .
- Moreover, as a consequence of (77),

- Thus, the matrix is invertible.
- Finally, (75) implies

- In order to prove that the matrix
is invertible
we show that the only solution of the equation
**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

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.

- Let be an matrix such that for .
- Then the matrix
is invertible and for all

**Proof**

- Let the stochastic matrix
be quasi-positive and let
be the
matrix introduced in
.
- Then,
for
, the matrix
is invertible, and

**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,
- 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

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

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

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