Markov Chains

The notion of Markov dependence, defined in section 5 for Bernoulli trials, may be extended to trials with several possible outcomes. Consider trials of an experiment with possible outcomes , in which . For and let be the event that on the th trial outcome occurred. The trials are defined as Markov dependent if for any integer from 1 to and integers , from 1 to , the events satisfy the condition

In discussing Markov dependent trials with possible outcomes, it is usual to employ an intuitively meaningful language. Instead of speaking of trials of an experiment with possible outcomes, we speak of observing at times the state of a system which has possible states. We number the states (or sometimes ) and let be the event that the system is in state at time . If (6.1) holds, we say that the system is a Markov chain with possible states. In words, (6.1) states that at any time the conditional probability of transition from one’s present state to any other state does not depend on how one arrived in one’s present state. One sometimes says that a Markov chain is a system without memory of the past.

Now suppose that for any states and the conditional probability \begin{align} P(i, j)= & \text { conditional probability that the Markov chain } \tag{6.2} \\ & \text { is at time } t \text { in state } j, \text { given that at time }(t-1) \\ & \text { it was in state } i, \end{align} is independent of . The Markov chain is then said to be homogeneous (or time homogeneous). A homogeneous Markov chain with states corresponds to the notion of Markov dependent repeated trials with possible outcomes. In this section, by a Markov chain we mean a homogeneous Markov chain.

The -step transition probabilities defined by \begin{align} P_{m}(i, j)= & \text { the conditional probability that the Markov } \tag{6.3} \\ & \text { chain is at time } t+m \text { in state } j, \text { given that at } \\ & \text { time } t \text { it was in state } i, \end{align} are given recursively in terms of by the system of equations, for , \begin{align} P_{m}(i, j)= & P_{m-1}(i, 1) P(1, j)+P_{m-1}(i, 2) P(2, j) \tag{6.4} \\ & +\cdots+P_{m-1}(i, r) P(r, j) \\ = & \sum_{k=1}^{r} P_{m-1}(i, k) P(k, j) \end{align} To justify (6.4) , write it in the form recall that is the event that at time the system is in state .

One may similarly prove

The unconditional probabilities, (6.6) the probability that at time the Markov chain is in state , are given for in terms of the initial unconditional probabilities by

One proves (6.7) in exactly the same way that one proves (6.4) and (6.5) . Similarly, one may show that

The transition probabilities of a Markov chain with states are best exhibited in the form of a matrix. The matrix is said to be an matrix, since it has rows and columns.

Given an matrix and an matrix , we define the product of the two matrices as the matrix whose element , lying at the intersection of the th row and the th column, is given by It should be noted that matrix multiplication is associative; for any matrices , and .

If we define the -step transition probability matrix of a Markov chain by we see that (6.4) and (6.5) may be concisely expressed.

Example 6A . If the transition probability matrix of a Markov chain is given by then the chain consists of three states, since is a matrix, and the 2 -step and 3 -step transition probability matrices are given by

If the initial unconditional probabilities are assumed to be given by then

We define a Markov chain with states as ergodic if numbers exist such that for any states and

In words, a Markov chain is ergodic if, as tends to , the -step transition probabilities tend to a limit that depends only on the final state and not on the initial state . If a Markov chain is ergodic, then after a large number of trials it achieves statistical equilibrium in the sense that the unconditional probabilities tend to limits

which are the same, no matter what the values of the initial unconditional probabilities . To see that (6.13) implies (6.14) , take the limit of both sides of (6.7) and use the fact that .

In view of (6.14) , we call the stationary probabilities of the Markov chain, since these represent the probabilities of being in the various states after one has achieved statistical equilibrium.

One of the important problems of the theory of Markov chains is to determine conditions under which a Markov chain is ergodic. A discussion of this problem is beyond the scope of this book. We state without proof the following theorem.

If there exists an integer such that then the Markov chain with transition probability matrix is ergodic.

