马尔可夫链游戏终止条件

清华学霸小课堂，今天我们请到的是青年歌，我从小学到大 新年歌的家人们。大家好，我们来讲一讲概率题之 markovlan， 对吧？我们翻译一下马尔克夫恋，我们简单理解， what is markovlan？ 我们来举一个简单的例子，小狗每天有两种状态，一种是奋斗，一种是躺拼。那第一天状态为奋斗，那我们 他第二天呢，就有零点六的概率是奋斗，零点四的概率躺平。那么相反，前一天的状态是躺平，那么他第二天啊，有零点六的概率为躺平，而零点四的概率为奋斗。 修狗这个人的人生，我们就把它看作一个链条，对吧？从第一天到无数天，每天都有一个状态，那么这个状态呢？他得到的概率只和前一天的 状态有关，那我们就可以把这个长长的链条缩短为只有两个元素的这样一个链条，对吧？从 n 减一天到 n 天，我们只要得到了 n 减一天的元素的状态，我们就可以预测第 n 天这个状态是如何。那我们来简单运用一下这样的思想，有 n 个编号为一到 n 的盒子， 第一个盒子中有两个白球，一个黑球啊，其余一个盒子有一个白球，一个黑球啊。从第一个盒子取一个球放到第二个盒子中， 再从第二个盒子中任取一个球放到第三个盒子中，以此类推。那么从第二个盒子中取到白球的概率是从第 n 个盒子中取到白球，概率是什么呢？啊？首先第一个小问，送文体秒杀，那么第二个第二个问，我们怎么去做呢？翻译一下题目，盒中球的组成 只有两种情况，第一种，两白一黑，也就是说在前一个盒子中他取出了白色的球，对吧？ 还有一种情况，一白两黑，在前面一个盒子中啊，取出了黑色的球，就只有两种可能，那我们知道 dn 减一个盒中的状态，就可以愉快的得到 dn 个盒子中状态的概率， 那我们就可以进行地推的思想，对吧？设 d n 减一个盒子为状态一的概率是 d n 减一，设 为状态二的概率为 p n 减一 hat， 对吧？就是小减 hat， 显然 p n 减一加 p n 减一 hat 等于一，那么在此基础上表示 p n 和 p n hat 怎么表示呢？ tn 我们可以翻翻译一下，对吧？有两种情况，一个是 dn 减一，合作为状态一的时候啊，两白一黑，非常简单，三分之二的概率，对吧？去到这个白色的球啊，那另一种就是 tn 减一 hat 里面三分之一的概， 取到白色的球，简单，好吧，非常简单，非常简单啊，我们继续来简单的部分，那么 p n 就可以表示成以下的式子，然后我们就可以简单的运用一下大家可能已经在之前学过的 简单的数列知识，构造出等比等差数列。我们一其实我们熟悉的同学就可以非常简单的发现，我们直接减去二分之一啊，两边就可以直接变成等比的形式， 于是我们就可以算出来了，具体的答案就留给同学们自行探索。那么今天的课程就讲到这里，你学会了吗？

