随机过程 Markov 链（中）

极限定理及平稳分布

极限定理

Th：（基本极限定理）若状态 $i$ 是周期为 $d$ 的常返状态，则：
$$\underset{n\to \infty }{\lim }{p}_{ii}^{(nd)}=\frac{d}{{\mu }_i}$$
当 $i$ 为零常返状态，即 ${\mu }_i=\infty$ 时，$\frac{d}{{\mu }_i}=0$ ；显然，当 $i$ 为非常返状态时，$\sum _{n=1}^{\infty }{p}_{ii}^{(n)}<\infty$ ，则 $\underset{n\to \infty }{\lim }{p}_{ii}^{(n)}=0$ 。

没有证明捏 ~(￣▽￣)~*

Th：设 $i$ 为常返状态，则：
$$i\text{为零常返状态}⟺\underset{n\to \infty }{\lim }{p}_{ii}^{(n)}=0$$
证明：

• 若 $i$ 为零常返状态，则 ${\mu }_i=\infty$ ，由上边的定理得 $\underset{n\to \infty }{\lim }{p}_{ii}^{(nd)}=\frac{d}{{\mu }_i}=0$ ，并且当 $m$ 不为 $d$ 的整数倍时，由周期的定义有 $p_{ii}^{(m)}=0$ ，因此综合两点得到 $\underset{n\to \infty }{\lim }{p}_{ii}^{(n)}=0$ ；

• 若 $\underset{n\to \infty }{\lim }{p}_{ii}^{(n)}=0$ ，反证法：设 $i$ 为正常返状态，则 ${\mu }_i<\infty$ ，故 $\underset{n\to \infty }{\lim }{p}_{ii}^{(nd)}=\frac{d}{{\mu }_i}>0$ ，矛盾。

Th：设 $i\leftrightarrow j$ 且为常返状态（上一节的定理，常返状态是个类性质），当 $i$ 为零常返状态时，$j$ 也为零常返状态（即零常返也是类性质）

证明：有：
$$p_{ii}^{(m+n+l)}\ge p_{ij}^{(n)}{p}_{jj}^{(l)}{p}_{ji}^{(m)}\ge 0$$
令 $l\to \infty$ ，则由上面的定理知，因为 $i$ 是零常返状态，所以 $\underset{l\to \infty }{\lim }{p}_{ii}^{(m+n+l)}=0$ ，因此：
$$0\ge p_{jj}^{(l)}\ge 0$$
即 $\underset{l\to \infty }{\lim }{p}_{jj}^{(l)}=0$ ，因此 $j$ 也是零常返状态，得证。

Th：接下来我们讨论 $p_{ij}^{(n)}$ 的极限性质：

• 若 $j$ 为非常返状态或零常返状态，则对 $\forall i\in S$ ，有：

$$\underset{n\to \infty }{\lim }{p}_{ij}^{(n)}=0$$

• 若 Markov 链为不可约、正常返，且非周期，则对于 $\forall i,j\in S$ ，有：

$$\underset{n\to \infty }{\lim }{p}_{ij}^{(n)}=\frac{1}{{\mu }_j}$$

证明：（1）由前边转移概率和首达概率的关系有：$p_{ij}^{(n)}=\sum _{l=1}^n{f}_{ij}^{(l)}{p}_{jj}^{(n-l)}$ ，对 $N<n$ ，有：（因为总有 $p_{jj}^n\le 1$ ）
$$\sum _{l=1}^n{f}_{ij}^{(l)}{p}_{jj}^{(n-l)}\le \sum _{l=1}^N{f}_{ij}^{(l)}{p}_{jj}^{(n-l)}+\sum _{l=N+1}^n{f}_{ij}^{(l)}$$
首先固定 $N$ ，令 $n\to \infty$ ：

• 若 $j$ 为非常返状态，由于 $\underset{n\to \infty }{\lim }\sum _{i=1}^n{p}_{jj}^{(i)}<\infty$ ，因此 $\underset{n\to \infty }{\lim }{p}_{jj}^{(n)}=0$ ，故 $\underset{n\to \infty }{\lim }\sum _{l=1}^N{f}_{ij}^{(l)}{p}_{jj}^{(n-l)}=0$ ；
• 若 $j$ 为零常返状态，由上面的定理可知，$\underset{n\to \infty }{\lim }{p}_{jj}^{(n)}=0$ ，故 $\underset{n\to \infty }{\lim }\sum _{l=1}^N{f}_{ij}^{(l)}{p}_{jj}^{(n-l)}=0$ ；

