回顾两类重要的随机过程

在上一篇随机过程的概述中，我们提到过两类非常非常典型且重要的随机过程，一类是：伯努利过程和泊松过程，这一类随机过程是无记忆性的，也就是说未来的状态不依赖于过去的状态——新的“成功”或“到达”不依赖于该过程过去的历史情况。

而另一类则正好相反，未来的情况会依赖于过去的情况，并且能够在某种程度上通过过去发生的情况去预测未来，例如这一篇我们的核心内容——马尔科夫过程，它在许许多多的领域都有深入和广泛的应用。

离散时间的马尔科夫链

马尔科夫链三要素

这是一类随着时间而发生状态变换的过程，因此分为离散时间的马尔科夫链和连续时间的马尔科夫链两类。我们首先考虑离散时间的马尔科夫链，它的状态在确定的离散时间点上发生变化。

离散时间的马尔科夫链有三个核心概念点：离散时间、状态空间、转移概率。

在离散时间的马尔科夫链中，我们通常使用 n 来表示时刻，用 Xn 来表示马尔科夫链在此时的状态，那么显然马尔科夫链所有的状态会构成一个集合 S，这个集合 S 我们把它称作是这个离散时间马尔科夫链的状态空间。

那么，在这个状态空间的基础之上，我们来讨论马尔科夫链的第二个概念：转移概率。转移概率是这么描述的：当离散时间的马尔科夫链当前的状态是 i 时，下一个状态等于 j 的概率就是转移概率，我们记作是 (P_{ij})。

转移概率 (P_{ij}) 本质上用一个条件概率就可以表达：

(P_{ij} = P(X_{n+1} = j| X_{n} = i), i,j ∈S)

我们举一个拥有三个状态的离散时间马尔科夫链，它的转移概率图如下：

在这幅图中标明的是"古明地觉"的三种状态，每天他都处于这三种状态中的一种：要么宅在家中，要么在外面运动，要么吃美食。这就是"古明地觉"的状态空间，如果今天"古明地觉"宅在家中，明天他仍然宅在家中的概率是 0.2，明天出去吃美食的概率是 0.6，明天出去运动的概率是 0.2，这就是他的几个转移概率。

马尔科夫性

如果我们说离散时间、状态空间和转移概率是离散时间马尔科夫链的构成要素，那么马尔科夫性则是它的灵魂特征。

这个特性具体描述为：只要时刻 n 马尔科夫链的状态为 i，不论过去发生了什么，也不论马尔科夫链是如何到达状态 i 的，下一个时刻 n+1 转移到状态 j 的概率一定都是转移概率(P_{ij})

我们还是用上面的图例来说明，比如"古明地觉"今天是在吃美食，那么不管她昨天是在运动还是宅在家中，他明天出去运动的概率都不变，就是 0.3，出去继续吃美食的概率也不变，还是 0.6。概况的说来就是：下一个状态只与当前状态有关，而与更早的历史状态无关。

语言上七七八八的说了这么多，又是举例子，又是理论术语的，其实落实在数学语言的表达上，还是一个条件概率等式的事儿：

即对任意的时刻 n，对状态空间中的任意状态 i, j ∈ S，以及时刻n前(也就是历史上的)任何可能的状态序列(i_{0},i_{1},…,i_{n-1})，均有：

(P(X_{n+1} = j|X_{n}=i,X_{n-1}=i-1,…,x_{0}=i_0) = P(X_{n+1} = j|X_n=i) = P_{ij})

很清楚也很直白：下一个状态 (X_{n+1})的状态只依赖于前一个状态(X_n)

转移概率和状态转移矩阵

那么问题来了，这个转移概率(P_{ij})具有什么样的性质呢？首先(P_{ij})必须满足非负性，这是必须的

其次再有(∑_{j=1}^{m}P_{ij} = 1)，这个等式对于所有的i都成立。其实这个很好理解，我们还是对照着上面那个"古明地觉"的状态图来看。比如她今天宅在家中，那么她明天继续宅在家中的概率是 0.2，明天出去运动的概率是 0.2，明天出去吃美食的概率是 0.6，不管这三个概率如何取值，如何分配，有一点是肯定的，就是三者相加必须等于 1。

我们关注一下这里特殊一点的情况，即当 i=j 时，(P_{ij}) 的取值问题。其实就是对应了"古明地觉"今天宅在家中，明天继续宅在家中的情况。虽然状态没有发生变化，但是我们可以认为是状态发生了一次特殊的转移，也就是自身转移。

在状态空间 S 中，任意两个状态 i 和 j 之间都有一个转移概率(P_{ij})，并且满足(P_{ij}) ≥ 0(当状态 i 无法转移到状态 j 的时候，(P_{ij})=0)。那么我们可以把状态空间中的状态间的所有转移概率按照顺序组织成一个二维矩阵，其中第i行、第j列的元素就是(P_{ij})，那么这个二维矩阵：

就称为是转移概率矩阵，它刻画了对应的马尔科夫链的本质。

