04-1Markov链

Lingfeng 2024-10-12

04-1Markov链

随机序列 $\{ X_{n},n=0,1,\dots \}$ 称为马尔可夫链，若它取有限或可列个值，其取值称为过程的状态，所有的状态集合称为过程的状态空间，记为 $S$ ，对任意的 $n\geq0$ 即状态 $i,j,i_{0},i_{1},\dots,i_{n-1}$ ，有 $\begin{align*} P\{ X_{n+1}=j\mid X_{0}=i_{0},X_{1}=i_{1},\dots,X_{n-1}=i_{n-1},X_{n}=i \} =P\{ X_{n+1}=j \mid X_{n}=i \} \end{align*}$

Definition (转移概率矩阵)

P=\left( \begin{matrix} p_{00} & p_{01} & p_{02} & \dots \\ p_{10} & p_{11} & p_{12} & \dots \\ \vdots & \vdots & \ddots & \vdots \\ p_{i 0} & p_{i 1} & p_{i 2} & \dots \end{matrix} \right)

其中 $p_{ij}=P\{ X_{n+1}=j\mid X_{n}=i \}$ 。其满足 $\begin{align*} p_{ij}\geq 0, & \quad i,j \in S \\ \sum_{j \in S} p_{ij}=1, & \quad \forall i\in S \end{align*}$

Theorem (状态转移方程)

设 $S=\{ 1,2,\dots,s \}$ ， $p_{0}=(P\{ X_{0}=1 \},P\{ X_{0}=2 \},\dots,P\{ X_{0}=s \})$ ， $P=\left(\begin{matrix} p_{11} & p_{12} & \dots & p_{1s} \\ p_{21} & p_{22} & \dots & p_{2s} \\ \vdots & \vdots & \ddots & \vdots \\ p_{s1} & p_{s2} & \dots & p_{ss} \end{matrix}\right)$ ，此时有 $p_{1}=(P\{ X_{1}=1 \},P\{ X_{1}=2 \},\dots,P\{ X_{1}=s \})=p_{0}P$

证明
注意到 $\forall j \in S$ ，有 $\begin{align*} P\{ X_{1}=j \} & =\sum_{i \in S} P\{ X_{1}=j\mid X_{0}=i \}P\{ X_{0}=i \} \\ & = p_{0} \begin{pmatrix} p_{1j} \\ p_{2j} \\ \vdots \\ p_{sj} \end{pmatrix} \end{align*}$ 因此有 $p_{1}=p_{0}P$

1.2 n步转移概率与C-K方程

Definition (n步转移概率)

