马尔科夫链

3.1 马氏链的概念

3.1.1 马尔科夫链的定义

定义 随机序列 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 若满足

则称为 马尔科夫链 (M.C., Markov, Chains), 且上述性质称为马尔可夫性或无后效性.

定义 对于 $\mathrm{\forall }i,j\in S$$\forall i, j \in S$, 称 $P\{X_{n+1}=j\mid X_n=i\}\equiv p_{ij}(n)$$P\Bqty{X_{n + 1} = j \mid X_n = i} \equiv p_{ij}(n)$ 为 $n$$n$ 时刻的 一步转移概率. 若还有 $p_{ij}(n)\equiv p_{ij}$$p_{ij}(n) \equiv p_{ij}$, 则称 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 为 齐次马氏链. 记 $\mathit{P}=(p_{ij})$$\bm P = (p_{ij})$ 为一步概率转移矩阵, 简称 转移矩阵 (Transition matrix).

3.1.1 独立随机变量和的序列

当 $i\in \mathbb{N}$$i \in \N$ 时, 令 $a_i\ge 0$$a_i \ge 0$, 其它情况下均为零, 且 ${\displaystyle \sum _{i=0}^{\mathrm{\infty }}{a}_i=1}$$\dsum_{i = 0}^{\infty} a_i = 1$.

设独立同分布随机变量序列 $\{{\rho }_n\in \mathbb{N},n\ge 0\}$$\Bqty{\rho_n \in \N, n \ge 0}$ 满足 $P\{{\rho }_n=i\}=a_i$$P\Bqty{\rho_n = i} = a_i$, 则其为马氏链.

令 $X_0=0$$X_0 = 0$, $X_n={\displaystyle \sum _{k=1}^n{\rho }_k}$$X_n = \knsum \rho_k$, 则 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 也是一马氏链, 且 $p_{ij}=a_{j-i}$$p_{ij} = a_{j - i}$.

3.1.2 直线上的随机游动

1 无限制的随机游动

令 $X_0=0$$X_0 = 0$, 且 $X_n-X_{n-1}$$X_n - X_{n - 1}$ 相互独立, 并满足

则 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 是一个马氏链.

状态的分类见第三节.

2 带吸收壁的随机游动

在无限制的随机游动基础上, 修改条件 $p_{00}=p_{bb}=1$$p_{00} = p_{bb} = 1$, 则为带两个吸收壁 $0$$0$ 和 $b$$b$ 的随机游动, 是一有限状态马氏链.

3 带反射壁的随机游动

在无限制的随机游动基础上, 修改条件 $p_{01}=p_{b,b-1}=1$$p_{01} = p_{b, b - 1} = 1$, 则为带反射壁 $0$$0$ 和 $b$$b$ 的随机游动.

4 艾伦费斯特模型

令 $S=\{-a,-a+1,\cdots ,-1,0,1,\cdots ,a\}$$S = \Bqty{-a, -a + 1, \cdots, -1, 0, 1, \cdots, a}$, 转移概率为

3.1.3 排队模型

1 离散排队系统

设独立同分布随机变量序列 $\{{\xi }_n\in \mathbb{N},n\ge 1\}$$\Bqty{\xi_n \in \N, n \ge 1}$ 表示第 $n$$n$ 个周期到达的顾客数, 服务台每个周期完成一个顾客的服务. 记第 $n$$n$ 周期开始的顾客数为 $X_n$$X_n$, 且 $a^{+}=max\{a,0\}$$a^+ = \max\Bqty{a, 0}$, 则

且 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 是一个马氏链. 设 $P\{{\xi }_n=k\}=a_k\ge 0$$P\Bqty{\xi_n = k} = a_k \ge 0$, ${\displaystyle \sum _{k=0}^{\mathrm{\infty }}{a}_k=1}$$\dsum_{k = 0}^\infty a_k = 1$, 则转移概率为

2 G/M/1 排队系统

只有一个服务员, 顾客到达服务台的时间间隔独立同分布 $G(x)$$G(x)$,

服务时间 $M$$M$ 独立同 $E(\mu )$$E(\mu)$, 且与顾客到达过程独立. 则 $(0,t]$$\pbqty{0, t}$ 内服务完的顾客数服从 $P(\mu )$$P(\mu)$.

记 $X_n$$X_n$ 表示第 $n$$n$ 个顾客到达服务台时系统内的顾客数, $T_n$$T_n$ 表示第 $n$$n$ 个顾客到达时刻, 则 $\{X_n,n\ge 1\}$$\Bqty{X_n, n \ge 1}$ 为马氏链.

令 $A=\{X_n=i,X_{n+1}=i+1-j\}(0\le j\le i)$$A = \Bqty{X_n = i, X_{n + 1} = i + 1 - j}\ (0 \le j \le i)$, 则

服务台由 $i$$i$ 个顾客转为空闲的概率, 则

3.1.4 离散分支过程

设群体某一代的每个个体产生的下一代个体数为相互独立的随机变量 $\xi \in \mathbb{N}$$\xi \in \N$,

且 $P\{\xi =k\}=a_k\ge 0,k\ge 0,{\displaystyle \sum _{k=0}^{\mathrm{\infty }}{a}_k=1}$$P\Bqty{\xi = k} = a_k \ge 0, k \ge 0, \dsum_{k = 0}^\infty a_k = 1$, 记 $X_n$$X_n$ 表示第 $n$$n$ 代个体的数目, 则

于是 $\{X_n,n\ge 1\}$$\Bqty{X_n, n \ge 1}$ 是马氏链, 且