所以得到：
$$p_{ij}^{(n)}=\sum _{l=1}^n{f}_{ij}^{(l)}{p}_{jj}^{(n-l)}\le \sum _{l=N+1}^n{f}_{ij}^{(l)}$$
由于 $\sum _{l=1}^{\infty }{f}_{ij}^{(l)}\le 1<\infty$ ，所以 $\underset{l\to \infty }{\lim }{f}_{ij}^{(l)}=0$ ，因此再令 $N\to \infty$ ，则 $\sum _{l=N+1}^n{f}_{ij}^{(l)}\to 0$ ，故：
$$\underset{n\to \infty }{\lim }{p}_{ij}^{(n)}\le 0\Rightarrow \underset{n\to \infty }{\lim }{p}_{ij}^{(n)}=0$$
（2）利用（1）中的式子可以得到：
$$\sum _{l=1}^N{f}_{ij}^{(l)}{p}_{jj}^{(n-l)}\le p_{ij}^{(n)}\le \sum _{l=1}^N{f}_{ij}^{(l)}{p}_{jj}^{(n-l)}+\sum _{l=N+1}^n{f}_{ij}^{(l)}$$
先固定 $N$ ，令 $n\to \infty$ ，由于 $j$ 是正常返、周期为 $1$ 的状态，由这一节的第一个定理可以得到：$\underset{n\to \infty }{\lim }{p}_{jj}^n=\frac{1}{{\mu }_j}$ ，即：
$$\frac{1}{{\mu }_j}\sum _{l=1}^N{f}_{ij}^{(l)}\le p_{ij}^{(n)}\le \frac{1}{{\mu }_j}\sum _{l=1}^N{f}_{ij}^{(l)}+\sum _{l=N+1}^n{f}_{ij}^{(l)}$$
又令 $N\to \infty$ ，由于这个 Markov 链是不可约的，因此 $i\leftrightarrow j$ ，故 $f_{ij}=1$ ，且由（1）中证明可以得到 $\sum _{l=N+1}^n{f}_{ij}^{(l)}\to 0$ ，故：
$$\frac{1}{{\mu }_j}\le \underset{n\to \infty }{\lim }{p}_{ij}^{(n)}\le \frac{1}{{\mu }_j}\Rightarrow \underset{n\to \infty }{\lim }{p}_{ij}^{(n)}=\frac{1}{{\mu }_j}$$
Th：状态有限的 Markov 链，不可能全为非常返状态，也不可能有零常返状态；从而不可约的有限 Markov 链是正常返的。

证明：（1）反证法，若状态空间为 S = { 1 ,   2 ,   ⋯   ,   N } S=\{1,\,2,\,\cdots,\,N\} S={1,2,⋯,N} 的 Markov 链全为非常返状态，则：

• 若 $i\to j$ ，由前面定理的（2）得到， $p_{ij}^{(n)}\to \frac{1}{{\mu }_j}=0$ （$n\to \infty$）；
• 若 $i\nrightarrow j$ ，则显然 $p_{ij}^{(n)}=0$ ；

即对任意 $i$ ，当 $n\to \infty$ 时都有 $\sum _{j=1}^N{p}_{ij}^{(n)}=0$ ；但是显然只有这 $N$ 个状态，因此 $\sum _{j=1}^N{p}_{ij}^{(n)}=1$ ，矛盾，因此不可能全为非常返状态；

（2）若 $S$ 中有零常返状态，设为 $i$ ，令 C = { j   ∣   i → j } C=\{j\,|\,i\to j\} C={j∣i→j} ，有 $\sum _{j\in C}{p}_{ij}^{(n)}=1$ ；由 $i$ 为常返状态得，由于 $i$ 是常返状态，所以 $f_{ii}=1$ ，又因为 $C$ 中状态有限，所以这个概率为 1 代表必然事件，即从 $i$ 出发，在有限步内必然可以回到 $i$ 。因此对于 $\forall j\in C$ ，都有 $j\to i$ 。故 $i\leftrightarrow j$ ，又因为零常返是类性质，因此 $j$ 也是零常返状态，则由前面一个定理的（1）得到 $\underset{n\to \infty }{\lim }{p}_{ij}^{(n)}=0$ 。故当 $n\to \infty$ 时，有 $\sum _{j\in C}{p}_{ij}^{(n)}=0$ ，与 $\sum _{j\in C}{p}_{ij}^{(n)}=1$ 矛盾。因此 $S$ 中不存在零常返状态。

