马尔科夫链（一）

文章目录

• 马尔科夫链（一）
• • @[toc]
  • 1 马尔可夫链
  • 2 转移概率
  • • 2.1 一步转移
    • 2.2 多步转移
  • 3 C-K方程
  • 4 矩阵运算方法

1 马尔可夫链

定义：设随机过程$X_n(n=0,1,2\dots )$在有限集合内取值，$X_n$的所有可能取值称为状态。定义转移概率
$$p_{n+1}(i,j)=\mathbb{P}(X_{n+1}=j|X_n=i,X_{n-1}=i_{n-1},\dots X_0=i_0)$$
即在随机过程$X_n$的所有历史状态下，$X_{n+1}$的条件概率为$p_{n+1}(i,j)$。如果$n+1$期的状态只与本期$X_n$有关，而与历史状态$X_{n-k}(k=1,2,\dots n)$无关，则称随机过程$X_n$具有马氏性，即
$$p_{n+1}(i,j)=\mathbb{P}(X_{n+1}=j|X_n=i)$$
对于任意时期$n$，若
$$p_{n+1}(i,j)=p_{n+2}(i,j)=p_{n+3}(i,j)=\dots$$

$$\mathbb{P}(X_{n+1}=j|X_n=i)=\mathbb{P}(X_{n+2}=j|X_{n+1}=i)=\dots$$

即条件概率与初始时点无关，则称$X_n$为具有时间齐次性的马尔可夫链，简称时齐性马尔可夫链。后文默认的马尔科夫链都是时齐性的。关于马尔科夫链的链的理解：
$$X_{n+1}\leftarrow X_n\leftarrow X_{n-1}\leftarrow X_{n-2}\dots$$
即$X_{n+1}$只与$X_n$有关，$X_n$只与$X_{n-1}$有关……就如同一个链条，将相邻时期的随机过程$X_n$串联起来。

---

2 转移概率

2.1 一步转移

例：在抽奖试验中，试验结果只有2元与0元，且抽奖成本为1元。设抽中的概率为0.4，为抽中的概率为0.6。某人退出试验的条件是要么身无分文，要么达到一定金额$N$离开。

设$X_n$表示某人$n$次抽奖后的金额，$X_{n+1}$只与$X_n$有关，而与之前的状态$X_{n-1},X_{n-2}\dots X_0$无关，则$X_n$具有马氏性，即
$$\begin{array}{rl}{p}_{n+1}(i,j)=& \mathbb{P}(X_{n+1}=j|X_n=i,X_{n-1}=i_{n-1},\dots X_0=i_0)\\ & \\ =& \mathbb{P}(X_{n+1}=j|X_n=i)\end{array}$$
其中转移概率$p(i,j)$满足
$$p_{n+1}(i,j)=\mathbb{P}(X_{n+1}=j|X_n=i)$$
在$n$次抽奖过程中，有第$i$元变为$i-1$元的概率为
$$p(i,i-1)=\mathbb{P}(X_{n+1}=i-1|X_n=i)=0.6$$
在$n$次抽奖过程中，有第$i$元变为$i+1$元的概率为
$$p(i,i+1)=\mathbb{P}(X_{n+1}=i-1|X_n=i)=0.4$$
则转移概率与停止条件
$$\begin{array}{rl}& p(i,i+1)=0.4,\\ & \\ & p(i,i-1)=0.6,i\in (0,N)\\ & \\ & p(0,0)=p(N,N)=1\end{array}$$
转移概率矩阵为
$$\mathbf{P}=\left[\begin{array}{cccc}p(0,0)& p(0,1)& \dots & p(0,N)\\ p(1,0)& p(1,1)& \dots & p(1,N)\\ ⋮& ⋮& & ⋮\\ p(N,0)& p(N,1)& \dots & p(N,N)\end{array}\right]$$
具体地，当$N=5$时，
$$\mathbf{P}=\left[\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ 0.6& 0& 0.4& 0& 0& 0\\ 0& 0.6& 0& 0.4& 0& 0\\ 0& 0& 0.6& 0& 0.4& 0\\ 0& 0& 0& 0.6& 0& 0.4\\ 0& 0& 0& 0& 0& 1\end{array}\right]$$
其中$p(i,j)$表示$i$状态转移到$j$状态的概率。根据概率的完备性，我们有
$$\begin{array}{rl}& p(i,j)\ge 0\sum _{j}p(i,j)=1\end{array}$$