最后一步由母函数得到.

3.1.5 马尔科夫链的检验

定理 3.1.1 设随机过程 $\{X_n,n\ge 0\}$$\Bqty{X_n,n \ge 0}$ 满足

1. 独立同分布随机变量 $\{{\xi }_n,n\ge 1\}$$\Bqty{\xi_n, n \ge 1}$ 与 $X_0$$X_0$ 也独立.

2. $f:S\times S\to S,(X_{n-1},{\xi }_n)\mapsto X_n$$f: S \times S \to S, (X_{n-1}, \xi_n) \mapsto X_n %= f(X_{n - 1}, \xi_n)$.

则 $\{X_n,n\ge 0\}$$\Bqty{X_n,n \ge 0}$ 是马尔科夫链, 且 $p_{ij}=P\{f(i,{\xi }_1)=j\}$$p_{ij} = P\Bqty{f(i, \xi_1) = j}$.

3.2 转移概率矩阵

3.2.1 随机矩阵与初始分布

定义 称矩阵 $\mathit{A}=(a_{ij}{)}_{S\times S}$$\bm A = (a_{ij})_{S \times S}$ 为 随机矩阵, 如果

1. $\mathrm{\forall }i,j\in S:a_{ij}\ge 0$$\forall i, j \in S: a_{ij} \ge 0$,

2. $\mathrm{\forall }i\in S:\sum _{j\in S}{a}_{ij}=1$$\forall i \in S: \sum_{j \in S} a_{ij} = 1$.

定义 定义马氏链的概率分布向量为

并称 $\pi (0)$$\pi(0)$ 为马氏链的初始分布.

备注 马氏链的特性完全由它的一步转移概率矩阵 $P$$P$ 与初始分布向量 $\pi (0)$$\pi(0)$ 决定, 且

定理 3.2.1

3.2.2 CK 方程

定义 称 $p_{ij}^{(m)}=P\{X_{n+m}=j\mid X_n=i\}$$p_{ij}^{(m)} = P\Bqty{X_{n + m} = j \mid X_n = i}$ 为 $m$$m$ 步转移概率, ${\mathit{P}}^{(m)}=(p_{ij}^{(m)})$$\bm P^{(m)} = (p_{ij}^{(m)})$ 为 $m$$m$ 步转移概率矩阵. 约定 $p_{ii}^{(0)}=0$$p_{ii}^{(0)} = 0$.

定理 3.2.2 (Chapman-Kolmogorov 方程)

3.3 状态的分类

3.3.1 状态相关定义

定义

• 吸收

  • 若 $p_{ii}=1$$p_{ii} = 1$, 则称状态 $i\in S$$i \in S$ 为 吸收态 (absorbing), 其集合记为 $A$$A$.

  • 若 $p_{ii}<1$$p_{ii} < 1$, 则称状态 $i\in S$$i \in S$ 为 过渡态 (transient), 其集合记为 $T$$T$.

• 可达

  • 对 $i,j\in S$$i, j \in S$, 若 $\mathrm{\exists }n\in \mathbb{N}:p_{ij}^{(n)}>0$$\exist n \in \N: p_{ij}^{(n)} > 0$, 则称自状态 $i$$i$ 出发可达状态 $j$$j$, 记为 $i\to j$$i \to j$.

  • 若从状态 $i$$i$ 通过 $n$$n$ 步可达 $j$$j$, 则记为 $i\stackrel{(n)}{\to }j$$i \overset{(n)}{\to} j$.

  • 若 $i\to j$$i \to j$ 且 $j\to i$$j \to i$, 则称 $i,j$$i, j$ 相通, 记为 $i\leftrightarrow j$$i \rla j$.

• 首达

  • 若 $i\to j$$i \to j$, 则定义 首达时间 为

    $$T_{ij}=min\{n:n\ge 1,X_n=j,X_0=i\}.$$

    否则记 $T_{ij}=\mathrm{\infty }$$T_{ij} = \infty$.

  • 定义 首达概率 为

    $$\begin{array}{rl}{f}_{ij}^{(n)}& =P\{T_{ij}=n\mid X_0=i\}\\ & =P\{X_n=j,X_k\ne j,1\le k\le n-1\mid X_0=i\}.\end{array}$$

    约定 $f_{ii}^{(0)}=0,p_{ii}^{(0)}=1$$f_{ii}^{(0)} = 0, p_{ii}^{(0)} = 1$, 并定义有限步首达的概率为 $f_{ij}={\displaystyle \sum _{n=1}^{\mathrm{\infty }}{f}_{ij}^{(n)}}$$f_{ij} = \nsum f_{ij}^{(n)}$.

  • 注意 $f_{ij}$$f_{ij}$ 不是 $f_{ij}^{(1)}$$f_{ij}^{(1)}$.

• 若 $f_{ii}=1$$f_{ii} = 1$,

  • 则称 $i$$i$ 为 常返状态, 否则称为 非常返状态 (或 瞬时状态).

  • 记 ${\mu }_i={\displaystyle \sum _{n=1}^{\mathrm{\infty }}n{f}_{ii}^{(n)}}$$\mu_i = \nsum n f_{ii}^{(n)}$, 若有限, 则称 $i$$i$ 为 正常返态, 否则称为 零常返态.

