Question

Three white and three black balls are distributed in two urns in such a way that each contains three balls. We will say that the system is in state i, i = 0, 1, 2, 3, if the first urn contains i, white balls. At each step, we draw one ball from each urn – the ball drawn from the first urn is placed into the second, and the ball from the second urn is placed into the first. Let X_n denote the state of the system after the n^th step.

Explain why {X_n, n = 0, 1, 2, …} is a Markov chain.

Draw the state transition diagram.

Determine its transition probability matrix.

What are the communicating classes? Why?

Is the Markov chain irreducible? Why?

What is the period of each state? Why?

Which states are transient? Which are recurrent? Why?

Answer 1

Answer 1:

A stochastic process {Xn; n = 0, 1, . . .} in discrete time with finite or infinite state space S is a Markov Chain with stationary transition probabilities if it satisfies: (1) For each n ? 1, if A is an event depending only on any subset of {Xn?1, Xn?2, . . . , 0}, then, for any states i and j in S, P(Xn+1 = j | Xn = i and A) = P(Xn+1 = j | Xn = i). (2) For any given states i and j P(Xn+1 = j | Xn = i) is same ? n ? 0. (1) is the MARKOV PROPERTY, More generally: For each n ? 1 and m ? 1, if A is as in (1), then for any states i and j in S: P(Xn+m = j | Xn = i and A) = P(Xn+m = j | Xn = i). Denote transition probabilities in (2) by pij = P(Xn+1 = j | Xn = i). Key consequences: P(Xn+1 = j ? Xn+2 = k | Xn = i) = P(Xn+2 = k | Xn+1 = j ? Xn = i)P(Xn+1 = j | Xn = i) = P(Xn+2 = k | Xn+1 = j)P(Xn+1 = j | Xn = i) = pjkpij .

Communication classes and irreducibility for Markov chains

For a Markov chain with state space S, consider a pair of states (i, j). We say that j is reachable

from i, denoted by i ? j, if there exists an integer n ? 0 such that P

n

ij > 0. This means that

starting in state i, there is a positive probability (but not necessarily equal to 1) that the chain

will be in state j at time n (that is, n steps later); P(Xn = j|X0 = i) > 0. If j is reachable

from i, and i is reachable from j, then the states i and j are said to communicate, denoted by

i ?? j. The relation defined by communication satisfies the following conditions:

1. All states communicate with themselves: P

0

ii = 1 > 0.

2. Symmetry: If i ?? j, then j ?? i.

3. Transitivity: If i ?? k and k ?? j, then i ?? j.

The above conditions imply that communication is an example of an equivalence relation,

meaning that it shares the properties with the more familiar equality relation “ = ”:

i = i. If i = j, then j = i. If i = k and k = j, then i = j.

Only condition 3 above needs some justification, so we now prove it for completeness:

Suppose there exists integers n, m such that P

n

ik > 0 and P

m

kj > 0. Letting l = n + m,

we conclude that P

l

ij ? P

n

ikP

m

kj > 0 where we have formally used the Chapman-Kolmogorov

equations. The point is that the chain can go from i to j by first going from i to k (n steps)

and then (independent of the past) going from k to j (an additional m steps).

If we consider the rat in the open maze, we easily see that the set of states C1 = {1, 2, 3, 4}

all communicate with one another, but state 0 only communicates with itself (since it is an

absorbing state). Whereas state 0 is reachable from the other states, i ? 0, no other state can

be reached from state 0. We conclude that the state space S = {0, 1, 2, 3, 4} can be broken up

into two disjoint subsets, C1 = {1, 2, 3, 4} and C2 = {0} whose union equals S, and such that

each of these subsets has the property that all states within it communicate. Disjoint means

that their intersection contains no elements: C1 ? C2 = ?