Brief introduction to Markov chains

Definitions, properties and PageRank example.

• Introduction
  1998年，Lawrence Page，Sergey Brin，Rajeev Motwani和Terry Winograd发表了“PageRank引用排名：将秩序引入网络”这篇文章，他们在谷歌的起源上引入了现在着名的PageRank算法。 二十多年后，谷歌已经成为一个巨人，即使算法已经发展很多，PageRank仍然是谷歌排名算法的“象征”（即使很少有人能真正说出它的重量） 占据算法）。

从理论的角度来看，值得注意的是，PageRank算法的一种常见解释依赖于马尔可夫链的简单但基本的数学概念。 我们将在本文中看到马尔可夫链是随机建模的强大工具，对任何数据科学家都有用。 更具体地说，我们将回答基本问题，例如：什么是马尔可夫链，他们有什么好的属性以及可以用它们做些什么？

• Outline
  在第一部分中，我们将给出理解马尔可夫链所需的基本定义。 在第二节中，我们将讨论有限状态空间马尔可夫链的特殊情况。 然后，在第三部分中，我们将讨论马尔可夫链的一些基本属性，并将用许多小例子说明这些属性。 最后，在第四部分中，我们将使用PageRank算法建立链接，并在玩具示例上查看Markov链如何用于对图表的节点进行排名。

What are Markov chains?

• 随机变量和随机过程
  在介绍马尔可夫链之前，让我们先快速提醒一下概率论的一些基本但重要的概念。

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

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

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

• Markov property and Markov chain

存在一些众所周知的随机过程族：高斯过程，泊松过程，自回归模型，移动平均模型，马尔可夫链等。 这些特殊情况各自具有特定属性，使我们能够更好地研究和理解它们。

研究随机过程的一个特性是“马尔可夫属性”。 以非正式的方式，马尔科夫财产说，对于一个随机过程，如果我们知道过程在给定时间所取得的价值，我们将不会通过收集更多知识获得有关该过程未来行为的任何其他信息 关于过去。 在稍微更多的数学术语中，对于任何给定的时间，给定现在和过去状态的过程的未来状态的条件分布仅取决于当前状态而不取决于过去状态（无记忆性质）。 具有马尔可夫属性的随机过程称为马尔可夫过程。
马尔可夫属性表达了这样一个事实，即在给定的时间步骤和了解当前状态，我们将不会通过收集有关过去的信息获得有关未来的任何其他信息。

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

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

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

然后，马尔可夫属性意味着我们可以得到

再次注意，这最后一个公式表达了这样一个事实：对于给定的历史（我现在和我之前的位置），下一个状态（我下一步）的概率分布仅取决于当前状态而不是 过去的国家。

注意。 我们决定在这篇介绍性文章中仅描述基本的同质离散时间马尔可夫链。 然而，也存在不均匀的（时间依赖的）和/或时间连续的马尔可夫链。 我们不会在下面讨论该模型的这些变体。 另请注意，上面给出的马尔可夫属性的定义极为简化：真正的数学定义涉及过滤概念，这远远超出了这种适度引入的范围。

• 表征马尔可夫链的随机动态
  我们在前一小节中介绍了与任何马尔可夫链匹配的一般框架。 现在让我们看看我们需要什么来定义这种随机过程的特定“实例”。

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

但是，由于马尔可夫属性，马尔可夫链的动态非常容易定义。 实际上，我们只需要指定两件事：初始概率分布（即时刻n = 0的概率分布）表示

和一个转移概率核（给出一个状态，在时间n + 1，在时间n，对于任何状态对，在另一个状态下成功）的概率

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

例如，假设我们想要知道过程的前3个状态的概率是（s0，s1，s2）。 所以，我们想要计算概率
在这里，我们使用总概率定律，表明具有（s0，s1，s2）的概率等于具有第一个s0的概率，乘以s1的概率给出我们之前有s0，乘以概率 最后得到s2，我们按顺序排序s0和s1。 在数学上，它可以写
然后出现马尔可夫假设给出的简化。 实际上，对于长链，我们将获得最后状态的重度条件概率。 但是，在Markov案例中，我们可以使用它来简化此表达式

例如我们有

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

有限状态空间马尔可夫链

• Matrix and graph representation
  我们假设在E中我们有可能的N个有限数：
  
  然后，初始概率分布可以由大小为N的行向量q0描述，并且转移概率可以由大小为N×N的矩阵p来描述，使得
  
  这种表示法的优点是，如果我们注意到在步骤n中用原始向量qn表示概率分布，使得它的分量由下式给出：

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

（此处不会详细说明，但可以很容易地恢复）。

当右侧乘以表示给定时间步长的概率分布的行向量乘以转移概率矩阵时，我们获得下一时间步的概率分布。
因此，我们在这里看到，将给定步骤的概率分布演变为下一步骤就像将初始步骤的行概率向量乘以矩阵p一样简单。 这也意味着我们拥有

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

• Example: the Towards Data Science reader

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

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

当读者每天不访问TDS时，他有25％的机会仍然没有访问第二天，50％的机会只访问，25％访问和阅读
当读者在没有阅读一天的情况下访问TDS时，他有50％的机会在第二天没有阅读的情况下再次访问，50％的人访问和阅读
当读者访问并阅读一天时，他有33％的机会在第二天不访问（希望这篇文章不会产生这种效果！），33％的机会只能访问，34％的机会访问并再次阅读
然后，我们有以下转换矩阵

