1,126 次浏览

马尔科夫链基础知识

记得学概率论总会提一个词:独立同分布。也即随机变量的取值互不影响,又服从同一个分布规律。正如我们进行伯努利实验,连续抛一枚骰子,上一个结果不会影响后一个结果,同时每个结果获得的概率都是\(\)\(p=1/6\)\(\)。

像伯努利过程、泊松过程这样的随机过程是无记忆的,未来的状态不会被过去的状态影响。不同于伯努利过程,马尔科夫链则考虑的是过去的状态会影响未来的状态。

马尔科夫链

马尔科夫链的核心假设是此时的状态只与上一个时刻的状态有关,而与其他时刻的状态无关。

对于一个状态空间\(\)\(S = \{1, \ldots, m\}\)\(\),马尔科夫链有转移概率\(\)\(p_{ij}\)\(\)来决定,在时刻\(\)\(n\)\(\),当链\(\)\(X\)\(\)的状态是\(\)\(i\)\(\),链\(\)\(X\)\(\)的下一个状态是\(\)\(j\)\(\)的概率是:\(\)\(p_{ij}=P(X_{n+1}=j | X_n = i)\)\(\)

所以对于马尔可夫链的假设我们可以知道对于此时状态\(\)\(j\)\(\),此前的状态\(\)\((i_0,\ldots, i_{n-1}, i)\)\(\):
\(\)\(P(X_{n+1}=j | X_n=i, X_{n-1}=i_{n-1}, \ldots, X_0=i_0) = P(X_{n+1}=j|X_n=i)=p_{ij}\)\(\)

对于当前状态为\(\)\(i\)\(\)的所有可能的下一个状态\(\)\(j\)\(\),有\(\)\(\sum ^m _{j=1}p_{ij} = 1\)\(\)

对于所有状态的转移概率可以构建一个转移概率矩阵

转移概率矩阵

路径的概率

利用马尔科夫链的性质,我们可以计算未来任何一个给定状态序列的概率。假设我们此时的状态为\(\)\(i_0\)\(\),目标状态为\(\)\(i_n\)\(\):
\(\)\(P(X_0=i_0, \ldots, X_n=i_n)=P(X_n=i_n|X_0=i_0, \ldots, X_{n-1}=i_{n-1})P(X_0=i_0, \ldots, X_{n-1}=i_{n-1})\)\(\)
\(\)\(=\ldots=P(X_0=i_0)p_{i_0 i_1} p_{i_1 i_2}\ldots p_{i_{n-1} i_n}\)\(\)

n步转移概率

给定当前状态\(\)\(i\)\(\),\(\)\(n\)\(\)个时间段后的状态是\(\)\(j\)\(\)的概率:\(\)\(r_{ij}(n)= P(X_n=j|X_0=i)\)\(\)

n步转移概率

计算n步转移概率,可以考虑上述图片,使用全概率公式进行迭代求解(利用马尔科夫链的性质:当前时刻状态只与上一时刻的状态有关):
\(\)\(P(X_n=j|X_0=i)=\sum ^m _{k=1}P(X_{n-1}=k|X_0=i)P(X_n=j|X_{n-1}=k, X_0=i)\)\(\)
\(\)\(=\sum ^m _{k=1}r_{ik}(n-1)p_{kj}\)\(\)
其中,\(\)\(r_{ij}(1)=p_{ij}\)\(\)(上述公式在reference1中存在打印错误)

举个简单的例子:对于学习,当前月考我们进步了,下次进步的概率为0.8(退步概率为0.2),当前月考我们退步了,下次进步概率为0.6(退步概率0.4)画出转移概率图。

转移概率图

写出转移概率矩阵:\(\)\(T=\begin{bmatrix} 0.8 & 0.2\\ 0.6 & 0.4 \end{bmatrix}\)\(\)

n步转移概率矩阵:
\(\)\(1 step: T= \begin{bmatrix} 0.8 & 0.2\\ 0.6 & 0.4 \end{bmatrix}\)\(\)
\(\)\(2 step: T^2=\begin{bmatrix} 0.76 & 0.24\\ 0.72 & 0.28 \end{bmatrix}\)\(\)
\(\)\(3 step: T^3=\begin{bmatrix} 0.752 & 0.248\\ 0.744 & 0.256 \end{bmatrix}\)\(\)
\(\)\(4 step: T^4=\begin{bmatrix} 0.7504 & 0.2496\\ 0.7488 & 0.2512 \end{bmatrix}\)\(\)
\(\)\(5 step: T^5=\begin{bmatrix} 0.7501 & 0.2499\\ 0.7498 & 0.2502 \end{bmatrix}\)\(\)

从n步转移概率矩阵,我们可以看到矩阵乘法的影子,同时可以看到当\(\)\(n \rightarrow \infty\)\(\)时,具有收敛的性质,且不依赖于初始状态(深入可以看reference1)

状态的分类

  1. 可达:即从转态i出去到状态j的转移概率为正
  2. 常返态:从状态i到可达状态j的链都可以回到状态i
  3. 非常返态:从状态i出去到某一可达状态j的链不可以回到状态i
  4. 常返类:常返态i的所有可达状态j构成的集合\(\)\(A(i)\)\(\)

reference
1. Dimitri P.Bertsekas, et al. 《概率论导论》中文第二版