Ergodic Markov Chains
label{sec 11.3}
A second important kind of Markov chain we shall study in detail is an ergodic Markov chain, defined as follows.
A Markov chain is called an ergodic chain if it is possible to go from every state to every state (not necessarily in one move).
In many books, ergodic Markov chains are called irreducible.
A Markov chain is called a regular chain if some power of the transition matrix has only positive elements.
In other words, for some [math]n[/math], it is possible to go from any state to any state
in exactly [math]n[/math] steps. It is clear from this definition that every regular
chain is ergodic. On the other hand, an ergodic chain is not necessarily
regular, as the following examples show.
Example
Let the transition matrix of a Markov chain be defined by
Then is clear that it is possible to move from any state to any state, so the chain is ergodic. However, if [math]n[/math] is odd, then it is not possible to move from state 0 to state 0 in [math]n[/math] steps, and if [math]n[/math] is even, then it is not possible to move from state 0 to state 1 in [math]n[/math] steps, so the chain is not regular. A more interesting example of an ergodic, non-regular Markov chain is provided by the Ehrenfest urn model. Example Recall the Ehrenfest urn model (Example).
The transition matrix for this example is
In this example, if we start in state 0 we will, after any even number of steps, be in either state 0, 2 or 4, and after any odd number of steps, be in states 1 or 3. Thus this chain is ergodic but not regular.
Regular Markov Chains
Any transition matrix that has no zeros determines a regular Markov chain. However, it is possible for a regular Markov chain to have a transition matrix that has zeros. The transition matrix of the Land of Oz example of Section \ref{sec 11.1} has [math]p_{NN} = 0[/math] but the second power [math]\mat{P}^2[/math] has no zeros, so this is a regular Markov chain.
An example of a nonregular Markov chain is an absorbing chain. For example,
let
be the transition matrix of a Markov chain. Then all powers of [math]\mat{P}[/math] will have a 0 in the upper right-hand corner.
We shall now discuss two important theorems relating to regular chains.
Let [math]\mat{P}[/math] be the transition matrix for a regular chain. Then, as [math]n \to \infty[/math], the powers [math]\mat{P}^n[/math] approach a limiting matrix [math]\mat{W}[/math] with all rows the same vector [math]\mat{w}[/math]. The vector [math]\mat{w}[/math] is a strictly positive probability vector (i.e., the components are all positive and they sum to one).
In the next section we give two proofs of this fundamental theorem. We give
here the
basic idea of the first proof.
We want to show that the powers [math]\mat{P}^n[/math] of a regular transition matrix tend
to a matrix
with all rows the same. This is the same as showing that [math]\mat{P}^n[/math] converges
to a matrix
with constant columns. Now the [math]j[/math]th column of [math]\mat{P}^n[/math] is [math]\mat{P}^{n}
\mat{y}[/math] where
[math]\mat{y}[/math] is a column vector with [math]1[/math] in the [math]j[/math]th entry and 0 in the other
entries. Thus
we need only prove that for any column vector [math]\mat{y},\mat{P}^{n} \mat{y}[/math]
approaches a
constant vector as
[math]n[/math] tend to infinity.
Since each row of [math]\mat{P}[/math] is a probability vector, [math]\mat{Py}[/math] replaces
[math]\mat{y}[/math] by
averages of its components. Here is an example:
The result of the averaging process is to make the components of [math]\mat{Py}[/math] more similar than those of [math]\mat{y}[/math]. In particular, the maximum component decreases (from 3 to 2) and the minimum component increases (from 1 to 3/2). Our proof will show that as we do more and more of this averaging to get [math]\mat{P}^{n} \mat{y}[/math], the difference between the maximum and minimum component will tend to 0 as [math]n \rightarrow \infty[/math]. This means [math]\mat{P}^{n} \mat{y}[/math] tends to a constant vector. The [math]ij[/math]th entry of [math]\mat{P}^n[/math], [math]p_{ij}^{(n)}[/math], is the probability that the process will be in state [math]s_j[/math] after [math]n[/math] steps if it starts in state [math]s_i[/math]. If we denote the common row of [math]\mat{W}[/math] by [math]\mat{w}[/math], then Theorem \ref{thm 11.3.6} states that the probability of being in [math]s_j[/math] in the long run is approximately [math]w_j[/math], the [math]j[/math]th entry of [math]\mat{w}[/math], and is independent of the starting state.
Example Recall that for the Land of Oz example of Section \ref{sec 11.1}, the sixth power of the transition matrix [math]\mat{P}[/math] is, to three decimal places,
Let [math]\mat {P}[/math] be a regular transition matrix, let
To prove part (a), we note that from Theorem,
Let [math]\mat{v}[/math] be any vector
with [math]\mat{v} \mat{P} = \mat{v}[/math]. Then [math]\mat{v} = \mat{v} \mat{P}^n[/math], and
passing to
the limit, [math]\mat{v} = \mat{v} \mat{W}[/math]. Let [math]r[/math] be the sum of the components
of [math]\mat{v}[/math].
Then it is easily checked that [math]\mat{v}\mat{W} = r\mat{w}[/math]. So, [math]\mat{v} =
r\mat{w}[/math].
To prove part (b), assume that [math]\mat{x} = \mat{P} \mat{x}[/math]. Then [math]\mat{x} =
\mat{P}^n
\mat{x}[/math], and again passing to the limit, [math]\mat{x} = \mat{W}\mat{x}[/math]. Since
all rows of
[math]\mat{W}[/math] are the same, the components of [math]\mat{W}\mat{x}[/math] are all equal, so
[math]\mat{x}[/math] is a
multiple of [math]\mat{c}[/math].
Note that an immediate consequence of Theorem is the fact that there is only one probability vector [math]\mat{v}[/math] such that [math]\mat{v}\mat{P} = \mat{v}[/math].
Fixed Vectors
A row vector [math]\mat{w}[/math] with the property [math]\mat{w}\mat{P} = \mat{w}[/math] is called a fixed row vector for [math]\mat{P}[/math]. Similarly, a column vector [math]\mat{x}[/math] such that [math]\mat{P}\mat{x} = \mat{x}[/math] is called a fixed column vector for [math]\mat{P}[/math].
Thus, the common row of [math]\mat{W}[/math] is the unique vector [math]\mat{w}[/math] which is both a fixed row vector for [math]\mat{P}[/math] and a probability vector. Theorem shows that any fixed row vector for [math]\mat{P}[/math] is a multiple of [math]\mat{w}[/math] and any fixed column vector for [math]\mat{P}[/math] is a constant vector.
One can also state Definition in terms of eigenvalues and
eigenvectors.
A fixed row vector is a left eigenvector of the matrix [math]\mat{P}[/math] corresponding
to the
eigenvalue 1. A similar statement can be made about fixed column vectors.
We will now give several different methods for calculating the fixed row vector
\mat{w} for
a regular Markov chain.
Example
By Theorem we can find the limiting vector [math]\mat{w}[/math] for the
Land of Oz from the fact that
These relations lead to the following four equations in three unknowns:
Our theorem guarantees that these equations have a unique solution. If the
equations are solved, we obtain the solution
To calculate the fixed vector, we can assume that the value at a particular state, say state one, is 1, and then use all but one of the linear equations from [math]\mat{w}\mat{P} = \mat{w}[/math]. This set of equations will have a unique solution and we can obtain [math]\mat{w}[/math] from this solution by dividing each of its entries by their sum to give the probability vector [math]\mat{w}[/math]. We will now illustrate this idea for the above example. Example We set [math]w_1 = 1[/math], and then solve the first and second linear equations from [math]\mat{w}\mat{P} = \mat{w}[/math]. We have
As mentioned above, we can also think of the fixed row vector [math]\mat{w}[/math] as a
left eigenvector of
the transition matrix [math]\mat{P}[/math]. Thus, if we write [math]\mat{I}[/math] to denote the
identity matrix, then
[math]\mat{w}[/math] satisfies the matrix equation
The program FixedVector uses one of the above methods
(depending upon the language in
which it is written) to calculate the fixed row probability vector for regular
Markov chains.
So far we have always assumed that we started in a specific state. The
following theorem generalizes Theorem to the case where the
starting state is itself determined by a probability vector.
Let [math]\mat{P}[/math] be the transition matrix for a regular chain and [math]\mat{v}[/math] an arbitrary probability vector. Then
By Theorem,
If we start a Markov chain with initial probabilities given by [math]\mat{v}[/math], then the probability vector [math]\mat{v} \mat{P}^n[/math] gives the probabilities of being in the various states after [math]n[/math] steps. Theorem then establishes the fact that, even in this more general class of processes, the probability of being in [math]s_j[/math] approaches [math]w_j[/math].
Equilibrium
We also obtain a new interpretation for [math]\mat{w}[/math]. Suppose that our starting vector picks state [math]s_i[/math] as a starting state with probability [math]w_i[/math], for all [math]i[/math]. Then the probability of being in the various states after [math]n[/math] steps is given by [math]\mat {w} \mat {P}^n = \mat {w}[/math], and is the same on all steps. This method of starting provides us with a process that is called “stationary.” The fact that [math]\mat{w}[/math] is the only probability vector for which [math]\mat {w} \mat {P} = \mat {w}[/math] shows that we must have a starting probability vector of exactly the kind described to obtain a stationary process.
Many interesting results concerning regular Markov chains depend only on the
fact that the chain has a unique fixed probability vector which is positive.
This property holds for all ergodic Markov chains.
For an ergodic Markov chain, there is a unique probability vector [math]\mat{w}[/math] such that [math]\mat {w} \mat {P} = \mat {w}[/math] and [math]\mat{w}[/math] is strictly positive. Any row vector such that [math]\mat {v} \mat {P} = \mat {v}[/math] is a multiple of [math]\mat{w}[/math]. Any column vector [math]\mat{x}[/math] such that [math]\mat {P} \mat {x} = \mat {x}[/math] is a constant vector.\n
Show ProofThis theorem states that Theorem is true for ergodic chains. The result follows easily from the fact that, if [math]\mat{P}[/math] is an ergodic transition matrix, then [math]\bar{\mat{P}} = (1/2)\mat {I} + (1/2)\mat {P}[/math] is a regular transition matrix with the same fixed vectors (see Exercises \ref{exer 11.3.24}--Exercise).
For ergodic chains, the fixed probability vector has a slightly different
interpretation. The following two theorems, which we will not prove here,
furnish an interpretation for this fixed vector.
Let [math]\mat{P}[/math] be the transition matrix for an ergodic chain. Let [math]\mat {A}_n[/math] be the matrix defined by
If [math]\mat{P}[/math] is the transition matrix of an ergodic chain, then
Theorem states
that there is only one fixed row probability vector for [math]\mat{P}[/math]. Thus, we
can use the same
techniques that were used for regular chains to solve for this fixed vector.
In particular,
the program FixedVector works for ergodic chains.
To interpret Theorem, let us assume that we have an ergodic
chain that
starts in state [math]s_i[/math]. Let [math]X^{(m)} = 1[/math] if the [math]m[/math]th step is to state [math]s_j[/math]
and 0
otherwise. Then the average number of times in state [math]s_j[/math] in the first [math]n[/math]
steps is given by
(Law of Large Numbers for Ergodic Markov Chains)\label{thm 11.3.12} Let [math]H_j^{(n)}[/math] be the proportion of times in [math]n[/math] steps that an ergodic chain is in state [math]s_j[/math]. Then for any [math]\epsilon \gt 0[/math],
We have observed that every regular Markov chain is also an ergodic chain. Hence, Theorems and \ref{thm 11.3.12} apply also for regular chains. For example, this gives us a new interpretation for the fixed vector [math]\mat {w} = (.4,.2,.4)[/math] in the Land of Oz example. Theorem predicts that, in the long run, it will rain 40 percent of the time in the Land of Oz, be nice 20 percent of the time, and snow 40 percent of the time.
Simulation
We illustrate Theorem \ref{thm 11.3.12} by writing a program to simulate the behavior of a Markov chain. SimulateChain is such a program. Example In the Land of Oz, there are 525 days in a year.
We have simulated the weather for one year in
the Land of Oz, using the program SimulateChain. The results are shown in Table.
| State | Times | Fraction |
| R | 217 | .413 |
| N | 109 | .208 |
| S | 199 | .379 |
We note that the simulation gives a proportion of times in each of the states not too different from the long run predictions of .4, .2, and .4 assured by Theorem. To get better results we have to simulate our chain for a longer time. We do this for 10,00 days without printing out each day's weather. The results are shown in Table. We see that the results are now quite close to the theoretical values of .4, .2, and .4.
| State | Times | Fraction |
| R | 4010 | .401 |
| N | 1902 | .19 |
| S | 4088 | .409 |
Examples of Ergodic Chains
The computation of the fixed vector [math]\mat{w}[/math] may be difficult if the transition matrix is very large. It is sometimes useful to guess the fixed vector on purely intuitive grounds. Here is a simple example to illustrate this kind of situation. Example A white rat is put into the maze of Figure \ref{fig 11.4}. There are nine compartments with connections between the compartments as indicated. The rat moves through the compartments at random. That is, if there are [math]k[/math] ways to leave a compartment, it chooses each of these with equal probability. We can represent the travels of the rat by a Markov chain process with transition matrix given by
That this chain is not regular can be seen as follows: From an odd-numbered state the process can go only to an even-numbered state, and from an even-numbered state it can go only to an odd number. Hence, starting in state [math]i[/math] the process will be alternately in even-numbered and odd-numbered states. Therefore, odd powers of [math]\mat{P}[/math] will have 0's for the odd-numbered entries in row 1. On the other hand, a glance at the maze shows that it is possible to go from every state to every other state, so that the chain is ergodic.
To find the fixed probability vector for this matrix, we would have to solve
ten equations in nine unknowns. However, it would seem reasonable that the
times spent in each compartment should, in the long run, be proportional to the
number of entries to each compartment. Thus, we try the vector whose [math]j[/math]th
component is the number of entries to the [math]j[/math]th compartment:
Example We recall the Ehrenfest urn model of Example. The transition matrix for this chain is as follows:
By Theorem \ref{thm 11.3.12}, we can interpret these values for [math]w_i[/math] as the proportion of times the process is in each of the states in the long run. For example, the proportion of times in state 0 is .0625 and the proportion of times in state 1 is .375. The astute reader will note that these numbers are the binomial distribution 1/16, 4/16, 6/16, 4/16, 1/16. We could have guessed this answer as follows: If we consider a particular ball, it simply moves randomly back and forth between the two urns. This suggests that the equilibrium state should be just as if we randomly distributed the four balls in the two urns. If we did this, the probability that there would be exactly [math]j[/math] balls in one urn would be given by the binomial distribution [math]b(n,p,j)[/math] with [math]n = 4[/math] and [math]p = 1/2[/math].
\exercises
General references
Doyle, Peter G. (2006). "Grinstead and Snell's Introduction to Probability" (PDF). Retrieved June 6, 2024.