我们沿用"古明地觉"的例子：我们令状态 1 为宅在家中；状态 2 为运动；状态 3 为吃美食，那么这个马尔科夫链就是一个 3×3 的 2 维矩阵。

马尔科夫链性质的总结

到这里，我们有必要停下来梳理一下马尔科夫链的最基本性质，一个马尔科夫链由以下主要特征确定：

第一是状态集合S = {1, 2, 3, …, m}
第二是可能发生状态转移的(i, j)，即那些(P_{ij} > 0)的状态对；
第三是(P_{ij})的取值；

而这三点都可以最终由一个二维的转移概率矩阵所描述。

并且由该上述特征所描述的马尔科夫链是一个随机变量序列(X_{0},X_{1},X_{2},…,X_{n})，它们取值于状态空间S，并且满足：对于任意的时间n，所有状态i，j∈S，以及之前所有可能的状态序列：(i_{0},i_{1},…,i_{n})，均有：

(P(X_{n+1} = j|X_{n}=i,X_{n-1}=i-1,…,x_{0}=i_0) = P(X_{n+1} = j|X_n=i) = P_{ij})

一步到达与多步转移

刚才我们花大篇幅介绍的转移概率(P_{ij})给出的是从状态i一步到达状态j的转移概率(P_{ij} = P(X_{n+1}=j|X_{n}=i))。那么我们进一步拓展，我们不是通过一步，而是通过m步(其中m>1)从状态i转移到状态j，那么这个对应的就是m步的状态转移概率。

写成条件概率的形式就是：

(P^{m}(i, j) = P(X_{n+m} = j|X_{n} = i))

这里我们换一个例子来看看，社会的流动性问题是大家都非常关注的一个问题，社会的流动性强，社会的底层通过自身的努力使得家族向社会中层甚至上层流动是社会始终保持活力重要推动力。

社会学中就有一个非常有名的反映社会阶层流动的马尔科夫链，在这个马尔科夫链的状态空间中，有三个状态，状态 1 是处于贫困水平，状态 2 是中产阶级，状态 3 是财富自由，它的状态转移矩阵为：

我们不讨论这里面数据的合理性和准确性，单单就事论事，如(P_{13}=0.1)，表示如果这一代人处于贫困水平，下一代人想成为财富自由的概率为 0.1，而继续处于贫困水平的概率要大得多，为 0.7。而如果这一代人处于财富自由的水平，那么他的下一代处于财富自由的概率也要大不少，为 0.4。

那么，我们现在思考这么一个问题，假设爷爷处于贫困水平（状态 1），那么父亲处于中产阶级（状态 2），而你处于财富自由水平（状态 3）的概率有多大？

从哪里入手呢？还是紧扣定义，从条件概率表达式入手：

(P(X_{2}=3,X_{1}=2|X_{0}=1)) = $ P(X_{2}=3,X_{1}=2,X_{0}=1) over P(X_{0}=1)$

=(P(X_{2}=3,X_{1}=2,X_{0}=1) over P(X_{1}=2,X_{0}=1)) · (P(X_{1}=2,X_{0}=1) over P(X_{0}=1))

=(P(X_{2}=3|X_{1}=2,X_{0}=1) · P(X_{1}=2,X_{0}=1))

由于这是一个马尔科夫链，因此满足：

(P(X_{2}=3|X_{1}=2,X_{0}=1) = P(X_{2}=3|X_{1}=2))

因此有：

(P(X_{2}=3,X_{1}=2|X_{0}=1) = P(X_{2}=3|X_{1}=2)P(X_{1}=2|X_{0}=1))

对应到转移概率矩阵中，就是从状态 1 转移到状态 2 的概率乘以从状态 2 转移到状态 3 的概率：

(P_{12}P_{23} = 0.2·0.2 = 0.04)

接下来我们不指定父亲的状态，只看这么一个问题，就是假设爷爷是贫困水平（状态 1），问孙子处于财富自由（状态 3）状态的概率有多大？

那么这里只指定了爷爷和孙子所处的状态，那么父亲这一代可以是处于贫穷、中产和财富自由中的任意一种状态，那么这个概率的表达式写起来也很简单：

(P(X_{2}=3|X_{0}=1) = P(X_{2}=3,X_{1}=1|X_{0}=1) + P(X_{2}=3,X_{1}=3|X_{0}=1)=P_{11}P_{13}+P_{12}P_{23}+P_{13}P_{33})

(=∑_{k=1}^{3}P_{1k}P_{k3}=0.7·0.1+0.2·0.2+0.1·0.4=0.15)

上面具体计算出来的结果对我们而言其实并不重要，我们重点还是回过头来看这个式子：

(P(X_{2}=3|X_{0}=1) = P_{11}P_{13}+P_{12}P_{23}+P_{13}P_{33})

对线性代数熟悉的同学应该对这个等式很敏感，它实际上就是

该转移矩阵中，第一行和第三列点乘的结果，如果按照矩阵相乘的运算法则，这个计算出来的结果恰好位于结果矩阵的第一行第三列，也正对应了从状态 1 到状态 3，两步状态转移的概率值。

试想，如果我们将概率转移矩阵与自身相乘，也就是求它的二次幂，即：

