从《狂赌之渊》到马尔可夫链（第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)

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

---

三、总结

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

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

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