有一类随机过程， 它具备所谓的“无后效性”(马氏性)，即要确定过程将来的状态， 知道它此刻的情况就足够了，并不需要对它以往状况的认识，这类过程称为Markov过程.我们将介绍Markov过程中最 简单的两种类型：离散时间的马氏链(简称马氏链)及连续时间的马氏链.

定义5.1 随机过程\(\{X_n, n=0,1,2,\dots\}\)称为马氏链， 若它只取有限或可列个值(若不另外说明，以非负整数集\(\{0,1,2,\dots\}\)来表示)， 并且对任意的 \(n \geq 0\)， 及任意状态\(i, j, i_0, i_1, \dots, i_{n-1}\)，有 \[\begin{align} P \{ X_{n+1} = j \;|\; X_0 = i_0, X_1=i_1, \dots, X_{n-1}=i_{n-1}, X_n=i \} =& P \{ X_{n+1}=j \;|\; X_n=i \} \tag{5.1} \end{align}\] 其中\(X_n = i\)表示过程在时刻\(n\)处于状态\(i\)， 称\(\{0, 1, 2, \dots\}\)为该过程的状态空间， 记为\(S\). 式(5.1)刻画了马氏链的特性， 称为马氏性。

条件独立性： 设\(A, B, C\)为随机事件， 若\(P(BC)>0\), 则 \[ P(A|BC) = P(A|B) \] 等价于 \[ P(AC | B) = P(A|B) P(C|B), \] 这时称给定\(B\)的条件下\(A\)和\(C\)相互独立。 集合函数\(P_B(A) = P(A|B)\)（\(A \in \mathscr F\)）是一个概率测度， 也有乘积公式、全概率公式等性质。

对随机变量\(X, Y, Z\)，若 \[\begin{aligned} P(X \leq x, Y \leq y | Z = z) = P(X \leq x | Z = z) P(Y \leq y | Z = z) \end{aligned}\] 则称\(X\)和\(Y\)在给定\(Z\)的条件下独立。 \(X, Y, Z\)都服从离散分布时，条件独立性等价于 \[\begin{aligned} P(X = x, Y = y | Z = z) = P(X = x | Z = z) P(Y = y | Z = z), \end{aligned}\] 也等价于 \[\begin{aligned} P(X = x | Y = y ,Z = z) = P(X = x | Z = z) . \end{aligned}\] 条件(5.1)等价于\(X_{n+1}\)和\(X_0, \dots, X_{n-1}\)在给定\(X_n\)的条件下条件独立。

定义5.2 称(5.1)式中的条件概率\(P \{ X_{n+1}=j | X_n=i \}\)为马氏链\(\{X_n, n=0, 1, 2, \dots\}\)的一步转移概率， 简称为转移概率.

一般情况下，转移概率与状态\(i\), \(j\)和时刻\(n\)有关.

定义5.3 当马氏链的一步转移概率\(P\{ X_{n+1}=j | X_n=i \}\)只与状态\(i, j\)有关， 而与\(n\)无关时， 称此马氏链为时齐马氏链， 记\(P\{ X_{n+1}=j | X_n=i \} = p_{ij}\)， 代表处于状态\(i\)的过程下一步转移到状态\(j\)的概率. 若\(P\{ X_{n+1}=j | X_n=i \}\)与\(n\)有关， 就称该马氏链为非时齐的.

在本书中，我们只讨论时齐马氏链，并且简称为马氏链.

当马氏链的状态为有限时，称为有限链， 否则称为无限链. 但无论状态有限还是无限， 我们都可以将\(p_{ij}(i, j \in S)\)排成一个矩阵的形式。令

\[ P = (p_{ij}) =\left(\begin{array}{ccccc} p_{00}& p_{01}& p_{02}&\cdots \\ p_{10}& p_{11}& p_{12}&\cdots \\ p_{20}& p_{21}& p_{22}&\cdots \\ \vdots&\vdots&\vdots&\ddots \end{array}\right) \] 称\(P\)为转移概率矩阵， 一般简称为转移矩阵. 由于概率是非负的， 且过程必须转移到某个状态， 所以容易看出\(p_{ij}(i, j \in S)\)有性质 \[\begin{equation} \begin{aligned} (1)& p_{ij}\geq 0, \ i,j \in S; \\ (2)& \sum_{j \in S} p_{ij} = 1, \ \forall i \in S. \end{aligned} \tag{5.2} \end{equation}\]

定义5.4 称矩阵为随机矩阵， 若矩阵元素具有(5.2))式中两条性质.

易见随机矩阵每一行元素的和都为1.

例5.1 (一个简单的疾病、死亡模型，Fix-Neyman) 考虑一个包含两个健康状态\(S_1,S_2\)以及两个死亡状态\(S_3,S_4\) (即由不同原因引起的死亡)的模型. 若个体病愈，则认为它处于状态\(S_1\)， 若患病，说处于\(S_2\)， 个体可以从\(S_1\), \(S_2\)进入\(S_3\)和\(S_4\)， 易见这是一个马氏链的模型，转移矩阵为 \[ P = \left(\begin{array}{cccc} p_{11}& p_{12}& p_{13}& p_{14}\\ p_{21}& p_{22}& p_{23}& p_{24}\\ 0& 0 &1& 0 \\ 0& 0 &0& 1 \end{array}\right) \]

例5.2 (赌徒的破产或称带吸收壁的随机游动) 系统的状态是\(0 \sim n\)， 反映赌博者在赌博期间拥有的钱数， 当他输光或拥有钱数为\(n\)时，赌博停止， 否则他将持续赌博. 每次以概率\(p\)赢得1， 以概率\(q=1-p\)输掉1. 这个系统的转移矩阵为 \[ P = \left(\begin{array}{cccccccc} 1&0& 0&0&\cdots&0& 0& 0\\ q& 0& p& 0&\cdots&0& 0& 0\\ 0& q& 0& p&\cdots&0& 0& 0\\ \cdot& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot\\ 0& 0& 0& 0&\cdots & q& 0& p\\ 0& 0& 0 &0 & \cdots& 0 &0& 1 \end{array}\right)_{(n+1)\times (n+1)} \]

例5.3 (带反射壁的随机游动) 设上例中当赌博者输光时将获得赞助1让他继续赌下去， 就如同一个在直线上做随机游动的球在到达左侧0点处就立刻反弹回1一样， 这就是一个一侧带有反射壁的随机游动. 此时转移矩阵为 \[ P = \left(\begin{array}{cccccccc} 0& 1& 0& 0& \cdot& 0& 0& 0\\ q& 0& p& 0& \cdots& 0& 0& 0\\ 0& q& 0& p&\cdots&0& 0& 0\\ \vdots& \vdots& \vdots& \vdots& & \vdots& \vdots& \vdots\\ 0& 0& 0& 0&\cdots &q& 0&p\\ 0& 0& 0 &0 & \cdots& 0 &0& 1 \end{array}\right)_{(n+1)\times (n+1)} \]

同样可考虑两侧均有反射壁的情况.

例5.4 (自由随机游动) 设一个球在全直线上做无限制的随机游动， 它的状态为\(0, \pm 1, \pm 2, \dots\). 它仍是一个马氏链， 转移矩阵为 \[ P = \left(\begin{array}{ccccccccccc} \cdot& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot & \cdot & \cdot\\ \cdots&q& 0& p& 0&\cdot& \cdot& \cdot& \cdot& \cdot& \cdot\\ \cdots&0& q& 0& p&\cdot& \cdot& \cdot& \cdot& \cdot& \cdot\\ & & & \ddots&\ddots&\ddots&& & & & \\ \cdots& \cdot& \cdot& \cdot&q&0&p&0& \cdot& \cdot& \cdot \\ \cdots& \cdot& \cdot& \cdot& 0&q&0& p&\cdot& \cdot& \cdot \\ \cdot& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot& \cdot \end{array}\right) \]

图5.1: 图上的简单随机游动

