We begin this section with a motivational example. Consider the connected graph on six vertices shown in [provisional cross-reference: fig-markovchain]. The first move is to choose a vertex at random and move there. Afterwards, we follow the following recursive procedures. If after \(i\) moves, you are at a vertex \(x\) and \(x\) has \(d\) neighbors, choose one of the neighbors at random, with each having probability \(1/d\) and move there. We then attempt to answer questions of the following flavor:
For each vertex \(x\text{,}\) let \(p_{x,m}\) denote the probability that you are at vertex \(x\) after \(m\) moves. Does \(\lim_{m\rightarrow\infty}p_{x,m}\) exist and if so, how fast does the sequence converge to this limit?
How many moves must I make in order that the probability that I have walked on every edge in the graph is at least \(0.999\text{?}\)
This example illustrates the characteristics of an important class of computational and combinatorial problems, which are collectively referred to as Markov Chains:
There is a finite set of states \(S_1\text{,}\) \(S_2,\dots,S_n\text{,}\) and at time \(i\text{,}\) you are in one of these states.
If you are in state \(S_j\) at time \(i\text{,}\) then for each \(k=1,2,\dots,n\text{,}\) there is a fixed probability \(p(j,k)\) (which does not depend on \(i\)) that you will be in state \(S_k\) at time \(i+1\text{.}\)
The \(n\times n\) matrix \(P\) whose \(j,k\) entry is the probability \(p(j,k)\) of moving from state \(S_j\) to state \(S_k\) is called the transition matrix of the Markov chain. Note that \(P\) is a stochastic matrix, i.e., all entries are non-negative and all row sums are \(1\text{.}\) Conversely, each square stochastic matrix can be considered as the transition matrix of a Markov chain.
For example, here is the transition matrix for the graph in [provisional cross-reference: fig-markovchain].
\begin{equation}
P =\begin{pmatrix}0 \amp 1/4 \amp 1/4 \amp 1/4 \amp 1/4 \amp 0 \\
1/2 \amp 0 \amp 0 \amp 1/2 \amp 0 \amp 0 \\
1/3 \amp 0 \amp 0 \amp 1/3 \amp 0 \amp 1/3 \\
1/3 \amp 1/3 \amp 1/3 \amp 0 \amp 0 \amp 0 \\
1 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \\
0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \\
\end{pmatrix}\tag{16.3.1}
\end{equation}
A transition matrix \(P\) is regular if there is some integer \(m\) for which the matrix \(P^m\) has only positive entries. Here is a fundamental result from this subject, one that is easy to understand but a bit too complex to prove given our space constraints.
Theorem 16.9.
Let \(P\) be a regular \(n\times n\) transition matrix. Then there is a row vector \(W=(w_1, w_2,\dots,w_n\)) of positive real numbers summing to \(1\) so that as \(m\) tends to infinity, each row of \(P^m\) tends to \(W\text{.}\) Furthermore, \(WP=W\text{,}\) and for each \(i=1,2,\dots,n\text{,}\) the value \(w_i\) is the limiting probability of being in state \(S_i\text{.}\)
Given the statement of
Theorem 16.9, the computation of the row vector
\(W\) can be carried out by eigenvalue techniques that are part of a standard undergraduate linear algebra course. For example, the transition matrix
\(P\) displayed in
(16.3.1) is regular since all entries of
\(P^3\) are positive. Furthermore, for this matrix, the row vector
\(W=(5/13, 3/13, 2/13, 2/13, 1/13, 1/13)\text{.}\) However, the question involving how fast the convergence of
\(P^m\) is to this limiting vector is more subtle, as is the question as to how long it takes for us to be relatively certain we have made every possible transition.
Subsection 16.3.1 Absorbing Markov Chains
A state \(S_i\) in a Markov chain with transition matrix \(P\) is absorbing if \(p_{i,i}=1\) and \(p_{i,j}=0\) for all \(j\neq i\text{,}\) i.e., like the infamous Hotel California, once you are in state \(S_i\text{,}\) “you can never leave.”
Example 16.10.
We modify the transition matrix from
(16.3.1) by making states
\(4\) and
\(5\) absorbing. The revised transition matrix is now:
\begin{equation}
P =\begin{pmatrix}0 \amp 1/4 \amp 1/4 \amp 1/4 \amp 1/4 \amp 0 \\
1/2 \amp 0 \amp 0 \amp 1/2 \amp 0 \amp 0 \\
1/3 \amp 0 \amp 0 \amp 1/3 \amp 0 \amp 1/3 \\
1/3 \amp 1/3 \amp 1/3 \amp 0 \amp 0 \amp 0 \\
0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 0 \\
0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 1 \\
\end{pmatrix}\tag{16.3.2}
\end{equation}
Now we might consider the following game. Start at one of the four vertices in \(\{1,2,3,4\}\) and proceed as before, making moves by choosing a neighbor at random. Vertex \(4\) might be considered as an “escape” point, a safe harbor that once reached is never left. On the other hand, vertex \(5\) might be somewhere one meets a hungry tiger and be absorbed in a way not to be detailed here.
We say the Markov chain is absorbing if there is at least one absorbing state and for each state \(S_j\) that is not absorbing, it is possible to reach an absorbing state—although it may take many steps to do so. Now the kinds of questions we would like to answer are:
If we start in non-absorbing state \(S_i\text{,}\) what is the probability of reaching absorbing state \(S_j\) (and then being absorbed in that state, a question which takes on genuine unpleasantness relative to tigers)?
If we are absorbed in state \(S_j\text{,}\) what is the probability that we started in non-absorbing state \(S_i\text{?}\)
If we start in non-absorbing state \(S_i\text{,}\) what is the expected length of time before we will be absorbed?
