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

### Irreducible and Aperiodic Markov Chains

• Recall
• In Theorem 2.4 we characterized the ergodicity of the Markov chain by the quasi-positivity of its transition matrix .
• However, it can be difficult to show this property of directly, especially if .
• Therefore, we will derive another (probabilistic) way to characterize the ergodicity of a Markov chain with finite state space. For this purpose we will need the following notion.
• For arbitrary but fixed states we say that the state is accessible from state if for some where . (notation: )
• Another (equivalent) definition for accessibility of states is the following:
• Let the number of steps until the Markov chain reaches the state for the first time. We define if for all .

Theorem 2.7   Let be such that . In this case is accessible from if and only if .

Proof

• The condition is obviously necessary because

and thus

for some if is accessible from .
• On the other hand if and for all , then

Remarks

• The property of accessibility is
• transitive, i.e., and imply that .
• This is an immediate consequence of the inequality (see Corollary 2.2) and of the definition of accessibility.
• Moreover, in case and we say that the states and communicate. (notation: )
• The property of communicating is an equivalence relation as
(a)
(reflexivity),
(b)
if and only if (symmetry),
(c)
and implies (transitivity).
• As a consequence,
• the state space can be completely divided into disjoint equivalence classes with respect to the equivalence relation .
• The Markov chain with transition matrix is called irreducible if the state space consists of only one equivalence class, i.e. for all .

Examples

• The definition of irreducibility immediately implies that the matrices

and

are irreducible.
• On the other hand the block matrix consisting of and

is not irreducible.

Besides irreducibility we need a second property of the transition probabilities, namely the so-called aperiodicity, in order to characterize the ergodicity of a Markov chain in a simple way.

Definition

• The period of the state is given by where ,,gcd'' denotes the greatest common divisor. We define if for all .
• A state is said to be aperiodic if .
• The Markov chain and its transition matrix are called aperiodic if all states of are aperiodic.

We will now show that the periods and coincide if the states belong to the same equivalence class of communicating states. For this purpose we introduce the notation if .

Theorem 2.8   If the states communicate, then .

Proof

• If , and for certain , then the inequalities from Corollary 2.2 imply that and .
• Thus, and are divisible by .
• As a consequence the difference is also divisible by .
• This shows that is a common divisor for all natural numbers having the property that , i.e.   .
• For reasons of symmetry the same argument also proves that .

Corollary 2.5   Let the Markov chain be irreducible. Then all states of have the same period.

In order to show

• that the characterization of an ergodic Markov chain (see Theorem 2.4) considered in Section 2.2.1 is equivalent to the Markov chain being irreducible and aperiodic,
• we need the following elementary lemma from number theory.

Lemma 2.3   Let an arbitrary but fixed natural number. Then there is a natural number such that

Proof

• If there are integers such that and .
• Therefore and hence

i.e., is the desired number.

Theorem 2.9   The transition matrix is quasi-positive if and only if is irreducible and aperiodic.

Proof

• Let us first assume the transition matrix to be irreducible and aperiodic.
• For every we consider the set whose greatest common divisor is as is aperiodic.
• The inequalities from Corollary  2.2 yield

and hence

 (50)

• We show that contains two successive numbers.
• If did not contain two successive numbers, the elements of would have a minimal distance .
• The consequence would be that for some and as otherwise for all .
• But this is a contradiction to our hypothesis gcd.
• Let now . Statement (50) then implies also and for arbitrary , where

 (51)

• We will show
• that there are natural numbers such that the difference between and is less than .
• From (51) we obtain

and hence for

• Therefore, the set contains two successive numbers.
• Statement (50) and Lemma 2.3 yield that for every there is an such that

 (52)

• This result, the irreducibility of and the inequality (25) in Corollary 2.2, i.e.

imply that for each pair of states there is a natural number such that

i.e., is quasi-positive.
• Conversely, the irreducibility and aperiodicity of quasi-positive transition matrices are immediate consequences of the definitions.

Remarks

• A simple example for a non-irreducible Markov chain
• can be given by our well-known model for the weather forecast where and

• If or , then the corresponding Markov chain is clearly not irreducible and therefore by Theorem 2.9 not ergodic.
• It is nevertheless possible that the linear equation system

 (53)

has one (or infinitely many) probability solutions .
• If for example and , then is a so-called absorbing state and is the (uniquely determined) solution of the linear equation system (53).
• If and , every probability solution solves the linear equation system (53).
• Now we give some examples for non-aperiodic Markov chains .
• In this context the random variables are not given by a stochastic recursion formula of the type (14) where the increments are independent and identically distributed random variables.
• We merely assume that the random variables are conditionally independent in the following sense.
• Note: As was shown in Section 2.1.3 it is nevertheless possible to construct a Markov chain that is stochastically equivalent to having independent increments, see the construction principle considered in (17)-(19).
• Let and be arbitrary finite (or countably finite) sets, let be an arbitrary function and let and be random variables
• such that

 (54)

• and such that for every the random variable is conditionally independent of the random variables given ,
• i.e., for arbitrary , and

where we define if .
• Moreover, we assume that for arbitrary and the probabilities do not depend on .
• One can show that the sequence recursively defined by (54) is a Markov chain whose transition matrix is given by

if for all .

Example
(Diffusion Model)
see P. Brémaud (1999) Markov Chains, Gibbs Fields, Monte Carlo Simulation, and Queues. Springer, New York, p.76

• The following simple model describing a diffusion process through a membrane was suggested in 1907 by the physicists Tatiana and Paul Ehrenfest. It is designed to model the heat exchange between two systems at different temperatures.
• We consider particles, which are distributed between two containers and that are permeably connected but insulated with respect to their environment.

• Assume there are particles in at time . Then one of the particles in the two containers is selected at random and transferred into the other container.
• The state of the system at time is hence either with probability (if the selected particle was in container ) or with probability (if the selected particle was in container ).
• The random variables can thus be defined recursively
• by the stochastic recursion formula

 (55)

• where given the random variable is conditionally independent of the random variables with and

• The entries of the transition matrix are therefore given by

• In particular this implies for all , i.e. the Markov chain given by (55) is not aperiodic (and thus by Theorem 2.9 not ergodic).
• In spite of this, the linear equation system

 (56)

has a (uniquely determined) probability solution where

 (57)

Remarks

• The diffusion model of Ehrenfest is a special case of the following class of Markov chains called birth and death processes with two reflecting barriers in literature.
• The state space considered is whereas the transition matrix is given by

 (58)

where , and for all .
• The linear equation system is of the form

• One can show that

• where is defined by the condition , i.e.

and, consequently,

• As we assume and for all , birth and death processes with two reflecting barriers are obviously irreducible.
• If the additional condition is satisfied for some , then birth and death processes with two reflecting barriers are also aperiodic (and hence ergodic by Theorem 2.9).

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