Markov chains with finite and countable state space, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET PDF Download

Markov Chains Introduction 

1. Consider a discrete time Markov chain{X_i,i = 1,2,...}that takes values on a countable (finite or infinite) set S = {x₁,x₂,...}, where xi is the i-th state, the state of the stochastic process at time i.

Examples of countable S are: 

• Z^d, d dimensional integers lattice
• set of all partitions of {1,2,...,n}
• set of all configurations of magnetic spins (-1 or 1) of a n×n lattice grid (Ising model)
• set of possible moves of a king on a chess board
• set of possible route of visitation of n cities (traveling salesman problem)
• set of all length d vectors of 0’s and 1’s
• any finite set 

It can be viewed as a stochastic process X_i indexed over time i = 1,2,.... It is called a Markov chain if it satisfies the Markov property: the next state X_i+1 depends only on the current state X_i (memoryless property), i.e. 

P(X_i+1 = x_j|X_i = x_i,···,X₀ = x₀)

= P(X_i+1 = x_j|X_i = x_i).

The probability P_ij = P(X_i+1 = x_j|X_i = x_i) is called the transition matrix. Any row of a transition matrix will sum to one, i.e.,P_j P_ij = 1 for all i. The initial distribution for X₀ determine the distribution for any n-th state.

2. Random walk. You play a coin tossing game. You win $1 if a head appears and lose $1 if a tail appears. Let X_i be your total gain after i tosses. Assume the coin is unbiased, then the transition matrix is given by

We can model the coin tossing a simple random walk   The expected pay off does not change over time, i.e. EX_i+1 = EX_i.

In this case,  Please compute this probability.

3. Chapman-Kolmogorov equation. Let    be the transition kernel from x to y in n-steps, i.e  Then we have

The the probability of reaching y from x in n-steps is the sum of all probabilities going from x to y through an intermediate point z. 

Let be a matrix

Then in terms of matrix, Chapman-Kolomogorov equation can be trivially written as P^m+n = P^mPⁿ.

4. Example. A rat became insane and moves back and forth between position 1 and 2. Let X_i be the position of the rat at the i-th move. Suppose that the transition probability is given by 

On a finite state space, a state i is called recurrent if the Markov chain returns to i with probability 1 in a finite number of steps otherwise the state is transient. The recurrent of a state is equivalent to a guarantee of a sure return. Is the state 1 and 2 recurrent? 

for j = 1,2. So the state 1 and 2 are recurrent.

5. Let us find P(X_n = 1|X₀ = 2). Note that this is n step transition probability denoted by P_n 12. It is computed by the Chapman-Kolmogorov equation. For this we need to compute . In general there are theorems to do this. We are glad to do this computationally for now and find out that

So we can see that the transition probabilities converge:   and  such that 

 Then π is a stationary distribution for the Markov chain with transition probability P if 

An interesting property on π_j is that it is the expected number of states a Markov chain should take to return to the original state j. In our crazy rat example, the rat will return to position 2 in average 3 steps if it was at the position 2 initially. 

7. An increased stability for a Markov chain can be achieved if we let X₀ ∼ π, i.e. P(X₀ = j) = π_j. We have X₁ ∼ π'P = π'. Similarly X_i ∼ π. 

 Note that π is the eigenvector corresponding to the eigenvalue 1 for the matrix P.

Actually you don’t need to have X₀ ∼ π to have a stable chain. If X₀ ∼ µ for any probability distribution, µ^'P_n → π^' as n →∞. 

8. In general, the Markov chain is completely specified in terms of the distribution of the initial state X₀ ∼ µ and the transition probability matrix P

9. This is the basis of MCMC. Given probability distribution π, we want to estimate some functions of π, e.g., E_πg(X). The idea is to construct a Markov chain X_i and let the chain run a long time (burn in stage) so that it will converge to its stationary distribution π. We then sample from an dependent sample from this stationary distribution and use it to estimate the integral function.

The difference between MCMC and a simple Monte-Carlo method is that MCMC sample are dependent and and simple Monte Carlo sample are independent.

Markov Chains Concepts

We want to know: Under what conditions will the chain will converge? What is the stationary distribution it converges to? We will talk about finite state space first, then extend it to infinite countable space

2.1 Markov Chains on Finite S

One way to check for convergence and stationarity is given by the following theorem:
Peron-Frobenius Theorem If there exists a positive integer n such that  (i.e.,all the elements of Pⁿ are strictly positive), then the chain will converge to the stationary distribution π.

Although the condition required in Peron-Frobenious theorem is easy to state, sometimes it is difficult to establish for a given transition matrix P. Therefore, we seek another way to characterize the convergence of a Markov chain with conditions that may be easier to check.

For finite state space, the transition matrix needs to satisfy only two properties for the Markov chain to converge. They are: ireducibility and aperiodicity.

Irreducibility implies that it is possible to visit from any state to any state in a finite number of steps. In other words, the chain is able to visit the entire S from any starting point X₀.

Aperiodicity implies that the Markov chain does not cycle around in the states with a finite period. The problem with periodicity is limiting the chain to return to certain states at some constant time intervals. Some definitions:
 

1. Two states are said to communicate if it is possible to go from one to another in a finite number of steps. In other words, x_i and x_j are said to communicate if there exists a positive integer such that  

2. A Markov chain is said to be irreducible if all states communicate with each other for the corresponding transition matrix. For the above example, the Markov chain resulting from the first transition matrix will be irreducible while the chain resulting from the second matrix will be reducible into two clusters: one including states x₁ and x₂, and the other including the states x₃ and x₄

3. For a state xi and a given transition matrix P_ij, define the period of x_i as d(x_i) = 

4. If two states communicate, then it can proved that their periods are the same. Thus, in an irreducible Markov chain where all the states communicate, they all have the same period. This is called the period of an irreducible Markov chain.

5. An irreducible Markov chain is called aperiodic if its period is one.

6. (Theorem) For a irreducible and aperiodic Markov chain on a finite state space, it can be shown that the chain will converge to a stationary distribution. If we let the chain run for long time, then the chain can be view as a sample from its (unique) stationary probability distribution. These two conditions also imply: that all the entries of  are positive for some positive integer n. The requirement needed for the Peron-Frobenius Theorem.

2.2 Markov Chains on Infinite but countable S

1. In case of infinite but countable state space, the Markov chain convergence requires an additional concept — positive recurrence — to ensure that the chain has a unique stationary probability.

2. The state x_i is recurrent iff P(the chain starting from xi returns to x_i infinitely often) = 1. A state is said to be transient if it is not recurrent.

3. It can be shown that a state is recurrent iff 

4. Another way to look at recurrent/transient: A state i is said to be transient if, given that we start in state i, there is a non-zero probability that we will never return back to i. Formally, let the random variable T_i be the next return time to state i

Ti = min{n : X_n = i|X₀ = i)

Then, state i is transient if T_i is not finite with some probability, i.e., P(T_i < ∞) < 1. If a state i is not transient, i.e., P(T_i < ∞) = 1 (it has finite hitting time with probability 1), then it is said to be recurrent. Although the hitting time is finite, it need not have a finite average. Let Mi be the expected (average) return time, state i is said to be positive recurrent if Mi is finite; otherwise, state i is null recurrent.

5. If two states x_i and x_j communicate, and x_i is (positive) recurrent, then x_j is also (positive) recurrent.

6. (Theorem) For a irreducible, aperiodic, and positive recurrent Markov chain on a countably infinite state space, it can be shown that the chain will converge to a stationary distribution. This chain is said to be ergodic.