---

2.2 多步转移

定义从状态$i$到$j$的$m$步转移概率为
$$p^m(i,j)=\mathbb{P}(X_{n+m}=j|X_n=i)$$
其中$p^m(i,j)$表示$m$步转移矩阵${\mathbb{P}}^m$矩阵的$i$行$j$列。事实上，$m$步转移矩阵就是一步转移矩阵$\mathbb{P}$的$m$次幂，即${\mathbb{P}}^m$

proof：以两步转移概率为例，设样本空间$\Omega$的总状态数为$n$，初始状态$X_0=i$，则一步转移状态为$X_1=k,k=1,2,3\dots n $。最后状态$X_2=j$。这里$X_1=k$为中间状态。因为
$$\begin{array}{rl}{p}^2(i,j)=& \mathbb{P}(X_2=j|X_0=i)\\ & \\ =& \sum _{k=1}^n\mathbb{P}(X_2=j,X_1=k|X_0=i)\\ & \\ =& \sum _{k=1}^n\frac{\mathbb{P}(X_2=j,X_1=k,X_0=i)}{\mathbb{P}(X_0=i)}\\ & \\ =& \sum _{k=1}^n\frac{\mathbb{P}(X_2=j,X_1=k,X_0=i)}{\mathbb{P}(X_1=k,X_0=i)}\frac{\mathbb{P}(X_1=k,X_0=i)}{\mathbb{P}(X_0=i)}\\ & \\ =& \sum _{k=1}^n\mathbb{P}(X_2=j|X_1=k,X_0=i)\mathbb{P}(X_1=k|X_0=i)\\ & \\ =& \sum _{k=1}^n\mathbb{P}(X_2=j|X_1=k)\mathbb{P}(X_1=k|X_0=i)\\ & \\ =& \sum _{k=1}^{n}p(i,k)p(k,j)\end{array}$$

于是得到
$$\begin{array}{rl}{p}^2(i,j)& =\sum _{k=1}^{n}p(i,k)p(k,j)\\ & \\ & =p(i,1)p(1,j)+p(i,2)p(2,j)+\cdots +p(i,n)p(n,j)\end{array}$$
即一步转移概率矩阵$\mathbb{P}$自己与自己相乘。

---

3 C-K方程

C-K(chapman-kolmogorov)方程将任意$n+m$步转移概率分解为$m$步转移概率矩阵与$n$步转移概率矩阵的乘积，即
$${\mathbb{P}}^{m+n}(i,j)=\mathbb{P}(X_{m+n}=j|X_0=i)=\sum _k{p}^n(i,k)p^m(k,j)$$
证明略参考相关随机过程书籍。事实上，两步转移是C-K方程的特例，令$m=n=1$得
$$p^2(i,j)=\sum _{k=1}^{n}p(i,k)p(k,j)$$

---

4 矩阵运算方法

由于多步转移概率矩阵计算需要用到矩阵乘法，现介绍以下几种方法：

• 软件计算(Matlab/Python/R/Stata/Octave/Mathmatical等)

大部分软件基本支持数值计算，这也是最快捷的方式。

• 暴力计算

不管运算量级多大，按照运算法则干就完事。但这种方法有些“莽夫”。不推荐

• 相似变换

参考本科教程任意一本线性代数的内容，将需要运算的矩阵作相似变换，相对暴力计算法，将大大提高矩阵的幂运算的效率。

---

-END-

参考文献：

刘次华 . 随机过程(第五版) [M]. 华中科技大学出版社,2014