例5.5 (图上的简单随机游动) 设有一蚂蚁在如图5.1上爬行， 当两个结点相临时， 蚂蚁将爬向它临近的一点， 并且爬向任何一个邻居的概率是相同的. 则此马氏链的转移矩阵为 \[ P = \left(\begin{array}{cccccc} 0&\frac{1}{2}&\frac{1}{2}&0&0&0\\ \frac{1}{2}&0&\frac{1}{2}&0&0&0\\ \frac{1}{4}&\frac{1}{4}& 0&\frac{1}{4}&\frac{1}{4}&0\\ 0&0&1&0&0&0\\ 0&0&\frac{1}{2}&0&0&\frac{1}{2}\\ 0&0&0&0&1&0 \end{array}\right) \]

例5.6 (Wright-Fisher遗传模型) 遗传的要素是染色体. 遗传性质的携带者称为基因， 它们位于染色体上. 基因控制着生物的特征， 它们是成对出现的. 控制同一特征的不同基因称为等位基因， 记这对等位基因为\(A\)和\(a\)， 分别称为显性的与隐性的. 在一个总体中基因\(A\)和\(a\)出现的频率称为基因频率， 分别记为\(p\)和\(1-p\).

设总体中的个体数为\(2N\)， 每个个体的基因按\(A\)型基因的基因频率的大小， 在下一代中转移成为\(A\)型基因. 因此，繁殖出的第二代的基因型是由试验次数为\(2N\)的Bernoulli试验所确定的， 即如果在第\(n\)代母体中\(A\)型基因出现了\(i\)次， 而\(a\)型基因出现了\(2N-i\)次， 则下一代出现\(A\)型基因的概率为\(p_i = \frac{i}{2N}\)， 而出现\(a\)型基因的概率为\(1-p_i\).

记\(X_n\)为第\(n\)代中携带\(A\)型基因的个体数， 则易知\(\{ X_n \}\)是一个状态空间为\(S = \{ 0, 1, 2, \dots, 2N \}\)的时齐马氏链， 其转移概率矩阵为\(P = (p_{ij})\)，其中 \[\begin{aligned} p_{ij} =& P\{X_{n+1}=j|X_n=i\}=C_{2N}^{j}p_{i}^{j}(1-p_i)^{2N-j} \\ =& C_{2N}^{j}\left(\frac{i}{2N}\right)^j\left(1-\frac{i}{2N}\right)^{2N-j} \end{aligned}\]

下面我们再给出几个所谓“嵌入马氏链”的例子，在这些情况下模型的马氏性不是明显的.

例5.7 (M/G/1排队系统) 假设顾客依照参数为\(\lambda\)的Poisson过程来到一个只有一名服务员的服务站， 若服务员空闲则顾客就能立刻得到服务, 否则排队等待直至轮到该顾客. 设每名顾客接受服务的时间是独立的随机变量, 有共同的分布\(G\)， 而且与来到过程独立. 这个系统称为\(M/G/1\)排队系统， 字母\(M\)代表顾客来到的间隔服从指数分布， \(G\)代表服务时间的分布， 数字1表示只有1名服务员. 考虑其中嵌入的马氏链。

解：

若以\(X(t)\)表示时刻\(t\)系统中的顾客人数， 则\(\{X(t), t \geq 0\}\)是不具备马氏性的， 因为若已知\(t\)时刻系统中的人数， 要预测未来， 虽然可以不用关心从最近的一位顾客到来又过去了多长时间 (因过程无记忆，所以这段时间不影响下一位顾客的到来)， 但要注意此刻在服务中的顾客已经接受了多长时间的服务 (因为\(G\)不是指数的， 不具备“无记忆性”，所以已经服务过的时间将影响到他何时离去).

我们可以这样考虑， 令\(X_n\)表示第\(n\)位顾客走后剩下的顾客数， \(n \geq 1\). 再令\(Y_n\)记第\(n+1\)位顾客接受服务期间到来的顾客数， 则 \[\begin{equation} X_{n+1} = \begin{cases} X_n - 1 + Y_n, & \text{若} X_n > 0 , \\ Y_n, & \text{若} X_n = 0 . \end{cases} \tag{5.3} \end{equation}\]

记\(T_n\)为第\(n\)位顾客到来的时刻， \(N(t)\)为截止到\(t\)时刻顾客到来的人数， 则\(\{N(t) \}\)与\(T_n\)是参数为\(\lambda\)的泊松过程以及相应的事件到来时刻。

如果\(X_n=0\)， 这表示第\(n\)位顾客接受完服务离开时没有其他顾客等候， 服务员变空闲， 直到\(T_{n+1}\)时第\(n+1\)位顾客到来， 这位顾客是当时的唯一顾客， 马上接受服务， 在第\(n+1\)位接受服务期间又到来\(Y_n\)位顾客排队等候， 所以在\(X_n=0\)条件下第\(n+1\)位离开时系统中有\(Y_n\)位顾客。

如果\(X_n>0\)， 则第\(n\)位顾客接受完服务离开时排队的队首顾客是第\(n+1\)位到来的顾客， 这位顾客马上接受服务， 还有\(X_n - 1\)位顾客排队等待， 在第\(n+1\)位顾客接受服务期间又到来\(Y_n\)位顾客加入排队， 所以在\(X_n>0\)条件下在第\(n+1\)位顾客离开时队伍中共有\(X_n - 1 + Y_n\)人。

举例说明。设\(n=5\)， \(X_5\)表示第5位顾客走后剩余的顾客数， 为一个非负整数值。 \(X_6\)表示第6位顾客走后剩余的顾客数， 这依赖于\(X_5\)的值和第5位顾客走后、第6位顾客走之前新到来的顾客人数\(Y_5\)。 分为两种情况， 若\(X_5=0\)， 则第6位顾客到来时直接接受服务， 这期间又来了\(Y_5\)位顾客， 第6位顾客离开时还剩\(Y_5\)位顾客； 若\(X_5 > 0\)， 则第5位顾客离开时第6位顾客是排在队首的顾客， 这时除了第6位顾客还有\(X_5-1 \geq 0\)位顾客， 在第6位顾客接受服务期间又来了\(Y_5\)位顾客， 第6位离开时还剩下原来队伍中的\(X_5-1\)位顾客和新来的\(Y_5\)位顾客。

可以证明\(Y_n\)的分布为： \[\begin{equation} P \{ Y_n = j \} = \int_0^{\infty} e^{-\lambda x} \frac{(\lambda x)^j}{j!} \,dG(x), \ j=0, 1,2,\dots \tag{5.4} \end{equation}\]

设第\(n+1\)位顾客接受服务的时间长度为\(Z\), \(Z \sim G(\cdot)\)， 在\(Z = x\)条件下， 接受服务期间到达的顾客数\(Y_n\)服从泊松P(\(\lambda x\))分布， 于是 \[\begin{aligned} P(Y_n = j | Z=x) = e^{-\lambda x} \frac{(\lambda x)^j}{j!}, \end{aligned}\] 由全期望公式， \[\begin{aligned} P(Y_n = j) =& E[ P(Y_n = j | Z) ] \\ =& \int_0^\infty P(Y_n = j | Z = x) \,dG(x) \\ =& \int_0^\infty e^{-\lambda x} \frac{(\lambda x)^j}{j!}\,dG(x) . \end{aligned}\]

这给出\(\{ Y_n \}\)的分布， 此分布并不依赖\(X_0, X_1, \dots, X_n\)的值， 所以\(P(X_{n+1}=j | X_{n}=i)\)与给定\(X_0, X_1, \dots, X_n\)的条件概率相同， \(X_n\)马氏性成立。 所以由(5.3)、(5.4)式得\(\{ X_n, n = 1, 2, \dots \}\)是马氏链， 转移概率为 \[\begin{aligned} p_{0j} =& P(X_{n+1}=j | X_n=0) = P(Y_n=j | X_n=0) = P(Y_n=j) \\ =& \int^{\infty}_0e^{-\lambda x}\frac{(\lambda x)^j}{j!}dG(x),\ \ j\geq 0 \\ p_{ij} =& P(X_{n+1}=j | X_n=i) \qquad(i \geq 1) \\ =& P(Y_n + i-1 = j | X_n=i) \\ =& P(Y_n = j-i+1) \qquad(i \geq 1, j \geq i-1) \\ =&\int^{\infty}_0e^{-\lambda x}\frac{(\lambda x)^{j-i+1}}{(j-i+1)!}dG(x), \ j \geq i-1, i \geq 1, \\ p_{ij} =& 0, \text{ 其他} \end{aligned}\]

