👨🏿 👒 🙍🏻 马尔可夫链条简介 🧑🏾‍🤝‍🧑🏼 🎶 🚣🏽

1998年，劳伦斯·佩奇（Lawrence Page），谢尔盖·布林（Sergey Brin），拉吉夫·莫特瓦尼（Rajiv Motwani）和特里·维诺格勒（Terry Vinograd）发表了文章“ PageRank引文排名：将订单推向网络”，描述了现在著名的PageRank算法，该算法成为Google的基础。在不到二十年的时间里，Google成为了一个巨头，尽管它的算法已经发展了很多，但PageRank仍然是Google排名算法的“象征”（尽管只有很少的人能真正说出它在当今算法中所占的权重）。

从理论的角度来看，有趣的是，PageRank算法的标准解释之一是基于简单但基本的马尔可夫链概念。从本文中，我们将看到马尔可夫链是用于随机建模的强大工具，可对任何数据科学家有用。特别是，我们将回答以下基本问题：什么是马尔可夫链，它们具有哪些良好特性，在它们的帮助下可以做什么？

简短评论

在第一部分中，我们给出了理解马尔可夫链所需的基本定义。在第二部分中，我们考虑有限状态空间中马氏链的特殊情况。在第三部分中，我们考虑了马尔可夫链的一些基本性质，并通过许多小例子说明了这些性质。最后，在第四部分中，我们将Markov链与PageRank算法相关联，并通过人工示例了解如何使用Markov链对图的节点进行排名。

注意事项 要了解此职位，需要了解概率和线性代数的基础知识。特别是，将使用以下概念：条件概率，特征向量和全概率公式。

什么是马尔可夫链？

随机变量和随机过程

在介绍马尔可夫链的概念之前，让我们简要回顾一下概率论的基本但重要的概念。

首先，在数学语言之外， 随机变量 X是由随机现象的结果确定的数量。其结果可能是数字（或“数字的相似度”，例如向量）或其他东西。例如，我们可以定义随机变量作为掷骰的结果（数字）或掷硬币的结果（不是数字，除非我们将“ eagle”指定为0，而将“ tails”指定为1）。我们还提到随机变量可能结果的空间可以是离散的或连续的：例如，正常随机变量是连续的，泊松随机变量是离散的。

此外，我们可以将随机过程 （也称为随机过程）定义为由集合T索引的一组随机变量，该变量通常表示不同的时间点（在下文中我们将假设这一点）。两种最常见的情况：T可以是一组自然数（具有离散时间的随机过程），也可以是一组实数（具有连续时间的随机过程）。例如，如果我们每天扔硬币，我们将设置一个具有离散时间的随机过程，而交易所期权的不断变化的值将设置一个具有连续时间的随机过程。在不同时间点的随机变量可以彼此独立（例如掷硬币的例子），或者具有某种依赖性（例如带有期权价值的例子）；此外，它们可以具有连续或离散的状态空间（在每个时间点可能的结果空间）。

不同类型的随机过程（离散/连续的空间/时间）。

马尔可夫财产和马尔可夫链

有众所周知的随机过程族：高斯过程，泊松过程，自回归模型，移动平均模型，马尔可夫链等。这些个案中的每一个都有某些属性，使我们可以更好地探索和理解它们。

马尔可夫性质是极大简化随机过程研究的性质之一。如果我们用一种非常非正式的语言来解释它，那么Markov属性就会告诉我们，如果我们知道某个给定时刻某个随机过程所获得的价值，那么我们将不会收到有关该过程的未来行为的任何其他信息，而会收集有关其过去的其他信息。用一种更数学的语言：在任何时候，具有给定当前状态和过去状态的流程的未来状态的条件分布仅取决于当前状态，而不取决于过去状态（ 缺少内存的属性）。具有Markov属性的随机过程称为Markov过程 。

马尔可夫属性意味着，如果我们知道给定时刻的当前状态，则不需要从过去收集的关于未来的任何其他信息。

基于此定义，我们可以公式化“具有离散时间的齐次马尔可夫链”的定义（以下为简单起见，我们将它们称为“马尔可夫链”）。 马尔可夫链是具有离散时间和离散状态空间的马尔可夫过程。因此，马尔可夫链是离散的状态序列，每个状态都取自满足Markov属性的离散状态空间（有限或无限）。

