7

7小七Seven

V1

2022/09/07阅读:64主题:自定义主题1

从《狂赌之渊》到马尔可夫链(第3话/共3话)

在这一节,我们跳出概率的一些计算,试着从“次数”这个角度尝试理解一下马尔可夫链的一些性质。


一、最后的冲刺阶段

正如题目所说,这是解决最终问题前面的最后一个准备工作了!我们现在的问题很简单,试着计算从任一状态i到一个常返态s的平均次数。为了计算这个问题,我们可以分成两种情况:i和s相等还是不相等。假设二者相等,那么很简单,步数为0.如果不相等,我们可以先试着算出i的下一个状态j到s的期望次数,然后再将结果+1,就可以得到:

我们使用 表示状态i到达状态s的期望次数,其中,右面的求和表示所有i的下一步t到达s的期望次数。

先举一个很简单的例子:如果我们的状态转换矩阵是这样:

它的转换图是

图1.状态转换图
图1.状态转换图

希望计算从1到3的平均次数,联立上面的方程,可以得到:

求解这个方程组,就可以得到: ,也就是说,从状态1到状态3,平均需要6步,而从状态2到状态3需要4步


二、关于骰子的问题,终于可以给出结果了!

让我们再重新回顾一下那一场《狂赌之渊 双》的赌局:对于一个骰子(默认为6面),定义1,2,3为Down(以下简称D),4,5,6为Up(以下简称U),两人分别在纸上写下一个长度为3的序列(例如:UUD,UDU等)。然后荷官开始一直掷骰子,直到谁先写的序列先出现,谁就获胜。

可以想见,长度为3的序列一共有8种,考虑到对称性(例如,UUD和DDU情况完全相同),因此,我们只考虑四种情况,分别是UUU,UUD,UDU,UDD。因此,我们现在的主要任务就是写出状态概率。我们在这里以UUD为例,演示一下应该怎么写。

假设一开始扔出的是D,那么定为状态1,下一次如果扔出D,则还为状态1,如果扔出U,则变成状态2(认为“前进”了一步);如果下一次扔出D,则可以认为之前“前功尽弃”,回到状态1,若扔出U,则变成状态3;如果下一次扔出U,则变成状态2(你能说出来为什么不是状态1吗?),如果扔出D则变成状态4.

综上所述,我们把概率转换矩阵和图表示成:

图2.UUD的状态转换图
图2.UUD的状态转换图

使用上面的公式计算平均次数,联立方程可以很容易得到: ,也就是平均需要12次才能出现这个序列!

让我们再来看一下UDD的情况,与上面类似,可以得到概率转换矩阵和转换图如下:

图3.UDD的状态转换图
图3.UDD的状态转换图

还是上面的公式,可以得到 .也就是说,只是UUD和UDD的微小区别,最后获胜的概率也不相同(事实上,UDD更容易获胜!)

(注:你能否从状态转换的角度看出来为什么UUD比UDD更难获胜?)

类似地,我们也可以算出UUU的平均次数是14次,UDU的平均次数是10次。因此,如果在公平的情况下,获胜概率的分布应该是:UDD(DUU)>UDU(DUD)>UUD(DDU)>UUU(DDD)

下面是剧中的解释,可以看出,在《狂赌之渊 双》中的解释是错误的(啊这……)

图4.《狂赌之渊 双》电视剧当中芽亚里的解释
图4.《狂赌之渊 双》电视剧当中芽亚里的解释

三、总结

虽然我们是以日剧《狂赌之渊》为例,但马尔可夫链这一概念,可以想见,在很多领域,例如经济学、人工智能、物理领域都有广泛的应用。它的本质简单说,就是状态之间的随机转换

另外,考虑到理解难度,我们在这里仅仅考虑 “离散情况”,即所有状态都是离散的。除此之外,马尔可夫链还有连续情况,也就是所有状态都是连续分布的,这个已经超出了我们的介绍范围。如果有兴趣的话,可以参考其他相关书籍(正如第一篇所说,这一系列只是科普性质,并没有严格的数学推导)

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

分类:

数学

标签:

数学

作者介绍

7
7小七Seven
V1