○○○○○○

例5.8 (订货问题) 考虑定货问题. 设某商店使用\((s,S)\)定货策略， 每天早上检查某商品的剩余量， 设为\(x\),则定购额为 \[\begin{equation} \begin{cases} 0, & \text{若} x \geq s, \\ S - x, & \text{若} x < s . \end{cases} \tag{5.5} \end{equation}\] 设定货和进货不需要时间， 每天的需求量\(Y_n\)独立同分布且\(P\{ Y_n = j \} = a_j, j = 0, 1, 2, \dots\). 现在我们要从上述问题中寻找一个马氏链.

解: 令\(X_n\)为第\(n\)天结束时的存货量， 因为要考虑需求量\(Y_{n+1}\)大于存货量\(X_n\)的情况， 所以第\(n+1\)天结束时的存货量为 \[\begin{aligned} X_{n+1} = \begin{cases} \max(0, X_n - Y_{n+1}), & X_n \geq s, \\ \max(0, S - Y_{n+1}), & X_n < s . \end{cases} \end{aligned}\]

对\(X_n = i \geq s\)， 有 \[\begin{aligned} X_{n+1} = \begin{cases} i - Y_{n+1}, & 0 \leq Y_{n+1} < i \\ 0, & Y_{n+1} \geq i, \end{cases} \end{aligned}\] 所以对\(1 \leq j \leq i\), \[\begin{aligned} p_{ij} =& P(X_{n+1} = j | X_n = i) \\ =& P(Y_{n+1} = i-j) = a_{i-j}, \end{aligned}\] 其中\(0 \leq i-j < i\)。 而对\(j=0\)有 \[\begin{aligned} p_{i0} =& P(i - Y_{n+1} \leq 0) = P(Y_{n+1} \geq i) \\ =& 1 - \sum_{k=0}^{i-1} a_k = 1 - \sum_{j=1}^{i} p_{ij} . \end{aligned}\]

当\(0 \leq i < s\)时， \[\begin{aligned} X_{n+1} = \begin{cases} S - Y_{n+1}, & 0 \leq Y_{n+1} < S \\ 0, & Y_{n+1} \geq S, \end{cases} \end{aligned}\] 所以对\(1 \leq j \leq S\), \[\begin{aligned} p_{ij} =& P(X_{n+1} = j | X_n = i) \\ =& P(Y_{n+1} = S-j) = a_{S-j}, \end{aligned}\] 其中\(0 \leq S-j < S\)。 而\(j=0\)时 \[\begin{aligned} p_{i0} =& P(S - Y_{n+1} \leq 0) = P(Y_{n+1} \geq S) \\ =& 1 - \sum_{k=0}^{S-1} a_k = 1 - \sum_{j=1}^{S-1} p_{ij} . \end{aligned}\]

总之有 \[\begin{aligned} p_{ij} =& \begin{cases} a_{i-j}, & j=1,2,\dots,i, s \leq i \leq S \\ 1 - \sum_{k=0}^{i-1} a_k, & j=0, s \leq i \leq S \\ a_{S-j}, & j=1,2,\dots,S, 0 \leq i < s \\ 1 - \sum_{k=0}^{S-1} a_k, & j=0, 0 \leq i < s . \end{cases} \end{aligned}\]

○○○○○○

例5.9 以\(S_n\)表示保险公司在时刻\(n\)的盈余， 这里的时间以适当的单位来计算(如天,月等). 初始盈余\(S_0 = x\)显然为已知， 但未来的盈余\(S_1, S_2, \dots\)却必须视为随机变量， 增量\(S_n - S_{n-1}\)解释为时刻\(n-1\)和时刻\(n\)之间获得的盈利，取整数值(可以为负). 假定\(X_1, X_2, \dots\)是不包含利息的盈利且独立同分布， 概率质量函数为\(p(x)\)，则 \[ S_n = S_{n-1}(1 + \gamma) + X_n, \] 其中\(\gamma\)为固定的利率, \(\{ S_n \}\)是一马氏链， 转移概率为 \[ p_{xy} = p(y - (1 + \gamma) x) . \]

命题5.1 设\(\{X_n, n = 0, 1, \dots \}\)是时齐离散时间离散状态马氏链， 状态空间为\(S\)， 则对任意\(n \geq 0\), \(m \geq 1\)和状态\(x_0, \dots, x_{n-1}, i, j \in S\)， 有 \[\begin{aligned} & P(X_{n+m} = j | X_n = i, X_{n-1} = x_{n-1}, \dots, X_0 = x_0) \\ =& P(X_{n+m} = j | X_n = i) \\ =& p_{ij}^{(m)}, \end{aligned}\] 与\(n\)无关。

当\(m=1\)时就是时齐马氏性的定义。

证明： 对\(m\)用数学归纳法。 已知\(m=1\)时成立。 设已知结论对\(1, \dots, m\)成立， 来证明结论对\(m+1\)成立。 \[\begin{aligned} & P(X_{n+m+1} = j | X_n = i, X_{n-1} = x_{n-1}, \dots, X_0 = x_0) \\ =& \sum_{k \in S} P(X_{n+m+1}=j, X_{n+m}=k | X_n = i, X_{n-1} = x_{n-1}, \dots, X_0 = x_0) \\ =& \sum_{k \in S} P(X_{n+m+1}=j | X_{n+m}=k, X_n = i, X_{n-1} = x_{n-1}, \dots, X_0 = x_0) \\ & \quad P(X_{n+m}=k | X_n = i, X_{n-1} = x_{n-1}, \dots, X_0 = x_0) \\ =& \sum_{k \in S} P(X_{n+m+1}=j | X_{n+m}=k) P(X_{n+m}=k | X_n = i) \\ =& \sum_{k \in S} p_{kj} p_{ik}^{(m)} \end{aligned}\] 与\(n\)和\(x_{n-1}, \dots, x_0\)无关， 所以在\(X_n=i\)条件下\(X_{n+m+1}\)与\(X_{n-1}, \dots, X_0\)条件独立， 有 \[\begin{aligned} & P(X_{n+m+1} = j | X_n = i, X_{n-1} = x_{n-1}, \dots, X_0 = x_0) \\ =& P(X_{n+m+1} = j | X_n = i) = p_{ij}^{(m+1)} \end{aligned}\] 与\(n\)无关。定理证毕。

○○○○○○

定义5.5 称条件概率 \[ p^{(n)}_{ij} = P \{ X_{m+n} = j | X_m = i \}, \ i,j \in S, m \geq 0, n \geq 1 \] 为马氏链的\(n\)步转移概率， 相应地称\(P^{(n)} = (p^{(n)}_{ij})\)为\(n\)步转移矩阵.

当\(n=1\)时, \(p^{(1)}_{ij}=p_{ij}\), \(P^{(1)} = P\)， 此外规定 \[ p^{(0)}_{ij} = \begin{cases} 0, & \text{当} i \neq j, \\ 1, & \text{当} i = j . \end{cases} \] 显然，\(n\)步转移概率\(p^{(n)}_{ij}\)指的就是系统从状态\(i\)经过\(n\)步后转移到\(j\)的概率， 它对中间的\(n-1\)步转移经过的状态无要求.

下面的定理给出了\(p^{(n)}_{ij}\)和\(p_{ij}\)的关系.

定理5.1 (Chapman-Kolmogorov方程，简称C-K方程) 对一切\(n, m \geq 0\), \(i, j \in S\)有 \[\begin{align} (1) &\; p^{(m+n)}_{ij} = \sum_{k \in S} p^{(m)}_{ik} p^{(n)}_{kj}; \\ (2) &\; P^{(n)} = P^n . \end{align}\]

证明：

