4.18 Markov chains

Work through these

• State the Markov property, and say what it throws away

  The next state depends on the present one and on nothing earlier. It is a strong assumption and it is what makes everything else in this topic computable, so it is worth knowing when it is false.

• Write a transition matrix, and check that every row sums to one

  The table of probabilities of moving from each state to each other state. The row sums are the first thing to check, because a matrix that fails that test is not a chain at all.

• Compute n-step probabilities, and apply the Chapman-Kolmogorov relation

  Raising the transition matrix to a power gives the probability of moving between two states in a given number of steps. The relation says why: a long path splits into two shorter ones at every intermediate state.

• Find the stationary distribution as an eigenvector with eigenvalue one

  The distribution that no longer moves when the chain is applied to it, which is where a long run settles. It is the eigenvector problem from linear algebra arriving in a new place.

• Say when a chain has a unique long-run answer, and when it does not

  A chain that can reach every state and does not cycle rigidly settles to one distribution regardless of where it started. Chains that fail either condition need a more careful answer.