7小七Seven
2022/09/07阅读:64主题:自定义主题1
从《狂赌之渊》到马尔可夫链(第3话/共3话)
在这一节,我们跳出概率的一些计算,试着从“次数”这个角度尝试理解一下马尔可夫链的一些性质。
一、最后的冲刺阶段
正如题目所说,这是解决最终问题前面的最后一个准备工作了!我们现在的问题很简单,试着计算从任一状态i到一个常返态s的平均次数。为了计算这个问题,我们可以分成两种情况:i和s相等还是不相等。假设二者相等,那么很简单,步数为0.如果不相等,我们可以先试着算出i的下一个状态j到s的期望次数,然后再将结果+1,就可以得到:
我们使用 表示状态i到达状态s的期望次数,其中,右面的求和表示所有i的下一步t到达s的期望次数。
先举一个很简单的例子:如果我们的状态转换矩阵是这样:
它的转换图是

希望计算从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.
综上所述,我们把概率转换矩阵和图表示成:

使用上面的公式计算平均次数,联立方程可以很容易得到: ,也就是平均需要12次才能出现这个序列!
让我们再来看一下UDD的情况,与上面类似,可以得到概率转换矩阵和转换图如下:

还是上面的公式,可以得到 .也就是说,只是UUD和UDD的微小区别,最后获胜的概率也不相同(事实上,UDD更容易获胜!)
(注:你能否从状态转换的角度看出来为什么UUD比UDD更难获胜?)
类似地,我们也可以算出UUU的平均次数是14次,UDU的平均次数是10次。因此,如果在公平的情况下,获胜概率的分布应该是:UDD(DUU)>UDU(DUD)>UUD(DDU)>UUU(DDD)
下面是剧中的解释,可以看出,在《狂赌之渊 双》中的解释是错误的(啊这……)

三、总结
虽然我们是以日剧《狂赌之渊》为例,但马尔可夫链这一概念,可以想见,在很多领域,例如经济学、人工智能、物理领域都有广泛的应用。它的本质简单说,就是状态之间的随机转换。
另外,考虑到理解难度,我们在这里仅仅考虑 “离散情况”,即所有状态都是离散的。除此之外,马尔可夫链还有连续情况,也就是所有状态都是连续分布的,这个已经超出了我们的介绍范围。如果有兴趣的话,可以参考其他相关书籍(正如第一篇所说,这一系列只是科普性质,并没有严格的数学推导)
注:以上内容来源于公众号“科普小白说”,一个做科普的公众号,如果有兴趣的可以关注一下哦
作者介绍