\[\begin{aligned} p^{(m+n)}_{ij} =& P\{ X_{m+n}=j | X_0 = i \} \\ =& \frac{P\{X_{m+n}=j,X_0=i\}}{P\{X_0=i\}} \\ =& \sum_{k\in S} \frac{P\{X_{m+n}=j,X_m=k,X_0=i\}}{P\{X_0=i\}} \quad\text{(全概率公式)}\\ =& \sum_{k \in S} \frac{P\{X_{m+n}=j,X_m=k,X_0=i\}}{P\{X_0=i\}} \frac{P\{X_m=k,X_0=i\}}{P\{X_m=k,X_0=i\}} \\ =& \sum_{k \in S} P\{X_{m+n}=j | X_m=k,X_0=i\} P\{X_m=k|X_0=i\} \\ =& \sum_{k \in S} p^{(n)}_{kj} \cdot p^{(m)}_{ik} \\ =& \sum_{k \in S} p^{(m)}_{ik} p^{(n)}_{kj} . \end{aligned}\] (2)是(1)的矩阵形式，利用矩阵乘法易得.

○○○○○○

推论5.1 对于正整数\(n, m, k, n_1, n_2, \dots, n_k\)和状态\(i, j, l\)， 总有 \[\begin{aligned} (1)\ & p_{ij}^{(n+m)} \geq p_{il}^{(n)} p_{lj}^{(m)}; \\ (2)\ & p_{ii}^{(n+k+m)} \geq p_{ij}^{(n)} p_{jl}^{(k)} p_{li}^{(m)}; \\ (3)\ & p_{ii}^{(n_1 + n_2 + \dots + n_k)} \geq p_{ii}^{(n_1)} p_{ii}^{(n_2)} \dots p_{ii}^{(n_k)}; \\ (1)\ & p_{ii}^{(nk)} \geq (p_{ii}^{(n)})^k . \end{aligned}\]

例5.10 设例5.2中， \(n=3\), \(p=q=\frac{1}{2}\). 赌博者从2元赌金开始赌博， 求解他经过4次赌博之后输光的概率.

解： 记\(p_{ij} = P(X_{n+1}=j | X_n = i)\), 则对\(00\), \(p^{(n)}_{jk}>0\). 再由C-K方程知道 \[ p^{(m+n)}_{ik} = \sum_{l \in S} p^{(m)}_{il} p^{(n)}_{lk} \geq p^{(m)}_{ij} p^{(n)}_{jk} > 0 , \] 故\(i \to k\). 同理可证\(k \to i\)， 即有\(i \leftrightarrow k\).

我们把任何两个互通状态归为一类， 由上述定理可知， 同在一类的状态应该都是互通的， 并且任何一个状态不能同时属于两个不同的类.

○○○○○○

定义5.7 若马氏链只存在一个类， 就称它是不可约的(irreducible)； 否则称为可约的(reducible).

图5.2: 图上的简单随机游动

例5.14 我们来看例5.1中疾病死亡模型的四个状态之间的关系. 为清楚起见，经常以图5.2所示的转移图来表示马氏链的状态变化. 由转移矩阵容易看出： \(S_1\)和\(S_2\)互通， \(S_1\)和\(S_2\)可达\(S_3\)和\(S_4\)， 但\(S_3\)和\(S_4\)不可达除本身以外的其它状态。 状态可分为三类\(\{S_1, S_2\}\), \(\{S_3\}\)和\(\{S_4\}\). 称\(S_3\)和\(S_4\)为吸收态， 这样的状态\(i\)满足 \[ p_{ii}^{(n)} = 1, \ n=0,1,2,\dots \]

读者可用类似的方法来说明赌徒输光问题(例5.2)中任何两个状态\(i, j(0 < i, j < n)\)都互通， 并可将所有状态分为三类： \(\{0\}\), \(\{1,2,\cdots,n-1\}\), \(\{n\}\).

下面我们给出状态的一些性质，然后证明同在一类的状态具有相同的性质.

定义5.8 (周期) 若集合\(\{n: n \geq 1,p_{ii}^{(n)} > 0\}\)非空， 则称它的最大公约数\(d = d(i)\)为状态\(i\)的周期. 若\(d>1\)，称\(i\)是周期的； 若\(d=1\)，称\(i\)是非周期的. 并特别规定上述集合为空集时， 称\(i\)的周期为无穷大.

注1：周期无穷大的状态\(i\)， 是在这个状态下一步必然离开而且永不返回的状态， 是吸收态的一个反面。

注2：由定义5.8知道， 即使\(i\)有周期\(d\)，但并不是对所有的 \(n, p^{(nd)}_{ii}\)都大于0. 例如，设集合 \(\{n: n \geq 1, p^{(n)}_{ii}>0\}\)为\(\{3,9,18,21,\dots\}\)， 则最大公约数\(d=3\)， 即\(3\)是\(i\)的周期， 显然，\(n=6,12, 15\)都不属于此集合， 即\(p^{(6)}_{ii}=0\), \(p^{(12)}_{ii}=0\), \(p^{(15)}_{ii}=0\). 类似地， 若非周期，即\(d=1\)， 也不一定有\(p_{ii} > 0\)， 如果\(p_{ii} = 0\)， \(p_{ii}^{(2)}>0\)， \(p_{ii}^{(3)}>0\)， 则最大公约数也是1。 但是可以证明，当n充分大之后一定有\(p^{(dn)}_{ii}>0\).

图5.3: 状态分类

例5.15 考察如图5.3所示的马氏链.

由状态1出发再回到状态1的可能步长为\(T=\{4,6,8,10,\dots\}\)， 它的最大公约数是2， 虽然从状态1出发2步并不能回到状态1， 我们仍然称2是状态1的周期.

○○○○○○

定理5.4 若状态\(i,j\)同属一类，则\(d(i)=d(j)\).

证明： 由类的定义知\(i \leftrightarrow j\)， 即存在\(m, n \geq 0\)， 使\(p^{(m)}_{ij}>0,p^{(n)}_{ji}>0\)， 则 \[ p^{(m+n)}_{ii} =\sum_{k \in S} p^{(m)}_{ik} p^{(n)}_{ki} \geq p^{(m)}_{ij} p^{(n)}_{ji} > 0. \] 对所有使得\(p^{(s)}_{jj}>0\)的\(s\), 有\(p^{(n+s+m)}_{ii} \geq p^{(m)}_{ij} p^{(s)}_{jj} p^{(n)}_{ji} > 0\). 显然\(d(i)\)应同时整除\(n+m\)和\(n+m+s\)， 则它必定整除\(s\). 而\(d(j)\)是\(j\)的周期， 所以也有\(d(i)\)整除\(d(j)\). 反过来也可证明\(d(j)\)整除\(d(i)\)，于是\(d(i)=d(j)\).

○○○○○○

定义5.9 (首达概率) 对于任何状态\(i, j\)， 以\(f^{(n)}_{ij}\)记从\(i\)出发经\(n\)步后首次到达\(j\)的概率， 记 \[\begin{aligned} f^{(n)}_{ij} =& P\{X_n=j, X_k \neq j, k=1,2, \dots, n-1| X_0 = i \}, \ n \geq 1 , \\ f^{(0)}_{ij} =& {\delta}_{i-j} = \begin{cases} 1, & i=j, \\ 0, & i \neq j . \end{cases} \end{aligned}\] 令 \[ f_{ij} = \sum_{n=1}^{\infty} f^{(n)}_{ij}, \]

注：\(f_{ij}\)是从\(i\)出发经过有限步可达状态\(j\)的概率。 \(i \to j\)当且仅当\(f_{ij}>0\)。

定义5.10 (常返状态) 若\(f_{jj} = 1\)， 称状态\(j\)为常返状态(recurrent)； 若\(f_{jj} < 1\)， 称状态\(j\)为非常返状态或瞬过状态.

注：对常返状态\(i\)， 从\(i\)出发以概率1在有限步内回到状态\(i\)。