• 周期

  • 若 $S_{\text{回转时间}}=\{n:n\ge 1,p_{ii}^{(n)}>0\}\ne \varnothing$$S_\text{回转时间} = \Bqty{n : n \ge 1, p_{ii}^{(n)} > 0} \ne \varnothing$, 则称该数集的最大公约数 $d(i)$$d(i)$ 为状态 $i$$i$ 的 周期.

  • 若 $d(i)>1$$d(i) > 1$, 则称 $i$$i$ 是 周期的; 若 $d(i)=1$$d(i) = 1$, 则称 $i$$i$ 为 非周期的.

  • 若状态 $i$$i$ 正常返且非周期, 则称 $i$$i$ 为 遍历状态.

• 备注

  • 若 $S_{\text{回}\text{转}\text{时}\text{间}}\ne \varnothing$$S_{回转时间} \ne \varnothing$, 则其有可数无穷个元素.

  • 若 $n_1,n_2\in S_{\text{回}\text{转}\text{时}\text{间}}$$n_1, n_2 \in S_{回转时间}$, 则 $\mathrm{\forall }k\in {\mathbb{N}}^{+}:k{n}_1,n_1+n_2\in S_{\text{回}\text{转}\text{时}\text{间}}$$\forall k \in \N^+ \colon kn_1, n_1 + n_2 \in S_{回转时间}$.

  • $d(i)$$d(i)$ 不一定属于 $S_{\text{回}\text{转}\text{时}\text{间}}$$S_{回转时间}$, 其整数倍亦然.

  • 对于 $\mathrm{\forall }\{a_n\in {\mathbb{N}}^{+},n\in {\mathbb{N}}^{+}\}$$\forall \Bqty{a_n \in \N^+, n \in \N^+}$, 可构造马氏链使得 $S_{\text{回}\text{转}\text{时}\text{间}}$$S_{回转时间}$ 等于 $\left\{a_n\right\}$$\Bqty{a_n}$ 在加法下生成的集合.

MATLAB 马氏链分析工具_matlab asymptotics_leida_wt的博客-CSDN博客

3.3.2 吸收态的性质

定理 3.3.0 设从状态 $i\in S$$i \in S$ 落入吸收态 $k\in A$$k \in A$ 的概率为 $q_{ik}$$q_{ik}$, 则 $q_{ik}$$q_{ik}$ 及其期望 ${\mu }_i$$\mu_i$ 由下列方程组给出 (求和号表示方程的联立)

1. ${\displaystyle \sum _{i\in T}:q_{ik}=p_{ik}+\sum _{j\in T}{p}_{ij}{q}_{jk}}$$\dsum_{i \in T}: q_{i k} = p_{i k} + \sum_{j \in T} p_{i j} q_{jk}$.

2. ${\displaystyle \sum _{i\in T}:{\mu }_i=1+\sum _{j\in T}{p}_{ij}{\mu }_j}$$\dsum_{i \in T}: \mu_i = 1 + \sum_{j \in T} p_{ij} \mu_j$.

证明

3.3.3 可达与首达

定理 3.3.1 对于 $\mathrm{\forall }i,j\in S,n\in {\mathbb{N}}^{+}$$\forall i, j \in S, n \in \N^+$, 有

1. $p_{ij}^{(n)}={\displaystyle \sum _{k=1}^{\mathrm{\infty }}{f}_{ij}^{(k)}{p}_{jj}^{(n-k)}}$$p_{ij}^{(n)} = \ksum f_{ij}^{(k)} p_{jj}^{(n-k)}$.

