第十三章 马尔可夫链
第十三章 马尔可夫链
本章首先从随机过程在不同时刻状态之间的特殊的统计联系，引入马尔可夫(Markov)过程的概念。然后，对马尔可夫链（状态、时间都是离散的马尔可夫过程）的两个基本问题，即转移概率的确定以及遍历性问题作不同程度的研究和介绍。
马尔可夫过程的理论在近代物理、生物学、管理科学、经济、信息处理以及数字计算方法等方面都有重要应用。
§1 马尔可夫过程及其概率分布
在物理学中，很多确定性现象遵从如下演变原则：由时刻 $ t_{0} $ 系统或过程所处的状态，可以决定系统或过程在时刻 $ t>t_{0} $ 所处的状态，而无需借助于 $ t_{0} $ 以前系统或过程所处状态的历史资料。如微分方程初值问题所描绘的物理过程就属于这类确定性现象。把上述原则延伸到随机现象，即当一物理系统或过程遵循的是某种统计规律时，可仿照上面的原则，引入以下的马尔可夫性或无后效性：过程（或系统）在时刻 $ t_{0} $ 所处的状态为已知的条件下，过程在时刻 $ t>t_{0} $ 所处状态的条件分布与过程在时刻 $ t_{0} $ 之前所处的状态无关。通俗地说，就是在已经知道过程“现在”的条件下，其“将来”不依赖于“过去”。
现用分布函数来表述马尔可夫性. 设随机过程 $ \{X(t), t \in T\} $ 的状态空间为 I. 如果对时间 t 的任意 n 个数值 $ t_1 < t_2 < \cdots < t_n, n \geq 3, t_i \in T $，在条件 $ X(t_i) = x_i, x_i \in I, i = 1, 2, \cdots, n-1 $ 下， $ X(t_n) $ 的条件分布函数恰等于在条件 $ X(t_{n-1}) = x_{n-1} $ 下 $ X(t_n) $ 的条件分布函数，即
$$ \begin{aligned}P\{X(t_{n})\leqslant x_{n}\mid X(t_{1})=x_{1},X(t_{2})=x_{2},\cdots,X(t_{n-1})=x_{n-1}\}\\=P\{X(t_{n})\leqslant x_{n}\mid X(t_{n-1})=x_{n-1}\},x_{n}\in\mathbf{R},\end{aligned} $$
或写成
$$ F_{t_{n}\mid t_{1}\cdots t_{n-1}}\left(x_{n},t_{n}\mid x_{1},x_{2},\cdots,x_{n-1};t_{1},t_{2},\cdots,t_{n-1}\right)=F_{t_{n}\mid t_{n-1}}\left(x_{n},t_{n}\mid x_{n-1},t_{n-1}\right) $$
则称过程 $ \{X(t), t \in T\} $具有马尔可夫性或无后效性，并称此过程为马尔可夫过程.
例1 设 $ \{X(t), t \geqslant 0\} $是独立增量过程，且 $ X(0) = 0 $，证明 $ \{X(t), t \geqslant 0\} $是一个马尔可夫过程.
证 由(1.1)式知，只要证明在已知 $ X(t_{n-1})=x_{n-1} $ 的条件下 $ X(t_{n}) $ 与
$ X(t_{j}), j=1,2,\cdots,n-2 $ 相互独立即可. 现由独立增量过程的定义知道, 当 $ 0 < t_{j} < t_{n-1} < t_{n}, j=1,2,\cdots,n-2 $ 时, 增量
$$ X(t_{j})-X(0)\quad 与 \quad X(t_{n})-X(t_{n-1}) $$
相互独立. 根据条件 $ X(0)=0 $ 和 $ X(t_{n-1})=x_{n-1} $，即有
$$ X(t_{j})\quad 与 \quad X(t_{n})-x_{n-1} $$
相互独立。再由第三章§4定理知，此时 $ X(t_{n}) $与 $ X(t_{j}) $， $ j=1,2,\cdots,n-2 $相互独立。这表明 $ X(t) $具有无后效性，即 $ \{X(t),t\geqslant0\} $是一个马尔可夫过程。
由上例知，泊松过程是时间连续状态离散的马氏过程；维纳过程是时间状态都连续的马氏过程。
时间和状态都是离散的马尔可夫过程称为马尔可夫链，简称马氏链，记为 $ \{X_n=X(n), n=0,1,2,\cdots\} $，它可以看作在时间集 $ T_1=\{0,1,2,\cdots\} $上对离散状态的马氏过程相继观察的结果。我们约定记链的状态空间为 $ I=\{a_1,a_2,\cdots\} $， $ a_i\in\mathbb{R} $。在链的情形，马尔可夫性通常用条件分布律来表示，即对任意的正整数 $ n,r $和 $ 0\leqslant t_1 $$ \begin{aligned}P&\{X_{m+n}=a_{j}\mid X_{t_{1}}=a_{i_{1}},X_{t_{2}}=a_{i_{2}},\cdots,X_{t_{r}}=a_{i_{r}},X_{m}=a_{i}\}\\&=P\{X_{m+n}=a_{j}\mid X_{m}=a_{i}\},\end{aligned} $$ 其中 $ a_{i} \in I $. 记上式右端为 $ P_{ij}(m, m+n) $，我们称条件概率 $$ P_{ij}(m,m+n)=P\{X_{m+n}=a_{j}\mid X_{m}=a_{i}\} $$ 为马氏链在时刻 m 处于状态 $ a_{i} $ 条件下，在时刻 $ m+n $ 转移到状态 $ a_{j} $ 的转移概率. 由于链在时刻 m 从任何一个状态 $ a_{i} $ 出发，到另一时刻 $ m+n $，必然转移到 $ a_{1}, a_{2}, \cdots $ 诸状态中的某一个，所以 $$ \sum_{j=1}^{+\infty}P_{ij}(m,m+n)=1,i=1,2,\cdots. $$ 由转移概率组成的矩阵 $ \boldsymbol{P}(m,m+n)=(\boldsymbol{P}_{ij}(m,m+n)) $ 称为马氏链的转移概率矩阵。由(1.4)式知，此矩阵的每一行元之和等于1。 当转移概率 $ P_{ij}(m,m+n) $ 只与 i,j 及时间间距 n 有关时，把它记为 $ P_{ij}(n) $，即 $$ P_{ij}\left(m,m+n\right)=P_{ij}\left(n\right), $$ 并称此转移概率具有平稳性.同时也称此链是齐次的或时齐的.以下我们限于讨论齐次马氏链. 在马氏链为齐次的情形下，由(1.3)式定义的转移概率 $$ P_{ij}(n)=P\{X_{m+n}=a_{j}\mid X_{m}=a_{i}\} $$ 称为与比链的 n 步转移概率， $ P(n)=(P_{ij}(n)) $ 为 n 步转移概率矩阵。在以下的讨论中特别重要的是一步转移概率 $$ p_{ij}=P_{ij}(1)=P\{X_{m+1}=a_{j}\mid X_{m}=a_{i}\} $$ 或由它们组成的一步转移概率矩阵 $$ X_{m+1} $$ $$ \begin{aligned}X_{m}\quad&\begin{array}{c}a_{1}\\a_{1}\end{array}\begin{bmatrix}p_{11}&p_{12}&\cdots&p_{1j}\end{bmatrix}\quad\begin{array}{c}\cdots\\ \end{array}\\&a_{2}\begin{bmatrix}p_{21}&p_{22}&\cdots&p_{2j}\end{bmatrix}\quad\begin{array}{c}\cdots\\ \end{array}\\&\vdots\begin{bmatrix}\vdots&\vdots&&\vdots\\p_{i1}&p_{i2}&\cdots&p_{ij}\end{bmatrix}\quad\begin{array}{c}\end{array}\\&\vdots\begin{bmatrix}\vdots&\vdots&&\vdots\\\end{bmatrix}\end{aligned}=\boldsymbol{P}(1)\xlongequal{ 记成 }\boldsymbol{P}. $$ 在上述矩阵的左侧和上达标上状态 $ a_{1}, a_{2}, \cdots $，是为了显示 $ p_{ij} $ 是由状态 $ a_{i} $ 经一步转移到状态 $ a_{i} $ 的概率. 例2(0-1传输系统) 在如图13-1只传输数字0和1的串联系统中，设每一级的传真率（输出与输入数字相同的概率称为系统的传真率，相反情形称为误码率）为p，误码率为q=1-p，并设一个单位时间传输一级， $ X_{0} $ 是第一级的输入， $ X_{n} $ 是第n级的输出（ $ n\geqslant1 $）。那么 $ \{X_{n},n=0,1,2,\cdots\} $ 是一随机过程，状态空间 $ I=\{0,1\} $，而且当 $ X_{n}=i,i\in I $ 为已知时， $ X_{n+1} $ 所处的状态的概率分布只与 $ X_{n}=i $ 有关，而与时刻n 以前所处的状态无关，所以它是一个马氏链，而且还是齐次的。它的一步转移概率和一步转移概率矩阵分别为 $$ p_{i j}=P\{X_{n+1}=j\mid X_{n}=i\}=\{\begin{array}{l l}p,&j=i,\\ q,&j\neq i,\end{array}i,j=0,1. $$ $$ 0\quad1 $$ 和 $$ \mathbf{P}=\mathop{^{0}}_{1}\mathop{^{p}}_{q}\mathbf{\Lambda}\mathbf{\Lambda}\mathbf{\Lambda}^{q}\mathbf{\Lambda}. $$ 例3（一维随机游动）设一醉汉Q（或看作一随机游动的质点），在如图13-2所示直线的点集 $ I=\{1,2,3,4,5\} $上作随机游动，且仅在1秒、2秒等时刻发生游动。游动的概率规则是：如果Q现在位于点 $ i(1 和5这两点称为反射壁.上面这种游动称为带有两个反射壁的随机游动. 若以 $ X_{n} $ 表示时刻 n 时 Q 的位置，不同的位置就是 $ X_{n} $ 的不同状态，那么 $ \{X_{n}, n=0,1,2,\cdots\} $ 是一随机过程，状态空间就是 I，而且当 $ X_{n}=i, i \in I $ 为已知时， $ X_{n+1} $ 所处的状态的概率分布只与 $ X_{n}=i $ 有关，而与 Q 在时刻 n 以前如何到达 i 是完全无关的，所以 $ \{X_{n}, n=0,1,2,\cdots\} $ 是一马氏链，而且还是齐次的。它的一步转移概率和一步转移概率矩阵分别为 $$ p_{ij}=P\{X_{n+1}=j\mid X_{n}=i\}=\{\begin{aligned}&\frac{1}{3},j=i-1,i,i+1,1 和 $$ \mathbf { P } = 3 \left[ \begin{array} { c c c c c } { 1 } & { 2 } & { 3 } & { 4 } & { 5 } \\ { 0 } & { 1 } & { 0 } & { 0 } & { 0 } \\ { 2 } & { 1 / 3 } & { 1 / 3 } & { 1 / 3 } & { 0 } \\ { 0 } & { 1 / 3 } & { 1 / 3 } & { 1 / 3 } & { 0 } \\ { 4 } & { 0 } & { 1 / 3 } & { 1 / 3 } & { 1 / 3 } \\ { 5 } & { 0 } & { 0 } & { 1 } & { 0 } \end{array} \right]. $$ 如果把1这一点改为吸收壁，就是说Q一旦到达1这一点，则就永远留在点1上.此时，相应链的转移概率矩阵只需把P中第1横行改为(1,0,0,0,0).总之，改变游动的概率规则，就可得到不同方式的随机游动和相应的马氏链. 随机游动的思想在数值计算方法方面有重要应用 $ ^{①} $. 例4（排队模型）设服务系统由一个服务员和只可以容纳两个人的等候室组成，见图13-3.服务规则是：先到先服务，后来者需在等候室依次排队.假定一个需要服务的顾客到达系统时发现系统内已有3个顾客（一个正在接受服务，两个在等候室排队），则该顾客即离去.设时间间隔 $ \Delta t $内有一个顾客进入系统的概率为q，有一原来被服务的顾客离开系统（即服务完毕）的概率为p.又设当 $ \Delta t $充分小时，在这时间间隔内多于一个顾客进入或离开系统实际上是不可能的.再 设有无顾客来到与服务是否完毕是相互独立的.现用马氏链来描述这个服务系统. 设 $ X_{n}=X(n\Delta t) $ 表示时刻 $ n\Delta t $ 时系统内的顾客数，即系统的状态. $ \{X_{n}, n=0,1,2,\cdots\} $ 是一随机过程，状态空间 $ I=\{0,1,2,3\} $，而且仿照例2、例3的分析，可知它是一个齐次马氏链. 下面来计算此马氏链的一步转移概率. $ p_{00} $——在系统内没有顾客的条件下，经 $ \Delta t $后仍没有顾客的概率（此处是条件概率，以下同）， $ p_{00}=1-q $ $ p_{01} $——系统内没有顾客的条件下，经 $ \Delta t $后有一顾客进入系统的概率， $ p_{01}=q $ $ p_{10} $——系统内恰有一顾客正在接受服务的条件下，经 $ \Delta t $后系统内无人的概率，它等于在 $ \Delta t $间隔内顾客因服务完毕而离去，且无人进入系统的概率， $ p_{10}=p(1-q) $. $ p_{11} $——系统内恰有一顾客的条件下，在 $ \Delta t $间隔内，他因服务完毕而离去，而另一顾客进入系统，或者正在接受服务的顾客继续要求服务，且无人进入系统的概率， $ p_{11}=pq+(1-p)(1-q) $. $ p_{12} $——正在接受服务的顾客继续要求服务，且另一个顾客进入系统的概率， $ b_{12}=(1-p)q $. $ p_{13} $——正在接受服务的顾客继续要求服务，且在 $ \Delta t $间隔内有两个顾客进入系统的概率.由假设，后者实际上是不可能发生的， $ p_{13}=0 $. 类似地，有 $ p_{21}=p_{32}=p(1-q) $， $ p_{22}=pq+(1-p)(1-q) $， $ p_{23}=q(1-p) $， $ p_{ij}=0(|i-j|\geqslant2) $. $ p_{33} $——一人因服务完毕而离去且另一人进入系统，或者无人离开系统的概率， $ p_{33}=pq+(1-p) $. 于是该马氏链的一步转移概率矩阵为 $$ \mathbf{P}=1\left[\begin{matrix}{0}&{1}&{2}&{3}\\ {0}&{1-q}&{q}&{0}\\ {0}&{1-q}&{p q+(1-p)(1-q)}&{q(1-p)}&{0}\\ {2}&{0}&{p(1-q)}&{p q+(1-p)(1-q)}&{q(1-p)}\\ {3}&{0}&{0}&{p(1-q)}&{p q+(1-p)}\\ \end{matrix}\right]. $$ 在实际问题中，一步转移概率通常可通过统计试验确定，下面看一实例。 例 5 某计算机机房的一台计算机经常出故障，研究者每隔 15 分钟观察一次计算机的运行状态，收集了 24 小时的数据（共作 97 次观察）。用 1 表示正常状态，用 0 表示不正常状态，所得的数据序列如下： $$ \begin{array}{l} 111001001111110011110111111001111111110001101101\\111011011010111101110111101111110011011111100111 \end{array} $$ 设 $ X_{n} $ 为第 $ n(n=1,2,\cdots,97) $ 个时段的计算机状态，可以认为它是一个齐次马氏链，状态空间 $ I=\{0,1\} $.96 次状态转移的情况是： 0→0,8次；0→1,18次； 1→0,18次；1→1,52次. 因此，一步转移概率可用频率近似地表示为 $$ p_{00}=P\{X_{n+1}=0\mid X_{n}=0\}\approx\frac{8}{8+18}=\frac{8}{26}, $$ $$ p_{01}=P\{X_{n+1}=1\mid X_{n}=0\}\approx\frac{18}{8+18}=\frac{18}{26}, $$ $$ p_{10}=P\{X_{n+1}=0\mid X_{n}=1\}\approx\frac{18}{18+52}=\frac{18}{70}, $$ $$ p_{11}=P\{X_{n+1}=1\mid X_{n}=1\}\approx\frac{52}{18+52}=\frac{52}{70}. $$ 例 6（续例 5）已知计算机在某一时段（15 分钟）的状态为 0，问在此条件下从此时段起此计算机能连续正常工作 3 刻钟（3 个时段）的条件概率为多少？ 解 由题意，某一时段的状态为0就是初始状态为0，即 $ X_{0}=0 $，由乘法公式、马氏性和齐次性得，所求条件概率为 $$ \begin{aligned}&P\{X_{1}=1,X_{2}=1,X_{3}=1\mid X_{0}=0\}\\&\quad=P\{X_{0}=0,X_{1}=1,X_{2}=1,X_{3}=1\}/P\{X_{0}=0\}\\&\quad=P\{X_{0}=0\}P\{X_{1}=1\mid X_{0}=0\}P\{X_{2}=1\mid X_{1}=1,X_{0}=0\}\bullet\\&P\{X_{3}=1\mid X_{2}=1,X_{1}=1,X_{0}=0\}/P\{X_{0}=0\}\\&\quad=P\{X_{1}=1\mid X_{0}=0\}P\{X_{2}=1\mid X_{1}=1\}P\{X_{3}=1\mid X_{2}=1\}\\&\quad=P_{01}(1)P_{11}(1)P_{11}(1)=\frac{18}{26}\bullet\frac{52}{70}\bullet\frac{52}{70}=0.382.\end{aligned} $$ 接着，我们来研究齐次马氏链的有限维分布.首先，记 $$ p_{j}(0)=P\{X_{0}=a_{j}\},\quad a_{j}\in I,\quad j=1,2,\cdots, $$ 称它为马氏链的初始分布. 再看马氏链在任一时刻 $ n \in T_1 $ 的一维分布： $$ p_{j}(n)=P\{X_{n}=a_{j}\},\quad a_{j}\in I,\quad j=1,2,\cdots. $$ 显然，应有 $ \sum_{j=1}^{+\infty} p_{j}(n) = 1 $。又有 $$ \begin{aligned}P\{X_{n}=a_{j}\}&=\sum_{i=1}^{+\infty}P\{X_{0}=a_{i},X_{n}=a_{j}\}\\&=\sum_{i=1}^{+\infty}P\{X_{n}=a_{j}\mid X_{0}=a_{i}\}P\{X_{0}=a_{i}\},\end{aligned} $$ 或即 $$ p_{j}(n)=\sum_{i=1}^{+\infty}p_{i}(0)P_{ij}(n),\quad j=1,2,\cdots. $$ 一维分布(1.6)也可用行向量表示成 $$ \boldsymbol{p}(n)=(\boldsymbol{p}_{1}(n),\boldsymbol{p}_{2}(n),\cdots,\boldsymbol{p}_{j}(n),\cdots). $$ 这样，利用矩阵乘法（I 是可列无限集时，仍用有限阶矩阵乘法的规则确定矩阵 之积的元),(1.7)式可写成 $$ \boldsymbol{p}(n)=\boldsymbol{p}(0)\boldsymbol{P}(n). $$ 此式表明，马氏链在任一时刻 $ n \in T_1 $ 时的一维分布由初始分布 $ p(0) $ 和 n 步转移概率矩阵所确定。 又，对于任意 n 个时刻 $ t_{1} $$ \begin{aligned}P&\{X_{t_{1}}=a_{i_{1}},X_{t_{2}}=a_{i_{2}},\cdots,X_{t_{n}}=a_{i_{n}}\}\\&=P\{X_{t_{1}}=a_{i_{1}}\}P\{X_{t_{2}}=a_{i_{2}}\mid X_{t_{1}}=a_{i_{1}}\}\cdots\cdots\cdot\\P&\{X_{t_{n}}=a_{i_{n}}\mid X_{t_{1}}=a_{i_{1}},X_{t_{2}}=a_{i_{2}},\cdots,X_{t_{n-1}}=a_{i_{n-1}}\}\\&=P\{X_{t_{1}}=a_{i_{1}}\}P\{X_{t_{2}}=a_{i_{2}}\mid X_{t_{1}}=a_{i_{1}}\}\cdots P\{X_{t_{n}}=a_{i_{n}}\mid X_{t_{n-1}}\\&=a_{i_{n-1}}\}=p_{i_{1}}(t_{1})P_{i_{1}i_{2}}(t_{2}-t_{1})\cdots P_{i_{n-1}i_{n}}(t_{n}-t_{n-1}).\end{aligned} $$ 由此，并结合(1.7)或(1.7) $ ^{1} $可知：马氏链的有限维分布同样完全由初始分布和转移概率所确定. 总之，转移概率决定了马氏链运动的统计规律。因此，确定马氏链的任意n步转移概率就成为马氏链理论中的重要问题之一。 为了确定齐次马氏链的 n 步转移概率 $ P_{ij}(n) $，首先介绍 $ P_{ij}(n) $ 所满足的基本方程. 设 $ \{X(n), n=0,1,2\cdots\} $是一齐次马氏链，则对任意的 $ u, v \in T_{1} $，有 $$ P_{ij}(u+v)=\sum_{k=1}^{+\infty}P_{ik}(u)P_{kj}(v),i,j=1,2,\cdots. $$ 方程(2.1)就是著名的切普曼—科尔莫戈罗夫(Chapman-Kolmogorov)方程，简称C-K方程. C-K 方程基于下述事实，即“从时刻 s 所处的状态 $ a_{i} $，即 $ X(s)=a_{i} $ 出发，经时段 $ u+v $ 转移到状态 $ a_{j} $，即 $ X(s+u+v)=a_{j} $ 这一事件可分解成“从 $ X(s)=a_{i} $ 出发，先经时段 u 转移到中间状态 $ a_{k}(k=1,2,\cdots) $，再从 $ a_{k} $ 经时段 v 转移到状态 $ a_{j} $”这样一些事件的和事件（见图 13-4）. 方程(2.1)的证明如下：先固定 $ a_k \in I $ 和 $ s \in T_1 $，由条件概率定义和乘法定理，有 $$ \begin{aligned}P\{&X(s+u+v)=a_{j},X(s+u)=a_{k}\mid X(s)=a_{i}\}\\=&P\{X(s+u)=a_{k}\mid X(s)=a_{i}\}P\{X(s+u+v)\\=&a_{j}\mid X(s+u)=a_{k},X(s)=a_{i}\}\\=&P_{ik}(u)P_{kj}(v)( 马氏性和齐次性 ).\end{aligned} $$ 又由于事件组“ $ X(s+u)=a_{k} $”, k=1,2,…构成一个划分，故有 $$ P_{ij}(u+v)=P\{X(s+u+v)=a_{j}\mid X(s)=a_{i}\} $$ $$ \sum_{k=1}^{+\infty}P\{X(s+u+v)=a_{j},X(s+u)=a_{k}\mid X(s)=a_{i}\}. $$ 将(2.2)式代入上式，即得所要证明的 C-K 方程. C-K 方程也可写成矩阵形式： $$ \mathbf{P}(u+v)=\mathbf{P}(u)\mathbf{P}(v). $$ 利用 C-K 方程我们容易确定 n 步转移概率. 事实上，在 $ (2.1)^{\prime} $ 式中令 u=1, v=n-1 ，得递推关系： $$ \mathbf{P}(n)=\mathbf{P}(1)\mathbf{P}(n-1)=\mathbf{P}\mathbf{P}(n-1), $$ 从而可得 $$ \boldsymbol{P}(n)=\boldsymbol{P}^{n}. $$ 就是说，对齐次马氏链而言，n步转移概率矩阵是一步转移概率矩阵的n次方。 进而可知，齐次马氏链的有限维分布可由初始分布与一步转移概率完全确定。 例1 设 $ \{X_{n}, n \geqslant 0\} $是具有三个状态0,1,2的齐次马氏链，一步转移概率矩阵为 $$ \mathbf { P } = \begin{bmatrix} { 0 } & { 1 } & { 2 } \\ { 0 } & { \frac { 1 } { 3 } / 4 } & { \frac { 1 } { 4 } / 4 } & { 0 } \\ { \frac { 1 } { 2 } } & { \frac { 1 } { 4 } / 2 } & { \frac { 1 } { 4 } / 4 } & { 0 } \\ { 0 } & { \frac { 1 } { 3 } / 4 } & { \frac { 1 } { 4 } / 4 } & { 0 } \end{bmatrix}, $$ 初始分布 $ p_{i}(0)=P\{X_{0}=i\}=1/3,i=0,1,2 $. 试求 (i) $ P\{X_{0}=0,X_{2}=1\} $; (ii) $ P\{X_{2}=1\} $. $$ \mathbf{P}(2)=\mathbf{P}^{2}=1\left[\begin{matrix}0&1&2\\ 0&5/8&5/16&1/16\\ 5/16&1/2&3/16\\ 2&9/16&1/4\end{matrix}\right]. $$ $$ \begin{aligned}P\{X_{0}=0,X_{2}=1\}&=P\{X_{0}=0\}P\{X_{2}=1\mid X_{0}=0\}\\&=p_{0}(0)P_{01}(2)=\frac{1}{3}\cdot\frac{5}{16}=\frac{5}{48}；\end{aligned} $$ (ii)由(1.7)式， $$ \begin{aligned}p_{1}(2)&=P\{X_{2}=1\}\\&=p_{0}(0)P_{01}(2)+p_{1}(0)P_{11}(2)+p_{2}(0)P_{21}(2)\\&=\frac{1}{3}\Big(\frac{5}{16}+\frac{1}{2}+\frac{9}{16}\Big)=\frac{11}{24}.\end{aligned} $$ 例2 在§1例2中，(i)设p=0.9，求系统二级传输后的传真率与三级传输后的误码率；(ii)设初始分布 $ p_{1}(0)=P\{X_{0}=1\}=\alpha,p_{0}(0)=P\{X_{0}=0\}=1-\alpha $。又已知系统经n级传输后输出为1，问原发字符也是1的概率是多少？ 解 先求出 n 步转移概率矩阵 $ \boldsymbol{P}(n)=\boldsymbol{P}^{n} $. 由于 $$ \mathbf{P}=\begin{matrix}0&1&\\ 0&0&1\\ 1&\begin{bmatrix}p&q\\ q&p\end{bmatrix}&\end{matrix}\quad(q=1-p) $$ 有相异的特征值 $ \lambda_{1}=1,\lambda_{2}=p-q $，由线性代数知识，可将 P 表示成对角矩阵 $$ \mathbf{\Lambda}=\left[\begin{matrix}{\lambda_{1}}&{0}\\ {0}&{\lambda_{2}}\\ \end{matrix}\right]=\left[\begin{matrix}{1}&{0}\\ {0}&{p-q}\\ \end{matrix}\right] $$ 的相似矩阵. 具体做法是: 求出 $ \lambda_{1}, \lambda_{2} $ 对应的特征向量 $$ \boldsymbol{e}_{1}=\begin{bmatrix}1/\sqrt{2}\\ 1/\sqrt{2}\end{bmatrix},\quad\boldsymbol{e}_{2}=\begin{bmatrix}-1/\sqrt{2}\\ 1/\sqrt{2}\end{bmatrix}. $$ 令 $$ \mathbf{H}=[\mathbf{e}_{1},\mathbf{e}_{2}]=\begin{bmatrix}1/\sqrt{2}&-1/\sqrt{2}\\ 1/\sqrt{2}&1/\sqrt{2}\end{bmatrix}, $$ 则 $ P=H\Lambda H^{-1} $. 于是，容易算得 $$ \begin{aligned}{\mathbf{P}^{n}}&{{}=(\mathbf{H}\mathbf{\Lambda}\mathbf{H}^{-1})^{n}=\mathbf{H}\mathbf{\Lambda}^{n}\mathbf{H}^{-1}}\\ {}&{{}\qquad0\quad1}\\ {}&{{}=\begin{aligned}{{0}\left[\begin{aligned}{}&{{}\frac{1}{2}+\frac{1}{2}(p-q)^{n}}&{\frac{1}{2}-\frac{1}{2}(p-q)^{n}}\\ {}&{{}\frac{1}{2}-\frac{1}{2}(p-q)^{n}}&{\frac{1}{2}+\frac{1}{2}(p-q)^{n}}\\ \end{aligned}\right].}\\ \end{aligned}}\\ \end{aligned} $$ (i) 由(2.4)式可知，当 p=0.9 时，系统经二级传输后的传真率与三级传输后的误码率分别为 $$ P_{11}(2)=P_{00}(2)=\frac{1}{2}+\frac{1}{2}(0,9-0,1)^{2}=0,820, $$ $$ P_{10}(3)=P_{01}(3)=\frac{1}{2}-\frac{1}{2}(0.9-0.1)^{3}=0.244; $$ （ii）根据贝叶斯公式，当已知系统经 n 级传输后输出为 1，原发字符也是 1 的概率为 $$ \begin{aligned}P\{X_{0}=1\mid X_{n}=1\}&=\frac{P\{X_{0}=1\}P\{X_{n}=1\mid X_{0}=1\}}{P\{X_{n}=1\}}\\&=\frac{p_{1}(0)P_{11}(n)}{p_{0}(0)P_{01}(n)+p_{1}(0)P_{11}(n)}\\&=\frac{\alpha+\alpha(p-q)^{n}}{1+(2\alpha-1)(p-q)^{n}}.\\ \end{aligned} $$ 对于只有两个状态的马氏链，一步转移概率矩阵一般可表示为： $$ \mathbf{P}=\begin{array}{c}0\\ 1\end{array}\begin{bmatrix}1-a&a\\ b&1-b\end{bmatrix},\quad0 利用类似于例2的方法，可得n步转移概率矩阵为 $$ \begin{aligned}\mathbf{P}(n)&=\mathbf{P}^{n}=\begin{array}{l}0\\ 0\\ 1\end{array}\begin{bmatrix}P_{00}(n)&P_{01}(n)\\ P_{10}(n)&P_{11}(n)\end{bmatrix}\\&=\frac{1}{a+b}\begin{bmatrix}b&a\\ b&a\end{bmatrix}+\frac{(1-a-b)^{n}}{a+b}\begin{bmatrix}a&-a\\ -b&b\end{bmatrix},n=1,2,\cdots.\end{aligned} $$ 这是解决两个状态的马氏链问题的有用公式. 对于一般的两个状态的马氏链，由(2.5)式可知，当0<a, b<1时， $ P_{ij}(n) $有极限 $$ \begin{aligned}\lim_{n\to+\infty}P_{00}(n)&=\lim_{n\to+\infty}P_{10}(n)=\frac{b}{a+b}\xlongequal{ 记成 }\pi_{0}.\\\lim_{n\to+\infty}P_{01}(n)&=\lim_{n\to+\infty}P_{11}(n)=\frac{a}{a+b}\xlongequal{ 记成 }\pi_{1}.\end{aligned} $$ 上述极限的意义是：对固定的状态 j，不管链在某一时刻从什么状态 (i=0 或 1) 出发，通过长时间的转移，到达状态 j 的概率都趋近于 $ \pi_{j} $，这就是所谓的遍 历性. 又由于 $ \pi_{0}+\pi_{1}=1 $ ，所以 $ (\pi_{0},\pi_{1})\xlongequal{ 记成 }\pi $ 构成一分布律，称它为链的极限分布. 另外，如若我们能用其他简便的方法直接由一步转移概率求得极限分布 $ \pi $ 则反过来，当 $ n\gg1 $ 时就可得到 n 步转移概率的近似值： $ P_{ij}(n)\approx\pi_{j} $. 一般，设齐次马氏链的状态空间为 I，若对于所有 $ a_{i}, a_{j} \in I $，转移概率 $ P_{ij}(n) $ 存在极限 $$ \lim_{n\to\infty}P_{ij}\left(n\right)=\pi_{j}\quad\left( 不依赖于 i\right) $$ 或 $$ \mathbf{P}(n)=\mathbf{P}^{n}\xrightarrow[(n\to+\infty)]{\left[\begin{matrix}{\pi_{1}}&{\pi_{2}}&{\cdots}&{\pi_{j}}&{\cdots}\\ {\pi_{1}}&{\pi_{2}}&{\cdots}&{\pi_{j}}&{\cdots}\\ {\vdots}&{\vdots}&{}&{\vdots}&{}\\ {\pi_{1}}&{\pi_{2}}&{\cdots}&{\pi_{j}}&{\cdots}\\ {\vdots}&{\vdots}&{}&{\vdots}&{}\\ \end{matrix}\right]}. $$ 则称此链具有遍历性. 又若 $ \sum_{j}\pi_{j}=1 $，则同时称 $ \pi=(\pi_{1},\pi_{2},\cdots) $ 为链的极限分布. 齐次马氏链在什么条件下才具有遍历性？如何求出它的极限分布？这问题在理论上已经圆满解决，但叙述它需要较多篇幅。下面仅就只有有限个状态的链，即有限链的遍历性给出一个充分条件。 定理 设齐次马氏链 $ \{X_{n}, n \geqslant 1\} $的状态空间为 $ I = \{a_{1}, a_{2}, \cdots, a_{N}\} $，P 是它的一步转移概率矩阵，如果存在正整数 m，使对任意的 $ a_{i}, a_{j} \in I $，都有 $$ P_{ij}(m)>0,\quad i,j=1,2,\cdots,N, $$ 则此链具有遍历性，且有极限分布 $ \pi=(\pi_{1},\pi_{2},\cdots,\pi_{N}) $，它是方程组 $$ \pi=\pi\mathbf{P} 或即 \pi_{j}=\sum_{i=1}^{N}\pi_{i}p_{ij},j=1,2,\cdots,N $$ 的满足条件 $$ \pi_{j}>0,\sum_{j=1}^{N}\pi_{j}=1 $$ 的唯一解. 证明略. 依照定理，为证有限链是遍历的，只需找一正整数 m，使 m 步转移概率矩阵 $ P^{m} $ 无零元。而求极限分布 $ \pi $ 的问题，化为求解方程组 (3.2) 的问题。注意，方程组 (3.2) 中仅 N-1 个未知数是独立的，而唯一解可用归一条件 $ \sum_{j=1}^{N} \pi_{j} = 1 $ 确定。 在定理的条件下，马氏链的极限分布又是平稳分布。意即，若用 $ \pi $ 作为链的初始分布，即 $ p(0)=\pi $，则链在任一时刻 $ n\in T_{1} $ 的分布 $ p(n) $ 永远与 $ \pi $ 一致。事实上，由 $ (1.7)^{\prime} $、 $ (2.3) $ 和 $ (3.2) $ 式，有 $$ p(n)=p(0)P(n)=\pi P^{n}=\pi P^{n-1}=\cdots=\pi P=\pi. $$ 例1 试说明§1例3中，带有两个反射壁的随机游动是遍历的，并求其极限分布（平稳分布）. 解 为简便计，以符号“×”代表转移概率矩阵的正的元.于是，由§1例3中的一步转移概率矩阵P，得 $$ \begin{aligned}\boldsymbol{P}(2)&=\boldsymbol{P}^{2}=\begin{bmatrix}0&\times&0&0&0\\\times&\times&\times&0&0\\0&\times&\times&\times&0\\0&0&\times&\times&\times\\0&0&0&\times&0\end{bmatrix}\begin{bmatrix}0&\times&0&0&0\\\times&\times&\times&0&0\\0&\times&\times&\times&0\\0&0&\times&\times&\times\\0&0&0&\times&0\end{bmatrix}=\begin{bmatrix}\times&\times&\times&0&0\\\times&\times&\times&\times&0\\\times&\times&\times&\times&\times\\0&\times&\times&\times&\times\\0&0&\times&\times&\times\end{bmatrix},\\\boldsymbol{P}(4)&=\boldsymbol{P}^{4}=\begin{bmatrix}\times&\times&\times&0&0\\\times&\times&\times&\times&0\\\times&\times&\times&\times&\times\\0&\times&\times&\times&\times\\0&0&\times&\times&\times\end{bmatrix}\begin{bmatrix}\times&\times&\times&0&0\\\times&\times&\times&\times&0\\\times&\times&\times&\times&\times\\0&\times&\times&\times&\times\\0&0&\times&\times&\times\end{bmatrix}=\begin{bmatrix}\times&\times&\times&\times&\times\\\times&\times&\times&\times&\times\\\times&\times&\times&\times&\times\\\times&\times&\times&\times&\times\\\times&\times&\times&\times&\times\end{bmatrix},\end{aligned} $$ 即 P(4) 无零元。由定理，链是遍历的。再根据(3.2)和(3.3)式，写出极限分布 $ \pi=(\pi_{1},\pi_{2},\cdots,\pi_{5}) $ 满足的方程组 $$ \{\begin{aligned}&\pi_{1}=(1/3)\pi_{2},\\ &\pi_{2}=\pi_{1}+(1/3)\pi_{2}+(1/3)\pi_{3},\\ &\pi_{3}=(1/3)\pi_{2}+(1/3)\pi_{3}+(1/3)\pi_{4},\\ &\pi_{4}=(1/3)\pi_{3}+(1/3)\pi_{4}+\pi_{5},\\ &\pi_{5}=(1/3)\pi_{4},\\ &\pi_{1}+\pi_{2}+\pi_{3}+\pi_{4}+\pi_{5}=1.\end{aligned}. $$ 先由前四个方程，解得： $ 3\pi_{1}=\pi_{2}=\pi_{3}=\pi_{4}=3\pi_{5} $。将它们代入归一条件，即最后一个方程，解之，得唯一解： $ \pi_{1}=\pi_{5}=1/11 $， $ \pi_{2}=\pi_{3}=\pi_{4}=3/11 $。所以极限分布为 $ \pi=(1/11,3/11,3/11,3/11,1/11) $。这个分布表明：经过长时间游动之后，醉汉Q位于点 $ i(1 例2 试说明§1例4（排队模型）中的链是遍历的，并求其极限分布. 解 依照例1，由§1例4中的一步转移概率矩阵P，可算得 $ P(3)=P^{3} $无零元.根据定理，链是遍历的.而极限分布 $ \pi=(\pi_{0},\pi_{1},\pi_{2},\pi_{3}) $满足下列方程组： $$ \{\begin{aligned}\pi_{0}&=(1-q)\pi_{0}+p(1-q)\pi_{1},\\ \pi_{1}&=q\pi_{0}+[pq+(1-p)(1-q)]\pi_{1}+p(1-q)\pi_{2},\\ \pi_{2}&=q(1-p)\pi_{1}+[pq+(1-p)(1-q)]\pi_{2}+p(1-q)\pi_{3},\\ \pi_{3}&=q(1-p)\pi_{2}+[pq+(1-p)]\pi_{3},\\ \pi_{0}&+\pi_{1}+\pi_{2}+\pi_{3}=1.\end{aligned}. $$ 解之，得唯一解 $$ \pi_{0}=p^{3}(1-q)^{3}/C,\quad\pi_{1}=p^{2}q(1-q)^{2}/C, $$ $$ \pi_{2}=pq^{2}(1-q)(1-p)/C,\quad\pi_{3}=q^{3}(1-p)^{2}/C, $$ 其中 $ C=p^{3}(1-q)^{3}+p^{2}q(1-q)^{2}+pq^{2}(1-q)(1-p)+q^{3}(1-p)^{2} $ 假若在此例中，p=q=1/2，则可算得 $ \pi_{0}=1/7\approx0.14 $， $ \pi_{1}=\pi_{2}=\pi_{3}=2/7\approx0.29 $，即此时极限分布为 $ \pi=(1/7,2/7,2/7,2/7) $。这就是说，经过相当长的时间以后，系统中无人的情形约占14%的时间，而系统中有一人、二人、三人的情形约各占29%的时间。 例 3 设一马氏链的一步转移概率矩阵为 $$ \mathbf{P}=\left[\begin{matrix}{0}&{1/2}&{0}&{1/2}\\ {1/2}&{0}&{1/2}&{0}\\ {0}&{1/2}&{0}&{1/2}\\ {1/2}&{0}&{1/2}&{0}\\ \end{matrix}\right]. $$ 试讨论它的遍历性. 解 先算得 $$ \mathbf{P}(2)=\mathbf{P}^{2}=\left[\begin{matrix}{1/2}&{0}&{1/2}&{0}\\ {0}&{1/2}&{0}&{1/2}\\ {1/2}&{0}&{1/2}&{0}\\ {0}&{1/2}&{0}&{1/2}\\ \end{matrix}\right]. $$ 进一步可验证：当 n 为奇数时， $ \boldsymbol{P}(n)=\boldsymbol{P}(1)=\boldsymbol{P};n $ 为偶数时， $ \boldsymbol{P}(n)=\boldsymbol{P}(2) $。这表明对任一固定的 $ j(=1,2,3,4) $，极限 $ \lim_{n\to+\infty}P_{ij}(n) $ 都不存在。按定义，此链不具遍历性。 马氏过程的内容除了讨论最简情形——马氏链之外，还研究状态离散、时间连续的马氏过程和状态、时间都是连续的马氏过程，它们都有比较完善的理论，而且讨论的主题也都是从各自场合的C-K方程出发，研究转移概率的确定方法和性质。本书除前面介绍的泊松过程和维纳过程这两个具体的马氏过程模型外不再作一般的介绍。 马尔可夫过程的主要特征是它具有无后效性（马氏性），通俗地说，就是在已知过程“现在”所处状态的条件下，其“将来”状态的概率分布不依赖于“过去”所处的状态。读者应了解无后效性的严格定义是由条件分布函数给出的。 泊松过程是时间连续、状态离散的马氏过程；维纳过程是时间、状态都连续的马氏过程。 本章主要讨论时间和状态都是离散的马氏链 $ \{X_n, n=1,2,\cdots\} $，约定状态空间 $ I=\{a_1, a_2,\cdots\}, a_i \in \mathbb{R} $（也可一一对应地用 $ a_i $的足标表示成 $ I=\{1,2,\cdots\} $）。马氏性可用条件分布律表 示为：对任意的整数 $ 0 \leqslant t_{1} < t_{2} < \cdots < t_{r} < m < m + n $ 和 $ a, \in I $ $$ \begin{aligned}&P\{X_{m+n}=a_{j}\mid X_{t_{1}}=a_{i_{1}},X_{t_{2}}=a_{i_{2}},\cdots,X_{t_{r}}=a_{i_{r}},X_{m}=a_{i}\}\\ &=P\{X_{m+n}=a_{j}\mid X_{m}=a_{i}\}.\\ \end{aligned} $$ 右端表示已知链在时刻 m 处于状态 $ a_{i} $ 条件下，在时刻 $ m+n $ 转移到状态 $ a_{j} $ 的概率。若这个概率只与 i, j 和时间差 n 有关，记为 $ P_{ij}(n) $，即 $$ P_{ij}(n)=P\{X_{m+n}=a_{j}\mid X_{m}=a_{i}\} $$ 则称链为齐次马氏链（以下限于讨论齐次链）， $ P_{ij}(n) $ 为 n 步转移概率， $ \boldsymbol{P}(n)=(\boldsymbol{P}_{ij}(n)) $ 为 n 步转移概率矩阵，这个矩阵的每一行元之和等于 1，即 $ \sum_{j=1}^{+\infty}P_{ij}(n)=1 $，往后可用它来校验计算 $ \boldsymbol{P}(n) $ 的正确性，特别重要的是一步转移概率 $$ p_{ij}=P_{ij}(1)=P\{X_{m+1}=a_{j}\mid X_{m}=a_{i}\} $$ 和一步转移概率矩阵 $ \boldsymbol{P}=\boldsymbol{P}(1)=(\boldsymbol{p}_{ij}) $. P 的元 $ p_{ij} $ 可根据具体链从一个状态经一个单位时间转移到其他各状态的概率来确定（包括统计估计方法）. 确定 n 步转移概率是马氏链理论中的关键问题. 在齐次链情形, 由著名的 C-K 方程可推出 $$ \mathbf{P}(n)=\left[\mathbf{P}(1)\right]^{n}=\mathbf{P}^{n}, $$ 即 n 步转移概率完全由一步转移概率所确定。计算 $ P^{a} $ 要用到线性代数中矩阵对角化的知识，也可利用现成的计算软件，读者只要对 P 为二阶矩阵的情形会求就可以了（见 §2 公式 (2.5)）。 马氏链的主题之一是给出有限维分布律的计算方法. 一维分布律： $ p_{j}(0)=P\{X_{0}=a_{j}\}, j=1,2,\cdots $（初始分布）， $$ p_{j}(n)=P\{X_{n}=a_{j}\}=\sum_{i=1}^{+\infty}p_{i}(0)P_{ij}(n),\quad n,j=1,2,\cdots. $$ n 维分布律：对任意 n 个时刻 $ t_{1} $$ P\{X_{t_{1}}=a_{i_{1}},X_{t_{2}}=a_{i_{2}},\cdots,X_{t_{n}}=a_{i_{n}}\}=p_{i_{1}}(t_{1})P_{i_{1}i_{2}}(t_{2}-t_{1})\cdots P_{i_{n-1}i_{n}}(t_{n}-t_{n-1}). $$ 综合起来看，马氏链的有限维分布律（或者说马氏链运动的统计规律）完全由初始分布和一步转移概率所确定。 马氏链的另一主题是讨论 $ P_{ij}(n) $ 当 $ n \to +\infty $ 时的极限问题. 我们只限于讨论 $ I = \{a_1, a_2, \cdots, a_N\} $ 即有限链的情形. 如对任意的 $ a_i, a_j \in I $, 都有 $$ \lim_{n\to+\infty}P_{ij}(n)=\pi_{j}(与 i 无关 ) $$ 就称此链具有遍历性. 因是有限链, 所以当链又具遍历性时, 对 $ \sum_{j=1}^{N} P_{ij}(n) = 1 $ 取极限 $ n \to +\infty $, 总有 $ \sum_{j=1}^{N} \pi_{j} = 1 $, 于是 $ \pi = (\pi_1, \pi_2, \cdots, \pi_N) $ 构成一分布律, 称为链的极限分布或平稳分布. 马氏链的遍历性表示一个系统经过长时间转移后达到平衡状态，即当 $ n \gg 1 $ 时， $ P_{ij}(n) \approx \pi_{i} $ 与起步状态 $ a_{i} $ 无关. 有限链具有遍历性的充分条件是：存在正整数 m，使对一切 $ a_{i}, a_{j} \in I $ 都有 $$ P_{ij}(m)>0, $$ 或即存在 m，使 m 步转移概率矩阵 $ \boldsymbol{P}(m)=\boldsymbol{P}^{m} $ 无零元（当 P 的阶数不高时，寻求 m 的方法见 §3 例1），而极限分布 $ \pi=(\pi_{1},\pi_{2},\cdots,\pi_{N}) $ 是方程组 $$ \{\begin{aligned}\pi&=\pi\mathbb{P},\\ \pi_{j}&>0,\sum_{j=1}^{N}\pi_{j}=1\end{aligned}. $$ 的唯一解. 无后效性（马氏性） 齐次马氏链 n 步转移概率与 n 步转移概率矩阵 C-K 方程 马氏链的有限维分布律 遍历性 极限分布（平稳分布） 4.（传染模型）有N个人及某种传染病，假设 （1）在每个单位时间内此 N 个人中恰有两人互相接触，且一切成对的接触是等可能的. （2）当健康者与患病者接触时，被传染上病的概率为 $ \alpha $ （3）患病者康复的概率是0，健康者如果不与患病者接触，得病的概率也为0. 现以 $ X_{n} $ 表示第 n 个单位时间内的患病人数。试说明这种传染过程，即 $ \{X_{n}, n \geqslant 0\} $ 是一马氏链，并写出它的状态空间及一步转移概率矩阵。 $$ \boldsymbol{P}=2\begin{bmatrix}{{{1/4}}}&{{{3/4}}}&{{{0}}} \\{{{1/3}}}&{{{1/3}}}&{{{1/3}}} \\{{{3}}}&{{{0}}}&{{{1/4}}}&{{{3/4}}}\end{bmatrix} $$ （1）计算 $ P\{X_{0}=1,X_{1}=2,X_{2}=2\} $. (2) 证明 $ P\{X_{1}=2, X_{2}=2 \mid X_{0}=1\}=p_{12}p_{22} $ （3）计算 $ P_{12}(2)=P\{X_{2}=2\mid X_{0}=1\} $ （4）计算 $ p_{2}(2)=P\{X_{2}=2\} $ 或雨是互为逆事件. 以0表示晴天状态，以1表示雨天状态， $ X_{n} $ 表示第n天的状态（0或1）. 试写出马氏链 $ \{X_{n}, n \geqslant 1\} $ 的一步转移概率矩阵. 又若已知5月1日为晴天，问5月3日为晴天，5月5日为雨天的概率各等于多少？ $$ \mathbf{P}=\begin{aligned}&0&1&\\ &1&\begin{bmatrix}0.75&0.25\\ 0.5&0.5\end{bmatrix},&\end{aligned} $$ 试证明相应齐次马氏链是遍历的，并求其极限分布（平稳分布）. （1）用定义解. （2）利用遍历性定理解. $$ \mathbf{P}=\begin{bmatrix}q&p&0\\ q&0&p\\ 0&q&p\end{bmatrix},\quad q=1-p,0 试证明此链具有遍历性，并求其平稳分布. $$ \mathbf{P}=\left[\begin{array}{ccc}1/2&1/2&0\\ 1/2&1/2&0\\ 0&0&1\end{array}\right], $$ 试证此链不是遍历的.
§2 多步转移概率的确定
解 先求出二步转移概率矩阵
§3 遍历性
小结
重要术语及主题
习题