7

7小七Seven

V1

2022/08/30阅读:14主题:自定义主题1

马尔可夫链第1话/共3话

大家好,我是小七!我!又回来了!

我知道你们又在说:怎么又托更这么长时间?你们听我狡辩解释一下,事情是这么回事儿:

在几天前,我在看一部日剧——《狂赌之渊》,如题目所见,这部剧主要讲的就是关于“赌博”的一些内容!当然,我们并不是想通过这部剧宣扬赌博(事实上,还是要远离赌博!)。但是,从历史的角度看,有一门学科的出现和赌博密不可分,没错,就是大家耳熟能详的“概率论”!在某种程度上,可以说:人们对赌博规则的研究,推动了概率论的发展(这件事情的起源是“赌金分配”问题,如果有时间我们再细说)(又挖了一个坑)

图1.《狂赌之渊》电视剧海报,我就是看这部剧粉上了滨边美波
图1.《狂赌之渊》电视剧海报,我就是看这部剧粉上了滨边美波

回到《狂赌之渊》当中,我们在《狂赌之渊 双》当中(无论是电视剧还是动漫)都有这样一个桥段(为了便于大家理解,这里面的人名都使用甲和乙代替):

对于一个均匀骰子(默认为6面),定义1,2,3为Down(以下简称D),4,5,6为Up(以下简称U),两人分别在纸上写下一个长度为3的序列(例如:UUD,UDU等)。然后荷官开始一直掷骰子,直到谁先写的序列先出现,谁就获胜。 例如,甲和乙分别写了UDU和UDD,掷骰结果为DDUDU,则UDU获胜。

我们暂且忽略剧中提到的“循环克制”问题,如果你现在作为主角参与这场赌局,你会写下怎样的序列呢?肯定是写出现概率最大的啊!那么,概率最大的序列又是哪个呢?

(注:关于“循环克制”,实际上是一种“桌游机制”,如同石头剪刀布一般,不存在最大的绝对获胜;如同《斗兽棋》一样,老鼠同样可以“吃”大象。关于桌游机制的问题,如果有时间有机会我们再细讲(好吧,又挖坑……),如果大家有兴趣,也可以参考一本书——Building Blocks of Tabletop Game Design,循环克制就是这本书的第RES-07号机制)

回到赌局当中,我问过大多数人(比如我们团队的一些人),得到的结果都是——等概率的! 确实,经过简单的计算我们可以知道,其一共只会有八种序列(2*2*2=8),那么如果只掷骰三次的话,确实是等概率的。 然而,事情似乎不是那么简单,因为我们需要的是比较谁先出现,然而,所有可能的序列当中确实有容易出现的和不容易出现的。

所以说,从现在开始,我们就来试图找出这个最优解,看看哪个序列获胜的概率最大!我们需要用到的理论就是——马尔可夫链,一个在物理、经济学、机器学习等领域频繁使用的数学模型!当然,你也能想见,这一篇文章肯定讲不完,所以我们会分成好几篇来完成这件事(正如题目所见,我们至少要用3篇才能解决这个问题)。首先,让我们先来看一下最基础的一些概念。

图2.安德雷·安德耶维齐·马尔可夫Андрей Андреевич Марков(1856年6月14日-1922年7月20日)
图2.安德雷·安德耶维齐·马尔可夫Андрей Андреевич Марков(1856年6月14日-1922年7月20日)

零、写在前面的话

在开始所有内容之前,先有一些注意事项请大家看一下:

  • 这一系列会是我所写主题当中最抽象的一篇(没有之一),还是那个样子,我会尽量避免数学的理论推导,仅从应用带你了解一些这个理论。如果需要深入学习,可能需要找其他参考书籍;

  • 由于这一理论的需求,我们可能会在这里面涉及到很多数学的概念,特别是线性代数和概率论的一些基本概念。当然,我会尽量把这些概念讲得简单易懂;

  • 由于理论的特殊性,我们的很多内容会使用计算机来模拟计算。也就是说,我们需要一些编程工作。在本文中,我会使用Mathematica作为演示的主体,但你也可以使用其他编程语言,如MATLAB,Python等。之所以选择Mathematica,主要是因为我用的是它的正版软件(我理解很多人都是对matlab比较熟悉,但没办法,我没有MATLAB的正版,所以只能用mathematica了)。如果有必要,可能会使用Python做补充说明。永远记住:编程只是工具!


一、先从一个天气预报开始说起

作为引入,让我们先来抛弃掉前面的赌局,而从一个更加简单的例子开始入手:

考虑某一个地方的天气情况,为了简化起见,仅考虑当地的天气有两种状态——“晴天”和“下雨”,并且天气状态仅与前一天的天气有关。例如,若今天晴天,则明天晴天的概率为0.7,下雨的概率为0.3;若今天下雨,则明天下雨的概率为0.8,晴天的概率为0.2.

如果我们用表格来表示这个概率,就可以写成:

明天晴天 明天下雨
今天晴天 0.7 0.3
今天下雨 0.2 0.8

