应用随机过程

定义 马尔可夫链

若随机序列 ${X_n:n\geqslant 0}$ 对任意 \(i_0,i_1,\ldots,i_n,i_{n+1}\in S,\ n\in\mathbb{N}_0\) 及 \(P(X_0=i_0,X_1=i_1,\cdots,X_n=i_n)>0\) 有 \(P(X_{n+1}=i_{n+1}|X_0=i_0,X_1=i_1,\cdots,X_n=i_n)=P(X_{n+1}=i_{n+1}|X_n=i_n)\) 则称其为马尔可夫链 (Markov chain).

注释

马尔可夫链的定义式揭示了马尔可夫链的特性, 即马尔可夫性或无后效性: 将来 \(X_{n+1}=i_{n+1}\) 与过去 \(X_0=i_0,X_1=i_1,\cdots,X_{n-1}=i_{n-1}\) 关于现在 $X_n=i_n$ 条件独立.

定义 一步转移概率与转移矩阵

$\forall~i,j\in S$, \(P(X_{n+1}=j|X_n=i)\triangleq p_{ij}(n)\) 称为时刻 $n$ 从 $i$ 到 $j$ 的一步转移概率.

若 $\forall~i,j\in S,\ p_{ij}(n)=p_{ij}$ 不依赖于 $n$, 则称 $X={X_n,n\geqslant 0}$ 为时齐马氏链 (HMC, Homogeneous Markov Chain). 记 $\pmb{P}=(p_{ij})_{i,j\in S}$, 则称 $\pmb{P}$ 为 $X$ 的一步转移概率矩阵, 简称为转移矩阵 (transition matrix).

定义 转移图

转移图是一个有向图 $G=(V,E)$, $V=S$, \(E=\Big\{\overrightarrow{ij}~|~i,j\in S,~p_{ij}>0\Big\}\)

例 随机游动

独立同分布随机变量序列 ${\xi_n,n\geqslant1}$ 取整数值, 整数值随机变量 $X_0$ 与 ${\xi_n,n\geqslant1}$ 独立, \(X_n=X_0+\sum_{k=1}^n\xi_k,\ \forall~n\geqslant1\) 则 ${X_n,n\geqslant0}$ 是时齐马氏链.

证明: $\forall~n\in\mathbb{N},\ i_0,i_1,\ldots,i_{n-1},i,j\in \mathbb{Z}$, \(\begin{aligned} & P(X_{n+1}=j|X_0=i_0,X_1=i_1,\cdots,X_{n-1}=i_{n-1},X_n=i)\\ =& P(X_n+\xi_{n+1}=j|X_0=i_0,X_1=i_1,\cdots,X_{n-1}=i_{n-1},X_n=i)\\ =& P(i+\xi_{n+1}=j|X_0=i_0,X_1=i_1,\cdots,X_{n-1}=i_{n-1},X_n=i)\\ =& P(\xi_{n+1}=j-i)\\ \end{aligned}\) 另一方面 \(\begin{aligned} P(X_{n+1}=j|X_n=i) &=P(i+\xi_{n+1}=j|X_n=i)\\ &=P(\xi_{n+1}=j-i)\\ \end{aligned}\) 则 \(P(X_{n+1}=j|X_0=i_0,X_1=i_1,\cdots,X_{n-1}=i_{n-1},X_n=i)=P(X_{n+1}=j|X_n=i)\) 所以 ${X_n,n\geqslant0}$ 是时齐马氏链.

定理 由当前事件和独立序列生成的马氏链

独立同分布随机变量序列 ${\xi_n,n\geqslant1}$ 均取值于 $S$, \(f:S\times S\to S\) \(X_n=f(X_{n-1},\xi_n)\) $X_0$ 与 ${\xi_n,n\geqslant1}$ 相互独立, 则 $X={X_n,n\geqslant0}$ 是时齐马氏链, 转移概率 \(p_{ij}=P(f(i,\xi_1)=j)\)

证明: 对 \(\forall~i_0,i_1,\cdots,i_{n-1},i,j\in S\) 有 \(\begin{aligned} & P(X_{n+1}=j|X_0=i_0,X_1=i_1,\cdots,X_{n-1}=i_{n-1},X_n=i)\\ =& P(f(X_n,\xi_{n+1})=j|X_0=i_0,X_1=i_1,\cdots,X_{n-1}=i_{n-1},X_n=i)\\ =& P(f(i,\xi_{n+1})=j|X_0=i_0,X_1=i_1,\cdots,X_{n-1}=i_{n-1},X_n=i)\\ =& P(f(i,\xi_{n+1})=j)\\ =& P(f(i,\xi_1)=j) \end{aligned}\) 另一方面 \(\begin{aligned} P(X_{n+1}=j|X_n=i) &=P(f(i,\xi_{n+1})=j|X_n=i)\\ &=P(f(i,\xi_{n+1})=j)\\ \end{aligned}\) 则 \(P(X_{n+1}=j|X_0=i_0,X_1=i_1,\cdots,X_{n-1}=i_{n-1},X_n=i)=P(X_{n+1}=j|X_n=i)\) 所以 ${X_n,n\geqslant0}$ 是时齐马氏链.