欢迎观看二零二二年树之道系列的第一期节目，这里祝所有的小伙伴新年快乐，新的一年里身体健康，事业、学业、家业顺利。 在之前五期节目中，我们分别用三期节目介绍了马尔克夫练的基础知识，两期节目介绍了蒙特卡洛模拟的两种抽样方法。 今天我会把这两个主题结合起来，带大家走进马尔克夫列蒙特卡罗方法 mark of chain monte carlo method 以下简称为 mc mc， 错过前面节目的朋友们完全不用担心，我会在本期节目中将重点概念再为大家重温一遍， 相信节目之后你一定能够更好的理解 mcmc 这以数据分析数据科学领域中的核心知识点。 由于本期内容涵盖知识点非常多，所以我会分四个章节进行介绍。一、从上两期节目中所介绍的逆转换接受拒绝抽样方法的局限性出发，引出为什么我们需要设计新的抽样方法。 二、为什么马尔克夫练元素的加入能够有效提升抽样效率？这背后的理论依据又是什么？三、 mcmc 方法之 metropolis hastings 算法的设计思路详解。 四、使用 r 语言对 metropolis 算法进行模拟演示。那么现在就让我们正式进入本期节目的核心内容。第一章，逆转换接受拒绝抽样的局限性在 前两期节目中，我们分别介绍了使用逆转换方法和接受拒绝方法进行抽样。在使用逆转换方法的过程中， 需要先对目标概率密度函数 pdf 求积分，得到累积分布函数 cdf， 再对 cdf 进行反函数求解，得到从均匀分布到目标分布的转化函数，这样就能实现从简单均匀分布出发，得到满足复杂目标分布的随机值了。 但之前求积分和求返函数的步骤却能给大家造成足够的麻烦，因此我们有了第二种抽样方法，接受拒绝方法。 接受拒绝方法中，我们需要设计一个简单的建议分布函数 gx， 再通过放大系数 m 让 m 乘 gx 落于目标函数 fx 上方，通过在 x 轴上根据 gx 生成随机值坐标 a， 然后在 y 轴上根据零到 m 乘 ga 的均匀分布生成随机坐标 b。 通过判断坐标 ab 是否能够落入接受区域来判定 a 能否最终被成功抽取。 不过该方法也有他的局限性，由于 m 乘 gx 需要处处大于我们的目标函数， 因此当目标函数是如图中形态的话，接受区域占比会非常小，真正实操阶段会耗费大量的时间和资源才能抽取足够的样本。了解了以上抽样方法的 线之后，我们再看 mcmc。 第二张 mcmc 为什么能够有效提升抽样效率呢？之前接受拒绝抽样效率低的原因之一是由于其没有充分利用前期的信息。 比如，当根据建议分布 gx 抽样出的 xn 恰好出现在其目标分布中的高密度区域时，如果下次抽样 xn 加一能够在这附近抽取，其接受的成功率自然也会相应较高。 但在接受拒绝方法中的每次抽样都是独立的，且建议分布函数不变， xn 的信息在下次抽样动作前会完全抹去，所以有相当的概率下次抽样会返回高拒绝区域的值。因此， 从直觉出发，我们需要让这个建议分布动起来，保留前期有用信息，并影响下次抽样。这样抽样效率是不是就更优了呢？为此，我们将马克夫恋的思想加入其中，最终流程会是这个样子的。 假设，我们根据初始的建议，正态分布 g x 零 c 个码进行抽样， x 零为初始设置的均值， c 个码为标准差得到 x 撇。假如 x 撇符合我们预设的规则， 我们则把 x 撇赋予 x e 作为鸡的均值参数用于下一次抽样。相反，假如 x 撇不满足规则，那么我们就会将原 零的值负于 x 一作为鸡的均值参数用于下一次抽样。这个链条会一直持续下去并收敛，达到稳态。 在马尔克夫练的节目中，我们介绍了稳态分布转移矩阵的概念。假如马尔克夫练的转移矩阵满足便利性，那么它存在唯一的稳态分布。现在你可以这样理解上面的 mcmc 链条， 我们就是需要设计这样一个判断规则，他能够起到转移矩阵的作用，让该链条能够收敛至稳态分布。而这个稳态分布就是我们目标函数概率密度分布了。 达到稳态后抽取的随机值就等同于从目标分布中进行抽样了。 到这里或许你还会有些迷茫，没关系，可以重温我们数字到十八到二十二级，然后再来体会我上面说的内容，一定会豁然开朗。 接下来让我们深入 mcmc 的具体算法之 match prolex hastings 算法。我会将上面的理论思路具象化，通过 mh 算法帮助大家更好的理解其精华。 第三张， metropolis hastings 算法 mh 算法的设计用到了马克夫链中一个叫做细致平稳 detailed balance 的概念。 我们假设有这样一个满足便利性的马尔克夫链，各状态已达到唯一的稳态分布 s， 如果其转移矩阵 t 满足下面的公式 s i i 乘以 t， i to j 等于 s， j 乘以 t， j to i， 我们撑起满足细致平稳条件。我会借用十九集中的例子介绍这里需要特别注意的两个点，第一点，并不是所有的稳态分布都满足细致平稳条件，比如该例中的稳态分布不满足细致平稳。 第二点，满足细致平稳条件的状态分布达到稳态分布。稳态分布有如下特点，项链 s 乘以矩阵 t 等于项链 s， 他的矩阵表达形式如下， 为了论证细致平稳条件也是稳态，我们就需要验证上述等式在细致平稳下也成立。 我们对细致平稳条件等式两边根据哀求和，然后等式右边做如下调整得到，因为从 j 状态转移去至所有状态的概率和为一。 因此最终下面的等式成立，符合稳态条件，证明完毕。我们可以用下面通俗的语言来进一步解释细致平稳公式。 从等式的两边来看，他等同于在说从处于状态 i 下期转移到状态 j 的概率与从处于状态 j 下期转移到状态 i 的概率相同， 他将对后面 mh 算法的构建起到决定性的作用。还记得第二章中的这句话吗？ 需要设计这样一个判断规则，他能够起到转移矩阵的作用，让该链条能够收敛至稳态分布，而这个稳态分布就是我们的目标函数分布。那么我们就是需要设计这个规则，能够使上述等式成立。 其实，等式的每一边都包括了两个步骤，步骤一，从旧状态下选出新状态作为候选对象。步骤二，判断是否需要转移至新状态。 我们用具体的数学语言来对这两个步骤进行推倒。步骤一，当已达到稳态，处于状态 i 的概率为 s i， 然后根据建议正态分布 g i c 个码，生成新的随机 值 j。 我们用 g j 基于 i 代表着均值参数为 i 时， j 被抽取出的概率 s i 乘以 g j， g i 则代表了从处于状态 a 下，根据 g i c m 选出了下期后选状态 j 的概率。 步骤二，我们定义 a j 基于 a， 它代表了接受 j 作为 a 转移后状态的概率。 两步相乘得到 s i 乘以 g j， g i， 再乘以 a j g i， 这就完美表达了从处于状态 a 转移到状态 j 的概率。同样的， sj 乘以 gig 与 j 乘以 aig 与 j 则代表了从处于状态 j 转移到状态 i 的概率。 两个公式在细致平稳条件下相等则有，其中 g j 基于 i 乘以 a， j 基于 i 和 g i 基于 j 乘以 a i 基于 j 对应了我们转移矩阵中的 t i to j 和 t j to i。 我们将上面的等式变换一下，得到 metropolis hasting 算法提出了一个满足上市等式的结法如下， 值得注意的是，由于基服从正态分布，它是对称的，那么基埃基于 j 与 g j g i 相等，两者相处抵消上述公式进一步得到精简。现在最后的问题是怎么求 s？ 由于我们知道函数 sx 就等同于我们的目标概率密度分布函数 pdfx， 而 pdfx 又等于我们的目标函数 fx 除以标准化常数 c， c 为 f， x 与 x 轴为成的积分值。很多时候 c 很难求解， 那么我们把 s j 等于 f j 除 c 和 s i 等于 f， i 除 c 带入上述等式，得到最终公式 a j 基于 i 等于一和 f j 除以 f i 中的最小值。这便是最初的 major produce 算法。而后期加入的 g i， g 与 j 除以 g， j 基于 i 作为 hastings 参数，则进一步扩大了该算法在非对称建议分布下使用的适用性。 到这里，之前提到的规则就已经设计出来了，我们有了建议分布 g， 同时有转移接受规则 a， 那么就可以顺着这个规则链条达到稳态分布，完美实现从目标分布中抽取随机值了。 让我们进入最中章第四章 metropolis 算法 r 语言实力在这个例子中，我们有一个，有两个正态分布，根据相应权重构成的新分布，设计一个 标准差位零点五变量 x 作为均值的正太分布。抽样公式 q， 为后续从该分布中抽取随机数做准备，需要提点标准差，可以尝试不同值来比较最终的抽样效果。 设置一个包含了一万个值的数据集合 x 覆盖初始变量 x 一为一 初始值，可以尝试不同值来比较最终的抽氧效果。接下来进入循环语句，循环九千九百九十九次， 每次循环哎。将当前的 xi 值作为变量 x 录入建议正太分布抽样公式 q 中得到心值 x j。 将 x i， x j 套入第三张 当中的 metropolis 公式，计算接受概率 a。 为了做出是否接受 xj 的决定，我们可以引入一个服从零到一间均匀分布的随机值，让他与 a 比较。 当 a 大的话，用 x j 值覆盖 x i 加一，否则用当前 x i 值覆盖 x i 加一。 完成循环后，我们可以绘制更新后的数据集合 x 的直方图，可以看到其能够很好的满足目标函数分布。 新年第一期数字到节目就到这里了，希望大家喜欢本期节目。今年除了本系列之外，我还会开一档新的节目，和大家分享一些工作学习方面的心得，让我们在新的一年里共同进步，那么下期节目再见！

