Notes on Markov Chains

1

Notes on Markov Chains

A Markov chain is a finite-state process that can be characterized completely by two objects – the finite set of states Z = {z1 , ..., zn } and the transition matrix Π = [π ij ]i,j=1,n that describes the probability of leaving state i and entering state j. Π must have rows that sum to 1 and are not negative: π ij

j

≥ 0 = 1 ∀i.

π ij

That is, with probability 1 you must move from state i to some state j and transition probabilities are never negative. Π gives the probability of transitioning between states in t and t + 1; correspondingly, Πn gives the probability of transitioning between states in t and t + n. For dynamic programming purposes, we will need the transition probability matrix to be time-invariant. We also need the invariant distribution, which is the ”long-run” probability of being in a given state, to be unique. Markov chains that have two properties possess unique invariant distributions. Definition 1 State i communicates with state j if π n > 0 and π n > 0 for ij ji some n ≥ 1. A Markov chain is said to be irreducible if every pair (i, j) communicate. An irreducible Markov chain has the property that it is possible to move from any state to any other state in a countable number of periods. Note that we do not require that such a movement is possible in one step, so π ij = 0 is permitted. Definition 2 The period of state i is given by k = gcd {n : π n > 0} . ii If k = 1 for all i the Markov chain is aperiodic. For a Markov chain that is both irreducible and aperiodic, Π possesses only one eigenvalue of modulus 1 (that is has one such eigenvalue is a consequence of the Perron-Frobenius theorem). It also does not possess more any absorbing states (a state i∗ such that π i∗ i∗ = 1) or transient states (a state i∗ such that π i∗ j = 0 ∀j = i∗ ). If these two conditions are satisfied, then there exists a set of probabilities [π ∗ ]i=1,n that define the unconditional probability of being in state i; this vector solves the...