Markov chain

A Markov chain, named after Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process usually characterized as memoryless: the next state depends only on the current state and not on the sequence of events that preceded it. This specific kind of "memorylessness" is called the Markov property. Markov chains have many applications as statistical models of real-world processes.

A simple two-state Markov chain

Definition

A Markov chain is a sequence of random variables X₁, X₂, X₃, ... with the Markov property, namely that, given the present state, the future and past states are independent. (X_t is the state vector X at time t.)

Transition matrix (Stochastic matrix), P

(http://en.wikipedia.org/wiki/Stochastic_matrix)

If the probability of moving from i to j in one time step is Pr(j|i) = p_ij, the stochastic matrix P is given by using p_ij as the ith row and jth column element.

Conditions for Convergence of Transition matrix

For a transition matrix P to converge to an invariant distribution, it must possess the following properties:

• Irreducibility
  A Markov Chain is said to be irreducible if every state in the state space S can be reached from every other state space in a finite number of moves with positive probability. An irreducible Markov Chain is said to possess a single class.

• Aperiodicity
  The periodicity d(i) of state s_i measures the minimum number of steps it takes to have positive probability of returning to that state. The "gcd" stands for "greatest common divisor" and represents the step multiple required to return state i. A state is called aperiodic if the minimum number of steps equal 1. A Markov Chain is said to be aperiodic if all the states in the Markov Chain are aperiodic.

• Recurrence
  A state s_i is called recurrent if the chain returns to s_i with probability 1 in a finite number of steps. The Markov Chain is recurrent if all the states in S are recurrent.

When these three properties are satisfied, then all the entries of P are 0 < p_ij < 1, ∀i, j ∈ P. Intuitively, this construction of P says that there is some positive probability of moving to (or remaining in) any other state from any other state at time n. We cannot get "stuck" in any state.

The construction of a transition matrix P, with 0 < p_ij < 1, ∀i, j ∈ P, ensures that the largest eigenvalue λ = 1 and all other eigenvalue λ ≠ 1 of P satisfy |λ| < 1.

Also, in this case there exists a vector having positive entries, summing to 1, which is an eigenvector associated to the eigenvalue λ = 1.

How do you prove whether a stochastic matrix is regular or not?

A Markov chain is regular if there exists k such that, for every states, the probability of getting from a state to another state in exactly k steps is > 0.

Theorem: a regular Markov chain converges to a unique stationary distribution regardless of start state.

A regular stochastic matrix A will have at least one A_k where k = 1, 2, …, n. Power that has all of its elements positive and greater than zero.

The easy way usually is to multiple the matrix by itself until you find one of powers with all positive elements. This can be a lengthy process. The more surefire method is to use Perron Frobenius Theorem and make sure the eigenvalues satisfy the condition of Perron Frobenius Theorem.

But any method that can demonstrated that all the elements of some power of A are all positive and not zero works.

Lectures

Reference

• http://en.wikipedia.org/wiki/Markov_chain
• Markov Chains.pdf
  (http://www.ece.rice.edu/~vc3/elec633/MarkovChains.pdf)
• Application to Markov Chains