注：对非常返状态\(i\)， 有概率\(p = 1 - f_{ii} > 0\)使得从\(i\)出发不再返回\(i\)。 每次回到\(i\)后从\(i\)出发看成一个Bernoulli试验， 不返回视作成功， 返回视作失败， 记\(Y\)为这样的试验的次数， 则\(Y\)服从几何分布， 是取有限值的随机变量， 而每次这样的试验， 在成功（一去不返）前， 都是有限次状态转移， 所以从瞬态\(i\)出发在有限次状态转移之后必定一去不返。

对于常返状态\(i\)， 令\(T\)表示从\(i\)出发首次返回\(i\)的时间，即\(X_0=i\)条件下 \[ T = \inf \{n \geq 1: X_n = i \}, \] 则\(T\)为一个取有限值的随机变量， \(P(T=n) = f^{(n)}_{ii}\), \(n=1,2,\dots\)， 期望值为 \[ \mu_i = E(T) = \sum_{n=1}^{\infty} n f^{(n)}_{ii} , \] 即\(\mu_i\)表示的是由\(i\)出发再返回到\(i\)所需的平均步数(时间).

定义5.11 (正常返状态) 对于常返状态\(i\)， 若\(\mu_i < \infty\)，则称\(i\)为正常返状态； 若\(\mu_i = +\infty\)，则称\(i\)为零常返状态. 特别地，若\(i\)为正常返状态， 且是非周期的，则称之为遍历状态.

显然对于吸收态， \(f_{ii}^{(1)} = p_{ii} = 1\), \(f_{ii}^{(n)} = 0\)(\(n \geq 2\))， \(f_{ii} = 1\)， 有\(\mu_i = 1\)， 是正常返状态。

例5.16 设马氏链的状态空间为\(S = \{1,2,3,4\}\)， 其一步转移概率矩阵为 \[ P = \left(\begin{array}{cccc} \frac{1}{2} &\frac{1}{2}&0 & 0\\ 1&0 & 0& 0\\ 0& \frac{1}{3}& \frac{2}{3}& 0\\ \frac{1}{2} & 0 & \frac{1}{2}& 0 \end{array}\right) \] 试将状态进行分类.

解： 由一步转移概率矩阵\(P\)， 对一切\(n \geq 1\)， \(f_{44}^{(n)}=0\)，从而 \[ f_{44} = \sum_{n=1}^{\infty} f_{44}^{(n)} =0 < 1 , \] 故状态4是非常返态. 这就是周期等于正无穷的情况： 从状态4出发以概率1不再返回。

又 \[\begin{aligned} f_{33}^{(1)} = & \frac{2}{3}, \\ f_{33}^{(n)} =& 0 \ (n\geq 2), \\ f_{33} =& \sum_{n=1}^{\infty} f_{33}^{(n)} = \frac{2}{3} < 1, \end{aligned}\] 故状态3是非常返态.

但状态1与2是常返态，因为 \[\begin{aligned} f_{11} =& f_{11}^{(1)} + f_{11}^{(2)} =\frac{1}{2} + \frac{1}{2} = 1 , \\ f_{22} =& \sum_{n=1}^{\infty} f_{22}^{(n)} = 0 + \frac{1}{2} + \frac{1}{2^2} + \frac{1}{2^3} + \dots = 1 . \end{aligned}\]

事实上， 从状态\(1\)出发， 以概率\(\frac{1}{2}\)在第一步回到\(1\)， 以概率\(\frac{1}{2}\)先去状态\(2\)然后从状态\(2\)在第二步返回状态\(1\)。

从状态\(2\)出发， 必然在第一步去状态\(1\)， 但从状态\(1\)又可以以概率\(\frac{1}{2}\)在第二步回到状态\(2\)， 也可能以概率\((\frac{1}{2})^{n-2} \cdot \frac{1}{2}\)在状态\(1\)停留\(n-2\)步后才返回状态\(2\)， 这样， \(f_{22}^{(1)} = 0\)， \(f_{22}^{(2)} = \frac{1}{2}\)， \(f_{22}^{(n)} = (\frac{1}{2})^{n-1}\)。

计算得 \[\begin{aligned} \mu_1 =& \sum_{n=1}^{\infty} n f_{11}^{(n)} =1 \cdot \frac{1}{2} + 2 \cdot\frac{1}{2} = \frac{3}{2} < \infty, \\ \mu_2 =& \sum_{n=1}^{\infty} n f_{22}^{(n)} = 1 \cdot 0 +2 \cdot\frac{1}{2} + 3\cdot\frac{1}{2^2} + \cdots + n \cdot \frac{1}{2^{n-1}} = 3 0\)使得\(p_{ij}^{(m)} > 0\)， 由C-K方程， \[ p_{ij}^{(m+n)} \geq p_{ij}^{(m)} p_{jj}^{(n)}, \] 于是 \[\begin{aligned} \sum_{n=1}^\infty p_{ij}^{(m+n)} \geq p_{ij}^{(m)} \sum_{n=1}^\infty p_{jj}^{(n)} = \infty . \end{aligned}\]

○○○○○○

命题5.2 若\(i\)与\(j\)互通且都为常返状态， 则\(f_{ij}=1\)。

证明： 如果\(f_{ij} < 1\)， 则设\(p_{ji}^{(n)} > 0\)， 有正概率\(p_{ji}^{(n)} (1 - f_{ij})\)使得从\(j\)出发不能返回\(j\)， 与\(j\)常返矛盾。

○○○○○○

定理5.6 常返性是一个类性质.

证明： 只要证明若\(i \leftrightarrow j\)， 则\(i, j\)同为常返或非常返状态.

由\(i \leftrightarrow j\)知， 存在\(n, m \geq 0\)， 使得\(p^{(n)}_{ij}>0\), \(p^{(m)}_{ji}>0\)， 由C-K方程总有 \[\begin{aligned} p^{(n+m+l)}_{ii} \geq& p^{(n)}_{ij}p^{(l)}_{jj}p^{(m)}_{ji} \\ p^{(n+m+l)}_{jj} \geq& p^{(m)}_{ji}p^{(l)}_{ii}p^{(n)}_{ij} , \end{aligned}\] 求和得到 \[\begin{aligned} \sum_{l=0}^{\infty} p_{ii}^{(n+m+l)} \geq& p_{ij}^{(n)} p_{ji}^{(m)} \sum_{l=0}^{\infty} p_{jj}^{(l)} \\ \sum_{l=0}^{\infty} p_{jj}^{(n+m+l)} \geq& p_{ij}^{(n)} p_{ji}^{(m)} \sum_{l=0}^{\infty} p_{ii}^{(l)} . \end{aligned}\]

可见，\(\sum_{l=0}^{\infty} p^{(l)}_{jj}\), \(\sum_{l=0}^{\infty} p^{(l)}_{ii}\)相互控制，同为无穷或有限， 从而\(i,j\)同为常返或非常返状态.

其次我们还可以证明， 当\(i,j\)同为常返状态时， 它们同为正常返状态或零常返状态. 证明将在下一节给出.

○○○○○○

推论5.5 若常返状态\(i\)可达状态\(j\)， 则\(j\)也是常返状态。

证明： 这时\(j\)必然可达\(i\)， 否则设\(p_{ij}^{(n)} > 0\)， 则从\(i\)出发有正概率\(p_{ij}^{(n)}\)达到\(j\)后不再回到\(i\)， 与常返性矛盾。 \(i, j\)互通， 则常返性相同，证毕。

○○○○○○

图5.4: 每个状态返回0

例5.17 设马氏链的状态空间\({S}=\{0,1,2,\dots\}\), 转移概率为 \(p_{00}=\frac{1}{2}\), \(p_{i,i+1}=\frac{1}{2}\), \(p_{i0}=\frac{1}{2}\), \(i \in S\). 由图5.4易知, \(f^{(1)}_{00}=\frac{1}{2}\), \(f^{(2)}_{00}=\frac{1}{2}\cdot\frac{1}{2}\), \(f^{(3)}_{00}=\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{1}{2}\), ……， \(f^{(n)}_{00}=\frac{1}{2^n}\)， 故 \[\begin{aligned} f_{00} =& \sum_{n=1}^{\infty} \frac{1}{2^n} = 1, \\ \mu_0 =& \sum_{n=1}^{\infty} n2^{-n} < \infty . \end{aligned}\] 可见状态0是正常返状态， 显然它是非周期的， 故0是遍历态. 对其他状态\(i>0\)， 由\(i \leftrightarrow 0\), 故\(i\)也是遍历的.