那么得到的新的 3×3 的二维矩阵里就包含了所有状态间，通过两步到达的概率值：

import numpy as np

A = np.array([[0.7, 0.2, 0.1],
              [0.3, 0.5, 0.2],
              [0.2, 0.4, 0.4]])


print(A @ A)
"""
[[0.57 0.28 0.15]
 [0.4  0.39 0.21]
 [0.34 0.4  0.26]]
"""

从结果中我们可以看出，第一行第三列确实就是我们刚刚求出来的概率值 0.15。

那么以此类推，我们想看看 n 步状态转移概率，那么就是求取上面的状态转移矩阵的n次幂

from functools import reduce
import numpy as np

A = np.array([[0.7, 0.2, 0.1],
              [0.3, 0.5, 0.2],
              [0.2, 0.4, 0.4]])


print(np.array(reduce(np.ndarray.__matmul__, [A] * 3)))
"""
[[0.513 0.314 0.173]
 [0.439 0.359 0.202]
 [0.41  0.372 0.218]]
"""
print(np.array(reduce(np.ndarray.__matmul__, [A] * 5)))
"""
[[0.47683 0.3353  0.18787]
 [0.46251 0.34373 0.19376]
 [0.45662 0.34708 0.1963 ]]
"""
print(np.array(reduce(np.ndarray.__matmul__, [A] * 10)))
"""
[[0.46823165 0.34033969 0.19142866]
 [0.4679919  0.34048014 0.19152797]
 [0.46789259 0.3405383  0.19156911]]
"""
print(np.array(reduce(np.ndarray.__matmul__, [A] * 20)))
"""
[[0.46808515 0.34042551 0.19148934]
 [0.46808508 0.34042555 0.19148937]
 [0.46808505 0.34042556 0.19148938]]
"""
print(np.array(reduce(np.ndarray.__matmul__, [A] * 100)))
"""
[[0.46808511 0.34042553 0.19148936]
 [0.46808511 0.34042553 0.19148936]
 [0.46808511 0.34042553 0.19148936]]
"""

很显然，随着 n 的逐渐增大，n 步状态转移矩阵收敛于：

[[0.46808511 0.34042553 0.19148936]
 [0.46808511 0.34042553 0.19148936]
 [0.46808511 0.34042553 0.19148936]]

我们发现，它每行的三个元素都是一模一样的，这说明不论你现在是贫穷水平、中产阶级还是财富自由，过了很多代以后，你的后代落入到三个阶层中任意一个阶层的概率都是一定的。而且最大的概率都是变成贫困阶层。当然这个只是我们依据给定的数据计算而来，具体是否符合社会学的常识，就不是我们所关心的问题了。不过确实也说明，富有从来不是一件容易的事儿。

最后我们看看由 n 步转移概率所派生出来的路径概率问题。

给定一个马尔科夫链模型，我们可以计算未来任何一个给定状态序列的概率，特别的我们有：

(P(X_{0}=i_{0},X_{1}=i_{1},…,X_{n}=i_{n})=P(X_{0}=i_{0})P_{i_{0}i_{1}}P_{i_{1}i_{2}}···P_{i_{n-1}i_{n}})

这个结合马尔可夫性和条件概率的描述形式，说明起来也是非常简单。

首先由贝叶斯定理可得：

(P(X_{0}=i_{0},X_{1}=i_{1},…,X_{n}=i_{n})=P(X_{n}=i_{n}|X_{0}=i_{0},X_{1}=i_{1},…,X_{n-1}=i_{n-1})P(X_{0}=i_{0},X_{1}=i_{1},X_{2}=i_{2},…X_{n-1}=i_{n-1}))

然后依照马尔可夫性：

(P(X_{n}=i_{n}|X_{0}=i_{0},X_{1}=i_{1},…,X_{n-1}=i_{n-1})=P(X_{n}=i_{n}|X_{n-1}=i_{n-1}) = P_{i_{n-1}i_{n}})

从而得到：

(P(X_{0}=i_{0},X_{1}=i_{1},…,X_{n}=i_{n})= P_{i_{n-1}i_{n}}P(X_{0}=i_{0},X_{1}=i_{1},…,X_{n-1}=i_{n-1}))

然后我们在这个式子的基础上不断递推就能得到最开始的：

(P(X_{0}=i_{0},X_{1}=i_{1},…,X_{n}=i_{n})= P(X_{0}=i_{0})P_{i_{0}i_{1}}P_{i_{1}i_{2}}···P_{i_{n-1}i_{n}})

这个路径问题举个例子就很好理解了，比如从你的太爷爷开始，太爷爷是贫穷，爷爷是贫穷，爸爸是中产，你是财富自由，你儿子中产，你孙子贫穷，这就是一个路径，当然是一个非常悲剧，典型的努力拼搏最后又富不过三代的悲剧路径：那么路径概率是(P(X_{0}=1)P_{11}P_{12}P_{23}P_{32}P_{21})，最左边的 (P(X_{0}=1)) 表示太爷爷是贫穷的概率，这个值指定了，整个路径的概率就可以计算出来了。