马尔可夫链

马尔可夫依赖的概念，在第5节中针对伯努利试验进行了定义，可以推广到具有多个可能结果的试验。考虑一个具有 $r$ 个可能结果 $s_{1}, s_{2}, \dots, s_{r}$ 的实验的 $n$ 次试验，其中 $r > 2$ 。对于 $k = 1, 2, \dots, n$ 和 $j = 1, 2, \dots, r$ ，令 $A_{k}^{(j)}$ 表示在第 $k$ 次试验中结果 $s_{j}$ 发生的事件。如果对于从1到 $n$ 的任何整数 $k$ 以及从1到 $r$ 的整数 $j_{1}, j_{2}, \dots, j_{k}$ ，事件 $A_{1}^{(j_{1})}, A_{2}^{(j_{2})}, \dots, A_{k}^{(j_{k})}$ 满足条件，则这些试验被定义为马尔可夫依赖的。

在讨论具有 $r$ 个可能结果的马尔可夫依赖试验时，通常采用一种直观易懂的语言。我们不说一个具有 $r$ 个可能结果的实验的 $n$ 次试验，而是说在 $n$ 个时刻观察一个具有 $r$ 个可能状态的系统的状态。我们将状态编号为 $1, 2, \dots, r$ （有时也编号为 $0, 1, \dots, r - 1$ ），并令 $A_{k}^{(j)}$ 表示系统在时刻 $k$ 处于状态 $j$ 的事件。如果(6.1)成立，我们就说该系统是一个具有 $r$ 个可能状态的马尔可夫链。用文字来说，(6.1)表明，在任何时刻，从当前状态转移到任何其他状态的条件概率，不依赖于如何到达当前状态。有时人们说，马尔可夫链是一个没有过去记忆的系统。

现在假设对于任何状态 $i$ 和 $j$ ，条件概率 $在时刻处于状态的条件概率，给定在时刻它处于状态$ 与 $t$ 无关。此时称该马尔可夫链是齐次的（或时间齐次的）。一个具有 $r$ 个状态的齐次马尔可夫链对应于具有 $r$ 个可能结果的马尔可夫依赖重复试验的概念。在本节中，我们所说的马尔可夫链均指齐次马尔可夫链。

由下式定义的 $m$ 步转移概率 $在时刻处于状态的条件概率，给定在时刻它处于状态$ 可以通过关于 $P (i, j)$ 的方程组递归地给出，对于 $m =$ $2, 3, \dots$ ，为了证明(6.4)，将其写成如下形式 $P [A_{m + 1}^{(j)} ∣ A_{1}^{(i)}] = \sum_{k = 1}^{r} P [A_{m}^{(k)} ∣ A_{1}^{(i)}] P [A_{m + 1}^{(j)} ∣ A_{m}^{(k)}]$ 回顾一下， $A_{m b}^{(j)}$ 是系统在时刻 $m$ 处于状态 $j$ 的事件。

类似地，可以证明

无条件概率，(6.6) $p_{n} (j) =$ 在时刻 $n$ 马尔可夫链处于状态 $j$ 的概率，对于 $n \geq 2$ ，可以通过初始无条件概率 $p_{1} (j)$ 由下式给出

证明(6.7)的方法与证明(6.4)和(6.5)的方法完全相同。类似地，可以证明

具有 $r$ 个状态的马尔可夫链的转移概率 $P (i, j)$ 最好以矩阵形式表示。矩阵 $P$ 被称为 $r \times r$ 矩阵，因为它有 $r$ 行和 $r$ 列。

给定一个 $m \times r$ 矩阵 $A$ 和一个 $r \times n$ 矩阵 $B$ ， $A = [\begin{array}{cccc} a_{11} & a_{12} & \dots & a_{1 r} \\ a_{21} & a_{22} & \dots & a_{2 r} \\ \dots & \dots & \dots & \dots \\ a_{m 1} & a_{m 2} & \dots & a_{m r} \end{array}] B = [\begin{array}{cccc} b_{11} & b_{12} & \dots & b_{1 n} \\ b_{21} & b_{22} & \dots & b_{2 n} \\ \dots & \dots & \dots & \dots \\ b_{r 1} & b_{r 2} & \dots & b_{r n} \end{array}]$ 我们定义这两个矩阵的乘积 $C = A B$ 为一个 $m \times n$ 矩阵，其位于第 $i$ 行和第 $j$ 列交叉处的元素 $c_{i j}$ 由下式给出应当注意，矩阵乘法满足结合律；对于任何矩阵 $A, B$ 和 $C$ ，有 $A (B C) =$ $(A B) C$ 。