例5.18 考虑直线上无限制的随机游动的常返性。 状态空间为\(S =\{ 0, \pm 1, \pm 2, \dots\}\)， 转移概率为\(p_{i,i+1} = 1-p_{i,i-1} = p\), \(i\in S\).

解： 对于状态0， 可知\(p^{(2n+1)}_{00}=0\), \(n=1,2,\dots\), 即从0出发奇数次不可能返回到0. 而 \[ p^{(2n)}_{00} = \binom{2n}{n} p^n (1-p)^n = \frac{(2n)!}{n!n!} [p(1-p)]^n . \] 即经过偶数次回到0当且仅当它向左、右移动距离相同.

由Stirling公式知, 当\(n\)充分大时， \(n! \sim n^{n+\frac{1}{2}} e^{-n} \sqrt{2\pi}\)， 则 \[ p^{(2n)}_{00} \sim \frac{[4p(1-p)]^n}{\sqrt{n\pi}}. \] 而\(p(1-p) \leq \frac{1}{4}\)且\(p(1-p)=\frac{1}{4} \iff p=\frac{1}{2}\). 于是\(p=\frac{1}{2}\)时, \(\sum_{n=0}^{\infty} p_{ii}^{(n)} = \infty\), 否则\(\sum_{n=0}^{\infty} p_{ii}^{(n)} < \infty\), 即当\(p \neq \frac{1}{2}\)时状态0是瞬过状态， \(p = \frac{1}{2}\)时是常返状态. 显然，过程的各个状态都是相通的， 故以此可得其他状态的常返性.

○○○○○○

图5.5: 离散状态马氏链状态分类

对于一个系统来说， 考虑它的长期的性质是很必要的， 本节我们将研究马氏链的极限情况和平稳马氏链的有关性质. 首先来看两个例子.

例5.19 设马氏链的转移矩阵为 \[ P = \left(\begin{array}{cc} 1-p & p\\ q & 1-q \end{array}\right), \ 0 < p, q 0\), \(p^{(l)}_{ji} > 0\)，从而由C-K方程可知 \[ p^{(n+m+l)}_{ii} \geq p^{(n)}_{ij} p^{(m)}_{jj} p^{(l)}_{ji} \geq 0 , \] 令\(m\to \infty\), 对上式取极限，知 \[ \lim_{m \to \infty} p^{(m)}_{jj} = 0， \] 从而\(j\)也为零常返状态. 反之由\(j\)为零常返状态也可推得\(i\)为零常返状态， 从而证明了\(i,j\)同为零常返状态或正常返状态.

○○○○○○

下面我们要利用定理5.7来讨论\(p^{(n)}_{ij}\)的极限性质. 一般说来, 我们讨论两个问题. 一是极限\(\lim_{n \to \infty}p^{(n)}_{ij}\)是否存在, 二是其极限是否与\(i\)有关. 首先有

定理5.8 (1) 若\(j\)为非常返状态或零常返状态， 则\(\forall i \in S\)都有 \[ \lim_{n \to \infty} p^{(n)}_{ij} = 0 . \]

(2) 若马氏链为遍历链（不可约、正常返、非周期）， 则对任意\(i, j \in S\)，有 \[ \lim_{n \to \infty} p_{ij}^{(n)} = \frac{1}{\mu_j} . \]

证明： (1) 由引理5.1，得 \[\begin{equation} p_{ij}^{(n)} = \sum_{l=1}^n f^{(l)}_{ij} p^{(n-l)}_{jj} . \tag{5.8} \end{equation}\] 对\(N < n\)，有 \[\begin{equation} \sum_{l=1}^n f_{ij}^{(l)} p_{jj}^{(n-l)} \leq \sum_{l=1}^N f_{ij}^{(l)}p_{jj}^{(n-l)} + \sum_{l=N+1}^n f^{(l)}_{ij} . \tag{5.9} \end{equation}\]

于是 \[\begin{aligned} \varlimsup_{n\to\infty} p_{ij}^{(n)} \leq& \sum_{l=1}^N f_{ij}^{(l)} \varlimsup_{n\to\infty} p_{jj}^{(n-l)} + \sum_{l=N+1}^{\infty} f^{(l)}_{ij} \\ =& 0 + \sum_{l=N+1}^{\infty} f^{(l)}_{ij} . \end{aligned}\] 由\(\sum_{l=1}^{\infty} f^{(l)}_{ij} \leq 1\)可知\(\lim_{N\to\infty} \sum_{l=N+1}^{\infty} f^{(l)}_{ij} = 0\)， 于是\(\varlimsup_{n\to\infty} p_{ij}^{(n)} \leq 0\)，\(\lim_{n\to\infty} p_{ij}^{(n)} = 0\)。

(2) 由(5.8)，取\(N < n\), 有 \[\begin{aligned} \varliminf_{n\to\infty} p_{ij}^{(n)} \geq& \sum_{l=1}^N f_{ij}^{(l)} \varliminf_{n\to\infty} p_{jj}^{(n-l)} \\ =& \sum_{l=1}^N f_{ij}^{(l)} \frac{1}{\mu_j}, \end{aligned}\] 令\(N \to \infty\)有 \[\begin{aligned} \varliminf_{n\to\infty} p_{ij}^{(n)} \geq& \frac{1}{\mu_j} \sum_{l=1}^\infty f_{ij}^{(l)} = \frac{1}{\mu_j} f_{ij} = \frac{1}{\mu_j} . \end{aligned}\] 这里用到\(i \to j\)且\(j\)常返则\(f_{ij}=1\)。

另一方面， 由(5.8)， \[\begin{aligned} \varlimsup_{n\to\infty} p_{ij}^{(n)} \leq& \sum_{l=1}^N f_{ij}^{(l)} \varlimsup_{n\to\infty} p_{jj}^{(n-l)} + \sum_{l=N+1}^\infty f_{ij}^{(l)} \\ =& \frac{1}{\mu_j} \sum_{l=1}^N f_{ij}^{(l)} + \sum_{l=N+1}^\infty f_{ij}^{(l)} , \end{aligned}\] 令\(N\to\infty\)得 \[\begin{aligned} \varlimsup_{n\to\infty} p_{ij}^{(n)} \leq& \frac{1}{\mu_j} \sum_{l=1}^\infty f_{ij}^{(l)} + 0 = \frac{1}{\mu_j} f_{ij} = \frac{1}{\mu_j}, \end{aligned}\] 故\(\lim_{n\to\infty} p_{ij}^{(n)} = \frac{1}{\mu_j}\)。

○○○○○○

注：结论(2)中\(\lim_{n\to\infty} p_{ij}^{(n)}\)可以理解为系统从状态\(i\)出发， 当\(n\)充分大时系统状态\(X_n\)位于状态\(j\)的比例。 5.3.4给出了针对逐条轨道的结论。

推论5.8 有限状态的马氏链， 不可能全为非常返状态， 也不可能有零常返状态， 从而不可约的有限马氏链是正常返的.

证明： 设状态空间\(S=\{1,2,\dots,N\}\). 若全部\(N\)个状态非常返， \(\forall i, j \in S\)有\(p^{(n)}_{ij} \to 0\), 注意 \[ \sum_{j=1}^N p^{(n)}_{ij} = 1, \] 令\(n \to \infty\)，等式左侧极限为0，右侧为1， 矛盾。

若\(S\)中有零常返状态，设为\(i\)。 令\(C = \{j: i \to j\}\), 由推论5.5可知\(C\)中的状态也是常返状态， 再由推论5.7可知\(C\)中的状态都是零常返状态， 从而 \[ \lim_{n\to\infty} p_{ij}^{(n)} = 0. \] 注意 \[ \sum_{j \in C} p^{(n)}_{ij} = 1, \] 在上式中令\(n \to \infty\)， 则左侧极限为0，右侧为1， 矛盾。

○○○○○○