设 $X={X_n,n\geqslant0}$ 是时齐马氏链, 一步转移概率矩阵 $\pmb{P}=(p_{ij})_{i,j\in S}$, \(\begin{aligned} p_{ij} &=P(X_{n+1}=j|X_n=i)\\ &=P(X_1=j|X_0=i)\\ \end{aligned}\) 则显然有 \(p_{ij}\geqslant0,~\sum_{j\in S}p_{ij}=1\) 这两条来自条件概率测度 $P(\cdot|X_n=i)$ 的基本性质.

定义 转移矩阵

称矩阵 $\pmb{A}=(a_{ij}){i,j\in S}$ 为转移矩阵, 若 $a{ij}\geqslant0$, 且 \(\sum_{j\in S}a_{ij}=1\)

记 $\pi_i(n)=P(X_n=i)$, \(\pmb{\pi}(n)=(\pi_1(n),\pi_2(n),\cdots,\pi_i(n),\cdots)\) 表示 $n$ 时刻 $X_n$ 的概率分布向量, $X_0\sim\pmb{\pi}(0)$ 称为 $X$ 的初始分布.

定理 概率分布的全概率公式

证明: 由全概率公式可知 \(\begin{aligned} P(X_{n+1}=j)&=\sum_{i\in S}P(X_n=i)P(X_{n+1}=j|X_n=i)\\ &=\sum_{i\in S} \pi_i(n)p_{ij} \end{aligned}\) 写成向量形式为 \(\pmb{\pi}(n+1)=\pmb{\pi}(n)\pmb{P}\) 反复应用则有 \(\pmb{\pi}(n)=\pmb{\pi}(0)\pmb{P}^n\)

注释

一个马尔可夫链的特性完全由它的一步转移概率矩阵 $\pmb{P}$ 及初始分布向量 $\pmb{\pi}(0)$ 决定.

定理 Kolmogorov-Chapman 方程 多步转移的全概率公式

记 $p_{ij}^{(m)}=P(X_{n+m}=j|X_n=i)$ 为 $m$ 步转移概率, $\pmb{P}^{(m)}={p_{ij}^{(m)}}$ 为 $m$ 步转移概率矩阵, 则 \(\begin{aligned} p_{ij}^{(m+n)}&=\sum_{k\in S}p_{ik}^{(m)}p_{kj}^{(n)}\\ \pmb{P}^{(m+n)}&=\pmb{P}^{(m)}\pmb{P}^{(n)}\\ \pmb{P}^{(n)}&=\pmb{P}^n \end{aligned}\)

证明: 由条件概率形式的全概率公式可知 \(\begin{aligned} p_{ij}^{(m+n)}&=P(X_{m+n}=j|X_0=i)\\ &=\sum_{k\in S}P(X_m=k|X_0=i)P(X_{m+n}=j|X_0=i,X_m=k)\\ &=\sum_{k\in S}P(X_m=k|X_0=i)P(X_{m+n}=j|X_m=k)\\ &=\sum_{k\in S} p_{ik}^{(m)}p_{kj}^{(n)} \end{aligned}\) 写成向量形式为 \(\pmb{P}^{(m+n)}=\pmb{P}^{(m)}\pmb{P}^{(n)}\)

注释

一个马尔可夫链运动规律的概率特性取决于它的转移概率矩阵特性.

定义 吸收态可达与互通

定理 互通为等价关系

状态相通关系为等价关系因其满足

注释

利用等价关系, 可以把马尔可夫链的状态空间分为若干等价类. 在统一等价类内的状态彼此相通, 在不同等价类中的状态不可能彼此相通. 然而, 从某一类出发以正的概率到达另一类的情形是可能的. 如一马尔可夫链的所有状态属于同一等价类, 则称它是不可约链.

定义 首达时间与首达概率

定义 常返与非常返

则称该集合的最大公约数 $d(i)$ 为状态 $i$ 的周期

定理 首达全概率公式

对 $\forall~i,j\in S$, $n\geqslant1$, 有

$n$ 步转移概率 \(p_{ij}^{(n)}=\sum_{l=1}^n f_{ij}^{(l)}p_{jj}^{(n-l)}\)

$n$ 步首达概率 \(f_{ij}^{(n)}=\sum_{k\neq j}p_{ik}f_{kj}^{(n-1)}\pmb{1}_{\{n>1\}}+p_{ij}\pmb{1}_{\{n=1\}}\)

可达与互通的有限步首达概率表示 \(\begin{aligned} i\to j&\Leftrightarrow f_{ij}>0\\ i\leftrightarrow j&\Leftrightarrow f_{ij}f_{ji}>0 \end{aligned}\)

定理 常返与非常返的充要条件

状态 $i$ 为常返状态, $f_{ii}=1$, 当且仅当 \(G_{ii}\triangleq\sum_{n=0}^\infty p_{ii}^{(n)}=\infty,\)

状态 $i$ 为非常返状态, $f_{ii}