在数学上，我们可以将马尔可夫链表示如下：

在每个时刻，过程从离散集合E中获取其值，从而

然后，马尔可夫属性暗示我们有

再次注意，最后一个公式反映了这样一个事实：对于时间顺序（我现在所在的位置以及我之前所在的位置），下一个状态（我将在下一个位置）的概率分布取决于当前状态，而不取决于过去的状态。

注意事项 在这篇介绍性文章中，我们决定仅讨论具有离散时间的简单齐次马尔可夫链。但是，也有不均匀（随时间变化）的马尔可夫链和/或连续时间链。在本文中，我们将不考虑模型的这种变化。还要注意的是，上述对马尔可夫性质的定义已大大简化：真正的数学定义使用了过滤的概念，这远远超出了我们对模型的介绍。

我们刻画马尔可夫链的随机动力学

在上一小节中，我们熟悉了与任何马尔可夫链相对应的一般结构。让我们看看我们需要为这种随机过程设置一个特定的“实例”。

首先，我们注意到难以完全确定不满足马尔可夫性质的离散时间随机过程的特征：给定时间点的概率分布可能取决于过去和/或将来的一个或多个时刻。所有这些可能的时间依赖性都可能使流程定义的创建复杂化。

但是，由于具有马尔可夫特性，因此确定马尔可夫链的动力学非常简单。的确如此。我们只需要确定两个方面： 初始概率分布 （即，在时间n = 0时的概率分布），表示为

以及转移概率矩阵 （它为我们提供了概率n + 1的状态是任意一对状态在时间n的另一个状态的下一个概率），表示为

如果这两个方面都是已知的，那么就可以清楚地定义过程的全部（概率）动态。实际上，然后可以循环计算该过程的任何结果的概率。

示例：假设我们想知道过程的前三个状态具有值（s0，s1，s2）的概率。也就是说，我们要计算概率

在这里，我们应用总概率公式，该公式表示获得（s0，s1，s2）的概率等于获得第一个s0的概率乘以获得s1的概率，假设我们先前收到的s0乘以获得s2的概率，同时考虑到以下事实：我们得到的顺序是s0和s1。从数学上讲，这可以写成

然后，根据马尔可夫假设确定了简化方法。实际上，在长链的情况下，我们获得了后者状态的强烈条件概率。但是，在马尔可夫链的情况下，我们可以利用以下事实简化此表达式：

这样

由于它们充分表征了过程的概率动力学，因此许多复杂事件只能基于初始概率分布q0和过渡概率矩阵p来计算。还值得一提的是另一种基本联系：在时间n +1处的概率分布的表达式，相对于在时间n处的概率分布的表达式

有限状态空间中的马尔可夫链

矩阵和图形表示

在这里，我们假设集合E具有有限数量的可能状态N：

然后，可以将初始概率分布描述为大小为N 的行向量 q0，并将转移概率描述为大小为N乘N的矩阵p，这样

这种表示法的优点在于，如果我们用行向量qn表示步骤n中的概率分布，从而指定其分量

然后保留简单的矩阵关系

（这里我们将不考虑证明，但是复制它非常简单）。

如果我们将描述给定时间阶段的概率分布的右侧行向量乘以过渡概率矩阵，则可以得到下一时间阶段的概率分布。

因此，正如我们所看到的，从给定阶段到下一阶段的概率分布的过渡被简单定义为初始步的概率行向量与矩阵p的右乘。另外，这意味着我们有

有限状态空间中的马尔可夫链的随机动力学可以很容易地表示为归一化的定向图，使得该图的每个节点都是一个状态，并且对于每对状态（ei，ej），如果p（ei，ej ）> 0。那么边缘值将是相同的概率p（ei，ej）。

示例：我们网站的读者

让我们用一个简单的例子说明所有这些。考虑虚拟访问者的日常行为。每天他有3种可能的状态：读者当天不访问该站点（N），读者访问该站点，但是不阅读整个帖子（V），并且读者访问该站点并阅读了整个帖子（R）。因此，我们具有以下状态空间：

假设在第一天，该读者有50％的机会仅访问该网站，并有50％的机会访问该网站并阅读至少一篇文章。然后，描述初始概率分布（n = 0）的向量如下所示：

还可以想象观察到以下概率：