推论5.9 若Markov链有一个零常返状态， 则必有无限个零常返状态.

证明： 设\(i\)为零常返状态， \(C = \{j: i \to j\}\), 则\(C\)中的状态也是零常返状态， 有\(\lim_{n\to\infty} p_{ij}^{(n)} = 0\)。 注意到 \[ \sum_{j \in C} p^{(n)}_{ij} = 1, \] 如果\(C\)为有限集合， 则上式两边令\(n \to \infty\)， 左侧极限为0，右侧为1， 矛盾， 所以\(C\)必为无限集合， 于是有无穷多个零常返状态。

○○○○○○

定理5.8没有讨论当\(j\)是正常返， 但非遍历时\(\lim_n p_{ij}^{(n)}\)的情况。 这种情况下，极限不一定存在， 存在时可能与\(i\)有关。 下面的定理侧面描述了这种情况：

定理5.9 设\(j\)为常返状态， 则对于任意的\(i \in S\)， 有 \[ \lim_{n\to\infty} \frac{1}{n+1} \sum_{k=0}^n p_{ij}^{(k)} = \frac{f_{ij}}{\mu_j} . \]

证明见(林元烈 2002) P.94定理3.3.5。

注1：左边的极限描述了从状态\(i\)出发， 在长期内平均处于状态\(j\)的概率， 这个概率等于从\(i\)可达\(j\)的概率， 除以从\(j\)返回\(j\)的平均间隔。 5.3.4给出了针对逐条轨道的结论。

如果\(i=j\)， 这个平均概率就等于\(1/\mu_j\)。

注2：可以将所有状态分为瞬态组\(T\)（不要求所有瞬态互通）和若干个常返状态组\(C_k, k=1,2,\dots\)， 其中\(C_k\)中的状态互通且为常返状态， 而\(C_k \cap C_j = \emptyset\)(\(k \neq j\))。 系统可以一直从瞬态出发一直在瞬态中运动（这要求有无穷多个瞬态）， 还可以从某个\(C_k\)出发一直在\(C_k\)中运动， 也可以从某个瞬态出发在有限步后进入某个\(C_k\)， 然后保持在\(C_k\)中运动。

下面的定理给出了\(j\)正常返但周期大于1的\(\lim_{n\to\infty} p_{ij}^{(n)}\)结果。 需要按周期中不同相位分别计算极限：

定理5.10 若\(j\)为正常返状态， 周期为\(d\)， 则对任意\(i \in S\)， \(0 \leq r \leq d-1\)， 有 \[\begin{equation} \lim_{n\to\infty} p_{ij}^{(nd+r)} = f_{ij}(r) \frac{d}{\mu_j}, \tag{5.10} \end{equation}\] 其中 \[ f_{ij}(r) = \sum_{m=0}^\infty f_{ij}^{(md + r)}, \] 当\(d=1\)时(这时状态\(j\)遍历)即 \[ \lim_{n\to\infty} p_{ij}^{(n)} = \frac{f_{ij}}{\mu_j} . \]

见(林元烈 2002) P.108定理3.5.2， 证明参考(何声武 1999)。

注：定理结论说明， 若\(j\)的周期\(d \geq 2\)， 则一般\(\lim_n p_{ij}^{(n)}\)不存在， 可以将\(n\)按照除以\(d\)的余数分为\(d\)个子序列， 每个子序列有单独的极限。

图5.6: 图上的简单随机游动

例5.21 设马氏链的状态空间为\({S}=\{1,2,3,4,5\}\)， 转移矩阵为 \[ P = \left(\begin{array}{ccccc} 1&0&0&0&0\\ 0&1&0&0&0\\ \frac{1}{2}&0&0&\frac{1}{2}&0\\ 0&0&\frac{1}{2}&0&\frac{1}{2}\\ 0&\frac{1}{2}&0&\frac{1}{2}&0 \end{array}\right) \] 试确定常返状态，瞬过状态， 并对常返状态\(i\)确定其平均回转时间\(\mu_i\).

解: 这是有限链，不能有零常返状态。

画出转移图5.6. 显然，状态\(1,2\)的周期为1， 状态\(3,4,5\)的周期为2.

\[ P^n \stackrel{n \to \infty}{\longrightarrow} \left(\begin{array}{ccccc} 1&0&0&0&0\\ 0&1&0&0&0\\ {*}&*&0&0&0\\ {*}&*&0&0&0\\ {*}&*&0&0&0 \end{array}\right) \] 从而\(1, 2\)是吸收态， 为正常返， \(\mu_1 = \mu_2 = 1\). \(3,4,5\)为瞬过状态。 此马氏链可分为三类，即\(\{1\}\),\(\{2\}\)和\(\{3,4,5\}\).

前面我们只讨论了马氏链的转移概率\(p_{ij}\)的有关问题， 下面我们将就它的初始分布的问题给出一些结论. 首先是关于马氏链的平稳分布和极限分布的概念.

定义5.12 对于马氏链，概率分布\(\{p_j, j \in S\}\)称为平稳分布，若 \[ p_j = \sum_{i \in S}p_i p_{ij}, \ \forall j \in S . \]

平稳分布又称不变分布。

记\(\boldsymbol \pi = (p_1, p_2, \dots)^T\)， 则平稳分布\(\boldsymbol \pi\)必须满足 \[ \boldsymbol \pi^T P = \boldsymbol\pi^T, \quad \boldsymbol \pi^T \boldsymbol 1 = 1. \]

若马氏链的初始分布\(P\{ X_0 = j \}= p_j\)是平稳分布， 则\(X_1\)的分布将是 \[\begin{aligned} P \{ X_1 = j \} =& \sum_{i \in S} P\{ X_1 = j | X_0 = i \} \cdot P\{ X_0 = i \} \\ =& \sum_{i \in S} p_{ij} p_i =p_j, \ \forall j \in S . \end{aligned}\] 这与\(X_0\)的分布是相同的， 依次递推可知\(X_n, n = 0,1,2,3,\dots\)将有相同的分布， 这也是为什么称\(\{p_i, i \in S \}\)为平稳分布的原因. 易见 \[ \boldsymbol \pi^T P^n = \boldsymbol\pi^T , \ n \geq 1 . \]

定理5.11 设马氏链\(\{X_n, n \geq 0 \}\)有平稳分布\(\boldsymbol \pi\)， 且\(X_0 \sim \boldsymbol \pi\)， 则\(\{X_n \}\)是严平稳的随机过程。

证明： 这时每一个\(X_n\)的边缘分布都是\(\boldsymbol \pi\)， 于是由定理5.2， \[ P(X_0 = i_0, X_1 = i_1, \dots, X_n = i_n) = \pi_{i_0} p_{i_0 i_1} p_{i_1 i_2} \dots p_{i_{n-1} i_n} , \] 同理有\(m \geq 0\)时 \[ P(X_m = i_0, X_{m+1} = i_1, \dots, X_{m+n} = i_n) = \pi_{i_0} p_{i_0 i_1} p_{i_1 i_2} \dots p_{i_{n-1} i_n} , \] 因此\(\{X_n, n\geq 0 \}\)是严平稳的。

定义5.13 称马氏链是遍历的， 如果所有状态不可约、非周期、正常返. 对于遍历的马氏链,极限 \[ \lim_{n \to \infty} p^{(n)}_{ij} = \pi_j = \frac{1}{\mu_j}, \quad j \in {S} \] 称为马氏链的极限分布。

定义中极限\(\pi_j=\frac{1}{\mu_j}\)， 是利用了定理5.8. 此定理说明， 对于遍历链， 不论从那个状态开始， 当\(n\)充分大时， 对任意\(n\)，\(X_n\)都有正概率处于状态\(j\)， \(j\)也是任意状态； \(X_n\)处于状态\(j\)的概率为正值\(\frac{1}{\mu_j}\)。 这给出了“遍历”这一术语的解释， 即系统在长时间运行中可以在任意时间到达任意状态。

下面的定理说明对于遍历的马氏链，极限分布就是平稳分布并且还是唯一的平稳分布.

