Next: Estimates for the Rate Up: Ergodicity and Stationarity Previous: Ergodicity and Stationarity   Contents

### 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
after (time-) steps.
• 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

 (33)

1. exist for all
2. are positive and independent of
3. 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

an arbitrary transition matrix such that .
• The -step transition matrix is given by

• If , this and (26) imply

and

 (34)

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.

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.

Theorem 2.4   The Markov chain with state space and transition matrix is ergodic if and only if is quasi-positive.

Proof

• First of all we show that the condition

 (35)

for some is sufficient for the ergodicity of .
• Let and . The Chapman-Kolmogorov equation (23) yields

and thus

i.e., for all , where we define . A similar argument shows that for all .
• Consequently, in order to show the existence of the limits in (33) it suffices to show that for all

 (36)

• For this purpose we consider the sets and for arbitrary but fixed states .
• Let . Then

and

• 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

 (37)

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

 (38)

• By the monotonicity of the differences in , (38) holds for every sequence of natural numbers.
• This proves (36).
• 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.

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

 (39)

and hence

 (40)

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

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

Theorem 2.5
• 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

 (41)

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

 (42)

for all .
• In particular (42) implies

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.

Next: Estimates for the Rate Up: Ergodicity and Stationarity Previous: Ergodicity and Stationarity   Contents
Ursa Pantle 2006-07-20