当读者一天不访问时，第二天不访问的可能性为25％，仅访问他的可能性为50％，阅读并阅读该文章的可能性为25％
当读者有一天访问该网站但没有阅读时，则他第二天有50％的机会再次访问该网站并且不阅读该文章，而他有50％的机会访问并阅读该文章
当读者在同一天访问并阅读文章时，第二天有33％的机会不登录（我希望这篇文章不会有这种效果！） ，仅登录该网站的机会为33％，再次访问并阅读该文章的机会为33％

然后，我们有以下转换矩阵：

从上一节中，我们知道如何为该读者计算第二天每种状态的概率（n = 1）

该马尔可夫链的概率动力学可以用图形表示如下：

以马尔可夫链图的形式进行演示，以模拟我们发明的访问者的行为。

马尔可夫链的性质

在本节中，我们仅讨论马尔可夫链的一些最基本的特性或特征。我们将不涉及数学细节，但将简要概述使用马尔可夫链必须研究的有趣点。如我们所见，在有限状态空间的情况下，马尔可夫链可以表示为图。将来，我们将使用图形表示来解释一些属性。但是，请不要忘记，这些属性不一定限于有限状态空间的情况。

可分解性，周期性，不可撤销性和可恢复性

在本小节中，让我们从表征状态或整个马尔可夫链的几种经典方法开始。

首先，我们提到马尔可夫链是不可分解的，如果有可能从任何其他状态到达任何状态（没有必要在一个时间步长内）。如果状态空间是有限的，并且链可以表示为图，那么可以说不可分解的马尔可夫链的图是强连通的（图论）。

不可分解性（不可还原性）的说明。 左边的链条不能缩短：从3或4我们不能变成1或2。右边的链条（增加一个边缘）可以缩短：每个状态都可以彼此到达。

如果状态离开周期后返回状态时，时间步长是k的倍数，则该状态具有周期k（k是返回路径所有可能长度的最大公因数）。如果k = 1，则他们说该状态是非周期性的，并且如果其所有状态都是非周期性的，则整个马尔可夫链都是非周期性的。在不可约马尔可夫链的情况下，我们还可以提到，如果一个状态是非周期性的，那么所有其他状态也是非周期性的。

周期性属性的说明。 左侧的链是周期性的，其中k = 2：离开任何状态时，返回状态始终需要2的倍数步数。右侧的链的周期为3。

如果在离开某个状态时我们永远不会返回该状态，则该状态是不可撤销的 。相反，如果我们知道离开某个状态后我们可以在将来以1的概率返回该状态（如果该状态不可撤销），则该状态被认为是可返回的。

返回/不可撤销属性的说明。 左侧的链具有以下属性：1、2和3是不可撤消的（当离开这些点时，我们不能绝对确定我们将返回到它们），周期为3，4和5是可返回的（当离开这些点时，我们完全可以确定），有一天我们将返回到它们），周期为2。右侧的链条具有另一个肋骨，使整个链条可恢复且非周期性。

对于返回状态，我们可以计算平均返回时间，这是离开状态后的预期返回时间 。请注意，即使返回的概率为1，这也不意味着预期的返回时间是有限的。因此，在所有返回状态中，我们可以区分正返回状态 （预期返回时间有限）和零返回状态 （预期返回时间无限）。

平稳分布，边际行为和遍历

在本小节中，我们将考虑表征由马尔可夫链描述的（随机）动力学某些方面的属性。

如果满足以下表达式，则状态空间E上的概率分布π称为平稳分布。

既然我们有

则平稳分布满足表达式

根据定义，平稳概率分布不会随时间变化。也就是说，如果初始分布q是固定的，则在随后的所有时间阶段它都是相同的。如果状态空间是有限的，则可以将p表示为矩阵，将π表示为行向量，然后得到

这再次表达了一个事实，即固定概率分布不会随时间变化（如我们所见，将右边的概率分布乘以p可让我们计算下一时间的概率分布）。请记住，当且仅当状态之一为正回报时，不可分解的马尔可夫链才具有固定的概率分布。

与平稳概率分布有关的另一个有趣的属性如下。如果链为正收益（即其中存在平稳分布）且为非周期性，那么无论初始概率是多少，随着时间间隔趋于无穷大，链的概率分布会收敛：他们说链具有极限分布 ，仅此而已，作为固定分布。通常，可以这样写：