Basic Definitions and Quasi-positive Transition Matrices

- If the Markov chain
has a very large number
of possible states, the spectral representation
(30) of the -step transition matrix
discussed in Section 2.1.4
turns out to be inappropriate in order to calculate
- the conditional probabilities of the random state
- as well as the (unconditional) probabilities of

- However, there are certain conditions
- ensuring the existence of the limits and , respectively, as well as their equality and independence of ,
- thus justifying to consider the limit
as
*approximation*of and if .

This serves as a motivation to formally introduce the notion of the
*ergodicity* of Markov chains.

**Definition**- The Markov chain
with
transition matrix
and the corresponding -step
transition matrices
) is
called
*ergodic*if the limits

- exist for all
- are positive and independent of
- form a probability function , i.e. .

**Example**- (
*Weather Forecast*)- In order to illustrate the notion of an ergodic Markov chain we return to the simple example of weather forecast already discussed in Sections 2.1.2 and 2.1.4.
- Let and
- The -step transition matrix
is given by
- If
, this and (26) imply

respectively. Note that the limit distribution in (34) does*not*depend on the choice of the initial distribution . - However, if
, then

The ergodicity of Markov chains on an arbitrary finite state space
can be characterized by the following notion from the theory of
positive matrices.

**Definition**-
- The
matrix
is called
*non-negative*if all entries of are non-negative. - The non-negative matrix
is called
*quasi-positive*if there is a natural number such that all entries of are positive.

- The
matrix
is called
**Remark**- If is a stochastic matrix and we can find a natural number such that all entries of are positive, then it is easy to see that for all natural numbers all entries of are positive.

**Proof**-
- First of all we show that the condition

for some is sufficient for the ergodicity of .- Let
and
. The Chapman-Kolmogorov
equation (23) yields
- Consequently, in order to show the existence of the limits
in (33) it suffices to show that for all

- For this purpose we consider the sets and for arbitrary but fixed states .
- Let
. Then
- By another application of the Chapman-Kolmogorov equation
(23) this yields for arbitrary and

- As a consequence,
and by induction one shows that for any

- This ensures the existence of an (unbounded) sequence
such that for all

- By the monotonicity of the differences
in
,
(38) holds for
*every*sequence of natural numbers. - This proves (36).

- Let
and
. The Chapman-Kolmogorov
equation (23) yields
- The limits are positive because
- Furthermore,
as the sum consists of
*finitely*many summands. - It follows immediately from
and
(33) that the condition (35) is
necessary for ergodicity if one takes into account that the state
space is finite.

- First of all we show that the condition
**Remarks**-
- As the limits
of ergodic
Markov chains do not depend on and the state space
is finite, clearly
- The proof of Theorem 2.4 does not only show the
existence of the limits
but
also yields the following
*estimate for the rate of convergence*: The inequality (37) implies

and hence

where denotes the integer part of . - Estimates like (39) and (40) are
referred to as
*geometric bounds*for the rate of convergence in literature.

- As the limits
of ergodic
Markov chains do not depend on and the state space
is finite, clearly

Now we will show that the limits
can be regarded as solution of a system of linear
equations.

- Let be an ergodic Markov chain with state space and transition matrix .
- In this case the vector
of the
limits
is the uniquely
determined (positive) solution of the linear equation system

when additionally the condition is imposed.

**Proof**-
- The definition (33) of the limits and the
Chapman-Kolmogorov equation (23) imply by changing
the order of limit and sum that
- Suppose now that there is another solution of (41) such that for all and .
- By induction one easily shows

for all . - In particular (42) implies

- The definition (33) of the limits and the
Chapman-Kolmogorov equation (23) imply by changing
the order of limit and sum that
**Remarks**-
- In matrix notation the linear equation system (41) is of the form .
- If the number of elements in the state space is reasonably small this equation system can be used for the numerical calculation of the probability function ; see Section 2.2.5.
- In case , Monte-Carlo simulation turns out to be a more efficient method to determine ; see Section 3.3.