《随机过程》第二章-马尔科夫链（Markov chain）

状态空间 \ 时间参数	离散 (D)	连续 (C)
离散 (D)	马氏链	连续时间马氏链
连续 (C)	-	布朗运动（金融数学）

定义和例子

定义

考虑一个离散时间的随机过程 $X_n\ (n=0,1,2,\ldots)$，$X_n$ 在有限集合内取值。我们称 $X_n$ 的所有可能取值为系统的状态（state）。

定义转移概率（transition probability），其表达式如下：

$$p_{n+1}(i,j)=\mathbb{P}\!\left(X_{n+1}=j \mid X_n=i,\ X_{n-1}=i_{n-1},\ X_{n-2}=i_{n-2},\ \ldots,\ X_0=i_0\right).$$

（时间轴：$\cdots\ X_{n-2}\ \ X_{n-1}\ \ X_n\ \ X_{n+1}\ \ X_{n+2}\ \cdots$，对应“过去—现在—将来”）

如果$p_{n+1}(i,j)=\mathbb{P}(X_{n+1}=j\mid X_n=i)$,称这个过程具有马氏性（Markov property），即：$X_{n+1}$ 只与 $X_n$ 有关，而与之前的状态 $(X_{n-1},\ldots,X_0)$ 无关。

如果时刻 $n$ 的取值与转移概率无关，即

$$\mathbb{P}(X_{n+1}=j\mid X_n=i)=p(i,j),\qquad \forall n,$$

则称为时齐性（time-homogeneous），相应的马氏链称作时齐马氏链。

后面的讨论默认马氏性和时齐性成立

例 1：赌徒破产问题

赌徒在一次赌博中，赢得 $1$ 美元的概率是 $0.4$；输掉 $1$ 美元的概率是 $0.6$。赌徒退出赌博的条件为：输光（财富为 $0$），或者财富数额达到 $N$ 美元。

假设随机变量 $X_n$ 表示赌徒在第 $n$ 次赌博后的财富数量。可见 $X_{n+1}$ 只与 $X_n$ 有关，而与之前的状态 $(X_{n-1},\ldots,X_0)$ 无关，$X_n$ 具有马氏性（Markov property），即：

$$\mathbb{P}\!\left( X_{n+1}=j \mid X_n=i,\ X_{n-1}=i_{n-1},\ X_{n-2}=i_{n-2},\ldots,\ X_0=i_0 \right)$$ $$= \mathbb{P}(X_{n+1}=j\mid X_n=i) = p(i,j).$$

马氏性的另一类表述：已知“现在” $X_n$ 的条件下，“将来” $X_{n+1}$ 与“过去” $(X_{n-1},\ldots,X_1,X_0)$ 无关的特性。

$p(i,j)$ 就是转移概率，其满足

$$p(i,j)=\mathbb{P}(X_{n+1}=j\mid X_n=i).$$

赌徒第 $(n+1)$ 次赌博，输钱的条件概率分别为：

$$p(i,i-1)=\mathbb{P}(X_{n+1}=i-1\mid X_n=i)=0.6,\quad \text{输}$$ $$p(i,i+1)=\mathbb{P}(X_{n+1}=i+1\mid X_n=i)=0.4,\quad \text{赢}$$

该问题中的转移概率取值分别为：

$$p(i,i+1)=0.4,\qquad p(i,i-1)=0.6,\qquad 0<i<N,$$ $$p(0,0)=1,\qquad p(N,N)=1,\qquad \text{此时赌博停止}.$$

$p(i,j)$ 的相应数值，可以标注在矩阵 $P$ 的第 $i$ 行、第 $j$ 列。这个矩阵称为转移矩阵（transition matrix）：

$$P= \begin{pmatrix} p(0,0) & p(0,1) & \cdots & p(0,N)\\ p(1,0) & p(1,1) & \cdots & p(1,N)\\ \vdots & \vdots & \ddots & \vdots\\ p(N,0) & p(N,1) & \cdots & p(N,N) \end{pmatrix}.$$

当 $N=5$ 时，转移矩阵如下（列标为 $0,1,2,3,4,5$）：

