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

大家好，我是小七！我！又回来了！

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

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

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

★

对于一个均匀骰子（默认为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篇才能解决这个问题）。首先，让我们先来看一下最基础的一些概念。

---

零、写在前面的话

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

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

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

• 由于理论的特殊性，我们的很多内容会使用计算机来模拟计算。也就是说，我们需要一些编程工作。在本文中，我会使用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计算的结果：

如果我们现在并不知道初始状态怎么办？例如，现在已知当地第一天晴天概率为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计算上面这个“递归”表达式：

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

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

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

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