如果我们通过下式定义马尔可夫链的 $m$ 步转移概率矩阵 $P_{m}$ 我们看到(6.4)和(6.5)可以被简洁地表达。

例6A。如果一个马尔可夫链的转移概率矩阵 $P$ 由下式给出 $P = [\begin{array}{ccc} 0 & \frac{1}{3} & \frac{2}{3} \\ \frac{2}{3} & 0 & \frac{1}{3} \\ \frac{1}{3} & \frac{2}{3} & 0 \end{array}]$ 那么该链由三个状态组成，因为 $P$ 是一个 $3 \times 3$ 矩阵，并且2步和3步转移概率矩阵由下式给出 $P_{2} = P P = [\begin{array}{ccc} \frac{4}{9} & \frac{4}{9} & \frac{1}{9} \\ \frac{1}{9} & \frac{4}{9} & \frac{4}{9} \\ \frac{4}{9} & \frac{1}{9} & \frac{4}{9} \end{array}], P_{3} = P_{2} P = [\begin{array}{ccc} \frac{1}{3} & \frac{2}{9} & \frac{4}{9} \\ \frac{4}{9} & \frac{1}{3} & \frac{2}{9} \\ \frac{2}{9} & \frac{4}{9} & \frac{1}{3} \end{array}]$

如果假设初始无条件概率由下式给出 $p_{1} = (p_{1} (1), p_{1} (2), p_{1} (3)) = (\frac{1}{2}, \frac{1}{4}, \frac{1}{4}),$ 那么

如果存在数 $π_{1}, π_{2}, \dots, π_{r}$ 使得对于任何状态 $i$ 和 $j$ ，有

则我们定义一个具有 $r$ 个状态的马尔可夫链是遍历的。用文字来说，一个马尔可夫链是遍历的，如果当 $m$ 趋于 $\infty$ 时， $m$ 步转移概率 $P_{m} (i, j)$ 趋于一个极限，该极限仅依赖于最终状态 $j$ ，而不依赖于初始状态 $i$ 。如果一个马尔可夫链是遍历的，那么经过大量试验后，它会达到统计平衡，即无条件概率 $p_{n} (j)$ 趋于极限

无论初始无条件概率 $p_{1} (j)$ 的值是多少，这些极限都是相同的。要看出(6.13)蕴含(6.14)，对(6.7)两边取极限，并利用 $\sum_{k = 1}^{r} p_{1} (k) = 1$ 这一事实。

鉴于(6.14)，我们称 $π_{1}, π_{2}, \dots, π_{r}$ 为马尔可夫链的平稳概率，因为它们代表了在达到统计平衡后处于各个状态的概率。

马尔可夫链理论的重要问题之一是确定一个马尔可夫链在什么条件下是遍历的。对这个问题的讨论超出了本书的范围。我们不加证明地陈述以下定理。

如果存在一个整数 $m$ 使得 $对于所有状态和$ 那么具有转移概率矩阵 $P$ 的马尔可夫链是遍历的。

有时无需展示一个所有元素都为正的 $m$ 步转移概率矩阵 $P_{m}$ ，也可以确定一个马尔可夫链是遍历的。给定马尔可夫链中的两个状态 $i$ 和 $j$ ，如果存在状态 $i_{1}, i_{2}, \dots, i_{Y}$ 使得

我们就说可以从 $j$ 到达 $i$ 。如果既可以从 $j$ 到达 $i$ ，又可以从 $i$ 到达 $j$ ，则称两个状态 $i$ 和 $j$ 是互通的。可以证明以下定理。

如果一个马尔可夫链中的所有状态都互通，并且存在一个状态 $i$ 使得 $P (i, i) > 0$ ，那么该马尔可夫链是遍历的。

在确定一个马尔可夫链是遍历的之后，下一个问题是求出平稳概率 $π_{j}$ 。从(6.4)可以清楚地看出，平稳概率满足线性方程组，