$$P= \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0.6 & 0 & 0.4 & 0 & 0 & 0 \\ 0 & 0.6 & 0 & 0.4 & 0 & 0 \\ 0 & 0 & 0.6 & 0 & 0.4 & 0 \\ 0 & 0 & 0 & 0.6 & 0 & 0.4 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}.$$

从图形上看，赌徒破产问题相当于一维带有吸收壁垒的随机游动（random walk with absorbing boundary）。

注意到：$p(0,0)=1$，$p(5,5)=1$。赌徒破产问题中的状态 $0$ 和状态 $5$ 均称为吸收态（absorbing state）。

例 2：埃伦费斯特链（Ehrenfest Chain）

总共有 $N$ 个球，且只可能在 $A$ 或 $B$ 盒中。每次随机地从任一盒中取球一枚，并投入另一盒中。

假设 $n$ 时刻 $A$ 盒中有 $i$ 个球，则：

• $(n+1)$ 时刻 $A$ 盒中有 $(i+1)$ 个球的概率是 $\dfrac{N-i}{N}$；
• $(n+1)$ 时刻 $A$ 盒中有 $(i-1)$ 个球的概率是 $\dfrac{i}{N}$。

即：

$$p(i,i+1)=\frac{N-i}{N},\qquad p(i,i-1)=\frac{i}{N},\qquad 1\le i\le N-1.$$

另外：

$$p(0,1)=1,\qquad p(N,N-1)=1.$$

当 $N=4$ 时，转移矩阵如下（列标为 $0,1,2,3,4$）：

$$P= \begin{pmatrix} 0 & 1 & 0 & 0 & 0\\ 0.25 & 0 & 0.75 & 0 & 0\\ 0 & 0.5 & 0 & 0.5 & 0\\ 0 & 0 & 0.75 & 0 & 0.25\\ 0 & 0 & 0 & 1 & 0 \end{pmatrix}.$$

马氏链的性质

• $p(i,j)\ge 0$，转移概率非负；
• $\sum_{j} p(i,j)=1$，转移矩阵每行元素之和均为 $1$。

例 3：Inventory Chain（库存链）

假设有一个电子产品店，若一天结束时，某款游戏的库存量为 1 或 0 时，他们需要订购足够些单位的商品，以使得第二天开始的库存总量为 5。假设第二天需求数量 $k$ 及对应的概率如下：

$k$	0	1	2	3
$p$	0.3	0.4	0.2	0.1

求库存链的转移矩阵。

令 $X_n$ 表示第 $n$ 天结束时的库存量（状态），则状态空间

$$\Omega=\{0,1,2,3,4,5\}.$$

第二天需求量 $K\in\{0,1,2,3\}$ 的分布为：

$k$	0	1	2	3
$\mathbb{P}(K=k)$	0.3	0.4	0.2	0.1

补货规则：若一天结束时库存为 $0$ 或 $1$，则补货使得第二天开始库存为 $5$；否则不补货。

因此可写成（第二天结束库存）：

$$X_{n+1}=\max(S_{n+1}-K,0),\quad S_{n+1}= \begin{cases} 5, & X_n\in\{0,1\},\\ X_n, & X_n\in\{2,3,4,5\}. \end{cases}$$

于是转移概率 $p(i,j)=\mathbb{P}(X_{n+1}=j\mid X_n=i)$ 组成的转移矩阵 $P$（行/列按 $0,1,2,3,4,5$ 排列）为：

$$P= \begin{pmatrix} 0 & 0 & 0.1 & 0.2 & 0.4 & 0.3\\ 0 & 0 & 0.1 & 0.2 & 0.4 & 0.3\\ 0.3 & 0.4 & 0.3 & 0 & 0 & 0\\ 0.1 & 0.2 & 0.4 & 0.3 & 0 & 0\\ 0 & 0.1 & 0.2 & 0.4 & 0.3 & 0\\ 0 & 0 & 0.1 & 0.2 & 0.4 & 0.3 \end{pmatrix}.$$

例 4：Repair Chain（修复链）

一台机器有三个关键零件，机器只要其中两个能工作就能正常运行；当有两个零件故障时，机器停止并被迅速修复。设状态空间为

$$S=\{0,1,2,3,12,13,23\},$$

