Markov Chains: Transition Probabilities, State Classification, and Stationary Distributions

离散时间Markov链

我们再来介绍一类特殊的随机变量序列 他的特点是只有现在的结果影响下次的结果 而之前的结果对下次结果没有影响；这就是马尔可夫链 他同时具有数学上的容易计算的性质以及比较符合现实中随机现象的特性 现在已经被广泛的使用 最近的研究让马尔科夫链在蒙特卡洛方法中起到了重要作用 MCMC方法在很多方面应用广泛 我们从离散开始研究

离散时间马尔可夫链的定义

基本定义

定义 设$X=\{X_n:n\geqslant0\}$是定义在概率空间($\Omega,\widehat{F},\mathbb{P})$上的随机过程，状态空间为可数集合 S, 如果对任意的非负整数 $n\geq0$ 以及$i_0,i_1,...,i_n,i_{n+1}\in S$ 有

\begin{aligned} &P(X_{n+1}=i_{n+1}|X_{0}=i_{0},X_{1}=i_{1},\cdots,\color{}{X_{n}=i_{n}}) \\ &=P(X_{n+1}=i_{n+1}|X_{n}=i_{n}) \end{aligned}

则称这个随机过程为一个离散马尔可夫链时间链

前面这个定义式是对Markov Chain 最本质特征的描述 我们可以称为马氏性或者无记忆性 他的核心意义就是 只有现在的结果影响下次的结果 而之前的结果对下次结果没有影响 表达式中的条件概率

$$P(X_{n+1}=i_{n+1}|X_{n}=i_{n})$$

称为从状态$i_{n}$到状态$i_{n+1}$的一步转移概率 记为$p_{i_{n}i_{n+1}}(n)$ 另外定义：

$$p_{ij}^{(k)}(n)\stackrel{{def}}{=}{P}(X_{n+k}=j\mid X_{n}=i)$$

表示从某个状态$i$出发 经历$k$次转移到达$j$的概率 称为$n$时刻的$k$次转移概率 能看出 一次转移概率是$k$次转移概率的特殊情况 我们约定$k$次转移概率矩阵形式如下

$$\left.\mathbf{P}^{(k)}\left(n\right)=\left(\begin{matrix}{p}_{ij}^{(k)}\left(n\right)\\\end{matrix}\right.\right)$$ $k=1$的时候 一步转移概率矩阵为 $$\mathbf{P}^{(1)}(n)=(p_{ij}^{(1)}(n))$$

简记为 \color{}{\mathbf{P}(n)=(p_{ij}(n))} 对于$k=0$的情况 我们约定

