前言
本章我们介绍Markov特性与Markov链。
离散时间Markov链
定义4.1：离散时间Markov链
设有随机过程$\{X_n|n=0,1,\cdots\}$，其样本空间（状态空间）$S$可数。若有：$\forall n\in \boldsymbol N,\forall s_0,s_1\cdots,s_n,s_{n+1}\in S$满足：
$$ P(X_{n+1}=s_{n+1}|X_n=s_n,\cdots,X_0=s_0)=P(X_{n+1}=s_{n+1}|X_n=s_n)\tag 1 $$
则称$\{X_n|n=0,1,\cdots \}$为一离散时间Markov链。
如果我们将时刻$n$称为“现在”或者“当下”，记为$A$；时刻$0,1,\cdots,n-1$称为“过去”，记为$B$；时刻$n+1$称为未来，记为$C$，则Markov特性为：未来的状态仅和当下的状态有关，而与过去的状态无关，也即：
$$ P(C|BA)=P(C|B)\tag 2 $$
等价地，易证明：
$$ P(CA|B)=P(C|B)P(A|B)\tag 3 $$
也即：以当下的状态作为条件，过去与未来的状态相互独立。
定义4.2：转移概率
设有一Markov链$\{X_n|n\geq 0 \}$，记概率：
$$ p_{ij}(n,m) \overset{\underset{\mathrm{def}}{}}{=}P(X_{n}=j|X_m=i)\quad m<n\in\boldsymbol N,i,j\in S\tag 4 $$
称为从时刻$m$状态$i$到时刻$n$状态$j$的转移概率。若一个转移概率仅与转移时间有关，则称该Morkov链为平稳Markov链，即：$p_{ij}(m+n,m)=p_{ij}(n)$，称$p_{ij}(n)$为$n$步转移概率。下文中若不额外说明，研究的均为平稳Markov链。
联合分布与转移矩阵
接下来，我们考察离散Markov链的$n$维联合分布：
$$ F_{t_0,\cdots,t_n}(i_0,\cdots,i_n)=P(X_{t_0}=i_0,\cdots,X_{i_n}=i_n)\tag 5 $$
其中$t_0<t_1<\cdots<t_n\in\boldsymbol N,\ i_0,\cdots,i_n\in \boldsymbol S$。容易知道：
$$ \begin{align} P(X_{t_0}=i_0,\cdots,X_{t_n}=i_n)&=P(X_{t_n}=i_n|X_{t_{n-1}}=i_{n-1},\cdots,X_{t_0}=i_0)\\ &=P(X_{t_n}=i_n|X_{t_{n-1}}=i_{n-1})\cdots P(X_{t_1}=i_1|X_{t_0}=i_0)P(X_{t_0}=i_0)\tag 6 \end{align} $$
如果我们进一步假设：$t_0=0,\ p_{i_0}\overset{\underset{\mathrm{def}}{}}{=}P(X_0=i_0)$，则我们有如下定理：
定理4.1：Markov联合分布与转移概率的关系
一个Markov链的联合分布可由初始分布与转移概率完全确定。具体地，设：$0=t_0<t_1<\cdots<t_n\in\boldsymbol N,\ i_0,\cdots,i_n\in \boldsymbol S,\ p_{i_0}\overset{\underset{\mathrm{def}}{}}{=}P(X_0=i_0)$，则：
$$ F_{t_0,\cdots,t_n}(i_0,\cdots,i_n)=P(X_{t_0}=i_0,\cdots,X_{t_n}=i_n) =p_{i_0}\cdot p_{i_0i_1}(t_1)\cdot p_{i_1i_2}(t_2-t_1)\cdots p_{i_{n-1}i_n}(t_n-t_{n-1}) \tag 7 $$
定义4.3：$n$步转移概率矩阵
我们记所有$n$步转移概率$p_{i,j}(n),i,j\in S,n\in\boldsymbol N_+$构成的矩阵：
$$ \boldsymbol P(n)\overset{\underset{\mathrm{def}}{}}{=} \begin{bmatrix} p_{i_0j_0}(n) &\cdots&p_{i_0j_t}(n)&\cdots&\\ \vdots &\ddots &\vdots &\ddots&\\ p_{i_sj_0}(n)&\cdots&p_{i_sj_t}(n)&\cdots &\\ \vdots&\ddots&\vdots&\ddots& \end{bmatrix}_{|S|\times |S|}\tag 8 $$
为$n$步状态转移概率矩阵。显然$p_{ij}(n)\geq 0,\ \forall i\in S,\sum_{j\in S}p_{ij}(n)=1$。我们通常称满足这两个性质的矩阵为随机矩阵。
对于较为复杂的$n$步转移，有时候我们更感兴趣单步转移。类似地，我们也可以定义单步转移概率：$p_{ij}$与单步转移矩阵：
$$ \boldsymbol P(1)\overset{\underset{\mathrm{def}}{}}{=} \begin{bmatrix} p_{i_0j_0} &\cdots&p_{i_0j_t}&\cdots&\\ \vdots &\ddots &\vdots &\ddots&\\ p_{i_sj_0}&\cdots&p_{i_sj_t}&\cdots &\\ \vdots&\ddots&\vdots&\ddots& \end{bmatrix}_{|S|\times |S|}\tag 9 $$
类似（7）式，我们有：
$$ F_{0,\cdots,n}(i_0,\cdots,i_n)=P(X_{0}=i_0,\cdots,X_{n}=i_n) =p_{i_0}\cdot p_{i_0i_1}\cdot p_{i_1i_2}\cdots p_{i_{n-1}i_n} \tag {10} $$
如何刻画单步转移与$n$步转移之间的关系呢？
Chapman-Kolmogorov方程
注意到：$p_{ij}(n)=\sum_{k\in S}p_{ik}\cdot p_{kj}(n-1),\ n\geq 2$，也即：$\boldsymbol P(n)=\boldsymbol P(1)\cdot P(n-1)$，因此$\boldsymbol P(n+m)=\boldsymbol P(n)\boldsymbol P(m)$，也即：
$$ p_{ij}(n+m)=\sum_{k\in S}p_{ik}(n)\cdot p_{kj}(m)\tag{11} $$
我们将（11）式称为Chapman-Kolmogorov方程，简称C-K公式。
显然地，我们可以得出：
$$ \boldsymbol P(n)=\boldsymbol P^n\tag{12} $$
状态的分类
定义4.4：Markov链的状态分类
下设有一Markov链$\{X_n|n\geq 0 \}$，其状态空间$S=\boldsymbol N=\{0,1,\cdots \}$。状态$i,j\in S$。约定：$p_{ij}(0)=1,if\ i=j,\ else\ 0$。
（1）可达与相通：若$\exists n\geq 0,\;s.t.\;p_{ij}(n)>0$，则称从状态$i$到$j$ 可达，记作$i\to j$。显然可达是等价关系。若$i\to j$且$j\to i$，则称称从状态$i$到$j$ 相通，记作$i\leftrightarrow j$。若$\forall i,j\in S,i\leftrightarrow j$，则称$X_n$是不可约的。
（2）闭集：设$A\subseteq S$，若$\forall i\in A,\;j\notin A$都有$i\not\to j$，则称$A$为一闭集。闭集可以理解为“进得去，出不来”的集合，所有进入闭集的状态都被吸收了。显然闭集的任意真子集都不是闭集，$S$是闭集的充要条件是$X_n$不可约（Proof：[1]1:41:28-1:48:33）。
首达、常返与瞬过
定义4.5：首达
（1）首达时间：设有状态$j\in S$，定义：
$$ \tau_j\overset{\text{def}}{=}\inf\{n\geq1|X_n=j \}\tag{13} $$
为状态$j$的首达时间。
（2）首达概率：定义概率：
$$ f_{ij}(n)\overset{\text{def}}{=}P(\tau_j=n|X_0=i)=P(X_n=j,X_{n-1}\neq j,\cdots,X_1\neq j|X_0=i) \tag{14} $$
为过程从状态$i$出发经过$n$步首次转移到$j$的概率。
定理4.2：首达概率的相关性质
（1）$p_{ij}(n)=\sum_{k=1}^n f_{ij}(k)\cdot p_{jj}(n-k)$。这个公式从时间的角度刻画了$n$步转移概率，而C-K公式给出的是$n$步转移概率在空间层面的分解与简化。
定义4.6：常返与瞬过
若对状态$i$满足：
$$ f_{ii}\overset{\text{def}}{=}\sum_{k=1}^{+\infty}f_{ii}(k)=1\tag{15} $$
则称$i$为常返态，否则称$i$为瞬过态（非常返） 。
由定义，若$i$是常返态，则：$P(\tau_i<\infty|X_0=i)=1$，即初始从$i$出发，经过有限步必然能回到$i$。
为了判断状态是否常返，我们希望把难以计算的$f_{ij}(n)$转换为相对好计算的$p_{ij}(n)$。
定理4.3：常返与瞬过的判定定理
（1）状态$i$常返的充要条件是：$\sum_{n=0}^{+\infty} p_{ii}(n)=+\infty$；
（2）状态$i$瞬过的充要条件是：$\sum_{n=0}^{+\infty} p_{ii}(n)=\frac{1}{1-f_{ii}}<+\infty$。
证明可见[2] P102-104。所以现在判断常返性只需要考察级数$\sum_{n=0}^{+\infty}p_{ii}(n)$即可。由上式还可知：常返态一定返回自身无穷多次；而瞬过态仅能返回自身有限次。
定理4.4：常返与瞬过的性质
（1）若$i\to j$，则：
$$ \sum_{n=1}^{+\infty}p_{ij}(n)=\infty\tag {16} $$
（2）若$i\not\to j$，则：
$$ \sum_{n=1}^{+\infty}p_{ij}(n)=0\tag{17} $$
（3）若$j$非常返，则：$\forall i\in S,\;\sum_{n=0}^{+\infty}p_{ij}(n)<+\infty,\;\lim_{n\to +\infty}p_{ij}(n)=0$。
（4）若$S$为有限集，则Markov链$X_n$必存在常返态。
（5）若$i\leftrightarrow j$，则$i,j$的常返状态相同，也即常返为类性质。
（6）若$i$常返，且$i\to j$，则必有$j\to i$，也即常返集为一闭集。
（7）若$i\to j,\;j\not\to i$，则$i$为瞬过态。
定义4.7：平均返回时间、零常返、正常返
常返态$i$的平均返回时间定义为：
$$ \mu_i\overset{\text{def}}{=} \sum_{n=1}^{+\infty} n\cdot f_{ii}(n)\tag{18} $$
显然地，$\mu_i$即是首达时间的期望。若$\mu_i=+\infty$，则称$i$是零常返的，表示虽然从$i$出发最终能回到$i$，但所需时间较长；若$\mu_i<+\infty$，则称$i$是正常返的，即返回的所需时间较短。
定理4.5：正常返与零常返的性质
（1）正常返与零常返也是类性质；
（2）若$S$为有限集，则Markov链$X_n$必存在常返态，且其所有常返态均为正常返态。（定理4.4 （4）的推广）
（3）有限不可约的Markov链所有状态均为正常返态。（（2）的推论）
Markov链的极限行为
所谓Markov链的极限行为，即是考察：$\lim_{n\to +\infty}p_{ij}(n)$或者等价地考察$\lim_{n\to +\infty}\boldsymbol{P}(n)$，也即考察链的渐进性与最终形态。首先由定理4.4（3），瞬过态的转移概率极限为0，表明以其为终点的转移行为最终都将消亡。我们首先给出状态的周期的定义。
定义4.8：状态的周期
设$i$为Markov链的任一状态，则使得$p_{ii}(n)>0$成立的所有$n$的最大公约数称为$i$的周期，记为$d(i)$。若$d(i)=1$则称$i$是非周期的。我们称非周期的正常返状态为遍历态。
定理4.6：
若$i\leftrightarrow j$，则$d(i)=d(j)$。也即周期性也是类性质。
定理4.7：弱遍历定理
设有不可约常返Markov链$\{X_n|n\geq 0\}$，则$\forall i,j\in S$有：
$$ \lim_{n\to +\infty}\frac 1n\sum_{k=0}^{n-1}p_{ij}(k)=\frac{1}{\mu_j}\tag{19} $$
容易看出其概率意义。左侧是恰好处在$j$状态的数目在总数$n$中所占比例，而右侧则是单位时间内返回$j$的次数。
将弱遍历定理推广我们可以得到Markov链的基本极限定理。
定理4.8：基本极限定理
设有Markov链$\{X_n|n\geq 0 \}$。
（1）若$i$为周期为$d$的常返态，则：
$$ \lim_{n\to +\infty}p_{ii}(n)=\frac{d}{\mu_i}\tag{20} $$
（2）若$i$为非周期正常返（即遍历态）则：
$$ \lim_{n\to +\infty}p_{ii}(n)=\frac{1}{\mu_i}\tag{21} $$
定义4.9：极限分布
设有Markov链$\{X_n|n\geq 0 \}$。
（1）若$j$为遍历态，则$\forall i\in S$：
$$ \lim_{n\to +\infty}p_{ij}(n) =\frac{f_{ij}}{\mu_j}\tag{22} $$
（2）进一步地，若$i\leftrightarrow j$，则：
$$ \lim_{n\to +\infty}p_{ij}(n)=\frac{1}{\mu_j}\tag{23} $$
（3）因此，对于不可约遍历链，极限$\lim_{n\to +\infty}p_{ij}(n)$存在且仅与末状态$j$有关（记为$p_j$），此时称$\boldsymbol p=[p_0,p_,1\cdots]^{\top}$为极限分布。
平稳分布
定义4.10：平稳分布
设有Markov链$\{X_n|n\geq 0 \}$，其转移概率矩阵为$\boldsymbol P$，$\boldsymbol 1=[1,\cdots,1]$。若有一随机向量$\boldsymbol \pi=[\pi_1,\cdots,]^\top$满足：
$$ \pi_i\geq 0;\;\boldsymbol\pi\boldsymbol 1=1,\;\boldsymbol\pi=\boldsymbol\pi\boldsymbol P(n)\tag{24} $$
则称$\boldsymbol \pi$为$X_n$的一个平稳分布。直观上理解，如果该Markov链的初始状态分布为平稳分布，则任意时刻的状态边缘分布都是该平稳分布。
定理4.9：
不可约非周期Markov链是正常返的充要条件为其存在平稳分布$\boldsymbol \pi$，且该平稳分布等于其极限分布$\boldsymbol p$。
Markov链的应用
应用一：MCMC（Markov Chain Monte Carlo）
应用二：HMM（Hidden Markov Models）
References
- 【随机过程 张颢 2020-2021学年-哔哩哔哩】 https://b23.tv/0uFCuX3 p14
- 随机过程，郑坚坚，中国科学技术大学出版社
