03：Markov过程和Markov链

Markov过程和Markov链

1 Markov过程

1.1 定义

对于一个随机过程$\{\xi (t), t\in T\}$，如果$\forall m+1$时刻，满足

$$f_{t_{m+1}|t_1,\dots,t_m}(x_{m+1}|x_1, \dots,x_m) = f_{t_{m+1}|t_m}(x_{m+1}|x_m)$$

即随机过程下一个时刻只与现在这个时刻有关，与过去都没有关系，这样的随机过程就叫做Markov过程。

1.2 性质

（1）Markov过程的有限维PDF写作

$$f_{t_1,\dots, t_m}(x_1,\dots,x_m)=f_{t_m|t_{m-1}}(x_m|x_{m-1})\cdots f_{t_2|t_1}(x_2|x_1)f_{t_1}(x_1)$$

（2）对于一个Markov过程，它的反向

$$f_{t_n|t_{n+1},\dots,t_{n+k}}(x_n|x_{n+1},\dots,x_{n+k})=f_{t_n|t_{n+1}}(x_n|x_{n+1})$$

也具有Markov性。

（3）未来两个时刻的分布

$$f_{t_1,t_3|t_2}(x_1,x_3|x_2)=f_{t_1|t_2}(x_1|x_2)f_{t_3|t_2}(x_3|x_2)$$

即马尔可夫性等价于条件独立性。

2 Markov链

2.1 定义

（1）对于一个离散的随机序列$\{X(n); n\geq 0\}$，给出一系列状态$i_0,i_1,\dots,i_n,i_{n+1}\in S$，S称为状态空间，则有

$$\begin{aligned} &P[X(n+1)=i_{n+1}|X(0)=i_0, X(1)=i_1,\dots,X(n)=i_n] \\ &=P[X(n+1)=i_{n+1}|X(n)=i_n] \end{aligned}$$

即未来一个时刻的状态只与现态有关，那么则称$\{X(n);n\geq 0\}$为Markov链。

（2）对于一个Markov链$\{X(n);n\geq 0\}$在n时刻有

$$P(X(n+1)=j|X(n)=i)\overset{def}{=}p_{ij}(n)$$

这个概率称为一步转移概率。如果对于$\forall i,j\in S$，有$p_{ij}(n)=p_{ij}$，即与时刻n无关，则称Markov链为齐次的Markov链。

（3）我们可以把所有的一步转移概率都写出来，即列出所有的$P_{ij},\forall i,j\in S$，这样可以构成一个矩阵，

$$\begin{bmatrix} p_{11} & p_{12} & \cdots & p_{1n} \\ p_{21} & p_{22} & \cdots & p_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ \end{bmatrix}$$

这个矩阵就叫做一步转移概率矩阵。矩阵的行代表目前处在其中一个状态$i$，下一步转移到了另外一个状态$j$的概率，列代表固定了下一个状态$j$，从某个状态$i$转移到这个状态的概率。注意固定矩阵的一行，其所有列的和为1。

$$\sum_{j}p_{ij}=1$$

(4) 对于一个齐次的Markov链，可以用状态转移图来表示

graph LR
A[1]
B[2]
C[3]
D[4]

B --1/3---> A
A --1--> A
B --1/3--> B
B --1/3---> C
C --1/3---> B
C --1/3--> C
C --1/3---> D
D --1--> C

上面的状态转移图代表的转移概率矩阵就是

$$\begin{bmatrix} 1 & 0 & 0 & 0 \\ 1/3 & 1/3 & 1/3 & 0 \\ 0 & 1/3 & 1/3 & 1/3 \\ 0 & 0 & 1 & 0 \end{bmatrix}$$

注意到其中状态1一旦进入之后，就会以概率1转移到自己，也就是说进入状态1之后就出不来了，这个状态被称为吸收壁。而在状态4中，一旦进入状态4，就会以概率1转移到状态3，也就是说进入状态4就会被反射出去，这个状态被称为反射壁。

（5）对于齐次Markov链，其m步转移概率为$p_{ij}^{(m)}=P[X(n+m)=j|X(n)=i]$，其构成的矩阵

$$P^{(m)} = \left(p_{ij}^{(m)}\right)$$

称为Markov链的m步转移概率矩阵。

