04-1Markov链

Lingfeng2024-10-12

04-1Markov链

设 $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)}

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 平稳分布

ON THIS PAGE