其中 $0$ 表示无故障；$1,2,3$ 表示对应零件单独故障；$12,13,23$ 表示对应两件故障（此时进入修复，下一步回到 $0$）。 当机器处于可运行状态时（$0,1,2,3$），一天内只有一个零件会坏，且

$$\mathbb{P}(\text{1坏})=0.01,\quad \mathbb{P}(\text{2坏})=0.02,\quad \mathbb{P}(\text{3坏})=0.04.$$

按状态顺序 $(0,1,2,3,12,13,23)$，转移矩阵为

$$P= \begin{pmatrix} 0.93 & 0.01 & 0.02 & 0.04 & 0 & 0 & 0\\ 0 & 0.94 & 0 & 0 & 0.02 & 0.04 & 0\\ 0 & 0 & 0.95 & 0 & 0.01 & 0 & 0.04\\ 0 & 0 & 0 & 0.97 & 0 & 0.01 & 0.02\\ 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}.$$

例 5：Two-steps Chain（两阶段马氏链）

设状态为“最近两次投篮结果”，状态空间

$$S=\{HH,\ HM,\ MH,\ MM\}.$$

其中 $H$ 表示投中（Hit），$M$ 表示未投中（Miss）。若最近两次分别为：

• $MM$：下一次投中概率 $1/2$；
• 恰有一次投中（$HM$ 或 $MH$）：下一次投中概率 $2/3$；
• $HH$：下一次投中概率 $3/4$。

按状态顺序 $(HH,HM,MH,MM)$，转移矩阵为

$$P= \begin{pmatrix} \frac{3}{4} & \frac{1}{4} & 0 & 0\\ 0 & 0 & \frac{2}{3} & \frac{1}{3}\\ \frac{2}{3} & \frac{1}{3} & 0 & 0\\ 0 & 0 & \frac{1}{2} & \frac{1}{2} \end{pmatrix}.$$

多步转移概率

$p(i,j)=\mathbb{P}(X_{n+1}=j\mid X_n=i)$ 给出了从状态 $i$ 到 $j$ 的一步转移概率；类似地，从 $i$ 到 $j$ 的 $m$ 步（$m>1$）转移概率定义为：

$$p^{m}(i,j)=\mathbb{P}(X_{n+m}=j\mid X_n=i).$$

这里的 $p^{m}(i,j)$ 是 $m$ 步转移矩阵 $P^{m}$ 第 $i$ 行、第 $j$ 列的数值。

定理

$m$ 步转移矩阵是 1 步转移矩阵 $P$ 的 $m$ 次幂，即 $P^{m}$。

C-K 方程（Chapman–Kolmogorov 方程）

$$p^{m+n}(i,j)=\mathbb{P}(X_{m+n}=j\mid X_0=i)=\sum_{k} p^{m}(i,k)\cdot p^{n}(k,j).$$

可见：

$$p^{2}(i,j)=\mathbb{P}(X_2=j\mid X_0=i)=\sum_{k=1}^{n} p(i,k)\cdot p(k,j),$$

可看作 C-K 方程的特例。

由 C-K 方程，还能得到如下不等式：

$$p^{m+n}(i,j)\ge p^{m}(i,k)\cdot p^{n}(k,j),\qquad \forall k.$$

$n$ 期赌徒破产问题（$N=5$）

一步转移矩阵：

$$P= \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0\\ 0.6 & 0 & 0.4 & 0 & 0 & 0\\ 0 & 0.6 & 0 & 0.4 & 0 & 0\\ 0 & 0 & 0.6 & 0 & 0.4 & 0\\ 0 & 0 & 0 & 0.6 & 0 & 0.4\\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}.$$

两步转移矩阵：

$$P^{2}= \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0\\ 0.6 & 0.24 & 0 & 0.16 & 0 & 0\\ 0.36& 0 & 0.48 & 0 & 0.16 & 0\\ 0 & 0.36 & 0 & 0.48 & 0 & 0.16\\ 0 & 0 & 0.36 & 0 & 0.24 & 0.40\\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}.$$

当 $n\to\infty$ 时，

$$\lim_{n\to\infty}P^n= \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0\\ 0.9242 & 0 & 0 & 0 & 0 & 0.0758\\ 0.8104 & 0 & 0 & 0 & 0 & 0.1896\\ 0.6398 & 0 & 0 & 0 & 0 & 0.3602\\ 0.3839 & 0 & 0 & 0 & 0 & 0.6161\\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}.$$

