|
EECS 126 - Probability and Random
Processes - J. Walrand |
MARKOV CHAINS:
DISCRETE TIME
·
Examples
·
Theorem
Key Ideas
A Markov chain models the random motion in time of a particle in a countable set. The key feature of that motion is that the particle has no memory of its past and does not carry a watch. That is, the future motion depends only on the current location. Consequently, the law of motion is specified by the one-step transition probabilities from any given location. Markov chains are an important class of models because they are fairly general and good numerical techniques exist for computing statistics about Markov chains.
Definition
A discrete-time Markov chain is a process X = {Xn, n ³ 0} that takes values in a countable set S and is such that
P[Xn + 1 = j | X0, …, Xn – 1, Xn = i] = P(i, j) for all i, j Î S and n ³ 0.
The matrix P = [P(i,j), i, j Î S] is the transition probability matrix of the Markov chain. The matrix P is any nonnegative matrix whose rows sum to 1. Such a matrix is called a stochastic matrix.
The finite dimensional distributions of X are specified by the initial distribution p0 = {p0(i) = P(X0 = i), i Î S} and by P. Indeed,
P(X0 = i0, X1 = i1,…, Xn = in}
= P(X0 = i0)P[X1 = i1| X0 = i0]P[X2 = i2| X0 = i0, X1 = i1]´…´P[Xn = in| X0 = i0,…, Xn - 1 = in - 1]
= P(X0 = i0)P[X1 = i1| X0 = i0]P[X2 = i2|X1 = i1]´…´P[Xn = in| Xn - 1 = in - 1]
= p0(i0)P(i0, i1)P(i1, i2)´…´P(in - 1, in).
Note in particular (by summing over i1, i2, …, in –1) that
P[Xn = j|X0 = i] = Pn(i, j)
Where Pn is the n-th power of the matrix P. (The power of a stochastic matrix is defined as that of a finite matrix.)
A state transition diagram can represent the transition probability matrix. Such a diagram shows the states and the probabilities are represented by numbers on arrows between states. By convention, no arrow between two states means that the corresponding transition probability is 0. (See examples below.)
Examples
We first look at the following state transition diagram.
Diagram [1] represents a Markov chain with S = {0, 1}. Its transition probability matrix is shown next to the diagram.
The following state transition matrix [2] corresponds to a Markov chain with S = {0, 1, 2, …}.
This is the state transition diagram of the sequence of fortunes with the rich uncle.
Also, for future reference, we introduce a few other examples. Markov chain [3] has two sets of states that do not communicate. (Recall that the absence of an arrow means that the corresponding transition probability is 0.)
Markov chain [4] has one state that cannot be exited from. Note that P(4, 4) = 1.
Markov chains [5] and [6] have characteristics that we will discuss later.
Consider the following “non-Markov” chain. The possible values are 0, 1, 2. The initial value is picked randomly. Also, with probability 1/2, the sequence increases (modulo 3), otherwise, it decreases. Thus, with probability p(0)/2, the sequence is {0, 1, 2, 0, 1, 2, …} and with probability p(0)/2 it is {0, 2, 1, 0, 2, 1, 0, …}. Similarly for the other two possible starting values. This is not Markov since by looking at the previous two values you can predict exactly the next one, which you cannot do if you only see the current value. Note that you can “complete the state” by considering the pair of two successive values. This pair is a Markov chain. More generally, if a sequence has a finite memory of duration k, the vector of k successive values is Markov.
Classification
The properties of Markov chains are determined largely (completely for finite Markov chains) by the “topology” of their state transition diagram. We need some terminology.
A Markov chain (or its probability transition matrix) is said to be irreducible if it can reach every state from every other state (not necessarily in one step). For instance, [1], [2], [5], and [6] are irreducible but [3] and [4] are not.
Define d(i) = g.c.d.{n > 0 | it is possible to go from i to i in n steps}. Here, g.c.d. means the greatest common divisor of the integers in the set. For instance, g.c.d.{6, 9, 15} = 3 and g.c.d.{12, 15, 25} = 1. For instance, for [1], d(1) = g.c.d.{1, 2, 3, …} = 1. For [2], d(2) = g.c.d.{2, 4, 5, 6, ..} = 1. For [5], d(1) = g.c.d.{3, 6, 9, …} = 3. For [6], d(1) = g.c.d.{3, 5, 6, ..} = 1.
If the Markov chain is irreducible, then it can be shown that d(i) has the same value for all i Î S. If this common value d is equal to 1, then the Markov chain is said to be aperiodic. Otherwise, the Markov chain is said to be periodic with period d. Accordingly, the Markov chains [1], [2], [6] are aperiodic and Markov chain [5] is periodic with period 3.
Define Ti = min{n ³ 0 | Xn = i}. If the Markov chain is irreducible, then one can show that P[Ti < ¥ | X0 = i] has the same value for all i Î S. Moreover, that value is either 1 or 0. If it is 1, the Markov chain is said to be recurrent. If it is 0, then the Markov chain is said to be transient. Every finite irreducible Markov chain is recurrent.
Moreover, if the irreducible Markov chain is recurrent, then E[Ti | X0 = i] is either finite for all i Î S or it is infinite for all i Î S. If E[Ti | X0 = i] is finite, then the Markov chain is said to be positive recurrent. Every finite irreducible Markov chain is positive recurrent. If E[Ti | X0 = i] is infinite, then the Markov chain is null recurrent. Also, one can show that
lim N ® ¥ [1{X1 = j} + 1{X1 = j} + … + 1{XN = j}]/N = 0 for all j if the Markov chain is null recurrent and
lim N ® ¥ [1{X1 = j} + 1{X1 = j} + … + 1{XN = j}]/N =: p(j) > 0 for all j if the Markov chain is positive recurrent.
Finally, if the Markov chain is irreducible, aperiodic, and positive recurrent, then
P[Xn = j | X0 = i] ® p(j) for all i, j Î S, as n ® ¥.
The Markov chain [2] is transient when p > 0.5, null recurrent when p = 0.5, and positive recurrent when p < 0.5.
Stationary Distribution
If P(Xn = i) = p(i) for i Î S (i.e., does not depend on n), the distribution p is said to be invariant. Since
P(Xn + 1 = i) = Sj P(Xn = j, Xn + 1 = i) = Sj P[Xn + 1 = i | Xn = j]P(Xn = j)
= Sj P(Xn = j)P(j, i),
if p is invariant, then
p(i) = Sjp(j)P(j, i), for i Î S.
These identities are called the balance equations. Thus, a distribution is invariant if and only if it satisfies the balance equations.
An irreducible Markov chain has at most one invariant distribution. It has one if and only if it is positive recurrent. In that case, the Markov chain is ergodic and asymptotically stationary in that the distribution of Xn converges to the stationary distribution as we saw in the previous section.
Examples of calculations of stationary distribution abound.
Theorem (This
theorem summarizes the discussion of the previous two sections)
Consider an irreducible Markov chain. It is either transient, null recurrent, or positive recurrent. Only the last case is possible for a finite Markov chain.
If the Markov chain is transient or null recurrent, then it has no invariant distribution; the fraction of time it is in state j converges to zero for all j, and the probability that it is in state j converges to 0 for all j.
If the Markov chain is positive recurrent, it has a unique invariant distribution p. The fraction of time that the Markov chain is in state j converges to p(j) for all j. If the Markov chain is aperiodic, then the probability that it is in state j converges to p(j) for all j.
First Passage Time
We can extend the example of the gambler’s ruin to a general Markov chain. For instance, let X be a Markov chain on S with transition probability matrix P. Let also A Ì S be a given subset and T = min{n ³ 0 | Xn Î A} and define a(i) = E[T | X0 = i]. Then one finds that
a(i) = 1 + SjP(i, j)a(j), for i Ï A.
Of course, a(i) = 0 for i Î A. In finite cases, these equations suffice to determine a(i). In infinite cases, one may have to introduce a boundary as we did in the case of the reflected fortune process. In many cases, no simple solution can be found.
Time Reversal
Assume that X is a stationary irreducible Markov chain with invariant distribution p and transition probability matrix P on S. How does the time-reversed process X’ = {XN – n, n ³ 0} look like? It turns out that X’ is also a stationary Markov chain with the same invariant distribution (obviously) and with transition probability matrix P’ given by
P’(i, j) = p(i)P(i, j)/p(j), i, j Î S.
In some cases, P = P’. In those cases, X and X’ have the same finite dimensional distributions (are indistinguishable statistically) and X is time-reversible. Thus, X is time-reversible if and only if it is stationary and
p(i)P(i, j) = p(j)P(j, i) , i, j Î S.
These equations are called the detailed balance equations. You can use these equations to verify that the stationary reflected fortune process is time-reversible.
Jean Walrand – November 2003 --- INDEX