定理5.12 (1) 对于遍历马氏链， \(\pi_j = \lim_{n \to \infty} p^{(n)}_{ij} = \frac{1}{\mu_j} > 0\)(\(j \in S\))是平稳分布且是唯一的平稳分布；

(2) 若马氏链所有状态都是非常返或零常返的，则平稳分布不存在.

证明： (1) 对遍历的马氏链， 由定理5.8知 \[ \lim_{n \to \infty}p^{(n)}_{ij} = \frac{1}{\mu_j} > 0 , \] 记为\(\pi_j\). 于是极限分布存在（极限分布存在则必唯一）。

先证明\(\{\pi_j, j \in S \}\)是平稳分布， 然后再来证明它是唯一的平稳分布。 这里仅给出有限链时的证明， 状态个数无限的链在证明时涉及到级数与极限交换次序， 需要较复杂的讨论，见5.7.2。

由于 \[ \sum_{j \in S} p^{(n)}_{ij} = 1 , \] 则有 \[\begin{equation} \lim_{n \to \infty} \sum_{j \in S} p^{(n)}_{ij} = 1 . \tag{5.11} \end{equation}\] 当\(S\)为有限状态时极限与求和可交换。 于是有 \[ \sum_{j \in S} \pi_j = 1 . \]

利用C-K方程得 \[ p^{(n+1)}_{ij} = \sum_{k \in S} p^{(n)}_{ik} p_{kj} , \] 两边取极限， 若\(S\)为有限状态则极限与求和可交换，于是 \[\begin{aligned} \lim_{n \to \infty} p^{(n+1)}_{ij} = \lim_{n \to \infty} \sum_{k \in S} p^{(n)}_{ik} p_{kj} =\sum_{k\in S}(\lim_{n \to \infty} p^{(n)}_{ik}) p_{kj} , \end{aligned}\] 即\(\pi_j = \sum_{k \in {S}}\pi_k p_{kj}\), 从而\(\{ \pi_j, j \in S \}\)是平稳分布.

再证\(\{\pi_j, j\in {S}\}\)是唯一的平稳分布. 假设另外还有一个平稳分布\(\{\tilde{\pi}_j, j \in S \}\), 则由 \[ \tilde{\pi}_j = \sum_{k \in S} \tilde{\pi}_k p_{kj} \] 归纳得到 \[\begin{equation} \tilde{\pi}_j = \sum_{k \in S} \tilde{\pi}_k p^{(n)}_{kj}, \quad n = 1, 2, \dots, \tag{5.12} \end{equation}\] 令\(n\to \infty\)， 若\(S\)为有限状态则极限与求和可交换， 有 \[\begin{aligned} \tilde{\pi}_j =& \sum_{i \in S} \tilde{\pi}_i \lim_{n \to \infty} p^{(n)}_{ij} \\ =& \sum_{i \in S} \tilde{\pi}_i \cdot \pi_j = \pi_j \cdot \sum_{i \in S} \tilde{\pi}_i = \pi_j, \ \forall j \in S . \end{aligned}\] 即平稳分布唯一.

(2) 所有状态都是零常返或瞬态时， 假设存在一个平稳分布\(\{\pi_j, j \in S\}\), 则由(5.12)有 \[ \pi_j = \sum_{i\in S} \pi_i p^{(n)}_{ij}, \ n = 1,2,\dots , \] 令\(n \to \infty\)， 若\(S\)为有限状态则极限与求和可交换， 因\(p^{(n)}_{ij}\to 0\), 推出\(\pi_j = 0, j \in S\), 这与\(\sum_{j \in S} \pi_j = 1\)矛盾。 于是对于所有状态都非常返或零常返的马氏链不存在平稳分布.

○○○○○○

注1：若马氏链为有限、不可约、非周期， 必为正常返从而为有限状态遍历马氏链， 平稳分布存在唯一且等于极限分布。 这时平稳方程存在唯一解且等于极限分布， 只要求解平稳方程。 这同时也给出了求\(\mu_j = \frac{1}{\pi_j}\)的方法。

注2：定理5.12没有给出马氏链存在正常返状态， 但非遍历链的结果。 实际上， 只要存在正常返状态， 平稳分布就存在， 但不一定唯一； 如果只有非常返和零常返状态， 平稳分布一定不存在。 下面的定理给出了一般的结果。

定理5.13 (1) 当且仅当所有状态都是非常返和零常返时， 马氏链没有平稳分布。

(2) 平稳分布存在唯一的充分必要条件是马氏链存在正常返状态且正常返状态都是互相连通的。

(3) 有限状态马氏链总存在平稳分布（不一定唯一）。

(4) 有限的不可约、非周期马氏链存在唯一的平稳分布。

见(林元烈 2002) P.111定理3.5.7。

注1：结论(1)说明只要有正常返状态就一定存在平稳分布但不一定唯一， 否则一定不存在平稳分布。 存在正常返状态是存在平稳分布的充分必要条件， 与是否不可约和是否非周期无关。

注2：结论(2)说明如果正常返状态按互通性分成两个或两个以上的组， 平稳分布就有多个。

注3：第(4)条是因为这时马氏链遍历， 由定理5.12第一条即可得结论。

注4: 结论(4)是因为有限状态、不可约、非周期必然遍历。 类似结论对无限状态马氏链是否成立？有如下结果。

定理5.14 不可约、非周期马氏链为遍历链（即状态都是正常返的）， 当且仅当它存在平稳分布。 这时平稳分布等于极限分布。

见(林元烈 2002) P.113定理3.5.8。 所以不可约、非周期马氏链或者是遍历的， 存在唯一的平稳分布同时也是极限分布； 或者是非常返或者零常返的， 这时不存在平稳分布， 也不存在极限分布。

定理5.15 设马氏链\(\{X_n, n \geq 0 \}\)不可约、非周期， 且有平稳分布\(\pi\)， 则 \[ \lim_{n\to\infty} \sum_{j \in S} |p_{ij}^{(n)} - \pi_j| = 0, \ \forall i \in S . \]

参见(钱敏平 et al. 2011) P.19定理1.5.5。 注意这时马氏链为遍历链， \(\pi\)是唯一的平稳分布和极限分布。 定理说明\(p_{ij}^{(n)}\)当\(n \to \infty\)时关于\(j\)一致地趋于\(\pi_j\)。

推论5.10 若不可约马氏链存在平稳分布\(\pi\)， 则 \[ \lim_{n\to\infty} \sum_{j \in S} \left| \frac{1}{n} \sum_{m=0}^n p_{ij}^{(m)} - \pi_j \right| = 0, \ \forall i \in S . \]

参见(钱敏平 et al. 2011) P.21推论1.5.6。 这时马氏链为正常返，但不一定是非周期的。 结论说明\(p_{ij}^{(n)}\)的局部平均序列\(\frac{1}{n} \sum_{m=0}^n p_{ij}^{(m)}\)当\(n \to \infty\)时关于\(j\)一致地趋于\(\pi_j\)。 因为没有要求非周期， 所以\(p_{ij}^{(n)}\)有可能等于0， 所以结论退化到了考虑\(\frac{1}{n} \sum_{m=0}^n p_{ij}^{(m)}\)， 这可以理解为从状态\(i\)出发， 时间\(1,2,\dots,n\)中的状态平均处于状态\(j\)的概率。 5.3.4给出了针对逐条轨道的结论。

例5.22 (用R和Julia计算平稳分布) 当马氏链为有限、不可约、非周期时， 平稳分布存在唯一，只要求解平稳方程。 用编程方法求解平稳方程。

平稳分布\(\boldsymbol \pi\)满足 \[ \boldsymbol \pi^T P = \boldsymbol\pi^T, \quad \boldsymbol 1^T \boldsymbol\pi = 1, \] 这是一个超定方程： \[ \begin{pmatrix} P^T - I \\ \boldsymbol 1^T \end{pmatrix} \boldsymbol \pi = \begin{pmatrix} \boldsymbol 0 \\ 1 \end{pmatrix}, \] 可以用最小二乘法求解\(\boldsymbol \pi\)。

R的输入\(P\)求解\(\boldsymbol \pi\)的函数：