因此，如果一个马尔可夫链是遍历的，那么存在(6.17)的一个解，满足条件 $对于$ 。可以证明，如果一个具有转移概率矩阵 $P$ 的马尔可夫链是遍历的，那么满足(6.18)的(6.17)的解是唯一的，并且必然满足(6.13)和(6.14)。因此，为了找到平稳概率，我们只需要求解(6.17)。

例6B。例6A中考虑的马尔可夫链是遍历的，因为对于所有状态 $i$ 和 $j$ ，有 $P_{2} (i, j) > 0$ 。为了计算平稳概率 $π_{1}, π_{2}, π_{3}$ ，我们只需要求解方程并满足(6.18)。显然 $π_{1} = π_{2} = π_{3} = \frac{1}{3}$ 是(6.19)的一个解，且满足(6.18)。从长远来看，状态1、2和3成为马尔可夫链的状态的可能性是相等的。

一个矩阵 $A = [\begin{array}{llll} a_{11} & a_{12} & \dots & a_{1 r} \\ a_{21} & a_{22} & \dots & a_{2 r} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{r 1} & a_{r 2} & \dots & a_{r r} \end{array}]$ 如果其任意一行元素之和等于1，则被定义为随机矩阵；用符号表示，如果 $对于$ ，则 $A$ 是随机矩阵。

The matrix $A$ is defined as doubly stochastic if in addition the sum of the entries in any column is equal to 1; in symbols, $A$ is doubly stochastic if (6.20) holds and also

It is clear that the transition probability matrix $P$ of a Markov chain is stochastic. If $P$ is doubly stochastic (as is the matrix in example 6A), then the stationary probabilities are given by in which $r$ is the number of states in the Markov chain. To prove (6.22) one need only verify that if $P$ is doubly stochastic then (6.22) satisfies (6.17) and (6.18) .

Example 6C . Random walk with retaining barriers. Consider a straight line on which are marked off positions $0, 1, 2, 3, 4$ , and 5, arranged from left to right. A man (or an atomic particle, if one prefers physically significant examples) performs a random walk among the six positions by tossing a coin that has probability $p$ (where $0 < p < 1$ ) of falling heads and acting in accordance with the following set of rules: if the coin falls heads, move one position to the right, if at $0, 1, 2, 3$ , or 4, and remain at 5, if at 5; if the coin falls tails, move one position to the left, if at $1, 2, 3, 4$ , or 5, and remain at 0, if at 0. The positions 0 and 5 are retaining barriers; one cannot move past them. In example $6 D$ we consider the case in which positions 0 and 5 are absorbing barriers; if one reaches these positions, the walk stops. The transition probability matrix of the random walk with retaining barriers is given by All states in this Markov chain communicate, since $0 < P (0, 1) P (1, 2) P (2, 3) P (3, 4) P (4, 5) P (5, 4) P (4, 3) P (3, 2) P (2, 1) P (1, 0)$

The chain is ergodic, since $P (0, 0) > 0$ . To find the stationary probabilities $π_{0}, π_{1}, \dots, π_{5}$ , we solve the system of equations:

We solve these equations by successive substitution.

From the first equation we obtain $q π_{1} = p π_{0} or π_{1} = \frac{p}{q} π_{0}$ By subtracting this result from the second equation in (6.24) , we obtain $q π_{2} = p π_{1} or π_{2} = \frac{p}{q} π_{1} = {(\frac{p}{q})}^{2} π_{0}$ Similarly, we obtain $\begin{array}{lll} q π_{3} = p π_{2} & or & π_{3} = \frac{p}{q} π_{2} = {(\frac{p}{q})}^{3} π_{0} \\ q π_{4} = p π_{3} & or & π_{4} = \frac{p}{q} π_{3} = {(\frac{p}{q})}^{4} π_{0} \\ q π_{5} = p π_{4} & or & π_{5} = \frac{p}{q} π_{4} = {(\frac{p}{q})}^{5} π_{0} . \end{array}$

To determine $π_{0}$ , we use the fact that

We finally conclude that the stationary probabilities for the random walk with retaining barriers for $j = 0, 1, \dots, 5$ are given by

If a Markov chain is ergodic, then the physical process represented by the Markov chain can continue indefinitely. Indeed, after a long time it achieves statistical equilibrium and probabilities $π_{1}, \dots, π_{r}$ exist of being in the various states that depend only on the transition probability matrix $P$ .

