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 .

- For arbitrary but fixed states we say that the state
is

**Proof**-
- The condition is obviously necessary because
and thusfor some if is accessible from .
- On the other hand if and
for all , then

- The condition is obviously necessary because
**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 .

- The property of accessibility is
**Examples**-
- The definition of irreducibility immediately implies that the
matrices
andare irreducible.
- On the other hand the block matrix
consisting of
and

- The definition of irreducibility immediately implies that the
matrices

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.

- The

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
.

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

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

**Proof**-
- If there are integers such that and .
- Therefore
and hence

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

- 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

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

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

- This result, the irreducibility of
and the inequality
(25) in Corollary 2.2, i.e.
- Conversely, the irreducibility and aperiodicity of quasi-positive
transition matrices are immediate consequences of the definitions.

- Let us first assume the transition matrix
to be irreducible
and aperiodic.
**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.

- can be given by our well-known model for the
- It is nevertheless possible that the linear equation system

has one (or infinitely many) probability solutions . - 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).

- In this context the random variables
are
- Let and be arbitrary finite (or countably finite) sets, let
be an arbitrary function and let
and
be
random variables
- such that

- 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 .

- such that
- One can show that the sequence
recursively defined by (54) is a Markov chain
whose transition matrix
is given by

- A simple example for a non-irreducible Markov chain
**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 ).

- We consider particles, which are distributed between two
containers and that are permeably connected but insulated
with respect to their environment.
- The random variables
can thus be defined recursively
- by the stochastic recursion formula

- 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).

- by the stochastic recursion formula
- In spite of this, the linear equation system

has a (uniquely determined) probability solution where

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

where , and for all . - The linear equation system
is
of the form
- One can show that
- where
is defined by the condition
, i.e.

- One can show that
- 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).

- The diffusion model of Ehrenfest is a special case of the following
class of Markov chains called