设 $p_{ij}^{(n)}=P\{ X_{m+n}=j\mid X_{m}=i \},\quad i,j \in S, m\geq 0,n\geq 1$ 为马尔可夫链的n步转移概率，同样可定义n步转移矩阵。约定 $p_{ij}^{(0)}=\left\{\begin{align*} 0, & \quad i \neq j \\ 1, & \quad i=j \end{align*}\right.$

Theorem (C-K方程)

对于任意 $n$ ， $m \geq 0$ ， $i$ ， $j \in S$ 有 $\begin{align*} p_{ij}^{(m+n)}& = \sum_{k \in S} p_{ik}^{(m)}p_{kj}^{(n)} \\ P^{(n)} &= P^{n} \end{align*}$

证明
$\begin{align*} p_{ij}^{(m+n)} & = P\{ X_{m+n}=j \mid X_{0}=i\} \\ & = \sum_{k \in S} P\{ X_{m+n}=j\mid X_{m}=k,X_{0}=i \}P\{ X_{m}=k\mid X_{0}=i \} \\ & = \sum_{k \in S} P\{ X_{m+n}=j\mid X_{m}=k \}P\{ X_{m}=k\mid X_{0}=i \} \\ & = \sum_{k \in S} p_{kj}^{(m)}p_{ik}^{(n)} \end{align*}$

2. 状态的分类及性质

Definition (互通)

称状态 $i$ 可达状态 $j$ ，若存在 $n\geq 0$ 使得 $p_{ij}^{(n)}>0$ ，记为 $i\to j$ 。若同时有 $j\to i$ ，则称 $i$ 与 $j$ 互通，记为 $i\leftrightarrow j$ 。互通的状态称为同一类。

Theorem (互通的性质)

显然互通有以下性质 $\begin{align*} i&\leftrightarrow j \\ i\leftrightarrow j &\implies j\leftrightarrow i \\ i\leftrightarrow j,j\leftrightarrow k &\implies i\leftrightarrow k \end{align*}$

Definition (周期)

若集合 $\{ n:n\geq 1,p_{ii}^{(n)}>0 \}$ 非空，则称它的最大公约数 $d=d(i)$ 为状态 $i$ 的周期。若 $d>1$ ，则称 $i$ 是周期的；若 $d=1$ ，则称 $i$ 是非周期的。当集合为空集时，称 $i$ 的周期为无穷大。

Theorem (周期与互通)

若 $i\leftrightarrow j$ ，则 $d(i)=d(j)$ 。

证明
令 $A=\{ n:n\geq 1,p_{ii}^{(n)}>0 \}$ ，注意到 $\exists m,n>0$ ，有 $i\stackrel{m}{\longrightarrow}j\stackrel{n}{\longrightarrow}i$ 故 $m+n\in A$ ，因此有 $m+n$ 是 $d(i)$ 的倍数。同时令 $B=\{ n:n\geq 1,p_{jj}^{(n)}>0 \}$ ，则对于任意 $s \in B$ ，有 $i\stackrel{m}{\longrightarrow}j\stackrel{s}{\longrightarrow}j\stackrel{n}{\longrightarrow}i$ 此时也有 $m+s+n$ 是 $d(i)$ 的倍数，故 $s$ 是 $d(i)$ 的倍数。由 $s$ 的任意性知 $d(i)$ 是 $B$ 的公约数，而 $d(j)$ 是 $B$ 的最大公约数，因此有 $d(j)$ 是 $d(i)$ 的倍数。同理可证 $d(i)$ 是 $d(j)$ 的倍数，从而 $d(i)=d(j)$ 。

Definition (常返态)

对于任意状态 $i$ ， $j$ ，设 $f^{(n)}_{ij}$ 记从 $i$ 出发经 $n$ 步后首次到达 $j$ 的概率，则有 $\begin{align*} f^{(0)}_{ij}&=\delta_{ij} \\ f^{(n)}_{ij}&= P\{ X_{n}=j,X_{k}\neq j,k=1,2,\dots,n-1\mid X_{0}=i \},n\geq 1\end{align*}$ 令 $f_{ij}=\sum_{n = 1}^{\infty}f^{(n)}_{ij}$ ，若 $f_{jj}=1$ ，则称状态 $j$ 为常返状态；反之为非常犯状态或瞬过状态。

Definition (平均步数)

$\mu_{i}=\sum_{n = 1}^{\infty} nf_{ii}^{(n)}$ 表示由 $i$ 出发再返回所需的平均步数。

Definition (正常返和零常返)

对于常犯状态 $i$ ，若 $\mu_{i}<+\infty$ ，则称 $i$ 为正常返状态；若 $\mu_{i}=+\infty$ ，则称 $i$ 为零常返状态；若 $\mu_{i}<+\infty$ ，且 $d(i)=1$ ，则称 $i$ 为遍历状态；若 $f_{ii}^{(1)}=1$ ，则称 $i$ 为吸收状态。

Theorem (首达分解定理)

对于任意状态 $i$ ， $j$ 及 $1\leq n<+\infty$ ，有 $p_{ij}^{(n)}=\sum_{l = 1}^{n} f_{ij}^{(l)}p_{jj}^{(n-l)}$

证明
由全概率公式知显然。

Theorem (常返判别定理)

状态 $i$ 为常返的 $\iff$ $\sum_{n = 0}^{\infty}p_{ii}^{(n)}=\infty$ ；状态 $i$ 为非常返的，有 $\sum_{n = 0}^{\infty}p_{ii}^{(n)}=\frac{1}{1-f_{ii}}$

证明
$\begin{align*} \sum_{n = 0}^{\infty} p_{ii}^{(n)} & = p_{ii}^{(0)}+ \sum_{n = 1}^{\infty} \left( \sum_{l = 1}^{n} f_{ii}^{l}p_{ii}^{(n-l)} \right) \\ & = 1+ \sum_{l = 1}^{\infty}f_{ii}^{l} \left( \sum_{n = l}^{\infty} p_{ii}^{(n-l)} \right) \\ & = 1+ f_{ii}\sum_{n = 0}^{\infty} p_{ii}^{(n)} \end{align*}$ 得到 $f_{ii}=1- \frac{1}{\sum_{n = 0}^{\infty} p_{ii}^{(n)}}$

Theorem (常返分解定理)

f_{ii}=p_{ii}+\sum_{l \neq i}p_{il}f_{li}

证明
$\begin{align*} f_{ii} & =\sum_{n = 1}^{\infty} f_{ii}^{(n)} \\ & = p_{ii}+ \sum_{n = 2}^{\infty} \sum_{l\neq i} p_{il}f_{li}^{(n-1)} \\ & =p_{ii}+ \sum_{l\neq i} p_{il} \sum_{n = 1}^{\infty} f_{li}^{(n) } \\ & = p_{ii}+\sum_{l\neq i} p_{il}f_{li} \end{align*}$

Lemma (互通常返性)

若 $i\to j$ 且 $i$ 为常返状态，则 $f_{ji}=1$ ，自然有 $j\to i$ 。若 $i$ 是零常犯态，也有 $j$ 为零常返态。

证明
考虑反证法，假设 $f_{ji}<1$ ，注意到 $\begin{align*} 1-f_{ii} & =1-p_{ii}-\sum_{l\neq i} p_{il}f_{li} \\ & = \sum_{l \neq i}p_{il}- \sum_{l \neq i}p_{il}f_{li} \\ & =\sum_{l \neq i} p_{il}(1-f_{li}) \\ & \geq p_{ij}(1-f_{ji})>0 \end{align*}$ 与 $f_{ii}=1$ 矛盾。故证毕。

Theorem (常返性与类)

常返性是类性质。若 $i\leftrightarrow j$ ，则 $i$ 常返必有 $j$ 也常返。

证明
由于 $i\leftrightarrow j$ ， $\exists n,m>0$ ，使得 $p_{ij}^{(n)}$ ， $p_{ji}^{(m)}>0$ ，此时 $p_{ii}^{(n+m+l)}\geq p_{ij}^{(n)}p_{jj}^{(l)}p_{ji}^{(m)}$ 因此 $\sum_{l = 0}^{\infty} p_{ii}^{(l)}\geq \sum_{l = 0}^{\infty} p_{ii}^{(n+m+l)}\geq p_{ij}^{(n)}p_{ji}^{(m)}\sum_{l = 1}^{\infty}p_{jj}^{(l)}$ 同理 $\sum_{l = 0}^{\infty} p_{jj}^{(l)}\geq b \sum_{l = 0}^{\infty} p_{ii}^{(l)}$ 其中 $0<b\leq1$ 。故 $\sum_{i = 0}^{\infty}p_{ii}^{(l)}$ 与 $\sum_{i = 0}^{\infty}p_{jj}^{(l)}$ 相互控制，由常返判别准则知定理成立。

3. 极限定理及平稳分布

3.1 极限定理

Theorem (Markov链基本极限定理)

若状态 $i$ 是周期为 $d$ 的常返态，则 $\lim_{ n \to \infty }p_{ii}^{(nd)}=\frac{d}{\mu_{i}}$

Corollary (零常返状态判定定理)

若 $i$ 是常返态，则 $i$ 是零常返态 $\iff$ $\lim_{ n \to \infty }p_{ii}^{(n)}=0$ 。

Theorem ( $p_{ij}^{(n)}$ 的极限性质)

若 $j$ 为非常犯状态或者零常犯状态，则 $\forall i \in S$ ，有 $\lim_{ n \to \infty } p_{ij}^{(n)}=0$ 若状态 $j$ 为正常返态，且 $d(j)=1$ ，若 $i\leftrightarrow j$ ，则有 $\lim_{ n \to \infty } p_{ij}^{(n)}= \frac{1}{\mu _{j}}$ 若 $i$ 为非常返态，状态 $j$ 为正常返态， $i\to j$ ，且 $d(j)=1$ ，则有 $\lim_{ n \to \infty } p_{ij}^{(n)}= \frac{f_{ij}}{\mu_{j}}$

Corollary (有限状态Markov链性质)

有限状态Markov链性质不会全为非常返态，也不会有零常返态，不可约有限Markov链一切状态都是正常返的。

证明
设 $S=\{ 1,2,\dots,N \}$ 。若 $N$ 个状态非常返，则 $\lim_{ n \to \infty } \sum_{j \in S}p_{ij}^{(n)} =\sum_{j\in S} \lim_{ n \to \infty } p_{ij}^{(n)} =0$ 但 $\sum_{j \in S}p_{ij}=1$ 矛盾。

3.2 平稳分布

Definition (平稳分布)

对于Markov链，概率分布 $\{ p_{j}, j \in S\}$ 为平稳分布，若 $p_{j}=\sum_{i \in S} p_{i}p_{ij}$ 即 $p = pP$

Theorem (对于不可约非周期的Markov链)

若它是遍历的，则 $\pi_{j}=\lim_{ n \to \infty } p_{ij}^{(n)}>0$ 是平稳分布且是唯一的平稳分布。
若状态是瞬过全为零常返，则平稳分布不存在。

证明
注意到 $\sum_{j \in S} p_{ij}^{(n)}=1$ 因此 $\lim_{ n \to \infty } \sum_{j \in S} p_{ij}^{(n)}=1$
由Fubini定理 $\sum_{j \in S}\pi_{j}=1$ 利用C-K方程 $p_{ij}^{(n+1)}=\sum_{k \in S}p_{ik}^{(n)}p_{k_{j}}$ 因此 $\lim_{ n \to \infty } p_{ij}^{(n+1)}=\sum_{k \in S}(\lim_{ n \to \infty } p_{ik}^{(n)})p_{kj} =\sum_{k \in S}\pi_{k}p_{kj}$ 即 $\pi_{j}=\sum_{k \in S}\pi_{k}p_{kj}$ 从而为平稳分布。

同时若也有 $\{ \tilde{\pi}_{j},j \in S \}$ 为平稳分布。注意到 $\begin{align*} \tilde{\pi}_{j}&=\sum_{k \in S}\tilde{\pi}_{k}p_{kj} \\ & = \sum_{k \in S}(\sum_{i \in S}\tilde{\pi}_{i}p_{ik})p_{kj} \\ \\ & = \sum_{i \in S}\tilde{\pi}_{i}\sum_{k \in S}p_{ik}p_{kj} \\ & = \sum_{i \in S}\tilde{\pi}_{i}p_{ij}^{(2)} \end{align*}$ 利用归纳法可得 $\tilde{\pi}_{j}=\sum_{i \in S}\tilde{\pi}_{i}p^{(n)}_{ij}$ 此时 $\tilde{\pi}_{j}=\sum_{i \in S}\tilde{\pi}_{i}\lim_{ n \to \infty } p_{ij}^{(n)}=\left( \sum_{i \in S}\tilde{\pi}_{i} \right)\pi_{j}=\pi_{j}$

Corollary (平稳分布和平均步数)

对于不可约非周期遍历的Markov链，有 $\lim_{ n \to \infty } p_{ij}^{(n)}=\pi_{j}=\frac{1}{\mu_{j}}$

04-1Markov链

04-1Markov链

1. 基本概念

1.1 定义

1.2 n步转移概率与C-K方程

2. 状态的分类及性质

3. 极限定理及平稳分布

3.1 极限定理

3.2 平稳分布