强化学习的数学基础之马尔可夫链（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两个事件：