We next desire to study an important class of non-ergodic Markov chains, namely those that possess absorbing states. A state $j$ in a Markov chain is said to be absorbing if $P (j, i) = 0$ for all states $i \neq j$ , so that it is impossible to leave an absorbing state. Equivalently, a state $j$ is absorbing if $P (j, j) = 1$ .

Example 6D . Random walk with absorbing barriers. Consider a straight line on which positions $0, 1, 2, 3, 4$ , and 5, arranged from left to right, are marked off. Consider a man who performs a random walk among the six positions according to the following transition probability matrix:

In the Markov chain with transition probability matrix $P$ , given by (6.26) , the states 0 and 5 are absorbing states; consequently, this Markov chain is called a random walk with absorbing barriers. The model of a random walk with absorbing barriers describes the fortunes of gamblers with finite capital. Let two opponents, $A$ and $B$ , have 5 cents between them. Let $A$ toss a coin, which has probability $p$ of falling heads. On each toss he wins a penny if the coin falls heads and loses a penny if the coin falls tails. For $j = 0, \dots, 5$ we define the chain to be in state $j$ if $A$ has $j$ cents.

Given a Markov chain with an absorbing state $j$ , it is of interest to compute for each state $i$ $u_{j} (i) = conditional probability of ever arriving at the absorbing state j, given that one started from state i .$

We call $u_{j} (i)$ the probability of absorption in state $j$ , given the initial state $i$ , since one remains in $j$ if one ever arrives there.

The probability $u_{j} (i)$ is defined on a sample description space consisting of a countably infinite number of trials. We do not in this book discuss the definition of probabilities on such sample spaces. Consequently, we cannot give a proof of the following basic theorem, which facilitates the computation of the absorption probabilities $u_{j} (i)$ .

If $j$ is an absorbing state in a Markov chain with states ${1, 2, \dots, r}$ , then the absorption probabilities $u_{j} (1), \dots, u_{j} (r)$ are the unique solution to the system of equations:

Equation (6.28) is proved as follows. The probability of going from state $i$ to state $j$ is the sum, over all states $k$ , of the probability of going from $i$ to $j$ via $k$ ; this probability is the product of the probability $P (i, k)$ of going from $i$ to $k$ in one step and the probability $u_{j} (k)$ of then ever passing from $k$ to $j$ .

Example 6E . Probability of a gambler’s ruin. Let $A$ and $B$ play the coin-tossing game described in example 6D. If $A$ ’s initial fortune is 3 cents and ’s initial fortune is 2 cents, what is the probability that $A$ ’s fortune will be 0 cents before it is 5 cents, and $A$ will be ruined?

Solution

For $i = 0, 1, \dots, 5$ let $u_{0} (i)$ be the probability that $A$ ’s fortune will ever be 0, given that his initial fortune was $i$ cents. In view of (6.28), the absorption probabilities $u_{0} (i)$ are the unique solution of the equations

To solve these equations we note that, defining $c = u_{0} (1) - u_{0} (0)$ , Therefore, there is a constant $c$ such that (since $u_{0} (0) = 1$ ), To determine the constant $c$ , we use the fact that $u_{0} (5) = 0$ . We see that so that Consequently, for $i = 0, 1, \dots, 5$ In particular, the probability that $A$ will be ruined, given his initial fortune is 3 cents, is given by

Exercises

6.1 . Compute the 2-step and 3-step transition probability matrices for the Markov chains whose transition probability matrices are given by

(i)

$P = [\begin{array}{ll} \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} \end{array}]$

$P = [\begin{array}{ccc} \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 \\ 0 & 0 & 1 \end{array}]$

Answer

(i), (iii) $P_{2} = P_{3} = P$ ;

(ii) $P_{2} = [\begin{array}{ccc} \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{4} & \frac{1}{2} & \frac{1}{4} \end{array}], P_{3} = [\begin{array}{ccc} \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 \\ \frac{3}{8} & \frac{1}{2} & \frac{1}{8} \end{array}]$

(iv) $P_{2} = P_{3} = [\begin{array}{ccc} \frac{1}{4} & \frac{1}{2} & \frac{1}{4} \\ \frac{1}{4} & \frac{1}{2} & \frac{1}{4} \\ \frac{1}{4} & \frac{1}{2} & \frac{1}{4} \end{array}]$