可见，随着赌徒不断进行赌博，其最终的结果只有两个：破产或赢到头。
赌徒在初始时如果只有 $1$ 美元，其破产的概率高达 $92.42\%$；如果有 $4$ 美元，其破产概率也高达 $38.39\%$。

如何求 $P^n$？

• 利用软件直接计算（比如：Matlab、Octave、Python 等等）。
• 做矩阵相乘的相关计算（适用于 $2\times2$、$3\times3$ 这样维数较低的情形，且 $n$ 不能太大）。
• 利用矩阵的相似变换进行求解（使用特征值、特征向量来求解）。

矩阵的相似变换求 $P^n$

将矩阵 $P$ 进行如下相似变换：

$$P_{(k\times k)} = Q_{(k\times k)}\,\Lambda Q_{(k\times k)}^{-1}.$$

其中：$\Lambda$ 是由 $P$ 的 $k$ 个特征值所构成的对角阵，即

$$\Lambda=\mathrm{diag}(\lambda_1,\lambda_2,\ldots,\lambda_k).$$

$Q$ 是由 $P$ 的特征向量所构成的矩阵。因此：

$$P^n = (Q\Lambda Q^{-1})(Q\Lambda Q^{-1})\cdots(Q\Lambda Q^{-1}) =Q\Lambda^n Q^{-1}.$$

状态的分类（Classification of States）

我们研究马氏链，主要是进行两类分析：瞬态分析和稳态分析。

• 瞬态分析是研究在某一固定时刻 $n$，马氏链对应系统的概率特征，即求 $n$ 步转移概率；
• 稳态分析是研究当 $n\to\infty$ 时，马氏链对应系统的概率特征，比如：$\lim_{n\to\infty} p^{(n)}(i,j)$ 是否存在；与状态的关系如何；极限概率能否构成概率分布。

为解决这两类问题，就需要对状态进行分类。

几个重要的标记

• $P_x(A)=\mathbb{P}(A\mid X_0=x)$：初始时刻状态为 $x$ 的条件下，事件 $A$ 发生的概率。

• $T_y=\min\{n:n\ge 1,\ X_n=y\}$：首次返回状态 $y$ 的最短时间。$T_y$ 可看作一个停时（stopping time）。（sup 上确界 / inf 下确界 ）（所以 min 有的时候会写成 inf）

• $\rho_{yy}=P_y(T_y<\infty)$：从初始时刻状态为 $y$ 出发，经过有限步首次返回到状态 $y$ 的概率。（$n \geq 1$）（返回$y$ 次数为$k$的话，概率为$\rho_{yy}^k$）

注意

• 由于当 $n=0$ 时，$\rho_{yy}=1$，因此为避免该情况，我们规定 $n\ge 1$。
• 从直观上不难得出，从初始时刻状态为 $y$ 返回状态 $y$ 的次数为 $k$ 的概率是 $p^{(k)}_{yy}$。

停时的概念

当某事件“在时刻 $n$ 停止”，记 $\{T=n\}$ 为停时（stopping time）。若 $T_y$ 是一个停时（首次返回状态 $y$ 的最短时间），则可以表示为：

$$\{T_y=n\}=\{X_n=y,\ X_{n-1}\ne y,\ldots,\ X_1\ne y\}.$$

结论:马氏性对停时也成立。

强马氏性

设 $T$ 是停时，假定 $T=n,\ X_T=y$，则关于 $X_0,\ldots,X_T$ 的其他信息与未来的概率无关，并且 $X_{T+k}\ (k\ge 0)$ 的行为与初始状态为 $y$ 的马氏链相同，即：

$$\mathbb{P}(X_{T+1}=z\mid X_T=y,\ T=n)=\mathbb{P}(X_1=z\mid X_0=y)=p(y,z),$$ $$\mathbb{P}(X_{T+k}=z\mid X_T=y,\ T=n)=\mathbb{P}(X_k=z\mid X_0=y)=p^{k}(y,z),\qquad k\ge 1.$$

注意：停时 $T$ 是随机的。