Th：若 Markov 链有一个零常返状态，则必有无限多个零常返状态。

证明：这是一个推论，和前面一个定理一样，如果只有有限多个零常返状态，则可以推出 $\sum _{j\in C}{p}_{ij}^{(n)}=0$ 与 $\sum _{j\in C}{p}_{ij}^{(n)}=1$ 矛盾

例：设 Markov 链的转移矩阵为：
$$P=\left[\begin{array}{cc}1-p& p\\ q& 1-q\end{array}\right]0<p,q<1$$
解：对于极限转移概率，需要考虑 $P^n$（$n\to \infty$），对 $P$ 进行特征值分解，得到：
$$P=QD{Q}^{-1}D=\left[\begin{array}{cc}1& 0\\ 0& 1-p-q\end{array}\right]Q=\left[\begin{array}{cc}1& -p\\ 1& q\end{array}\right]Q^{-1}=\left[\begin{array}{cc}\frac{q}{p+q}& \frac{p}{p+q}\\ -\frac{1}{p+q}& \frac{1}{p+q}\end{array}\right]$$
则：
$$P^n=QD{Q}^{-1}QD{Q}^{-1}\cdots QD{Q}^{-1}=Q{D}^n{Q}^{-1}=\left[\begin{array}{cc}\frac{q+p(1-p-q{)}^n}{p+q}& \frac{p-p(1-p-q{)}^n}{p+q}\\ \frac{q-q(1-p-q{)}^n}{p+q}& \frac{p+q(1-p-q{)}^n}{p+q}\end{array}\right]$$
故：
$$\underset{n\to \infty }{\lim }{P}^n=\left[\begin{array}{cc}\frac{q}{p+q}& \frac{p}{p+q}\\ \frac{q}{p+q}& \frac{p}{p+q}\end{array}\right]$$
可见此 Markov 链的 $n$ 步转移概率的极限存在。

例：设 Markov 的状态空间 S = { 1 ,   2 ,   3 ,   4 ,   5 } S=\{1,\,2,\,3,\,4,\,5\} 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$ ；

解：画出状态转移图：

显然状态 1、2 的周期为 1，3、4、5 的周期为 2；用分块矩阵计算，可以得到：
$$
\lim\limits_{n\to\infty}P^n=\begin{bmatrix}
1 & 0 & 0 & 0 & 0 \
0 & 1 & 0 & 0 & 0 \

• & * & 0 & 0 & 0 \
• & * & 0 & 0 & 0 \
• & * & 0 & 0 & 0 \
  \end{bmatrix}
  $$
  从而 $1$ 和 $2$ 为正常返状态，3、4、5 为非常返状态。 由这节开头的极限定理可知 $\underset{n\to \infty }{\lim }{p}_{ii}^{(nd)}=\frac{d}{{\mu }_i}$ ，因此 ${\mu }_1={\mu }_2=1$ （由定义也可以知道，状态 1 或 2 平均一步就可以返回原来的状态）。此 Markov 链可以分为三类： { 1 } \{1\} {1} { 2 } \{2\} {2} { 3 ,   4 ,   5 } \{3,\,4,\,5\} {3,4,5}

平稳分布与极限分布

平稳分布：对于 Markov 链，概率分布 { p j ,   j ∈ S } \{p_j,\,j\in S\} {pj​,j∈S} 称为平稳分布，若：
$$p_j=\sum _{i\in S}{p}_i{p}_{ij}$$
若 Markov 的初始分布 $P(X_0=j)=p_{j}j\in S$ 是平稳分布，则：
$$\begin{array}{rl}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\end{array}$$
得到任意 $X_i$ 都有着相同的分布，这就是为什么称为平稳分布。

遍历：如果所有状态相通（即不可约）且均是周期为 $1$ （即非周期）的正常返状态，则称 Markov 链是遍历的；

• 遍历的 Markov 链：不可约、正常返、非周期