It is sometimes possible to establish that a Markov chain is ergodic without having to exhibit an -step transition probability matrix , all the entries of which are positive. Given two states and in a Markov chain, we say that one can reach from if states exist such that

Two states and are said to communicate if one can reach from and also from . The following theorem can be proved.

If all states in a Markov chain communicate and if a state exists such that , then the Markov chain is ergodic.

Having established that a Markov chain is ergodic, the next problem is to obtain the stationary probabilities . It is clear from (6.4) that the stationary probabilities satisfy the system of linear equations,

Consequently, if a Markov chain is ergodic, then a solution of (6.17) that satisfies the conditions exists. It may be shown that if a Markov chain with transition probability matrix is ergodic then the solution of (6.17) satisfying (6.18) is unique and necessarily satisfies (6.13) and (6.14) . Consequently, to find the stationary probabilities, we need solve only (6.17) .

Example 6B . The Markov chain considered in example 6A is ergodic, since for all states and . To compute the stationary probabilities , we need only to solve the equations subject to (6.18) . It is clear that is a solution of (6.19) satisfying (6.18) . In the long run, the states 1,2, and 3 are equally likely to be the state of the Markov chain.

A matrix is defined as stochastic if the sum of the entries in any row is equal to 1; in symbols, is stochastic if

The matrix is defined as doubly stochastic if in addition the sum of the entries in any column is equal to 1; in symbols, is doubly stochastic if (6.20) holds and also

It is clear that the transition probability matrix of a Markov chain is stochastic. If is doubly stochastic (as is the matrix in example 6A), then the stationary probabilities are given by in which is the number of states in the Markov chain. To prove (6.22) one need only verify that if is doubly stochastic then (6.22) satisfies (6.17) and (6.18) .

Example 6C . Random walk with retaining barriers. Consider a straight line on which are marked off positions , and 5, arranged from left to right. A man (or an atomic particle, if one prefers physically significant examples) performs a random walk among the six positions by tossing a coin that has probability (where ) of falling heads and acting in accordance with the following set of rules: if the coin falls heads, move one position to the right, if at , or 4, and remain at 5, if at 5; if the coin falls tails, move one position to the left, if at , or 5, and remain at 0, if at 0. The positions 0 and 5 are retaining barriers; one cannot move past them. In example we consider the case in which positions 0 and 5 are absorbing barriers; if one reaches these positions, the walk stops. The transition probability matrix of the random walk with retaining barriers is given by All states in this Markov chain communicate, since

The chain is ergodic, since . To find the stationary probabilities , we solve the system of equations: \begin{align} & \pi_{0}=q \pi_{0}+q \pi_{1} \\ & \pi_{1}=p \pi_{0}+q \pi_{2} \\ & \pi_{2}=p \pi_{1}+q \pi_{3} \\ & \pi_{3}=p \pi_{2}+q \pi_{4} \tag{6.24} \\ & \pi_{4}=p \pi_{3}+q \pi_{5} \\ & \pi_{5}=p \pi_{4}+p \pi_{5}. \end{align}

We solve these equations by successive substitution.

From the first equation we obtain By subtracting this result from the second equation in (6.24) , we obtain Similarly, we obtain

To determine , we use the fact that

We finally conclude that the stationary probabilities for the random walk with retaining barriers for are given by

If a Markov chain is ergodic, then the physical process represented by the Markov chain can continue indefinitely. Indeed, after a long time it achieves statistical equilibrium and probabilities exist of being in the various states that depend only on the transition probability matrix .

We next desire to study an important class of non-ergodic Markov chains, namely those that possess absorbing states. A state in a Markov chain is said to be absorbing if for all states , so that it is impossible to leave an absorbing state. Equivalently, a state is absorbing if .

Example 6D . Random walk with absorbing barriers. Consider a straight line on which positions , and 5, arranged from left to right, are marked off. Consider a man who performs a random walk among the six positions according to the following transition probability matrix:

