强化学习的数学基础之马尔可夫链（Markov Chain）

马尔可夫链（Markov Chain）是由马尔可夫性质推导出来的一种重要的概率模型。马尔科夫链是一种离散时间的随机过程，作为现实世界的统计模型，有很多应用。在热力学、统计力学、排队理论、金融领域等都有重要的应用价值。

作为一种离散时间的随机过程，与其对应的模型是马尔可夫过程（Markov Process），这是一种连续时间随机过程的模型。本节将主要介绍马尔科夫链。

一、随机过程的简单理解

随机过程研究的是在时间维度上的事件发生的规律，也就是说这里有两个东西存在，一个是时间，一个是事件。换句话说，我们希望研究每一个时间点上某个事件发生的规律，同时还研究在某一个时间点发生某个事件后，下一个时间点可能会发生什么。显然，时间这个东西可以有两种描述方式，一种是连续时间，一种是离散时间。连续时间是指将时间当作可以无限分割的连续变量研究，而离散时间则将时间当作分离的时间点研究。因此，对于随机过程来说，也分成连续时间随机过程与离散时间的随机过程。而马尔科夫链就是一种离散时间的随机过程。

二、马尔科夫链的数学形式（Markov Chain）

前面说了，马尔科夫链是由马尔可夫性质推导出来的一种概率模型。因此，马尔可夫链最基本的假设就是不管当前的状态是怎么来的，它下一个状态都将只取决于当前的状态是什么，在此之前发生了什么都不会影响到下一个状态。而状态之间的变化概率，也就是说当前状态发生之后，下一个状态会是什么这个问题，马尔科夫链使用的是状态转移概率矩阵来描述。

因此，对于马尔科夫链的数学描述，我们可以这样表示。 首先，我们有一个状态空间$S$，它是所有可能的状态集合。 其次，我们有一个状态转移概率矩阵$P$，这个矩阵中的每一个元素$p_{ij}$是指从状态$i$转移到状态$j$的概率。

现在我们假设我们的马尔科夫链是一个随机变量的序列（可以理解为随机变量的集合，按照时间顺序排列，每一个随机变量都表示那个时间点上事件的发生情况）：$X_0,X_1,\cdots$ 那么，马尔科夫链具有如下性质：

Pr(X_{n+1}=x|X_1=x_1,X_2=x_2,...,X_n=x_n)=Pr(X_{n+1}=x|X_n=x_n)=

解释一下就是，当随着时间的过去已经发生了一系列的事件$X_1=x_1,X_2=x_2,...,X_n=x_n$，那么下一个时间点发生的事情的概率将只取决于当前时间点的情况。之前发生啥都不重要了。因此，我们可以使用状态转移概率矩阵来描述这个性质了。因为，我们只需要有一个矩阵，其行是各个可能的状态，而列也是各个可能的状态，里面每一个元素都是一个状态转移到另一个状态的概率，至此就可以完全用来描述马尔可夫链了。

三、一个简单的例子

如下图所示，只有状态空间里只有A和B两个事件：

那么，我们就可以用如下的一个状态转移概率矩阵来描述这个事件发生的情况了。

\begin{bmatrix}
0.3 & 0.7 \\
0.9 & 0.1
\end{bmatrix}

它的第一行的含义表示当发生了A事件之后，下次发生A的概率是0.3，发生B的概率是0.7。第二行表示发生了B之后，下次发生A的概率是0.8，发生B的概率是0.2。至于是由哪些事件发生导致的A和B的出现，不需要关心。

四、马尔科夫链的重要注意事项

需要注意的是上述概率转移矩阵指的是一次转移的概率矩阵。但是状态转移可能是多个步骤。也就是说初始状态假设为A，那么经过两个时间点之后，变成A和B的概率是多少，这个结果并不是一次转移矩阵的结果，而是需要经过计算得到。但是计算也很简单，例如还是上述转移概率矩阵，那么2步骤的转移概率结果就是：

\begin{bmatrix}
0.72 & 0.28 \\
0.36 & 0.64
\end{bmatrix}

计算很简单，例如A状态2步骤之后还是A的概率就是$0.3 \times 0.3+0.7 \times 0.9=0.72$，也就是第一行第一列的结果了。

除了多步骤的转移概率矩阵外，还需要注意的是极限平稳状态。也就是说某些马尔科夫链经过足够次数转移之后会达到一个稳定的转移状态。意思就是k-步骤转移概率再往前计算也不会有变化。这个性质的应用是帮助我们预测的。例如城市人口和农村人口的互相转移有一定概率，但是经过足够多时间后，这个转移概率就会稳定，也就意味着如果我们知道现在有多少城市人口和农村人口，那么如果有一个固定的转移概率矩阵人口会互相转化，我们很容易知道未来某个时间点之后农村和城市人口数就大致不会变化了。当然，并不是所有的马尔科夫链都能达到平稳状态，这个与是否有周期性，且是否任意状态联通相关，但是可以理论证明。

知道了上面这些内容我们就知道，如果掌握了状态转移概率矩阵，我们就可以知道这个马尔可夫链的所有信息，也就可以预测未来了。但是，实际中，状态转移概率矩阵的求解是最麻烦的。因为，我们几乎没有任何理论可以直接求解。所以只能通过估计的方法来近似计算。一般来说，已经有很多方法可以解决这种问题，包括Metropolis–Hastings算法（马尔科夫蒙特卡洛MCMC方法的一种）等（参考：Efficient algorithm to compute Markov transitional probabilities for a desired PageRank论文）。这也是解决实际问题中最重要的困难之一。

参考： https://en.wikipedia.org/wiki/Markov_chain https://brilliant.org/wiki/markov-chains/ https://www.win.tue.nl/~iadan/que/h3.pdf https://zh.wikipedia.org/wiki/%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E9%93%BE