根据前面的小节，我们知道如何为这个读者计算第二天每个州的概率（n = 1）

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

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

Markov Chains properties

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

• 可还原性，周期性，短暂性和复发性
  让我们从这个小节开始，用一些经典的方法来描述一个国家或整个马尔可夫链。
  首先，我们说马尔可夫链是不可简化的，如果它可以从任何其他国家到达任何一个州（不一定是在一个时间步骤）。 如果状态空间是有限的并且链可以用图表来表示，那么我们可以说不可约马尔可夫链的图是强连通的（图论）。
  不可约性属性的例证。 左边的链不是不可简化的：从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由表示为的静态分布（空间均值）加权

然后遍历定理告诉我们，当轨迹变得无限长时的时间平均值等于空间平均值（由静态分布加权）。 可以写出遍历属性

换句话说，它表示，在极限情况下，轨迹的早期行为变得可以忽略不计，只有长期静止行为在计算时间均值时才真正重要。

• Back to our TDS reader example
  我们再次考虑我们的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阅读器”示例。
我们还可以注意到π（R）= 1 / m（R，R）的事实，这在考虑它时有一个非常合乎逻辑的身份（但我们不会在这篇文章中给出更多细节）。

由于链是不可约的和非周期性的，这意味着，从长远来看，概率分布将收敛到静止分布（对于任何初始化）。 换句话说，无论我们的TDS阅读器的初始状态如何，如果我们等待足够长的时间并随机选择一天，那么我们有一个概率π（N），读者今天不会访问，概率为π （五）读者访问但未阅读，读者访问和读取的概率π（R）。 为了更好地掌握这种收敛性，让我们看一下下图，它显示了从不同起点开始的概率分布演变和（快速）收敛到静止分布

可视化3个不同初始化概率分布（蓝色，橙色和绿色）向静止分布（红色）的收敛。

一个经典的例子：PageRank算法

现在是时候回到PageRank了！ 在进一步讨论之前，让我们提一下这样一个事实，即我们将为PageRank提供的解释不是唯一可能的解释，原始论文的作者在设计方法时并不一定考虑马尔可夫链。 但是，以下解释具有很大的优点，可以很好理解。

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

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

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

PageRank背后的假设是，静态分布中最可能的页面也必须是最重要的（我们经常访问这些页面是因为它们从过程中也经常访问的页面接收链接）。然后，静态概率分布为每个状态定义PageRank的值。

• • A toy example
    为了使这一切更加清晰，让我们考虑一个玩具示例。 假设我们有一个小网站，其中有7个页面标记为1到7，并且页面之间有链接，如下图所示。
    
    为清楚起见，在先前的表示中没有显示每个转换的概率。 但是，由于“导航”应该是纯随机的（我们也谈论“随机漫步”），使用以下简单的规则可以轻松恢复这些值：对于具有K个外链的节点（带有K链接到其他节点的页面） （）），每个外链的概率等于1 / K. 因此，概率转移矩阵由下式给出
    
    其中0.0值已被’。'替换以便于阅读。 在进一步计算之前，我们可以注意到这个马尔可夫链是不可约的以及非周期性的，因此，在长期运行之后，系统收敛到静止分布。 正如我们已经看到的，我们可以通过求解下面的左特征向量问题来计算这个静态分布
    
    这样做我们获得了每页的PageRank值（静态分布的值）

在我们的玩具示例中计算的PageRank值包含7页。
这个小网站的PageRank排名是1> 7> 4> 2> 5 = 6> 3。

Takeaways

本文的主要内容如下：

随机过程是随机变量的集合，通常随时间变化索引（索引通常表示离散或连续时间）
对于随机过程，Markov属性表示，鉴于目前，未来的概率与过去无关（该属性也称为“无记忆属性”）
离散时间马尔可夫链是具有离散时间指数的随机过程，并且验证马尔可夫性质
马尔可夫链的马尔可夫性质使得对这些过程的研究更容易处理，并且可以得出一些有趣的显式结果（平均重现时间，平稳分布…）
对PageRank（不是唯一的）的一种可能的解释在于想象一个网页冲浪者，它随机地从一个页面导航到另一个页面，并将诱导的静态分布作为排名因素（粗略地说，稳定状态下访问量最大的页面）必须是由其他访问过的页面链接的那个，然后必须是最相关的页面）
最后，让我们再次强调马尔可夫链在处理随机动力学时对问题建模的强大作用。由于它们的良好特性，它们被用于各种领域，例如排队理论（优化电信网络的性能，其中消息必须经常竞争有限的资源并且在所有资源已经被分配时排队），统计数据（众所周知的“马尔可夫”）蒙特卡洛链“随机变量生成技术基于马尔可夫链”，生物学（生物种群进化建模），计算机科学（隐马尔可夫模型是信息理论和语音识别中的重要工具）等。

显然，马尔可夫链在建模和计算方面提供的巨大可能性远远落后于这种适度的介绍，因此，我们鼓励有兴趣的读者阅读更多有关这些工具的信息。置于（数据）科学家工具箱中。

谢谢阅读！