对于0步转移的特殊情况，规定

$$p_{ij}^{(0)}= \begin{cases} 1\quad i=j \\ 0\quad i\neq j \end{cases}$$

2.2 定理与性质

（1）m步转移概率矩阵是一步转移概率矩阵的m次幂。
证明：由Chapman-Kolmogrov方程
对于齐次Markov链，我们有

$$p_{ij}^{(m+r)} = \sum_{k}p_{ik}^{(m)}p_{kj}^{(r)}$$

如果将求和展开

$$\begin{aligned} p_{ij}^{(m+r)} &= \sum_{k}p_{ik}^{(m)}p_{kj}^{(r)} \\ &=p_{i1}^{(m)}p_{1j}^{(r)}+p_{i2}^{(m)}p_{2j}^{(r)}+\cdots+p_{in}^{(m)}p_{nj}^{(r)} \\ &=\boldsymbol{p_{i}^{(m)T}}\boldsymbol{p_{j}^{(r)}} \end{aligned}$$

发现其就是矩阵相乘时行/列向量的运算，再将$p_{ij}^{(m+r)}$放入矩阵，可以得到

$$\boldsymbol{P^{(m+r)}}=\boldsymbol{P^{(m)}}\boldsymbol{P^{(r)}}$$

则可以递推地推出

$$P^{(m)}=P^{(m-1+1)}=P^{(m-1)}P^{(1)}=\cdots=P^m$$

因为$P^{(1)}=P$，于是得到一个重要结论，m步转移概率矩阵是一步转移概率矩阵的m次幂。

（2）初始分布与绝对分布：我们之前在计算概率的时候，都是条件概率$p_{ij}$，表示在现态为$i$，下个状态为$j$的概率，如果我们要知道无条件概率，那么需要知道初始状态的概率分布。

初始概率为$p_j=P(X_0=j)$，这些概率组成的集合$\{p_j\}$为初始分布。所有初始概率组成的向量$\vec P(0)=(p_1,p_2,\dots)^T$为初始概率向量。

借助于全概率公式，我们对所有可能初始状态计算条件概率，得到

$$\begin{aligned} p_j(n)&=\sum_{i}P(x_n=j|x_0=i)P(x_0=i) \\ &=\sum_{i}p_{ij}^np_i \end{aligned}$$

算出来的无条件概率称之为绝对概率$p_j(n)=P(X_n=j)$，这些概率组成的集合$\{p_j(n)\}$为绝对分布。所有绝对概率组成的向量$\vec P(n)=(p_1(n),p_2(n),\dots)^T$为绝对概率向量。

注意到n时刻的绝对概率分布也可以由$n-1$时刻的绝对概率分布得到，即

$$\begin{aligned} p_j(n)&=\sum_i P(x_n=j|x_{n-1}=i)P(x_{n-1}=i)\\ &=\sum_{i}p_i(n-1)p_{ij} \end{aligned}$$

把求和展开之后，同样也可以写成向量相乘的形式

$$\begin{cases} \vec P^T(n) =\vec P^T(0)\times \vec P^{(n)}\quad 向量\times 转移矩阵\\ \vec P^T(n) = \vec P^T(n-1)\times \vec P\quad 向量\times 转移矩阵 \end{cases}$$

（3）有限维概率分布
设$\{X_n, n\in T\}$，其状态为$i_1,\dots,i_n\in S$，对$\forall i\in S$有

$$\begin{aligned} P\{X_1=i,\dots X_n=i_n\}&=\sum_{i}P(X_n=i_n|X_{n-1}=i_{n-1})\cdots P(X_2=i_1|X_1=i) P(X_0=i)\\ &=\sum_{i}P(X_0=i)\prod_{j=1}^nP(X_j=i_j|X_{j-1}=i_{j-1})\\ &=\sum_{i}p_i\prod_{j=1}^n(P_{i_{j-1}i_j}) \end{aligned}$$

其中$i_0=i$。上述式子最后的连续乘法代表着相差一个时刻($j-1$和$j$)的转移，即一步转移概率。

一般随机过程的全部特征，可以由有限维分布表征出来，但很难求解。从上述公式看出，Markov链的有限维分布由初始概率和一步转移概率决定，比起一般的随机过程，问题得到了简化。