$$\left.p_{ij}^{(0)}(n)=\delta_{ij}=\left\{\begin{matrix}{1,}&{i=j}\\{0,}&{i\neq j}\\\end{matrix}\right.\right.\quad(i,j\in S)$$

此时转移概率矩阵是单位矩阵 不难验证 转移概率矩阵是随机矩阵 即

$$p_{ij}^{(k)}\left(n\right)\geqslant0,\quad\sum_{j\in S}p_{ij}^{\left(k\right)}\left(n\right)=1$$

齐次马尔可夫链

在实际的应用中 我们会见到马氏链一个更加特殊的性质：一步转移概率与时刻$n$无关 也就是$$p_{ij}\left(n\right)=p_{ij}\left(n+1\right)=p_{ij}\left(n+2\right)=\cdots$$此时我们称马氏链具有时齐性 或者称为齐次马氏链 后面我们研究马氏链往往要求是齐次的，如果对于每个时间都用不同的转移概率矩阵，问题就有点复杂了 一步转移概率有一种直观的表示方法：状态状体图；就是把所有的状态都写出来，然后依次画出每个状态转移到另一个状态的一步转移概率就好了

例子

我们举出一些马尔可夫链的例子和研究如何验证一个随机过程是马尔可夫链

无限制随机游动

对于质点的无限制随机游动问题 如果$p$的概率加一 $q$的概率减一 能从定义分析出一步转移概率为

$$p_{ij}=\begin{cases}p,&\text{i=0,±1,±2,...,}j=i+1\\q,&\text{i=0,±1,±2,...,}j=i-1\\0,&|i-j|>1\end{cases}$$

简单理解一下我们是怎么写出来的 从$i$状态一步转移到$j$状态的条件是两者得相邻 一侧是$p$ 另一侧是$q$ 如果不相邻 那概率就是0 这当然满足马氏性（从直观的理解上） 我们用定义也可以做到验证 我们尝试用定义验证他的马氏性 还是从变换的机理出发 把$X_n$变为一系列随机变量序列的和（里面的随机变量是广义的伯努利分布）

$$\mathbf{X}_{n}=\xi_{0}+\xi_{1}+\cdots+\xi_{n}$$

所以有

\begin{gathered} P(X_{n+1}=i_{n+1}\big|X_{0}=i_{0},X_{1}=i_{1},\cdots,\color{}{X_{n}=i_{n}}\big) \\ =\frac{P(X_{0}=i_{0},X_{1}=i_{1},\cdots,X_{n}=i_{n},X_{n+1}=i_{n+1})}{P(X_{0}=i_{0},X_{1}=i_{1},\cdots,X_{n}=i_{n})} \\ =\frac{P(\xi_{0}=i_{0},\xi_{1}=i_{1}-i_{0},\cdots,\xi_{n+1}=i_{n+1}-i_{n})}{P(\xi_{0}=i_{0},\xi_{1}=i_{1}-i_{0},\cdots,\xi_{n}=i_{n}-i_{n-1})} \end{gathered}

根据独立性化简有

$$=P(\xi_{n+1}=i_{n+1}-i_{n})$$

也就是

$$\begin{aligned}=\begin{cases}p,&i_{n+1}-i_n=1\\1-p,&i_{n+1}-i_n=-1\\0,&\text{其它}\end{cases}\\\end{aligned}$$ $$=P(X_{n+1}=i_{n+1}|X_n=i_n)$$

所以从定义也可以验证马氏性 其他的验证马氏性的问题也从这里类似的思路出发

有限制随机游动

设质点在直线上的${0，1，···，a}$各点上作随机游动，移动规则如下

• 除了$0$和$a$上的游动 $p$右移 $q$左移 $r$不变
• 在$0$处移动$r_{0}$ 不变 $p_0$ 右移
• 在$1$处移动$r_{a}$ 不变 $p_a$ 左移 我们的规则对时间$n$没有限制 所有也是齐次马氏链 一步转移概率矩阵为

$$\mathbf{P}=\begin{bmatrix}r_0&p_0&0&0&\cdots&0&0&0\\q&r&p&0&\cdots&0&0&0\\0&q&r&p&\cdots&0&0&0\\\vdots&\vdots&\vdots&\vdots&\cdots&\vdots&\vdots&\vdots\\0&0&0&0&\cdots&q&r&p\\0&0&0&0&\cdots&0&q_a&r_a\end{bmatrix}$$

群体增长

群体增长 设某种生物群体的每个个体在其生存期内彼此独立的产生后代，假设每个个体都以概率$p_k$产生$k$个后代，且有

$$p_k\geq0,\sum_kp_k=1$$

用$X_n$表示第$n$代生物群体总数 他也是一个马氏链 想要研究一步转移概率需要让我们知道每个生物的后代数 所以 定义$i$个个体的后代数为随机变量 有概率分布

$$P(\xi_{l}=k)=p_{k}$$

自然的从定义计算一步转移概率

$$\begin{aligned}p_{ij}&=P(X_{n+1}=j\big|X_{n}=i\big)\\&=P(\xi_{1}+\xi_{2}+\cdots+\xi_{i}=j\big)\end{aligned}$$

齐次性是可以自然看出的 我们这两个例子一个从最自然的感觉出发，一个从变化的机理出发，最后都得到了一步转移概率矩阵

马尔可夫链的概率分布

Chapman-kolmogorov方程(C-K方程)

设$X=\{X_{n},n\ge 0\}$是状态空间S上的马氏链，则有

$$p_{ij}^{(k+m)}(n)=\sum_{l\in S}p_{il}^{(k)}(n)p_{lj}^{(m)}(n+k),n,m,k\geq0,i,j\in S$$

或者矩阵形式

$$\mathbf{P}^{(k+m)}(n)=\mathbf{P}^{(k)}(n)\mathbf{P}^{(m)}(n+k)$$

这个方程的结论告诉我们 马尔可夫链的$k$步转移概率由其一步转移概率所完全确定 如果他是齐次马氏链 我们只需要取$m=1$ 就可以用一步转移和$k$步转移导出$k+1$步转移 如果再取$k=1$ 就可以导出各种转移概率分布 直观解释 系统$n$时从状态$i$出发,经$k+m$步转移,于$n+k+m$时到达状态$j$,可以看作 系统$n$时从状态$i$出发，先经$k$步转移，于$n+k$时到达某 中间状态$l$,再在$n+k$时从该中间状态$l$出发又经$m$步转移，于$n+k+m$时到达状态$j$，而中间状态l要取遍整个状态空间$S$ 注意矩阵表示，可以直接用矩阵乘积计算多步转移概率矩阵，齐次更好算

初始分布与绝对分布

初始分布

马氏链$X={X_n}$的状态空间为$S$ 记 $q_j^{(0)}=P(X_0=j)$, $j\in S$ 则称概率分布 $\{q_j^{(0)}:j\in S\}$ 为马氏链X的初始分布 称向量

$$\mathbf{q}^{(0)}=(q_1^{(0)},q_2^{(0)},\cdots q_j^{(0)},\cdots)$$

为马尔可夫链的初始分布向量 初始分布研究的是 我们不进行任何转移 最初的时间 各个状态的概率

绝对分布

马氏链$X=\{X_n\}$ 的状态空间为$S$ 记 $q_{j}^{(n)}=\mathbf{P}(X_{n}=j)$, 则称概率分布 $\{q_j^{(n)}:j\in S\}$ 为马氏链X的绝对分布 称向量

$$\mathbf{q}^{(n)}=(q_1^{(n)},q_2^{(n)},\cdots q_j^{(n)},\cdots)$$

为马尔可夫链的绝对分布向量 绝对分布研究的是 经过不断的转移后 在某个时间 最后各个状态的概率

两者的联系

齐次马尔可夫链$X$的绝对分布由其初始分布和一步转移概率完全确定 概率形式为

$$q_j^{(n)}=\sum_{i\in S}q_i^{(0)}p_{ij}^{(n)}(0)$$

矩阵形式为

$${q}^{(n)}={q}^{(0)}{P}^{(n)}(0)$$

齐次马氏链可以去掉0 我们用CK方程从一步转移得到多步转移；现在用这个定理能从初始分布导出任意时间的绝对分布

有限维分布

马尔可夫链$X$的有限维分布由其初始分布和一步转移概率所完全确定 我们给出公式有

$$P\{X_{t_1}=i_1,X_{t_2}=i_2,\cdots,X_{t_n}=i_n\}$$ $$=\sum_{i\in S}q_i^{(0)}\cdot p_{ii_1}^{(t_1)}(0)\cdot p_{ii_2}^{(t_2-t_1)}(t_1)\cdots p_{i_{n-1}i_n}^{(t_n-t_{n-1})}(t_{n-1}).$$

这一节的所有例子要处理的方法都一样；无论是什么问题，都会转化为求$k$步转移概率矩阵和初始分布求绝对分布的问题；搞明白问题变形就好了

马尔可夫链状态的分类

状态类型定义

研究自己到自己 定义：

$$f_{ij}^{(n)}=P\{X_n=j,X_k\neq j,k=1,2,\cdots,n-1|X_0=i\}$$

为$0$时刻从状态$i$出发 $n$步转移后首次到达$j$的概率 称为首达概率

$$f_{ij}^{(+\infty)}=P\{X_{n}\neq j,n=1,2,\cdots|X_{0}=i\}$$

为$0$时刻从状态$i$出发 永远不能到达$j$的概率

$$f_{ij}=\sum_{n=1}^{\infty}f_{ij}^{(n)}$$

为$0$时刻从状态$i$出发 经过有限步转移后终究到达状态$j$的概率 称为迟早概率 特别的 $i=j$ 的时候

$f_{ii}$ 为$0$时刻从状态$i$出发 经过有限步转移后终究返回$i$的概率

定义：

• 若$f_{ii}=1$ 则称状态i是常返的
• 若$f_{ii}<1$ 则称状态i是非常返的 滑过状态 如果一个状态是常返的 那么有$\begin{aligned}f_{ii}=\sum_{n=1}^{\infty}f_{ii}^{(n)}=1\end{aligned}$ 也就是这是一个概率分布则

$$\mu_{ii}=\sum_{n=1}^{\infty}n\cdot f_{ii}^{(n)}$$

称为返回的平均时间 如果一个状态是常返的 若

• $\mu_{ii}<\infty$ 则称是正常返的
• $\mu_{ii}=\infty$ 则称是零常返的 想要研究常返的问题还是只能从定义入手

记GCD函数求集合的最大公约数 记

$$d_i=\mathrm{GCD}\{n|n\geq1,p_{ii}^{(n)}>0\}$$

如果$d_i>1$ 称为周期状态 周期为$d_i$ 如果 $d_i=1$ 称为非周期状态 如果状态$i$是正常返非周期的，则称为遍历状态；如果是正常返周期态，称为周期态 周期是针对常返的概念，非常返不研究周期

状态类型判断

定理：对于马氏链

• $i$是常返的$(f_{ii}=1)$充要条件为 $\sum_{n=1}^{\infty}p_{ii}^{(n)}=+\infty$
• $i$是非常返的$(f_{ii}<1)$充要条件为 $\sum_{n=1}^{\infty}p_{ii}^{(n)}<+\infty$ 这个定理让我们能从$n$步转移概率入手确定常返态 这个转移概率能靠CK方程计算

定理：设状态$i$是常返的，则

• $i$是零常返的充要条件是$\lim_{n\to\infty}p_{ii}^n=0$
• $i$是遍历态的充要条件是$\lim_{n\to\infty}p_{ii}^n=\frac{1}{\mu_{ii}}>0$
• $i$是正常返周期态的充要条件是$\lim_{n\to\infty}p_{ii}^n$ 不存在

推论： 如果$j$是 非常返状或零常返态则对任意的状态$i$ 有

$$\lim_{n\to\infty}p_{ij}^{(n)}=0$$

推论：对于非周期态问题

• 如果存在$n$ 让$p_{ii}^{(n)}>0,p_{ii}^{(n+1)}>0$ 则$i$非周期
• 如果存在正整数$m$ 状态$j$ 让 $p_{\mathrm{ij}}^{(\mathrm{m})}>0$则$j$非周期

状态之间的关系

研究两个状态互相 定义： 如果存在$n\ge 1$ 让 $p_{ij}^{(n)}>0$ 则称状态i可达状态j 记为 $i\rightarrow j$ 如果两个状态互相可达 就称为两个状态互通 容易验证

• 可达具有传递性
• 互通具有传递性
• 互通具有对称性 定理：
• $i\rightarrow j\Leftrightarrow f_{ij}>0$
• 如果i常返 并且 $i\rightarrow j$ 则有 $f_{ji}=1$ 所以两个状态互通 定理： 两个互通的状态： 要么同为非常返的 或者同为零常返的 或者同为正常返周期态且周期相同 或者同为遍历态 这样我们就能从一个状态的情况推断其他状态的情况

状态空间的分解

容易验证 互通满足自反 对称 传递性 也就是是一种等价关系 那么就可以划分等价类了 由于互通的状态状态类型相同 这就是分解的讨论基础

定理：包含常返态的等价类$S_n$是不可约闭集 定理：齐次马氏链的状态空间$S$可唯一地分解为有限或可列无限多个互不相交的状态子集的并 也就是

$$S=D\cup C_1\cup C_2\cup\cdots$$

其中的$D$是非常返状态构成的状态子集 $C$均是由常返态构成的不可约闭集 每个状态子集中有着相同的状态类型

定理：设X是状态有限的齐次马氏链，则

• X的非常返状态集D不可能是闭集
• X不存在零常返状态
• 若X是不可约的，则X所有的状态都是正常返的 这些定理就可以让我们分解状态空间,想要分解还是要靠画转移概率图

从状态转移图分析状态

CK方程计算太复杂了 状态转移图是最方便的

• 所有有出了返回不了自己的状态都是非常返的
• 出去了能返回自己的是常返的
• 有限状态齐次马氏链不存在零常返 所有的常返的都是正常返
• 研究周期通过数的方法人工寻找大于0的pii 找最大公约数
• 互通状态的状态类型相同

转移概率的极限

转移概率的极限 研究的是$$\lim_{n\to\infty}P_{ij}^{(n)}$$的性质 包括是否存在和与$i$是否无关

极限分布

设$X=\{X_n,n=0,1,...\}$为齐次马氏链，若对任意的状态 $i,j$

$\lim_{n\to\infty}p_{ij}^{(n)}=\pi_j$, 且$\pi_j>0,\sum_{j\in S}\pi_j=1$ $n\to\infty$

则$\{\pi_j,j\in S\}$是一概率分布，称之为马氏链的极限分布 后面的研究都是针对于此

从状态空间研究极限分布

当$i~j$ 属于不同常返态的不可约闭集的时候 有

$$\lim_{n\to\infty}p_{ij}^{(n)}=0$$

当$i~j$ 正常返周期态的状态子集时

$$\lim_{n\to\infty}p_{ij}^{(n)}\text{不存在}$$

下面我们来开始研究计算的问题 我们不加解释的研究下面形式的极限

\lim_{n\to\infty}\color{}{p_{ij}^{(nd_j+r)}}

给出定理：当$j$是正常返态的 则

$$\lim_{n\to\infty}p_{ij}^{(nd_j+r)}=f_{ij}(r)\frac{d_j}{\mu_{jj}}$$

计算这个极限概率 需要使用$n$步转移 周期 平均返回时间 推论：当马氏链是不可约的遍历链时 对于任意的$i~j$ 有

$$\lim_{n\to\infty}p_{ij}^{(n)}=\frac{1}{\mu_{jj}}>0$$

极限概率存在并且和初始状态无关 我们只需要计算平均返回时间就好了 但是还可以继续简化 定理：当马氏链是不可约的遍历链时 对于任意的$i~j$ 有

$$\lim_{n\to\infty}p_{ij}^{(n)}=\frac{1}{\mu_{jj}}\stackrel{def}{=}\pi_{j}$$

并且有 $\pi_j$是线性方程组 $\begin{aligned}x_j=\sum_{i\in S}x_ip_{ij}\end{aligned}$ 满足条件$x_{j}\geq0,\sum_{j\in S}x_{j}=1$ 的唯一解 我们以后计算极限分布只需要解方程组就可以了 然后再用倒数求平均返回时间 解方程组 一方面我们再高等代数中做过介绍 并且哪怕使用手算也是可以慢慢解决的

转移概率的平稳分布

平稳分布

称概率分布$\pi_j$ 是齐次马氏链的一个平稳分布 如果有

$$\pi_j=\sum_{i\in S}\pi_ip_{ij},\quad j\in S$$

或者矩阵形式为

$$\pi=\pi P$$

其中$\pi$是极限分布向量 $P$是转移概率矩阵 平稳分布是在极限分布的基础上进行定义的 由于一步转移具有不变性 那么一定有

$$\pi_j=\sum_{i\in S}\pi_ip_{ij}^{(n)}$$

定理：如果$\pi$是一个齐次马氏链的平稳分布 则取$\pi$为初始分布有 则有 一：

$$P(X_n=i)=\sum_{k\in S}P(X_0=k)P(X_n=i\begin{vmatrix}X_0=k\end{vmatrix}$$ $$=\sum_{k\in S}\pi_{k}p_{ki}^{(n)}=\pi_{i}$$

也就是绝对分布具有不变性 二：任取$t,n,m,i$ 有

$$P(X_{t_1+m}=i_1,\cdots,X_{t_n+m}=i_n)=P(X_{t_1}=i_1,\cdots,X_{t_n}=i_n)$$

该马氏链是一个严平稳时间序列

研究平稳分布的存在和计算

不可约的马氏链——遍历链

唯一的极限分布$$\{\pi_{j}=\frac{1}{\mu_{jj}},j\in S\}$$就是平稳分布 计算这个平稳分布可以用前一节的定理解方程组得到

不可约的马氏链——周期链

假设$X$是不可约齐次马氏链 状态空间中每一个状态都是正常返的 周期为$d$则有$X$有唯一的平稳分布$\{\pi_{j}=\frac{1}{\mu_{ij}},j\in S\}$ 他也可以通过解方程组

$$\begin{aligned} &\pi_{j}=\sum_{i\in S}\pi_{i}p_{ij} \\ &\sum_{j\in S}\pi_{j}=1, \end{aligned}$$

得到

一般齐次马尔可夫链

设状态空间为$S=D\cup C_{0}\cup C_{1}\cup\cdots$ 其中$D$是非常返状态集 $C_0$是零常返状态集$C_m$是正常返不可约闭集 记$H=\bigcup_{k\geq1}C_{k}$ 则

• $X$不存在平稳分布的充要条件是 $H=\Phi$
• $X$存在唯一平稳分布的充要条件是 只有一个正常返的不可约闭集
• $X$存在无穷多个平稳分布的充要条件是至少存在两个一个正常返的不可约闭集 哪怕平稳分布不唯一 我们依旧可以计算平稳分布 如下例 对于七个状态的齐次马尔科夫链 一步转移概率矩阵为

$$P=\begin{bmatrix}0.5&0.5&0&0&0&0\\0&2/3&1/3&0&0&0&0\\1/3&0&2/3&0&0&0&0\\0&0&0&0.5&0.5&0&0\\0&0&0&0.5&0.5&0&0\\0&0&0&0&0&1&0\\\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}&\frac{1}{7}\end{bmatrix}$$

分解状态空间有

$$\begin{aligned}S&=D\cup C_1^+\cup C_2^+\cup C_3^+\\\\&=\{6\}\cup\{0,1,2\}\cup\{3,4\}\cup\{5\}\end{aligned}$$

所以有无穷多个平稳分布 使用分块矩阵

$$P_1=\begin{pmatrix}1/2&1/2&0\\0&2/3&1\\1/3&0&2/3\end{pmatrix}\quad P_2=\begin{pmatrix}1/2&1/2\\1/2&1/2\end{pmatrix}\quad P_3=1$$

解方程组有

$$\pi^{(1)}=\{\frac28,\frac38,\frac38\}\quad\pi^{(2)}=\{\frac12,\frac12\}\quad\pi^{(3)}=\{1\}$$

所以平稳分布为

$$\boldsymbol{\pi}=\{\frac{2\lambda_1}8,\frac{3\lambda_1}8,\frac{3\lambda_1}8,\frac{\lambda_2}2,\frac{\lambda_2}2,\lambda_3,0\}$$

其中有$\lambda_1+\lambda_2+\lambda_3=1$ 在平稳分布的基础上进行的计算是一个很容易的事情 我们有不少好用的性质可以使用