介绍

从理论的角度来看，PageRank算法的一种常见解释依赖于Markov链的简单但基本的数学概念。在本文中，我们将看到马尔可夫链是用于随机建模的强大工具，它对任何数据科学家都是有用的。本文将回答一些基本的问题，例如:什么是马尔科夫链?它们有什么好的性质?

在第一节中，我们将给出理解马尔科夫链的基本定义。在第二节中，我们将讨论有限状态空间马尔可夫链的特殊情况。在第三节中，我们将讨论马尔可夫链的一些基本性质，并用许多小例子来说明这些性质。最后，在第四节中，我们将使用PageRank算法进行链接，并在示例中查看如何使用Markov链对图中的节点进行排序。

注意。本文要求概率和线性代数的基础知识。

什么是马尔可夫链？

随机变量和随机过程

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

首先，在非数学术语中，随机变量 X是一个变量，其值被定义为随机现象的结果。该结果可以是数字（或“数字类似”，包括向量），也可以不是。例如，我们可以将随机变量定义为掷骰子的结果(数字)以及投掷硬币的输出(（不是数字，除非您指定例如0到正面和1到背面）。还要注意，随机变量的可能结果的空间可以是离散的，也可以是连续的：例如，正态随机变量是连续的，而泊松随机变量是离散的。

然后我们可以定义一个随机过程作为由集合T索引的随机变量的集合，其通常表示不同的时间瞬间（我们将在下面假设）。两种最常见的情况是：T是自然数集（离散时间随机过程）或T是实数集（连续时间随机过程）。例如，每天翻转硬币定义了离散时间随机过程，而股票市场期权价格的连续变化定义了连续时间随机过程。不同时刻的随机变量可以彼此独立（硬币翻转示例）或以某种方式依赖（股票价格示例），也可以具有连续或离散的状态空间（每个时刻可能结果的空间） ）。

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

马尔可夫性质和马尔可夫链

存在一些众所周知的随机过程：高斯过程，泊松过程，自回归模型，移动平均模型，马尔可夫链等。

研究随机过程的一个特性是“马尔可夫性质”。当一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态；换句话说，在给定现在状态时，它与过去状态（即该过程的历史路径）是条件独立的，那么此随机过程即具有马尔可夫性质。具有马尔可夫性质的过程通常称之为马尔可夫过程。

Markov性质表示在给定的时间步长并且知道当前状态时，我们不会通过收集关于过去的信息来获得关于未来的任何额外信息。

基于先前的定义，我们现在可以定义“齐次离散时间马尔可夫链”（为了简单起见，将在下文中将其表示为“马尔可夫链”）。马尔可夫链是一个具有离散时间和离散状态空间的马尔可夫过程。所以，马尔可夫链是状态的离散序列，每个状态都来自于一个离散的状态空间，它遵循马尔可夫性质。

在数学上，我们可以表示马尔可夫链

在每个时刻，过程在离散集E中取其值，使得

那么

再次注意，最后这个公式表达了这样一个事实:对于给定的历史状态(现在的位置和以前的位置)，下一个状态(我接下来要去的位置)的概率分布只取决于当前状态，而不取决于过去的状态。

请注意。本文只描述基本的齐次离散时间马尔可夫链。然而，也存在非齐次(时间相关)和/或时间连续马尔可夫链。我们不会在下面讨论模型的这些变体。还请注意，上面给出的马尔可夫性质的定义是极其简化的:真正的数学定义涉其他概念，这远远超出了本文简单介绍的范围。

马尔可夫链的随机动态

在前面的小节中，我们介绍了一个由任意马尔可夫链匹配的通用框架。现在让我们来看看我们需要什么来定义这种随机过程的特定"实例"

首先注意，不验证马尔可夫性质的离散时间随机过程的完全描述可能是痛苦的：给定时间的概率分布可能取决于过去和/或未来的一个或多个时刻。所有这些可能的时间依赖性使得对过程的任何适当描述可能是困难的。

然而，由于马尔科夫性质，马尔科夫链的动态非常容易定义。实际上，我们只需要指定两件事:初始概率分布(即n=0时刻的概率分布)

和一个转移概率kernel (它给出了任意一对状态在n+1时刻的状态在n时刻成功的概率)

通过已知的前两个对象，可以很好地定义过程的完整（概率）动态。实际上，可以以循环方式计算任何实现过程的概率。

例如，假设我们想要知道过程的前3个状态的概率是（s0，s1，s2）。所以，我们想要计算概率

在这里，我们使用全概率定理。在数学上，它可以写成

然后给出了马尔可夫假设的简化形式。确实，我们可以用长链来获得最后几个状态的条件概率。然而，在马尔科夫的情况下我们可以用它来简化这个表达式

这样我们就有了

由于它们完全表征了过程的概率动态，因此可以仅基于初始概率分布q0和转移概率核p来计算许多其他更复杂的事件。最后一个需要给出的基本关系是n+1时刻的概率分布相对于n时刻的概率分布的表达式

有限状态空间马尔可夫链

矩阵和图表示

我们假设在E中我们有可能的N个有限数：

初始概率分布可以由大小为N 的行向量 q0 描述，并且转移概率可以由大小为N×N的矩阵p来描述，使得

这种表示法的优点是，如果我们注意到在步骤n中用原始向量qn表示概率分布，使得它的分量由下式给出：

然后，简单矩阵关系保持不变

当右侧乘以表示给定时间步的概率分布的行向量乘以转移概率矩阵时，我们获得下一时间步的概率分布

因此，我们在这里看到，将给定步的概率分布演变为下一步骤就像将初始步的行概率向量乘以矩阵p一样简单。这也意味着我们拥有

有限状态空间马尔可夫链的随机动态可以很容易地表示为一个有值的有向图，图中的每个节点都是一个状态，对于所有状态对(ei,ej)，存在一条从ei到ej的边，如果p(ei,ej)>0。这条边的值就是相同的概率p(ei,ej)

示例：

我们举一个简单的例子来说明这一切。考虑虚构的数据科学读者的日常行为。对于每一天，有3种可能的状态：读者今天不访问TDS（N），读者访问TDS但没有阅读完整帖子（V）和读者访问TDS并阅读至少一篇完整帖子（R）。所以，我们有以下状态空间

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

再想象一下，观察到的概率如下:

如果读者不是每天访问TDS，那么第二天他仍然有25%的机会不访问TDS, 50%的机会只访问TDS, 25%的机会访问和阅读TDS当读者在没有阅读的情况下访问TDS时，有50％的机会访问和阅读，有50％的机会在第二天没有阅读的情况下再次访问，当读者每天访问和阅读时，他有33%的机会第二天不访问，33%的机会只访问和34%的机会再次访问和阅读

然后，我们有下面的转换矩阵

根据前面的小节，我们知道如何为这个读者计算第二天每种状态的概率(n=1)

最后，该马尔可夫链的概率动态可以用图形表示如下

马尔可夫链的图形表示模拟我们虚构的TDS阅读行为

马尔可夫链性质

在本节中，我们仅提供一些基本的马尔可夫链属性或特征。我们的想法不是深入研究数学细节，而是更多地概述使用马尔可夫链时需要研究的兴趣点。正如我们已经看到的那样，在有限状态空间的情况下，我们可以将马尔可夫链描绘成图形，注意我们将使用图形表示来说明下面的一些性质。但是，应该记住，这些性质不一定限于有限状态空间情况。

可还原性，周期性，瞬变性和重现性

在这一小节中，让我们从描述状态或整个马尔可夫链的一些经典方法开始。

首先，我们说一个马尔可夫链是不可约的，如果它可以从任何其他状态到达任何状态(不一定是在一个时间步)。如果状态空间是有限的，链可以用图表示，那么我们可以说不可约马尔可夫链的图是强连通的(图论)。

不可约性的说明。左边的链不是不可约的:从3或4不能得到1或2。右边的链(添加了一条边)是不可约的:可以从任何其他状态到达每个状态。

状态具有周期k，如果在离开它时，任何返回到该状态需要多个k个时间步（k是所有可能的返回路径长度的最大公约数）。如果k = 1，则状态被认为是非周期性,如果整个马尔可夫链的所有状态都是非周期性的，那么整个马尔可夫链就是非周期性的。对于不可约的马尔可夫链，我们还可以提到这样的事实：如果一个状态是非周期性的，则所有状态都是非周期性的。

周期性的说明。左边的链是2周期的:当离开任何状态时，它总是需要2步的倍数才能回到它。右边的链是3周期的。

如果当我们离开这个状态时，我们永远不会返回它的非零概率状态是瞬变的。相反，如果我们知道我们将在离开之后以概率1返回该状态（如果它不是瞬变的），则状态是重现的。

重现/瞬变性质的例证。左边的链是这样的：1,2和3是瞬变的（当离开这些点时我们不能完全确定我们会回到它们）和3是周期性的而4和5是重现的（当离开这些时）我们绝对肯定我们会在某个时间回到他们身上，2周期性的。右侧的链条还有一条边缘，使整条链重现并且非周期性。

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

平稳分布，限制行为和遍历性

在本小节中，我们将讨论表征马尔可夫链描述的（随机）动态的某些方面的性质。

一个概率分布在状态空间Eπ是一个平稳分布验证

我们有

然后进行平稳分布验证

根据定义，一个平稳的概率分布是这样的，它不会随着时间的推移而变化。如果初始分布q是平稳分布那么它在以后的时间步长中都是不变的。如果状态空间是有限的,则p可以用矩阵表示，π可以用原始向量表示，然后我们得到

再一次，它表达了一个事实，一个平稳的概率分布不会随着时间的推移而变化(正如我们看到的，将一个概率分布乘以p就可以计算出下一个时间步的概率分布)。注意，当且仅当不可约马尔可夫链的所有状态都为正重现性时，它的概率分布是平稳的。

另一个与平稳概率分布相关的有趣性质如下。如果链是正重现性(因此存在一个平稳分布)且非周期的，那么无论初始概率是多少，当时间步长趋于无穷时，链的概率分布是收敛的:链的极限分布就是平稳分布。一般情况下可以写成

让我们再次强调这样一个事实，即在初始概率分布上没有假设：无论初始设置如何，链的概率分布都会收敛到平稳分布（链的平衡分布）。

最后，遍历性是另一个与马尔可夫链行为相关的有趣性质。如果马尔可夫链是不可约的，那么我们也说这个链是“遍历的”，因为它验证了下面的遍历定理。假设我们有一个从状态空间E到实线的应用程序f(.)(例如，处于每种状态的成本)。我们可以定义使应用程序沿着给定轨迹运行的平均值(时间平均值)。对于第n项，它表示为

我们还可以计算应用f除以集合E的均值，用平稳分布(空间均值)表示

遍历定理告诉我们，当轨迹变得无限长时，时间均值等于空间均值(由平稳分布加权)。可以写出遍历性质

换句话说，它的意思是，在极限情况下，轨迹的早期行为可以忽略不计，只有在计算时间平均值时，长期稳态行为才是真正重要的。

回到我们的TDS示例

我们再次考虑我们的TDS阅读器示例。在这个简单的例子中，链明显不可约，非周期性，所有状态都是反复出现的。

为了显示可以用马尔可夫链计算的有趣结果，我们想要查看状态R的平均重现时间（状态“访问和读取”）。换句话说，我们想回答以下问题：当我们的TDS读者访问并读取时，我们平均需要等待多少天，他才会再次访问和阅读?让我们试着直观地了解如何计算这个值。

首先

我们要计算m(R,R),对离开R后到达的第一步进行推理，我们得到

然而，这个表达式需要知道m(N,R)和m(V,R)才能计算m(R,R)这两个量可以用同样的方式表示

因此，我们有3个具有3个未知数的方程，当我们求解该系统时，我们得到m（N，R）= 2.67，m（V，R）= 2.00和m（R，R）= 2.54。状态R的平均重现时间的值则为2.54。因此，我们看到，通过一些线性代数，我们设法计算状态R的平均重现时间（以及从N到R的平均时间以及从V到R的平均时间）。

总结这个例子，让我们看看这个马尔可夫链的平稳分布是什么。为了确定平稳分布，我们必须求解下面的线性代数方程

因此，我们必须找到与特征值1相关的p的左特征向量。解决这个问题，我们得到以下平稳分布

由于链是不可约的非周期的，这意味着，从长远来看，概率分布将收敛于平稳分布(对于任何初始化)。换句话说，不管TDS阅读器的初始状态是什么，如果我们等待足够长的时间,然后随机选择一天，那么我们有一个概率π（N）表示读者不会在这一天访问，和读者访问但不阅读的概率π（V）以及读者访问并阅读的概率π（ R）。为了更好地理解收敛性，让我们看一下下面的图表，它展示了从不同起点开始的概率分布的演变以及(快速)收敛到平稳分布的过程

可视化3个不同初始化概率分布（蓝色，橙色和绿色）向平稳分布（红色）的收敛 一个经典的例子：PageRank算法

在进一步讨论之前，让我们提一下这样一个事实，即我们将为PageRank提供的解释不是唯一可能的解释，原始论文的作者在设计方法时并不一定考虑马尔可夫链。

随机上网的人

PageRank尝试解决的问题如下：我们如何通过使用它们之间的现有链接对给定集合的页面进行排名（我们可以假设此集合已经过滤，例如在某些查询上）？

为了解决这个问题并能够对页面进行排名，PageRank大致如下进行。我们认为上网者在初始时就在其中一个页面上。然后，这个上网者开始随机地导航，通过点击每个页面上的一个链接，该链接指向所考虑的集合的另一个页面（假设不允许链接到该集合之外的页面）。对于给定页面，所有允许的链接都有相同的机会被点击。

我们这里有一个马尔可夫链的设置：页面是不同的可能状态，转换概率是由页面到页面的链接定义的（加权使得在每个页面上所有链接的页面都有相同的机会被选择）。如果我们还假设定义的链是重现正和非周期性的（使用一些小技巧来确保我们满足这个设置），那么在很长一段时间后，“当前页面”概率分布会收敛到稳态分布。因此，无论起始页面如何，经过很长一段时间后，如果我们选择随机时间步长，每个页面都有一个概率作为当前页面。

PageRank背后的假设是，平稳分布中最可能出现的页面也一定是最重要的(我们经常访问这些页面，因为它们接收的链接来自于在此过程中也经常访问的页面)。平稳概率分布定义了每个状态的PageRank值。

一个例子

为了使这一切更加清晰，让我们考虑一个示例。假设我们有一个小网站，其中有7个页面标记为1到7，并且页面之间有链接，如下图所示。

为清楚起见，在前面的表示中没有显示每个转换的概率。然而，由于“导航”应该是纯随机的，可以使用以下简单的规则轻松恢复值:对于具有K个外链的节点(具有K个到其他页面的链接的页面)，每个外链的概率等于1/K。所以,概率转移矩阵由下式给出

其中0.0值已被'.'取代 为了便于阅读。在进一步计算之前，我们可以注意到这个马尔可夫链是不可约的以及非周期性的，因此，在长期运行之后，系统收敛到稳态分布。正如我们已经看到的，我们可以通过求解下面的左特征向量问题来计算这个稳态分布

这样做我们获得了每页的PageRank值（稳态分布的值）

在我们的示例中计算的PageRank值包含7页。

这个小网站的PageRank排名是1> 7> 4> 2> 5 = 6> 3。

最后

最后，让我们再次强调马尔可夫链在处理随机动态时对问题建模的强大作用。由于它们的良好特性，它们被用于各种领域，例如排队理论（优化电信网络的性能），统计(众所周知的“马尔可夫链蒙特卡罗随机变量生成技术是基于马尔可夫链)、生物(生物种群进化的造型),计算机科学(隐马尔可夫模型是信息论和语音识别的重要工具)等。