6.2 . For each Markov chain in exercise 6.1, determine whether or not (i) it is ergodic, (ii) it has absorbing states.

6.3 . Find the stationary probabilities for each of the following ergodic Markov chains:

$[\begin{array}{ll} \frac{2}{3} & \frac{1}{3} \\ \frac{1}{3} & \frac{2}{3} \end{array}]$

(ii)

$[\begin{array}{ll} \frac{2}{3} & \frac{1}{3} \\ \frac{2}{3} & \frac{1}{3} \end{array}]$

(iii)

$[\begin{array}{ll} 0.99 & 0.01 \\ 0.01 & 0.99 \end{array}]$

Answer

(i), (iii) $π_{1} = π_{2} = \frac{1}{2}$ ; (ii) $π_{1} = \frac{2}{3}, π_{2} = \frac{1}{3}$ .

6.4 . Find the stationary probabilities for each of the following ergodic Markov chains: $[\begin{array}{ccc} \frac{1}{3} & \frac{1}{4} & \frac{5}{12} \\ \frac{1}{3} & \frac{1}{4} & \frac{5}{12} \\ \frac{1}{3} & \frac{1}{4} & \frac{5}{12} \end{array}]$

6.5 . Consider a series of independent repeated tosses of a coin that has probability $p > 0$ of falling heads. Let us say that at time $n$ we are in state $s_{1}, s_{2}, s_{3}$ , or $s_{1}$ depending on whether outcomes of tosses $n - 1$ and $n$ were $(H, H), (H, T), (T, H)$ , or $(T, T)$ . Find the transition probability matrix $P$ of this Markov chain. Also find $P^{2}, P^{3}, P^{4}$ .

Answer

$P$ has rows $(p, q, 0, 0), (0, 0, p, q), (p, q, 0, 0), (0, 0, p, q)$ . For $n > 1$ the rows are $(p^{2}, p q, p q, q^{2})$ .

6.6 . Random walk with retaining barriers. Consider a straight line on which positions $0, 1, 2, \dots, 7$ are marked off. Consider a man who performs a random walk among the positions according to the following transition probability matrix: $P = [\begin{array}{llllllll} q & p & 0 & 0 & 0 & 0 & 0 & 0 \\ q & 0 & p & 0 & 0 & 0 & 0 & 0 \\ 0 & q & 0 & p & 0 & 0 & 0 & 0 \\ 0 & 0 & q & 0 & p & 0 & 0 & 0 \\ 0 & 0 & 0 & q & 0 & p & 0 & 0 \\ 0 & 0 & 0 & 0 & q & 0 & p & 0 \\ 0 & 0 & 0 & 0 & 0 & q & 0 & p \\ 0 & 0 & 0 & 0 & 0 & 0 & q & p \end{array}]$ Prove that the Markov chain is ergodic. Find the stationary probabilities.

6.7 . Gambler’s ruin. Let two players $A$ and $B$ have 7 cents between them. Let $A$ toss a coin, which has probability $p$ of falling heads. On each toss he wins a penny if the coin falls heads and he loses a penny if the coin falls tails. If $A$ ’s initial fortune is 3 cents, what is the probability that $A$ ’s fortune will be 0 cents before it is 7 cents, and that $A$ will be ruined.

Answer

$\frac{4}{2}$ if $p = q = \frac{1}{2}, (q^{7} - p^{4} q^{3}) / (q^{7} - p^{7})$ if $p \neq q$ .

6.8 . Consider 2 urns, I and II, each of which contains 1 white and 1 red ball. One ball is drawn simultaneously from each urn and placed in the other urn. Let the probabilities that after $n$ repetitions of this procedure urn $I$ will contain 2 white balls, 1 white and 1 red, or 2 red balls be denoted by $p_{n}, q_{n}$ , and $r_{n}$ , respectively. Deduce formulas expressing $p_{n + 1}, q_{n + 1}$ , and $r_{n + 1}$ in terms of $p_{n}, q_{n}$ , and $r_{n}$ . Show that $p_{n}, q_{n}$ , and $r_{n}$ tend to limiting values as $n$ tends to infinity. Interpret these values.

6.9 . In exercise 6.8 find the most probable number of red balls in urn $I$ after (i) 2, (ii) 6 exchanges.

Answer

$1$ .