本文为《Linear algebra and its applications》的读书笔记

Markov chains

The Markov chains are used as mathematical models of a wide variety of situations. The model is used to describe an experiment or measurement that is performed many times in the same way, where the outcome of each trial of the experiment will be one of several specified possible outcomes, and where the outcome of one trial depends only on the immediately preceding trial.

For example, if the population of a city and its suburbs were measured each year, then a vector such as
x 0 = [ . 6 . 4 ] \boldsymbol x_0=\begin{bmatrix}.6\\.4\end{bmatrix} x0​=[.6.4​]

could indicate that 60% of the population lives in the city and 40% in the suburbs.

A vector with nonnegative entries that add up to 1 is called a probability vector (概率向量). A stochastic matrix (随机矩阵) is a square matrix whose columns are probability vectors. A Markov chain is a sequence of probability vectors x 0 , x 1 , x 2 . . . \boldsymbol x_0,\boldsymbol x_1,\boldsymbol x_2... x0​,x1​,x2​..., together with a stochastic matrix P P P, such that
x 1 = P x 0 ,     x 2 = P x 1 ,     x 3 = P x 2 ,     . . . \boldsymbol x_1=P\boldsymbol x_0,\ \ \ \boldsymbol x_2=P\boldsymbol x_1,\ \ \ \boldsymbol x_3=P\boldsymbol x_2,\ \ \ ... x1​=Px0​,   x2​=Px1​,   x3​=Px2​,   ...

Thus the Markov chain is described by the first-order difference equation
x k + 1 = P x k       f o r   k = 0 , 1 , 2 , . . . \boldsymbol x_{k+1}=P\boldsymbol x_k\ \ \ \ \ for\ k=0,1,2,... xk+1​=Pxk​     for k=0,1,2,...

When a Markov chain of vectors in R n \mathbb R^n Rn describes a system or a sequence of experiments, the entries in x k \boldsymbol x_k xk​ list, respectively, the probabilities that the system is in each of n n n possible states, or the probabilities that the outcome of the experiment is one
of n n n possible outcomes. For this reason, x k \boldsymbol x_k xk​ is often called a state vector (状态向量).

EXAMPLE 1
Section 1.10 examined a model for population movement between a city and its suburbs. The annual migration between these two parts of the metropolitan region was governed by the m i g r a t i o n   m a t r i x migration\ matrix migration matrix M M M:

The columns of M M M are probability vectors, so M M M is a stochastic matrix.

EXERCISE 19
Let S S S be the 1 × n 1 \times n 1×n row matrix with a 1 in each column,
S = [ 1 1 . . . 1 ] S =\begin{bmatrix} 1&1&...&1 \end{bmatrix} S=[1​1​...​1​]

a. Explain why a vector x \boldsymbol x x in R n \mathbb R^n Rn is a probability vector if and only if its entries are nonnegative and S x = 1 S\boldsymbol x = 1 Sx=1.
b. Let P P P be an n × n n \times n n×n stochastic matrix. Explain why S P = S SP = S SP=S.
c. Let P P P be an n × n n \times n n×n stochastic matrix, and let x \boldsymbol x x be a probability vector. Show that P x P\boldsymbol x Px is also a probability vector.
d. show that if P P P is an n × n n \times n n×n stochastic matrix, then so is P 2 P^2 P2.

Predicting the Distant Future

The most interesting aspect of Markov chains is the study of a chain’s long-term behavior. For instance, what happens to the population distribution in Example 1 “in the long run”?

Before answering these questions, we turn to a numerical example.

EXAMPLE 3
Let P = [ . 5 . 2 . 3 . 3 . 8 . 3 . 2 0 . 4 ] P=\begin{bmatrix} .5&.2&.3\\ .3&.8&.3\\.2&0&.4 \end{bmatrix} P=⎣⎡​.5.3.2​.2.80​.3.3.4​⎦⎤​ and x 0 = [ 1 0 0 ] \boldsymbol x_0=\begin{bmatrix} 1\\0\\0 \end{bmatrix} x0​=⎣⎡​100​⎦⎤​. Consider a system whose state is described by the Markov chain x k + 1 = P x k       f o r   k = 0 , 1 , 2 , . . . \boldsymbol x_{k+1}=P\boldsymbol x_k\ \ \ \ \ for\ k=0,1,2,... xk+1​=Pxk​     for k=0,1,2,... What happens to the system as time passes?
SOLUTION

The results of further calculations are shown below, with entries rounded to four or five significant figures.

These vectors seem to be approaching q = [ . 3 . 6 . 1 ] \boldsymbol q=\begin{bmatrix} .3\\.6\\.1 \end{bmatrix} q=⎣⎡​.3.6.1​⎦⎤​. The probabilities are hardly changing from one value of k k k to the next. Observe that the following calculation is exact (with no rounding error):

When the system is in state q \boldsymbol q q, there is no change in the system from one measurement to the next.

Steady-State Vectors (稳态向量)

If P P P is a stochastic matrix, then a steady-state vector (or equilibrium vector (平衡向量)) for P P P is a probability vector q \boldsymbol q q such that
P q = q P\boldsymbol q=\boldsymbol q Pq=q

It can be shown that every stochastic matrix has a steady-state vector.

The next example shows how to find a steady-state vector.

EXAMPLE 5
Let P = [ . 6 . 3 . 4 . 7 ] P=\begin{bmatrix} .6&.3\\ .4&.7\end{bmatrix} P=[.6.4​.3.7​]. Find a steady-state vector for P P P.
SOLUTION
First, solve the equation P x = x P\boldsymbol x = \boldsymbol x Px=x.

For P P P as above,

Row reduce the augmented matrix:

The general solution is x 2 [ 3 / 4 1 ] x_2\begin{bmatrix} 3/4\\1\end{bmatrix} x2​[3/41​].

Next, choose a simple basis for the solution space. One obvious choice is [ 3 / 4 1 ] \begin{bmatrix} 3/4\\1\end{bmatrix} [3/41​] but a better choice with no fractions is w = [ 3 4 ] \boldsymbol w=\begin{bmatrix} 3\\4\end{bmatrix} w=[34​].

Finally, find a probability vector in the set of all solutions of P x = x P\boldsymbol x = \boldsymbol x Px=x. Divide w \boldsymbol w w by the sum of its entries and obtain
q = [ 3 / 7 4 / 7 ] \boldsymbol q=\begin{bmatrix}3/7\\4/7\end{bmatrix} q=[3/74/7​]

The next theorem shows that what happened in Example 3 is typical of many stochastic matrices. We say that a stochastic matrix is regular (正则的) if some matrix power P k P^k Pk contains only strictly positive entries.

Also, we say that a sequence of vectors { x k : k = 1 , 2 , . . . } \{\boldsymbol x_k : k = 1, 2,...\} {xk​:k=1,2,...} converges to a vector q \boldsymbol q q as k → ∞ k \rightarrow \infty k→∞ if the entries in x k \boldsymbol x_k xk​ can be made as close as desired to the corresponding entries in q \boldsymbol q q by taking k k k sufficiently large.

注意到，将 P − I P-I P−I 的前 n − 1 n-1 n−1 行加到第 n n n 行上，必可将第 n n n 行化为 0 行，因此 P x = x P\boldsymbol x=\boldsymbol x Px=x 必有非平凡解

This theorem is proved in standard texts on Markov chains. The amazing part of the theorem is that the initial state has no effect on the long-term behavior of the Markov chain. You will see later (in Section 5.2) why this is true for several stochastic matrices studied here.