让我们来看一下这个例子有什么特点:首先,未来的天气状态依赖于之前的天气状态,用比较数学化的语言来说,如果要预测第n+1个状态 ,那么必须知道前面的n个状态;其次,还有一个重要的特点:未来的天气状态仅仅依赖于前一天的,也就是说,第n+1个状态 仅仅依赖 的状态,并且,所有天气的状态都是有限的。我们将满足上述特点的过程称为“马尔可夫过程”

再进一步,为了简化,我们把晴天称为状态1,下雨称为状态2,那么定义:

为“转移概率”。其中,S为所有状态组成的集合,在这一例子中,S就是集合{1,2}

(一点小补充: 表示 发生条件下 发生的概率,因此,上面的转移概率其含义为:当 为状态i时, 为状态j的概率)

根据定义,我们就可以写出上面问题的转移概率:

进一步,如果将下标的第一个数作为行标,第二个数作为列标,就可以写成矩阵的形式,即

称这一矩阵为“转移概率矩阵”。


二、这些有什么用?

前面只是背景铺垫,下面才开始计算一些有趣的东西。首先先来热一下身:

如果第一天是晴天,计算前三天的天气为“晴天、晴天、下雨”的概率?

(有没有感觉有点前面赌局的意思了?当然,我们还有很长的路要走)

这里有一个公式,很简单,如果你能把前面的转移概率公式看明白,这个公式应该很简单:

(注:第二行实际上就是我们通常所听说的贝叶斯公式:即

如果现在,我们给定初始状态,即 ,那么,这个概率就可以化简成:

利用这个公式,我们就可以计算前面所说的“晴天,晴天,下雨”的概率为:

下面是使用Mathematica计算的结果:

图3.Mathematica计算程序,其中In[9]定义了马尔可夫过程,也就是转移概率矩阵,In[10]用以计算特定的概率
图3.Mathematica计算程序,其中In[9]定义了马尔可夫过程,也就是转移概率矩阵,In[10]用以计算特定的概率

如果我们现在并不知道初始状态怎么办?例如,现在已知当地第一天晴天概率为0.6,下雨概率为0.4,那么出现上面的序列概率又是多少呢?不要忘记我们最原始的公式啊!只要把这个概率乘以第一天晴天的概率也就是0.6就可以得到结果为0.126了!


三、走出一步到多步的跨越

在前面,我们都仅仅讨论的是一步转换概率,也就是从某一个状态经过一步到某一个状态的概率。然而,在很多时候,我们可能希望计算多步概率。比如,还是前面“晴天—下雨”的例子,现在希望计算从晴天经过三步到下雨的概率是多少?

为了表述清楚,我们使用 表示从状态i经过n步到状态j的概率,好在有一个方程已经解决了这个问题——“查普曼-科莫高洛夫方程”,即

其中m是状态数,例如,在前面的例子中, .

对于这个公式,我们不会试图从数学上证明它,但我会告诉你这个公式的含义是什么。其本质就是一个“递推公式”,其中, 表示经过n-1步从i到k的概率,然后再乘以 就是经过n步从状态i经过状态k再到状态j的概率,这里的求和表示把状态k“遍历”了一遍,即令所有状态都是状态k计算一遍,然后求和就是总的概率。

如果理解了上面的公式,就让我们看一下前面下雨的例子吧!还是老规矩,晴天是状态1,下雨是状态2,那么我们要计算的,实际上就是 ,利用上面的公式,可以得到

现在,我们就把3步概率转换成了2步概率,进一步就可以得到这个概率。当然,这个运算量比较大,我们善用计算机的手段,这里使用Mathematica计算上面这个“递归”表达式:

图4.Mathematica程序,其中r就是前面的递推表达式,即查普曼-科莫高洛夫方程
图4.Mathematica程序,其中r就是前面的递推表达式,即查普曼-科莫高洛夫方程

Tips:事实上,我们也可以直接使用Mathematica里面的内置函数来解决这个问题,只不过为了演示公式的正确性,我们写了这样一个函数。在实际应用的过程中,我们可以直接使用它的内置函数(因为使用递归计算会极大消耗计算机的资源,这是由它的复杂度决定的,当然,这是数据结构与算法的内容,并不是我们的重点)

图5.使用内置函数也可以得到同样的结果
图5.使用内置函数也可以得到同样的结果

也可以看出来,如果计算20步的概率,显然使用内置函数的效率高得多,而且,在Mathematica12.0当中,计算1000步就已经超出了递归深度,而使用内置函数还能非常快速地计算出来。当然,这并不是我们的重点!

图6.使用递归算法,计算20步大约需要6.5s,而使用内置函数则可以“瞬间”得到结果。并且,在计算1000步的情况下,使用内置函数同样没有问题
图6.使用递归算法,计算20步大约需要6.5s,而使用内置函数则可以“瞬间”得到结果。并且,在计算1000步的情况下,使用内置函数同样没有问题

等一下!我们似乎看到了什么不得了的东西!为什么20步的概率和1000步的概率如此接近?这是巧合吗?当然不是!实际上,这是马尔可夫链的一个性质,但我们在这一篇已经讲不完了,留到下一期再说吧!

注:以上内容来源于公众号“科普小白说”,一个做科普的公众号,如果有兴趣的可以关注一下哦

分类:

数学

标签:

数学

作者介绍

7
7小七Seven
V1