In the Markov chain with transition probability matrix , given by (6.26) , the states 0 and 5 are absorbing states; consequently, this Markov chain is called a random walk with absorbing barriers. The model of a random walk with absorbing barriers describes the fortunes of gamblers with finite capital. Let two opponents, and , have 5 cents between them. Let toss a coin, which has probability of falling heads. On each toss he wins a penny if the coin falls heads and loses a penny if the coin falls tails. For we define the chain to be in state if has cents.

Given a Markov chain with an absorbing state , it is of interest to compute for each state

We call the probability of absorption in state , given the initial state , since one remains in if one ever arrives there.

The probability is defined on a sample description space consisting of a countably infinite number of trials. We do not in this book discuss the definition of probabilities on such sample spaces. Consequently, we cannot give a proof of the following basic theorem, which facilitates the computation of the absorption probabilities .

If is an absorbing state in a Markov chain with states , then the absorption probabilities are the unique solution to the system of equations:

Equation (6.28) is proved as follows. The probability of going from state to state is the sum, over all states , of the probability of going from to via ; this probability is the product of the probability of going from to in one step and the probability of then ever passing from to .

Example 6E . Probability of a gambler’s ruin. Let and play the coin-tossing game described in example 6D. If ’s initial fortune is 3 cents and ’s initial fortune is 2 cents, what is the probability that ’s fortune will be 0 cents before it is 5 cents, and will be ruined?

Solution

For let be the probability that ’s fortune will ever be 0, given that his initial fortune was cents. In view of (6.28), the absorption probabilities are the unique solution of the equations

To solve these equations we note that, defining , Therefore, there is a constant such that (since ), To determine the constant , we use the fact that . We see that so that Consequently, for In particular, the probability that will be ruined, given his initial fortune is 3 cents, is given by

Exercises

6.1 . Compute the 2-step and 3-step transition probability matrices for the Markov chains whose transition probability matrices are given by

(i)

Answer

(i), (iii) ;

(ii)

(iv)

6.2 . For each Markov chain in exercise 6.1, determine whether or not (i) it is ergodic, (ii) it has absorbing states.

6.3 . Find the stationary probabilities for each of the following ergodic Markov chains:

(ii)

(iii)

Answer

(i), (iii) ; (ii) .

6.4 . Find the stationary probabilities for each of the following ergodic Markov chains: $Multiple \tag\left[\begin{array}{lll} \frac{1}{2} & \frac{1}{4} & \frac{1}{4} \tag{i} \\ \frac{1}{4} & \frac{1}{2} & \frac{1}{4} \\ \frac{1}{4} & \frac{1}{4} & \frac{1}{2} \end{array}\right]\]$

6.5 . Consider a series of independent repeated tosses of a coin that has probability of falling heads. Let us say that at time we are in state , or depending on whether outcomes of tosses and were , or . Find the transition probability matrix of this Markov chain. Also find .

Answer

has rows . For the rows are .

6.6 . Random walk with retaining barriers. Consider a straight line on which positions are marked off. Consider a man who performs a random walk among the positions according to the following transition probability matrix: Prove that the Markov chain is ergodic. Find the stationary probabilities.

6.7 . Gambler’s ruin. Let two players and have 7 cents between them. Let toss a coin, which has probability of falling heads. On each toss he wins a penny if the coin falls heads and he loses a penny if the coin falls tails. If ’s initial fortune is 3 cents, what is the probability that ’s fortune will be 0 cents before it is 7 cents, and that will be ruined.

Answer

if if .

6.8 . Consider 2 urns, I and II, each of which contains 1 white and 1 red ball. One ball is drawn simultaneously from each urn and placed in the other urn. Let the probabilities that after repetitions of this procedure urn will contain 2 white balls, 1 white and 1 red, or 2 red balls be denoted by , and , respectively. Deduce formulas expressing , and in terms of , and . Show that , and tend to limiting values as tends to infinity. Interpret these values.

6.9 . In exercise 6.8 find the most probable number of red balls in urn after (i) 2, (ii) 6 exchanges.

Answer

Exercises

Quick Links

Social Media