极限分布：对于遍历的 Markov 链，极限：
$$\underset{n\to \infty }{\lim }{p}_{ij}^{(n)}={\pi }_j$$
称为 Markov 的极限分布；由上一节的极限定理可知，${\pi }_j=\frac{1}{{\mu }_j}$ ；

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

Th：对于不可约非周期的 Markov 链：

• 若它是遍历的，则 KaTeX parse error: Expected group after '_' at position 11: \pi_j=\lim_̲\limits{n\to\in… （$j\in S$） 是平稳分布，并且是唯一的平稳分布；
• 若状态都是瞬过的或全为零常返的（肯定是无穷多个状态），则平稳分布不存在；

证明：

（1）对于遍历的 Markov 链，由上一节的极限定理可知，${\pi }_j=\frac{1}{{\mu }_j}$ 是存在的，首先证明 { π j ,   j ∈ S } \{\pi_j,\,j\in S\} {πj​,j∈S} 是平稳分布。由于 $\sum _{j\in S}{p}_{ij}^{(n)}=1$ ，有：
$$\underset{n\to \infty }{\lim }\sum _{j\in S}{p}_{ij}^{(n)}=1$$
显然式中的极限和求和可以交换顺序，得到：
$$\sum _{j\in S}{\pi }_j=1$$
由 C-K 方程得到：
$$p_{ij}^{(n+1)}=\sum _{k\in S}{p}_{ik}^{(n)}{p}_{kj}$$
两边对 $n$ 取极限得到：
$${\pi }_j=\underset{n\to \infty }{\lim }{p}_{ij}^{(n+1)}=\underset{n\to \infty }{\lim }\sum _{k\in S}{p}_{ik}^{(n)}{p}_{kj}=\sum _{k\in S}\underset{n\to \infty }{\lim }\left(p_{ik}^{(n)}\right)p_{kj}=\sum _{k\in S}{\pi }_k{p}_{kj}$$
即 ${\pi }_j=\sum _{k\in S}{\pi }_k{p}_{kj}$ ，从而 { π j ,   j ∈ S } \{\pi_j,\,j\in S\} {πj​,j∈S} 是平稳分布。

再证明 { π j ,   j ∈ S } \{\pi_j,\,j\in S\} {πj​,j∈S} 是唯一的平稳分布。设还有另一个平稳分布 { π ~ j ,   j ∈ S } \{\tilde\pi_j,\,j\in S\} {π~j​,j∈S} ，则由 ${\tilde{\pi }}_j=\sum _{k\in S}{\tilde{\pi }}_k{p}_{kj}$ 归纳得到：
$${\tilde{\pi }}_j=\sum _{k\in S}{\tilde{\pi }}_k{p}_{kj}^{(n)},n=1,2,\cdots$$
两边对 $n$ 取极限得到：
$${\tilde{\pi }}_j=\sum _{k\in S}{\tilde{\pi }}_k\underset{n\to \infty }{\lim }{p}_{kj}^{(n)}=\sum _{k\in S}{\tilde{\pi }}_k{\pi }_j$$
由上面的证明可知 $\sum _{k\in S}{\tilde{\pi }}_k=1$ ，因此 ${\tilde{\pi }}_j={\pi }_j$ ，所以得证平稳分布唯一。

（2）反证法：假设存在一个平稳分布 { π j ,   j ∈ S } \{\pi_j,\,j\in S\} {πj​,j∈S} ，则由（1）中证明得到：
$${\pi }_j=\sum _{k\in S}{\pi }_k{p}_{kj}^{(n)},n=1,2,\cdots$$
$j$ 为非常返或者零常返状态，当 $n\to \infty$ 时，由上一节的 $p_{kj}^{(n)}$ 的极限性质得，$\underset{n\to \infty }{\lim }{p}_{kj}^{(n)}=0$ ，因此 ${\pi }_j=0$ （$\forall j\in S$），但是这个是不可能的，因此对于非常返的或者零常返的 Markov 链，不存在平稳分布。

注意：

• 不可约、非周期的 Markov 链，只要有一个是正常返状态，就全是正常返状态；只要有一个是非常返状态，就全是非常返状态；只要有一个是零常返状态，就全是零常返状态。所有说这个定理的两种情况已经包括了所有的不可约、非周期的 Markov 链；
• ${\pi }_j=\frac{1}{{\mu }_j}$ 是一种简便计算状态的平均回转时间的方法；

下面的例子你可以看到，往往是直接解对应的线性方程组来得到平稳分布。

例：设甲袋中有 $k$ 个白球和 $1$ 个黑球，乙袋中有 $k+1$ 个白球，每次从两袋中任取一球，交换后放入对方的袋中。证明经过 $n$ 次交换后，黑球仍在甲袋中的概率 $p_n$ 满足 $\underset{n\to \infty }{\lim }p=\frac{1}{2}$ ；

解：以 $X_n$ 表示第 $n$ 次取球后甲袋中的黑球数，则 { X n ,   n = 1 ,   2 ,   ⋯   } \{X_n,\,n=1,\,2,\,\cdots\} {Xn​,n=1,2,⋯} 是状态空间为 S = { 0 ,   1 } S=\{0,\,1\} S={0,1} 的时齐 Markov 链，一步转移矩阵为：
$$P=\left[\begin{array}{cc}\frac{k}{k+1}& \frac{1}{k+1}\\ \frac{1}{k+1}& \frac{k}{k+1}\end{array}\right]$$
它的平稳分布满足：
$$\{\begin{array}{l}{\pi }_0=\frac{k}{k+1}{\pi }_0+\frac{1}{k+1}{\pi }_1\\ {\pi }_1=\frac{1}{k+1}{\pi }_0+\frac{k}{k+1}{\pi }_1\end{array}$$
且有规范性条件 ${\pi }_0+{\pi }_1=1$ ，解得 $\pi =({\pi }_0,{\pi }_1)=(\frac{1}{2},\frac{1}{2})$ ，故经过 $n$ 次交换过后，黑球仍在甲袋中的概率为：
$$\underset{n\to \infty }{\lim }{p}_n=\underset{n\to \infty }{\lim }P(X_n=1)={\pi }_1=\frac{1}{2}$$
例：某种商品的销售情况共有连续 24 个季度的数据（其中 1 表示畅销，2 表示滞销）：
$$\begin{array}{cccccccccccccccccccccccc}1& 1& 2& 1& 2& 2& 1& 1& 1& 2& 1& 2& 1& 1& 2& 2& 1& 1& 2& 1& 2& 1& 1& 1\end{array}$$
如果该商品的销售情况近似满足时齐性于 Markov 性：

（1）试确定销售状态的一步转移概率矩阵；

（2）如果现在是畅销，试预测之后的第四个季度的销售状况；

（3）如果影响销售的所有因素不变，试预测长期的销售状况；

解：以 $X_n$ 表示第 $n$ 季度该商品的销售状况，则 { X n ,   n = 1 ,   2 ,   ⋯   } \{X_n,\,n=1,\,2,\,\cdots\} {Xn​,n=1,2,⋯} 为状态空间为 S = { 1 ,   2 } S=\{1,\,2\} S={1,2} 的时齐 Markov 链。

（1）由 $1\to 1$ 有 $7$ 次，$1\to 2$ 有 $7$ 次，故 $p_{11}=p_{12}=\frac{1}{2}$ ；由 $2\to 1$ 有 $7$ 次，$2\to 2$ 有 $2$ 次，故 $p_{21}=\frac{7}{9}$ ，$p_{22}=\frac{2}{9}$ ；一步转移矩阵为：
$$P=\left[\begin{array}{cc}\frac{1}{2}& \frac{1}{2}\\ \frac{7}{9}& \frac{2}{9}\end{array}\right]$$
（2）有：
$$P^{(4)}=P^4=\left[\begin{array}{cc}0.611& 0.389\\ 0.605& 0.395\end{array}\right]$$
如果现在是畅销，则四个季度之后该商品以 0.611 的概率畅销；

（3）由平稳方程 $({\pi }_0,{\pi }_1)=({\pi }_0,{\pi }_1)P$ 和规范性条件 ${\pi }_0+{\pi }_1=1$ 得到：
$$\{\begin{array}{l}{\pi }_0=\frac{1}{2}{\pi }_0+\frac{7}{9}{\pi }_1\\ {\pi }_1=\frac{1}{2}{\pi }_0+\frac{2}{9}{\pi }_1\\ {\pi }_0+{\pi }_1=1\end{array}$$
解得 $\pi =({\pi }_0,{\pi }_1)=(\frac{14}{23},\frac{9}{23})$ ，即长期下去，该商品将以 $\frac{14}{23}$ 的概率畅销。