2. $\begin{array}{c}{f}_{ij}^{(n)}=\{\begin{array}{ll}{\displaystyle \sum _{k\ne j}{f}_{kj}^{(n-1)}{p}_{ik},}& n>1\\ p_{ij},& n=1.\end{array}\end{array}$$f_{ij}^{(n)} = \begin{cases} \dsum_{k \ne j} f_{kj}^{(n-1)} p_{ik}, & n > 1 \\ p_{ij}, & n = 1. \end{cases} % \dsum_{k \ne j} f_{kj}^{(n-1)} p_{ik} I_\Bqty{n > 1} + p_{ij} I_\Bqty{n = 1}$

3. $i\to j\iff f_{ij}>0$$i \to j \RLA f_{ij} > 0$.

引理 1 记 $\left\{p_{ii}^{(n)}\right\}$$\Bqty{p_{ii}^{(n)}}$ 和 $\left\{f_{ii}^{(n)}\right\}$$\Bqty{f_{ii}^{(n)}}$ 的母函数分别为 $P(\rho )={\displaystyle \sum _{n=0}^{\mathrm{\infty }}{p}_{ii}^{(n)}{\rho }^n}$$P(\rho) = \nosum p_{ii}^{(n)} \rho^n$ 和 $F(\rho )={\displaystyle \sum _{n=0}^{\mathrm{\infty }}{f}_{ii}^{(n)}{\rho }^n}$$F(\rho) = \nosum f_{ii}^{(n)} \rho^n$, 则

3.3.4 常返与非常返

定理 3.3.2

1. 状态 $i$$i$ 为常返态, 当且仅当 ${\displaystyle \sum _{n=0}^{\mathrm{\infty }}{p}_{ii}^{(n)}=\mathrm{\infty }}$$\nosum p_{ii}^{(n)} = \infty$.

2. 状态 $i$$i$ 为非常返态, 当且仅当 ${\displaystyle \sum _{n=0}^{\mathrm{\infty }}{p}_{ii}^{(n)}={\displaystyle \frac{1}{1-f_{ii}}}<\mathrm{\infty }}$$\nosum p_{ii}^{(n)} = \dfrac{1}{ 1 - f_{ii} } < \infty$.

备注 令 $S(i)={\displaystyle \sum _{n=0}^{\mathrm{\infty }}{I}_{\{X_n=i\}}}$$S(i) = \nosum I_\Bqty{X_n = i}$ 表示马氏链到达 $i$$i$ 的次数, 于是 $E[S(i)\mid X_0=i]={\displaystyle \sum _{n=0}^{\mathrm{\infty }}{p}_{ii}^{(n)}}$$E\bqty{S(i) \mid X_0 = i} = \nosum p_{ii}^{(n)}$.

推论 1 若 $j$$j$ 非常返, 则对于 $\mathrm{\forall }i\in S$$\forall i \in S$,

1. ${\displaystyle \sum _{n=1}^{\mathrm{\infty }}{p}_{ij}^{(n)}<\mathrm{\infty }}$$\nsum p_{ij}^{(n)} < \infty$.

2. $\underset{n\to \mathrm{\infty }}{lim}{p}_{ij}^{(n)}=0$$\nlim p_{ij}^{(n)} = 0$.

推论 2 若 $j$$j$ 为常返态, 则

1. 当 $i\to j$$i \to j$ 时, ${\displaystyle \sum _{n=1}^{\mathrm{\infty }}{p}_{ij}^{(n)}=\mathrm{\infty }}$$\nsum p_{ij}^{(n)} = \infty$.

2. 当 $i\nrightarrow j$$i \not\to j$ 时, ${\displaystyle \sum _{n=1}^{\mathrm{\infty }}{p}_{ij}^{(n)}=0}$$\nsum p_{ij}^{(n)} = 0$.

3.3.5 无穷多次到达

定理 3.3.3 记

则

定理 3.3.4 由定理 3.3.3 即得:

1. 状态 $i$$i$ 常返 $\iff g_{ii}=1$$\RLA g_{ii} = 1$.

2. 状态 $i$$i$ 非常返 $\iff g_{ii}=0$$\LRA g_{ii} = 0$.

备注

• 若 $i$$i$ 常返, 则几乎所有样本轨道无穷多次回到 $i$$i$.

• 若 $i$$i$ 非常返, 则几乎所有样本轨道有限次回到 $i$$i$.

3.3.6 平均到达时间

引理 设正项级数 $A(z)={\displaystyle \sum _{n=0}^{\mathrm{\infty }}{a}_n{z}^n}$$A(z) = \nosum a_n z^n$ 在 $[0,1)$$\bpqty{0, 1}$ 收敛, 则

备注 该引理为实分析中的结果, 由 Hardy 与 Littlewood 给出.

定理 3.3.5 设 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 是一常返的马氏链, 即状态空间 $S$$S$ 是单一的常返类, 则对于 $\mathrm{\forall }i,j\in S$$\forall i, j \in S$, 有

方法 计算平均到达时间, 有如下思路

1. 计算 ${\mu }_{ij}$$\mu_{ij}$ 的分布, 从而求得期望.

2. 计算 $\underset{n\to \mathrm{\infty }}{lim}{\mathit{P}}^{(n)}$$\nlim \bm P^{(n)}$, 从而由定理 3.3.5 和下一节的引理得到.

3. 由递推式, 对于有 $n$$n$ 个元素的状态空间, 列出 $n^2$$n^2$ 个方程的线性方程组.

3.3.7 平均回转时间

引理 若极限 $\underset{n\to \mathrm{\infty }}{lim}{a}_n$$\nlim a_n$ 存在, 则

定理 3.3.6 设 $i$$i$ 常返且周期为 $d$$d$, 则

其中 ${\mu }_i$$\mu_i$ 为 $i$$i$ 的平均回转时间. 当 ${\mu }_i=+\mathrm{\infty }$$\mu_i = +\infty$ 时, 右式理解为 0.

3.3.8 零常返与遍历

定理 3.3.7 设 $i$$i$ 常返, 则

1. $i$$i$ 零常返, 当且仅当 $\underset{n\to \mathrm{\infty }}{lim}{p}_{ii}^{(n)}=0$$\nlim p_{ii}^{(n)} = 0$.

2. $i$$i$ 为遍历, 当且仅当 $\underset{n\to \mathrm{\infty }}{lim}{p}_{ii}^{(n)}={\displaystyle \frac{1}{{\mu }_i}}>0$$\nlim p_{ii}^{(n)} = \dfrac{1}{\mu_i} > 0$.

3.3.9 相通与不可约链

性质 相通关系 '$\leftrightarrow$$\rla$' 为等价关系, 即

1. 自反性: $i\leftrightarrow i$$i \rla i$.

2. 对称性: $i\leftrightarrow j\Rightarrow j\leftrightarrow i$$i \rla j \RA j \rla i$.

3. 传递性: $i\leftrightarrow j\wedge j\leftrightarrow k\Rightarrow i\leftrightarrow k$$i \rla j \and j \rla k \RA i \rla k$.

定义 若一马氏链的所有状态属于同一等价类, 则称它是 不可约链.

定理 3.3.8 若 $i$$i$ 常返, 且 $i\to j$$i \to j$, 则 $j$$j$ 常返, 且 $f_{ji}=1$$f_{ji} = 1$.

定理 3.3.9 若 $i\leftrightarrow j$$i \rla j$, 则

1. $i$$i$ 与 $j$$j$ 同为非常返, 或同为正常返, 或同为零常返.

2. $i$$i$ 与 $j$$j$ 同为非周期, 或有相同的周期.

3.3.10 常返态等价命题

定理 3.3.10 下列命题等价:

1. $i$$i$ 为常返态 (即 $f_{ii}=1$$f_{ii} = 1$).

2. $P\{\bigcup _{n=1}^{\mathrm{\infty }}\{X_n=i\}\mid X_0=i\}=1$$P\Bqty{\ncup\Bqty{X_n = i} \mid X_0 = i} = 1$.

3. $P\{S_1(i)=+\mathrm{\infty }\mid X_0=i\}=1$$P\Bqty{S_1(i) = +\infty \mid X_0 = i} = 1$.

4. ${\displaystyle \sum _{n=1}^{\mathrm{\infty }}{p}_{ii}^{(n)}=+\mathrm{\infty }}$$\nsum p_{ii}^{(n)} = +\infty$.

5. $E\{S_1(i)\mid X_0=i\}=+\mathrm{\infty }$$E\Bqty{S_1(i) \mid X_0 = i} = +\infty$.

马氏链状态分类的总结

3.3.11 直线上随机游动

直线上年无限制的随机游动的定义.

命题 3.3.11 直线上的随机游动构成马氏链, 并且是周期为 2 的不可约链. 该马氏链中 $\mathbb{Z}$$\Z$ 构成一个等价类, 当 $p={\displaystyle \frac{1}{2}}$$p = \dfrac{1}{2}$ 时为常返类, 否则为非常返类.

3.3.12 高维的随机游动

定义 令 $X_0=(0,0)$$X_0 = (0, 0)$, 且 $X_n-X_{n-1}$$X_n - X_{n - 1}$ 相互独立, 并满足

则 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 称为平面上的对称随机游动. 高维对称随机游动类似定义.

命题 3.3.12 高维对称随机游动构成马氏链, 并且是周期为 2 的不可约链.

引理 3.3.13 ${\displaystyle \sum _{k=0}^n{(\genfrac{}{}{0ex}{}{n}{k})}^2=(\genfrac{}{}{0ex}{}{2n}{n})}$$\dsum_{k = 0}^n \binom{n}{k}^2 = \binom{2n}{n}$.

命题 3.3.13 在平面对称随机游动中, ${\mathbb{Z}}^2$$\Z^2$ 构成一个常返类.

定理 3.3.14 (Polya 定理) 在 $d$$d$ 维空间对称随机游动中, ${\mathbb{Z}}^d$$\Z^d$ 构成一个非常返类.

证明

3.4 状态空间的分解

3.4.1 闭集与不可约

定义 若 $\mathrm{\forall }i\in C\subset S,j\notin C:i\nrightarrow j$$\forall i \in C \subset S, j \notin C: i \not\ra j$, 则称 $C$$C$ 是 闭集. 若 $\mathrm{\forall }i,j\in C:i\leftrightarrow j$$\forall i, j \in C: i \rla j$, 则称该闭集 不可约.

引理 $C$$C$ 是闭集的充要条件为, $\mathrm{\forall }i\in C,j\notin C,n\in {\mathbb{N}}^{+}:p_{ij}^{(n)}=0$$\forall i \in C, j \not\in C, n \in \N^+: p_{ij}^{(n)} = 0$.

定理 3.4.1 所有常返状态构成一闭集.

备注 之后用 $C$$C$ 表示所有常返态的闭集, 用 $T$$T$ 表示所有非常返态的集合.

推论 不可约马氏链全为非常返态, 或全为零常返态, 或全为正常返态. (也可以由定理 3.3.9 得到)

3.4.2 常返态的分解

定理 3.4.2 若 $C\ne \varnothing$$C \ne \varnothing$, 则存在不交闭集序列 $\left\{C_n\right\}$$\Bqty{C_n}$, 使得 $C=C_1\cup C_2\cup \cdots$$C = C_1 \cup C_2 \cup \cdots$, 且有

1. $C_n$$C_n$ 中任两状态相通.

2. $C_h\cap C_l=\varnothing ,h\ne l$$C_h \cap C_l = \varnothing, h \ne l$.

其中 $C_n(n\in {\mathbb{N}}^{+})$$C_n\ (n \in \N^+)$ 均为互不相通闭集, 称为基本常返闭集.

推论 状态空间 $S$$S$ 可分解为

其中 $\left\{C_h\right\}$$\Bqty{C_h}$ 为基本常返闭集, $T$$T$ 不一定是闭集.

备注 若系统从某非常返状态出发, 则可能一直在非常返集 $T$$T$ 中运动, 也可能进入某一基本常返闭集 $C_h$$C_h$ 中并一直在其中运动.

定理 3.4.3 若 $S$$S$ 为有限集, 则 $T$$T$ 一定是非闭集.

推论 有限不可约马氏链的状态都是常返的, 即 $T=\varnothing ,S=C$$T = \varnothing, S = C$.

3.4.3 分解概率矩阵

引理 1 设 $C_h\subset S$$C_h \subset S$ 为闭集, 则 $C_h$$C_h$ 上的转移子矩阵 ${\mathit{P}}_n^{(m)}=(p_{ij}^{(m)}),i,j\in C_h$$\bm P_n^{(m)} = (p_{ij}^{(m)}), i, j \in C_h$ 为随机矩阵.

引理 2 若将转移概率矩阵分解为 $S=C_1\cup C_2\cup \cdots \cup C_h\cup T_{h+1}\cup \cdots \cup T_n$$S = C_1 \cup C_2 \cup \cdots \cup C_h \cup T_{h + 1} \cup \cdots \cup T_{n}$, 其中任一等价类中的状态可达且仅可达该等价类或前面的等价类中的状态. 于是, 转移概率矩阵可分解为

定理 3.4.4 若转移概率矩阵按上述形式分解, 则

1. ${\mathit{P}}_l(1\le l\le h)$$\bm P_{l} (1 \le l \le h)$ 是局限在 $C_l$$C_l$ 上的随机矩阵.

2. $\begin{array}{c}{\mathit{P}}^n=\left[\begin{array}{cc}{\mathit{P}}_C^n& \mathbf{0}\\ {\mathit{R}}_n& {\mathit{Q}}_T^n\end{array}\right]\end{array}$$\bm P^n = \begin{bmatrix} \bm P_C^n & \bm 0 \\ \bm R_n & \bm Q_T^n \end{bmatrix}$, 其中 ${\mathit{R}}_1=\mathit{R}$$\bm R_1 = \bm R$, ${\mathit{R}}_n={\mathit{R}}_{n-1}{\mathit{P}}_C+{\mathit{Q}}_T^{n-1}\mathit{R}$$\bm R_n = \bm R_{n-1} \bm P_C + \bm Q_T^{n-1} \bm R$.

3. $\underset{n\to \mathrm{\infty }}{lim}{\mathit{Q}}_T^n=\mathbf{0}$$\nlim \bm Q_T^n = \bm 0$.

3.5 ${\mathit{P}}^n$$\boldsymbol P^n$ 的极限性态与平稳分布

3.5.1 ${\mathit{P}}^n$$\boldsymbol P^n$ 的极限形态

欲求 $\underset{n\to \mathrm{\infty }}{lim}P\{X_n=i\}\equiv \underset{n\to \mathrm{\infty }}{lim}{\pi }_i(n)$$\nlim P\Bqty{X_n = i} \equiv \nlim \pi_i(n)$, 可研究 $\underset{n\to \mathrm{\infty }}{lim}{p}_{ij}^{(n)}$$\nlim p_{ij}^{(n)}$.

1 $j$$j$ 非常返或零常返

定理 3.5.1 若 $j$$j$ 非常返或零常返, 则

推论 1 有限马氏链没有零常返状态, 并且总存在正常返状态.

推论 2 不可约的有限马氏链的状态都是正常返的.

推论 3 若马氏链有一零常返态, 则必有无穷多个零常返态.

2 $j$$j$ 为正常返态

定理 3.5.2 若 $j$$j$ 正常返, 且周期为 $d$$d$, 则对于 $\mathrm{\forall }i\in S,0\le r\le d-1$$\forall i \in S, 0 \le r \le d - 1$, 有

其中 $f_{ij}(r)={\displaystyle \sum _{m=0}^{\mathrm{\infty }}{f}_{ij}^{(md+r)},0\le r\le d-1}$$f_{ij}(r) = \dsum_{m=0}^\infty f_{ij}^{(md + r)}, 0 \le r \le d - 1$.

证明 略.

推论 1 若 $j$$j$ 遍历, 则对 $\mathrm{\forall }i\in S$$\forall i \in S$, 有

推论 2 对于不可约的遍历链 (即所有状态遍历), 对 $\mathrm{\forall }i,j\in S$$\forall i, j \in S$, 有

定理 3.5.3 若 $j$$j$ 常返, 则 $\mathrm{\forall }i\in S$$\forall i \in S$, 有

备注 定理 3.5.2 的推论 1 是定理 3.5.3 的特例.

推论 如不可约马氏链的状态是常返的, 则 $\mathrm{\forall }i,j\in S$$\forall i, j \in S$, 有

定理 3.5.4 若对于不可约的遍历链, $\{{\pi }_i={\displaystyle \frac{1}{{\mu }_i}}\}$$\Bqty{\pi_i = \dfrac{1}{\mu_i}}$ 是方程组

满足条件 $x_j\ge 0,j\in S,\sum _{j\in S}{x}_j=1$$x_j \ge 0, j \in S, \sum_{j \in S} x_j = 1$ 的唯一解.

3.5.2 平稳分布

定义 若定义在 $S$$S$ 上的概率分布 $\mathit{\pi }=\{{\pi }_1,{\pi }_2,\cdots \}$$\bm \pi = \Bqty{\pi_1, \pi_2, \cdots}$ 满足 $\mathit{\pi }=\mathit{\pi }\mathit{P}$$\bm \pi = \bm \pi \bm P$, 即

则称为 马氏链的平稳分布 (或不变概率测度).

备注 对于一个平稳分布, 有 $\mathit{\pi }=\mathit{\pi }{\mathit{P}}^n$$\bm \pi = \bm \pi \bm P^n$.

定理 3.5.5 设 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 是马氏链, 则其为平稳过程的充要条件是 $\mathit{\pi }(0)=\{{\pi }_i(0),i\in S\}$$\bm \pi(0) = \Bqty{\pi_i(0), i \in S}$ 是平稳分布, 即 $\mathit{\pi }(0)=\mathit{\pi }(0)\mathit{P}$$\bm \pi(0) = \bm \pi(0) \bm P$.

定理 3.5.6 不可约遍历链恒有唯一的平稳分布 $\{{\pi }_i={\displaystyle \frac{1}{{\mu }_i}}\}$$\Bqty{\pi_i = \dfrac{1}{\mu_i}}$, 且 ${\pi }_j=\underset{n\to \mathrm{\infty }}{lim}{p}_{ij}^{(n)}$$\pi_j = \nlim p_{ij}^{(n)}$.

定理 3.5.7 令 $C_{+}$$C_+$ 为马氏链中全体正常返态构成的集合, 于是有

1. 不存在平稳分布 $\iff C_{+}=\varnothing$$\RLA C_+ = \varnothing$.

2. 平稳分布唯一存在 $\iff$$\RLA$ 只有一个基本正常返闭集 $C_{+}$$C_+$.

3. 有限状态马氏链的平稳分布总存在.

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

备注 由证明过程可知, 若存在 $n$$n$ 个基本正常返闭集, 则存在 $2^n-1$$2^n - 1$ 个平稳分布.

3.5.3 $\underset{n\to \mathrm{\infty }}{lim}{\pi }_j(n)$$\lim\limits_{n\to\infty} \pi_j(n)$ 的存在性

定义 若 $\mathrm{\forall }j\in S,\underset{n\to \mathrm{\infty }}{lim}{\pi }_j(n)={\pi }_j^{\ast }$$\forall j \in S, \nlim \pi_j(n) = \pi_j^*$ 存在, 则称 ${\mathit{\pi }}^{\ast }=\{{\pi }_1^{\ast },\cdots ,{\pi }_j^{\ast },\cdots \}$$\bm \pi^* = \Bqty{\pi_1^*, \cdots, \pi_j^*, \cdots}$ 为马氏链的 极限分布.

备注 即 $\underset{n\to \mathrm{\infty }}{lim}\mathit{\pi }(0){\mathit{P}}^n={\mathit{\pi }}^{\ast }$$\nlim \bm \pi(0) \bm P^n = \bm \pi^*$, 于是 ${\mathit{\pi }}^{\ast }={\mathit{\pi }}^{\ast }\mathit{P}$$\bm \pi^* = \bm \pi^* \bm P$, 因此极限分布是平稳分布.

定理 3.5.8 非周期不可约链是正常返的充要条件是它存在平稳分布, 且此时平稳分布就是极限分布.

备注 不可约遍历链的极限分布是平稳分布, 且当 $n$$n$ 充分大时,

例 1 设 $\begin{array}{c}S=\{1,2\},\mathit{P}=\left[\begin{array}{cc}\frac{3}{4}& \frac{1}{4}\\ \frac{5}{8}& \frac{3}{8}\end{array}\right]\end{array}$$S = \Bqty{1, 2}, \bm P = \begin{bmatrix} \frac{3}{4} & \frac{1}{4} \\ \frac{5}{8} & \frac{3}{8} \end{bmatrix}$, 求其平稳分布与极限分布 $\underset{n\to \mathrm{\infty }}{lim}{\mathit{P}}^n$$\nlim \bm P^n$.

例 2 设 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 为艾伦费斯特链, 不过 $S=\{0,1,2,\cdots ,2N\}$$S = \Bqty{0, 1, 2, \cdots, 2N}$, 转移概率为

求此链的 ${\pi }_j$$\pi_j$ 与 ${\mu }_j$$\mu_j$.

3.5.4 求和或积分与极限交换

定理 3.5.9 (Levy 单调收敛定理) 设行向量 $\mathit{\pi }$$\bm \pi$ 的分量非负, 若列向量序列

满足 $0\le {\mathit{f}}^{(1)}\le \cdots \le {\mathit{f}}^{(n)}\le \cdots$$0 \le \bm f^{(1)} \le \cdots \le \bm f^{(n)} \le \cdots$, 且 $\underset{n\to \mathrm{\infty }}{lim}{\mathit{f}}^{(n)}=\mathit{f}$$\nlim \bm f^{(n)} = \bm f$, 则 $\mathit{\pi }\mathit{f}=\underset{n\to \mathrm{\infty }}{lim}\mathit{\pi }{\mathit{f}}^{(n)}$$\bm \pi \bm f = \nlim \bm \pi \bm f^{(n)}$, 即

定理 3.5.10 (Fatou 定理) 设行向量 $\mathit{\pi }$$\bm \pi$ 的分量非负, 若列向量序列 $\left\{{\mathit{f}}^{(n)}\right\}$$\Bqty{\bm f^{(n)}}$ 满足

且 $\underset{n\to \mathrm{\infty }}{lim}{\mathit{f}}^{(n)}\equiv \mathit{f}$$\nlim \bm f^{(n)} \equiv \bm f$ 存在, 则

定理 3.5.11 (Lebesgue 控制收敛定理) 设行向量 $\mathit{\pi }$$\bm \pi$ 的分量非负, 若列向量序列 $\{{\mathit{f}}^{(n)}\ge 0\}$$\Bqty{\bm f^{(n)} \ge 0}$ 满足

其中 $c>0$$c > 0$ 为常数, 且 $\underset{n\to \mathrm{\infty }}{lim}{\mathit{f}}^{(n)}\equiv \mathit{f}$$\nlim \bm f^{(n)} \equiv \bm f$ 存在, 则

3.6 离散时间的 Phase-Type 分布

3.6.1 Phase-Type 分布与记号

定义 设 $\{X_n,n\ge 0\}$$\Bqty{X_n, n \ge 0}$ 是马氏链 (M.C.),

1. 状态空间 $\tilde{S}=S\cup S_0$$\wt S = S \cup S_0$, 其中

   1. $S=\{1,2,\cdots ,p\}$$S = \Bqty{1, 2, \cdots, p}$ 为瞬时态集 (非常返态集),

   2. $S_0=0$$S_0 = 0$ 为吸收态 (常返闭集).

2. 一步转移概率矩阵 $\begin{array}{c}\tilde{\mathit{P}}=\left[\begin{array}{cc}\mathit{P}& {\mathit{P}}_0\\ \mathbf{0}& 1\end{array}\right]\end{array}$$\wt{\bm P} = \begin{bmatrix} \bm P & \bm P_0 \\ \bm 0 & 1 \end{bmatrix}$, 其中

   1. $\mathit{P}$$\bm P$ 为瞬时态集的转移矩阵,

   2. ${\mathit{P}}_0=(\mathit{I}-\mathit{P})\mathit{e}$$\bm P_0 = (\bm I - \bm P) \bm e$, 其中

   3. $\mathit{e}=(1,1,\cdots ,1{)}^{\mathrm{T}}$$\bm e = (1, 1, \cdots, 1)\trans$.

3. 记从瞬时态集到吸收态集的首达时间为 $\tau =inf\{n:n>0,X_n\in S_0\}$$\tau = \inf\Bqty{n : n > 0, X_n \in S_0}$.

则称 $\tau$$\tau$ 的分布为 Phase-Type 分布, 简称 PH 分布.

记号

• $\pi (0)=({\alpha }_0,\mathit{\alpha })$$\pi(0) = (\alpha_0, \bm \alpha)$, 其中 $\mathit{\alpha }=({\alpha }_1,\cdots ,{\alpha }_p)$$\bm \alpha = (\alpha_1, \cdots, \alpha_p)$, ${\alpha }_k\ge 0$$\alpha_k \ge 0$, ${\displaystyle \sum _{k\in S}{\alpha }_k=1}$$\dsum_{k \in S} \alpha_k = 1$.

• $g_k=P\{\tau =k\}$$g_k = P\Bqty{\tau = k}$, $g_k(i)=P\{\tau =k\mid X_0=i\}$$g_k(i) = P\Bqty{\tau = k \mid X_0 = i}$, ${\mathit{g}}_k={(g_k(i),i\in S)}^{\mathrm{T}}$$\bm g_k = \pqty{g_k(i), i \in S}\trans$,

• $g(\lambda )=E({\lambda }^{\tau })$$g(\lambda) = E(\lambda^\tau) %= \dsum_{k=0}^\infty g_k \lambda^k$, $g(i,\lambda )=E\{{\lambda }^{\tau }\mid X_0=i\}$$g(i, \lambda) = E\Bqty{\lambda^\tau \mid X_0 = i}$, $\mathit{g}(\lambda )=(g(i,\lambda ),i\in S)$$\bm g(\lambda) = \pqty{g(i, \lambda), i \in S}$.

3.6.2 概率分布及其母函数

引理 若矩阵 $\mathit{Q}$$\bm Q$ 满足 $\underset{n\to \mathrm{\infty }}{lim}{\mathit{Q}}^n=\mathbf{0}$$\nlim \bm Q^n = \bm 0$, 则 $(\mathit{I}-\mathit{Q}{)}^{-1}$$(\bm I - \bm Q)\inv$ 存在, 且

推论 设 $\{S=1,2,\cdots ,m\}$$\Bqty{S = 1, 2, \cdots, m}$ 有限, 令 $p_{ij}^{(0)}=I_{\{i=j\}}$$p_{ij}^{(0)} = I_\Bqty{i = j}$, 定义转移概率母函数 ${\varphi }_{ij}(z)={\displaystyle \sum _{n=0}^{\mathrm{\infty }}{p}_{ij}^{(n)}{z}^n}$$\phi_{ij}(z) = \nosum p_{ij}^{(n)} z^n$, 其中 $\left|z\right|<1$$\vqty{z} < 1$ 且 $i,j\in S$$i, j \in S$, 母函数矩阵 $\mathbf{\Phi }(z)=({\varphi }_{ij}(z))$$\bm \Phi(z) = (\phi_{ij}(z))$, 则

定理 3.6.1

1. $\begin{array}{c}{g}_k=\{\begin{array}{ll}{\alpha }_0,& k=0,\\ \mathit{\alpha }{\mathit{P}}^{k-1}{\mathit{P}}_0,& k\ge 1.\end{array}\end{array}$$g_k = \begin{cases} \alpha_0, & k = 0, \\ \bm \alpha \bm P^{k-1} \bm P_0, & k \ge 1. \end{cases}$

2. $\begin{array}{c}{\mathit{g}}_k=\{\begin{array}{ll}\mathit{e},& k=0,\\ {\mathit{P}}^{k-1}{\mathit{P}}_0,& k\ge 1.\end{array}\end{array}$$\bm g_k = \begin{cases} \bm e, & k = 0, \\ \bm P^{k-1} \bm P_0, & k \ge 1. \end{cases}$

3. $g(\lambda )={\alpha }_0+\lambda \mathit{\alpha }(\mathit{I}-\lambda \mathit{P}{)}^{-1}{\mathit{P}}_0$$g(\lambda) = \alpha_0 + \lambda \bm \alpha (\bm I - \lambda \bm P)\inv \bm P_0$.

4. $\mathit{g}(\lambda )=\mathit{e}+\lambda (\mathit{I}-\lambda \mathit{P}{)}^{-1}{\mathit{P}}_0$$\bm g(\lambda) = \bm e + \lambda (\bm I - \lambda \bm P)\inv \bm P_0$.

3.6.3 PH 分布的反问题

定理 3.6.2 记 $\mathit{B}(k,p)=({\mathit{g}}_k,{\mathit{g}}_{k+1},\cdots ,{\mathit{g}}_{k+p-1})$$\bm B(k, p) = (\bm g_k, \bm g_{k+1}, \cdots, \bm g_{k+p-1})$ 为 $p\times p$$p \cp p$ 矩阵, 称之为该马氏链首达时间 $\tau$$\tau$ 的条件分布向量矩阵, 则