马尔克夫恋是除了贝耶斯公式之外最简单的贝耶斯网络。这里举一个例子，假设某地的天气只有晴阴、雨三种状态，每天的天气状态只与昨天的天气有关。另外，每天的天气状态都以相同的概率影响第二天的天气。 这里我们用虚表示 d i 天的天气每相邻两天形成了依赖关系。总结起来说，马尔可夫列由三个要素组成，第一，有限的状态空间 s。 比如当前的状态空间由秦英语三个值组成。第二，条件概率矩阵 p， 该矩阵指明了任意两个状态之间状态转移的条件概率。第三，初始概率分布派零。他指明了秦英语三个状态的初始概率。显然，这三个概率之和 应该等于一。马尔克夫恋要解决两个基本问题，第一，根据当天的状态预测之后第一天乃至于地暗天的状态，根据初始概率分布派联合条件概率转移矩阵批。 结合贝耶斯网络的联合概率公式，我们可以得知第一天的概率分布，派一等于派零成一批， 派二等于派一乘一批，以此类推，派安等于派安减一乘一批。根据这个地推公式，我们有一个解析解，派安等于派零乘以批的 n 次方。另外，由于批的每一行概率之和都等于一， 所以可以证明存在一个整数，使得对于任何大于等于该整数的整数 n、 p 的 n， 四方都等于一个常数矩阵，其该常数矩阵的每一列的概率值都完全相等。比如 图，就拿当前图中所显示的矩阵劈来说，只要安足够大，则劈得任四方的第一列都是零点五，第二列和第三列都是零点二五。这会造成一个结果， 那就是无论初始概率分布派零等于多少，帝安天以及之后的每一天的概率分布都等于常数项量，零点五、零点二五、零点二五。这说明很多随机过程最终状态的概率分布将取经于稳定，并且与初始状态无关。 马尔克夫恋要解决的第二个基本问题是如何根据状态序列推测出条件概率转移矩阵批。假设我们在上个例子中观测了足够多的连续的天气状况，据此，我们怎样推断出条件概率转移矩阵批的每一个值呢？只要学习了大数定理，方法非常简单。 第一步，先统计如图所示的平度表。该表表示在第一天处于某个特定状况的条件下，第二天出现另一个特定状况的数量有多少。比如第一行第一列的三表示第一天天晴， 第二天也天晴的情况一共出现了三次，其余的值的含义依次类推。第二步就是把上述频度表转化为条件概率表。方法就是把表中的每一个值除以该行所有值之和。 根据大数定理，只要状态序列足够长，根据平度表计算得到的条件概率表就有很高的知性度。也就是说，这样的条件概率表比较靠谱。 具体的证明过程跟上个视频中所提到的大数定理的证明类似，这里省略。最后，我们总结一下马尔克夫恋的本质， 这很重要。作为一种特殊的贝耶斯网络，马尔克夫恋的每个节点的状态集合都相同。比如前面那个例子中， 每个节点都只能取清英语三个值中的一个值，而一般的贝耶斯网络中并不要求所有节点的状态集合相同。 第二，每个节点都只依赖于前一个节点，第一个节点除外。而一般的笨夜思网络中既可以有分联，也可以有会连，唯一的限制是不能有还。第三，每相邻两个节点之间的条件概率转移矩阵是完全相同的，而一般的笨夜思网络中显然不存在这种限制。 第四，马尔克夫恋是除贝斯公式之外第二种简单的贝耶斯网络。所以一方面，马尔克夫恋也要从所有节点的联合概率角度考虑一切问题。另 一方面，由于任意相邻节点之间的条件概率转移矩阵都相同，所以在计算联合概率时又提供了一些便利。总之，不学好马尔可夫恋，你是不可能理解你马尔可夫恋以及其他更复杂的黑夜思网络的。