什么样的马尔科夫链可以被无损地粗粒化？

原创集智百科团队 2025-06-23 21:44 上海

导语

成块性（Lumpability）是马尔科夫链的粗粒化理论中一种描述是否可聚类或可粗粒化的概念，最早由Kemeny和Snell在其1969年的著作Finite Markov Chains[1]中提出。Lump一词有‘块’的意思。判断一个马尔科夫链是否可成块（lumpable），就是要判定是否存在一种状态划分方式，能够将原始的马尔科夫链压缩为一个保留其主要动力学特征的简化链。

简而言之，成块性要求被聚类成一个块中的状态转移到其他块的概率在粗粒化前后（即状态被归并，转移概率矩阵被约简前后）要保持一致。这种划分虽然抹除了分组内部状态的微观差异，但能精确保持块间的转移机制，并为状态空间的合理划分提供了严格的数学判据，从而使得在状态空间上定义的分组方案自然蕴含了一个合理的宏观的动力学，即宏观的概率转移矩阵。

符合成块性的粗粒化方案通常满足很好的性质，如它能保证对宏观层面上的最大预测性、微观与宏观过程的一致性等。这使得成块性成为马尔科夫链维度约简研究中最常用的标准之一。

为了系统梳理因果涌现最新进展，北京师范大学系统科学学院教授、集智俱乐部创始人张江老师领衔因果涌现系列读书会，目前已经持续到「因果涌现第六季」读书会，如果你对这一话题感兴趣，非常推荐你加入社区！

“集智百科精选”是一个长期专栏，持续为大家推送复杂性科学相关的基本概念和资源信息。作为集智俱乐部的开源科学项目，集智百科希望打造复杂性科学领域最全面的百科全书，欢迎对复杂性科学感兴趣、热爱知识整理和分享的朋友加入，文末可以扫码报名加入百科志愿者！

↑↑↑扫码直达百科词条

关键词：因果涌现，有效信息

张江、梁京昊 | 作者

张江、袁冰、刘凯威、杨明哲、王志鹏 | 整理&审校

1. 成块性为什么重要？

2. 最初定义

2.1 基本概念定义

2.2 简化过程定义

2.3 成块的划分

2.4 举例

3. 成块性的充分必要条件

3.1 定义三种概率

3.2 成块性充要条件定理

3.3 成块性的宏观动力学

3.4 定理1的证明

3.5 马尔科夫链的成块性

4. 成块性的正例和反例

4.1 正例

4.2 反例

4.3 一个更复杂的正例

5. 成块性满足的性质

5.1 宏观最大预测性

5.2 成块划分和粗粒化的可交换性

5.3 一致性

6. 成块性概念的变种

6.1 强成块性 Strong/Ordinary Lumpability

6.2 弱成块性 Weak Lumpability

6.3 精确成块性 Exact Lumpability

6.4 严格成块性 Strict Lumpability

6.5 准成块性 Quasi Lumpability

6.6 比例成块性 Proportional Lumpability

7. 成块性和粗粒化

7.1 基于成块性的粗粒化方法（未给定成块的划分的情况）

8. 成块性的相关概念

8.1 因果态

1. 成块性为什么重要？

为理解成块性 (lumpability) 的重要性，我们先通过一个反例来揭示不满足成块性的粗粒化方案的缺陷，从而让读者感受到引出成块性概念的必要性。给定如下图所示的马尔科夫链，假设我们尝试进行如下的粗粒化操作，即将状态{1,2}合并为宏观态 $A$ ，{3,4}合并为 $B$ 。

图1：不满足一致性粗粒化示例

当我们构建粗粒化后的尺寸为 $2$ ×2的宏观马尔科夫链 $P$ ′时，分组A到分组B的概率应满足：从 $A$ 或 $B$ 的中任一微观态出发，转移到 $A$ 或 $B$ 中各个状态的总概率必须相同，这是根据条件概率的加法公理而自然导出的要求。

例如，图中的 $P$ ′左上角的元素（组 $A$ 到组 $A$ 的概率）等于微观态1或微观态2转移到A的概率，都等于0.6。同理，右上角的元素（组 $A$ 到组 $B$ 的概率）等于0.4。

然而，当我们计算左下角的（即组 $B$ 到组 $A$ 的概率）的概率时发现：从微观态3转移到组 $A$ 的概率为0.3+0.3=0.6，从微观态4转移到组 $A$ 的概率为0.1+0.1=0.2。这种组内转移概率的冲突导致我们无法定义唯一的 $B$ →A的宏观转移概率。

为了得到一组合理的宏观转移概率，我们可以尝试如下三种取值方案：设从微观态3到A的概率=0.6；设从微观态4到A的概率=0.2；然后把0.6和0.2取平均，从而得到一个转移概率：0.4。事实上，这种方案强行构造了一个宏观的转移矩阵。这种强制定义的转移概率粗粒化方案看似合理，但是却暗藏着矛盾。

比如设左下角的所有元素的概率=0.6，右下角的所有元素概率=0.4，则我们可强行得到一个宏观转移概率矩阵（TPM）：

虽然该TPM满足马尔科夫概率转移矩阵的所有条件，但将它与微观态分布以及粗粒化操作合在一起以后，就可能导致不合理性。

例如，我们假设系统的微观初始状态分布为：(1, 0, 0, 0)，则根据我们的粗粒化方案，系统的宏观初始状态分布则会是(1, 0)。我们可以计算宏观和微观各演化2步后的概率：微观为(0.28, 0.28, 0.28, 0.16)，宏观为(0.6, 0.4)。我们发现，把两步演化后得到的微观的状态分布映射到宏观后便会得到一个宏观态分布：(0.56, 0.44)，这与前述由两步宏观动力学演化得到的状态分布(0.6, 0.4)不一样。也就是说，宏观和微观的演化结果不一致，这样的粗粒化方案被称为不满足一致性。它构建的宏观动力学无法准确地反映系统的演化，与本来的微观动力学存在偏差。

所以，我们需要一个能保证一致性的状态划分以及粗粒化方案，并根据该划分定义对应的宏观动力学，来准确反映微观动力学在宏观上的映射。而成块性是一种针对状态划分方案的指标。当一个状态划分满足成块性时，它一定能保证宏观和微观动力学的一致性。而且，它还能保证动力学算子和粗粒化算子的可交换性，也就是说，无论我们是先做粗粒化再经历动力学演化（宏观动力学演化），还是我们先经历动力学演化（微观动力学演化）再进行粗粒化，这两条路径，如图1所示，最终得到的结果都是一样的。

2. 最初定义

为了严谨地介绍成块性这一定义，我们将详细翻译文章[1]中的部分内容。读者也可直接跳到更简洁直观的‘成块性的充分必要条件'的部分。

2.1 基本概念定义

首先，我们形式化地定义微观尺度的马尔科夫链为：设微观状态空间为有限集 $S$ ={s1,s2,...,sn}，系统在 $t$ 时刻的状态分布向量 $s$ ⁽^t⁾=[Pr(s⁽^t⁾=s1),Pr(s⁽^t⁾=s2),...,Pr(s⁽^t⁾=sn)]为系统处于各个微观状态的概率，其中 $s (t)$ 表示系统在第t时刻的状态变量。

对于一个给定的微观状态空间的划分（state partition）： $A$ ={A1,A2,...,Ar}，我们可以将其视为一个宏观状态空间，其中 $A k$ 为第k个宏观态。

因此，微观状态空间 $S$ 和宏观状态空间 $A$ 之间存在硬性划分映射关系 $Φ$ :S→A，并且满足

即：1. $A$ 中的每个元素 $A$ i都包括若干个 $s$ i；2. $A$ i和 $A$ j之间没有交集，即每个 $s$ i只能属于一个 $A$ i；3. $S$ 中的每个元素都必须属于某个 $A$ 的元素，即 $A$ 覆盖了 $S$ 。

2.2 简化过程定义

我们考虑马尔科夫过程的线性投影，因此 $Φ$ 是一个 ${$ 0,1}ⁿ^×^r的投影矩阵。对于任意 $Φ$ ，我们可以定义一个简化过程（lumped process）， ${$ A⁽^t⁾:A⁽^t⁾=s⁽^t⁾Φ}，即通过投影矩阵 $Φ$ 将微观的动力学轨迹 $s$ ⁽^t⁾投影到宏观状态空间 $A$ 上。

图2：矩阵粗粒化示例

例如图2所示的4状态马尔科夫链，选择投影矩阵时，微观状态序列

(s 1, s 3, s 4, s 2, s 2, s 3)

在被分组后的状态上就表现为序列：

(A 1, A 2, A 2, A 1, A 1, A 2)

，这个序列实际上便自然定义了一个新的随机过程，我们称其为简化过程（lumped process）。

正式地，我们有定义：

定义1：简化过程（lumped process）及其重要概率

简化过程（lumped process），是微观轨迹在聚类后的状态空间上的投影。

对于投影后的轨迹 $A (t)$ ，我们可以定义三种不同概率：

其中， $π$ 为初始微观状态分布。

这些公式分别描述了：

1. 式子1.1：初始宏观状态分布：系统在 $t$ =0，在微观状态分布为 $π$ 的条件下，任意微观状态 $s$ ⁽⁰⁾属于某个宏观状态 $A$ i的概率；

2. 式子1.2：单步转移概率：已知微观状态分布为 $π$ ，并且系统在 $t$ =0的微观状态 $s$ ⁽⁰⁾属于某个宏观状态 $A$ i的条件下，那么在时间 $t$ =1时刻，系统的微观状态 $s$ ⁽¹)属于某个宏观状态 $A$ j的概率；

3. 式子1.3：历史依赖转移概率：已知微观状态分布为 $π$ ，并且已知系统的历史微观状态 ${$ s⁽⁰⁾,...,s⁽^t⁻¹⁾}分别对应某个宏观状态 ${$ Ai,Aj,⋯,Ak}，那么系统在时间 $t$ ，它的微观状态 $s$ ⁽^t⁾属于某个宏观状态 $A$ m的概率；

式子1.1, 1.2, 1.3描述的简化过程，是我们从任意一个初始状态分布 $s$ ⁽⁰⁾=π开始，走了 $t$ 步的微观动力学，然后在每一步 $t$ 做粗粒化得到 $A$ ⁽^t⁾的过程。在这里，我们强调对初始状态分布 $π$ 的依赖，是因为这三个概率的取值有可能会随着不同的 $π$ 而变化。

因为简化过程是从 $s$ ⁽^t⁾先经历微观动力学演化再粗粒化到达 $A$ ⁽^t⁺¹⁾，所以走的是图2中"微观状态->微观动力学->粗粒化->宏观状态"的这条路径（细心的读者可能会发现在图中还有另一条路径，我们会在后面讨论）。需要注意的是，虽然我们能对任意一个状态划分 $Φ$ 定义这样的简化过程，但是这些简化过程不一定会拥有马尔科夫性。

因为有些简化过程的概率会受到初始状态 $π$ 的影响，或者它们不符合马尔科夫性。如图1的例子所示，我们无法用这种‘失败’的简化过程来描述一个和微观过程保持一致的宏观动力学。下面，我们会用成块性这一新概念来定义所谓的‘成功’的动力学，即我们会把‘成功’的情况定义为成块的划分，而‘失败’的情况则是不成块的。

2.3 成块的划分

定义2：成块的划分 lumpable partition

对于一个给定的状态划分 $Φ$ ，当下列两个条件同时满足时， $Φ$ 是一个成块的划分（lumpable partition）。

1. 定义1中式子1.3所描述的简化过程具有马尔科夫性，即式子1.3可写成式子1.2的形式

2. 转移概率(transition probability)，即式子1.3或式子2，对任何微观初始状态(starting vector) $π$ 都保持一致，从而我们能够得出宏观的概率转移矩阵

其中，因为在一般情况下， $Φ$ 不是方阵，所以我们定义 $Φ$ †为 $Φ$ 的伪逆矩阵，满足 $Φ$ Φ†Φ=Φ。另外， $Φ$ TΦ是一个对角阵，对角线上的元素为每个 $A$ i包括了多少个微观状态的计数，而它的逆矩阵就是把对角线上的元素全部取倒数。

不满足上述两个条件的，都不被定义为成块的划分。也就是说，不是所有的简化过程都是成块的，即使他们的命名方式（lumped process和lumpable process）相似。

2.4 举例

下图给出两个马尔科夫链和对应分组（分组方式都是将前两个状态分为一组，后两个状态分为一组）的例子，一个是成块的，一个是不成块的：

图3：对成块的和不成块的矩阵做粗粒化

从图3的成块划分的例子中，我们看到对于分组矩阵，成块的动力学TPM可以找到一个简化过程，而这个简化过程满足马尔可夫性，且对所有初始状态都保持一致。无论

s

⁽^t⁾是什么，

{

s⁽^t⁾,s⁽^t⁺¹⁾}投影到宏观空间上的

{A (t), A (t + 1)}

的

P (A (t + 1) | A (t))

都保持一致。

对于不成块的例子，我们或许可以给它强制定义一个简化过程的TPM，比如，但这个简化过程并不能对任何微观初始状态保持一致，只能对s(t)=π=[1 0 0 0]适用。

而s(t)=π=[0 1 0 0]适不适用这个简化过程。它适用的是。这里的不适用是指，这个简化过程不能描述以这个 $π$ 为初始状态出发的微观状态序列投影的宏观状态序列。我们看到，对于这个例子，马尔科夫矩阵有两个简过程 $P$ 1′和 $P$ 2′，而它们各自只适用于一些微观初始状态(starting vector) $π$ ，并不满足定义2中的条件，所以 $Φ$ 对于这个TPM来说不是一个成块的划分。事实上，这个TPM只存在一个成块的划分，就是不做任何分组，因此它无法按照成块性的定义进行粗粒化。在后面“成块性概念的变种”的部分，我们会提到，虽然对这个TPM做的划分不符合（强）成块性的要求，但是它实际上满足弱成块性（Weak Lumpability），即简化过程对部分微观初始状态适用。

3. 成块性的充分必要条件

通过上面的例子，我们对成块性有了初步的直观理解：在成块的划分中，有两个分组，所以有四个框。每一个框里，每一列相加的和都是一样的。例如，在左上角的框中， $0.3$ +0.3=0.2+0.4。这就是成块性更通俗的解释，就是它成块了，在某些文献中，作者们会直接使用这个通俗版的解释，而且这两者之间是存在充分必要条件关系的[1]。

3.1 定义三种概率

为了后续讨论方便，我们首先引入三个概率的定义：

为状态 $s m$ 到 $s k$ 的转移概率，以及

为系统上一时刻处于微观态 $s k$ ，下一时刻处于分组 $A i$ 中的任意一个微观态的概率，以及：

为系统上一时刻处于分组 $A i$ 中的任意一个微观态，下一时刻则处于分组 $A j$ 中的任意一个微观态的概率。

3.2 成块性充要条件定理

进一步，文献[1]中提出了判断一个马尔科夫链对给定划分 $A$ 是否成块的充分必要条件为：

定理1：

给定划分 $A$ 是成块的充分必要条件为：

对于任意一对 $A i, A j$ ，每一个属于 $A i$ 的状态 $s k$ 的都是一样的：

对于都成立。

根据式子2的定义，也就是说， $A$ i里的每一个状态 $s$ k转移到 $A$ j中的所有状态的转移概率之和是相同的，即：

对于 $\forall A i, A j$ 和 $\forall s k, s l \in A i$ 都成立。

3.3 成块性的宏观动力学

满足这个条件后，我们就可以将 $A$ j中的所有微观状态 $s$ l合并为一个宏观状态 $A$ j，因为它们从其他宏观状态的转入概率是一致的。同样的，我们也可以将 $A$ i中的所有微观状态 $s$ k合并为一个宏观状态 $A$ i，因为这些微观状态 $s$ k（和 $A$ i）到其他宏观状态的转出概率是一致的。

例如，在下图中， $s$ 1和 $s$ 2都属于 $A$ 1，它们到 $A$ 1和 $A$ 2的转移概率是一样的；同样， $s$ 3和 $s$ 4都属于 $A$ 2，它们到宏观状态的转移概率也是一样的。因此， $[$ [1,2],[3,4]]是 $P$ 的一个成块划分。

图4：成块性充分必要条件实例

基于这个条件，我们可以定义成块划分的宏观动力学

A

⁽^t⁾=A⁽^t⁻¹⁾P′：

定义3：成块性的宏观动力学

对于给定的微观状态集合 $S$ ，以及微观动力学，即所有微观态转移概率和成块的划分 $A$ ，宏观动力学等于 $A i$ 中任意状态 $s k$ 到 $A j$ 的概率：

对于 $\forall k \in A i$ 都成立。

这个公式表明，群组 $A$ i到群组 $A$ j的转移概率 = 群组 $A$ i中任意状态 $s$ k到群组 $A$ j的转移概率 = 群组 $A$ i中任意状态 $s$ k到群组 $A$ j中的所有状态的转移概率之和。

我们记所有的为矩阵，这里 $M = | A |$ 。由此，我们也可以直接定义 $P$ 和 $P$ ′之间的关系：

其中， $Φ$ TΦ是一个对角阵，对角线上的元素为每个 $A$ i包括了多少个微观状态的计数，其逆矩阵就是把对角线上的元素全部取倒数。由该公式，我们便可以直接计算 $P'$ 。

根据成块划分 $Φ$ 定义好宏观动力学后，我们可以走另一条路径了：微观状态->粗粒化->宏观动力学->宏观状态。我们发现，这条路径与微观状态->微观动力学->粗粒化->宏观状态是一致的。无论从哪个微观状态出发，最终都能到达相同的宏观状态。所以，这满足了动力学和粗粒化这两个算子的可交换性（Exchangeability）。具体的证明将在后面的‘成块性满足的性质’部分介绍。

3.4 定理1的证明

这里，我们翻译了作者在书[1]中提供的定理1的必要性和充分性的证明。

必要性部分的证明：

必要性是指，如果一个马尔可夫链的划分 $A$ 是成块的，那么它必然满足上述条件。

从成块的划分的定义可知， $A$ 的转移概率满足宏观马尔可夫性，且这个转移概率对每个 $π$ 保持一致。也就是说，无论从哪个具体的初始状态 $π$ 开始，只要它属于 $A$ i这个群组里，在 $t$ =1时刻转移到 $A$ j的概率都是相同的。

我们设这个（ $A$ i中任意微观状态 $s$ k的）共同的转移概率为。当初始状态 $π$ 属于某个 $A$ i时，。

所以，这表明，如果一个马尔可夫链的简化过程满足成块性，那么从任一集合到另一集合的转移概率必须是一个集合间的固定值，而与集合内的具体状态（无论是 $π$ 还是 $s$ k）无关。这个固定值正是式子5定义的宏观状态转移概率，所以满足了该条件。

充分性部分的证明：

充分性是指，如果一个马尔可夫链的某个状态划分 $A$ 满足这个条件，那么它就是成块的。我们需要证明的是，如果上述条件满足，那么马尔可夫性成立，即对于任何给定的 $t$ ，转移概率只依赖于 $t$ −1时刻的宏观态 $A$ i和 $t$ 时刻的宏观态 $A$ j，而不依赖于 $t$ −1的 $A$ i中的具体状态是哪个 $s$ ⁽^t⁻¹⁾，或是 $t$ −1前的宏观状态。

这个条件要求 $t$ −1时刻属于 $A$ i的任一微观态 $s$ k，转移概率，这意味着无论我们从 $A$ i中的哪个微观状态开始，转移到 $A$ j的概率都是相同的。

因此，当我们已知 $t$ −1的宏观状态是 $A$ i时，计算 $t$ 时刻转移到 $A$ j的概率时，我们只需要使用，而不需要关心 $A$ i中的具体状态。

由于转移概率只依赖于群组 $A$ i和 $A$ j，而不依赖于 $A$ i中的具体状态，因此我们可以将 $A$ i中的所有状态合并为一个状态，并且合并后的链仍满足马尔可夫性。所以，上述条件为成块性的充分条件。

从这两个证明里，我们也可以看到微观动力学路径和宏观动力学路径的一致性。无论我们从 $A$ i中的哪个具体状态 $s$ ⁽^t⁻¹⁾开始，只要当前的宏观状态是 $A$ i，我们就可以计算下一步转移到 $A$ j的概率，而不依赖于 $s$ ⁽^t⁻¹⁾。这表明，微观 $s$ ⁽^t⁻¹⁾->宏观 $A$ ⁽^t⁻¹⁾->宏观动力学-> $A$ ⁽^t⁾不会影响未来状态的预测，因此微观和宏观两个路径得出的 $A$ ⁽^t⁾的概率是一致的。同样的，具体的证明将在后面的‘成块性满足的性质’部分介绍。

3.5 马尔科夫链的成块性

请注意：成块性有一个非常重要的前提：我们需要给定一个对马尔科夫链的状态划分，然后根据马尔科夫状态转移矩阵来判断这个划分对这个马尔科夫链是否成块。

所以，正式来说，成块性并不是一个马尔科夫链本身的属性，而是对马尔科夫链的某个状态划分的属性。这一前提也提醒我们，在讨论成块性时，必须明确状态划分的方式。不同的划分方式可能导致不同的结论。一个马尔科夫链可能在某种划分下是成块的，而在另一种划分下则不成块。因此，成块性更多地反映了状态划分与马尔科夫链的适配性，而不是马尔科夫链本身的特性。

然而，有时候为了简略表达，我们可以定义马尔科夫链的成块性为：

定义：马尔科夫链的成块性：

若给定马尔科夫链，并且存在一个成块的状态划分 $A$ ，且该划分不能是微观矩阵本身，划分后的宏观态数量须少于微观态数量，那么我们称该链是成块的。

4. 成块性的正例和反例

对于一个马尔科夫链，有些分组是成块的，有些分组是不成块的。这里，我们给出两个简单的例子，分别提供了正例和反例。

我们用到的是这样一个转移矩阵：

4.1 正例

我们可以看到，123行都是一样的，所以把 ${$ s1,s2,s3}分在一组 $A$ 1，并把状态 $s$ 4分在另外一组 $A$ 2，是一个成块的划分。接下来我们来计算一下。

计算结果符合定理1，所以这个划分是成块的。而对应的宏观动力学为：

4.2 反例

现在我们来看一个反例：把状态1、2分为一组，状态3、4分为另一组。同样的，我们来计算一下。这次我们需要对3和4分开计算了。

这里我们就能看到，，当同一组的两个状态 $s$ 3和 $s$ 4对其他组的转移概率不一样的话，我们无法确定的取值是或。

如果我们强行按照这样来分组，假设，我们会发现这样的粗粒化结果违背了成块性一开始的定义2，即粗粒化后的转移概率对所有的初始微观状态 $π$ 都适用。因为当 $π$ =s4的时候，这个转移概率就是错的，即使 $π$ ≠s4，任何初始微观状态 $π$ 都会在某时刻 $n$ 达到 $s$ 4并导致转移概率出错。

4.3 一个更复杂的正例

三个相同状态的例子可能稍微有点简单，接下来我们来看一个稍微复杂一点的例子：

对于这个马尔科夫矩阵， ${$ {1,2},{3,4}}是一个成块的分组。分组后的转移矩阵为：

5. 成块性满足的性质

在马尔科夫链的粗粒化过程中，我们通常有多个目标：

降低压缩后的动力学维度，以简化模型复杂性；

保留动力学中有用的信息，以确保模型的有效性；

保持压缩前后过程的一致性，以确保模型的可靠性。

然而，这些目标之间往往存在矛盾：压缩的维度越多，保留的信息就越少，压缩前后的一致性就越难保持。成块性作为一种较为严格的划分方式，虽然在压缩维度上可能不如其他方法显著，但它能够保留在宏观层面上所有有用的信息，并且确保粗粒化前后过程的一致性。

除此之外，成块性的划分及对应的动力学的粗粒化还具备很多良好的性质。

5.1 宏观最大预测性

宏观最大预测性是指，在将微观状态粗粒化为宏观状态后，我们就不再需要微观状态了，只用宏观状态就能预测后续的宏观状态。

具体来说，我们只需要知道宏观状态 $A$ ⁽^t⁾，就可以最大化地预测 $A$ ⁽^t⁺¹⁾，而微观状态 $s$ ⁽^t⁺¹⁾虽然能提供一些额外信息，但是对于预测 $A$ ⁽^t⁺¹⁾并无帮助。这意味着条件互信息 $I$ (A⁽^t⁺¹⁾;s⁽^t⁺¹⁾|A⁽^t⁾)=0。宏观动力学不需要任何来自微观状态的修正，就能独立且正确地反映系统在宏观层面上的演化。

尽管成块性划分能够准确预测宏观动力学，但它无法确保像计算力学中的因果态那样的微观最大预测性。因为在聚类过程中会损失微观状态的信息，使得我们无法辨别某个 $A$ ⁽^t⁾具体是哪个微观态 $s$ (^t⁾。这个信息的损失是不可逆的，所以从微观粗粒化到宏观之后，就无法再还原到微观了。

5.2 成块划分和粗粒化的可交换性

为了说明所谓的可交换性的概念，我们绘制了粗粒化操作和动力学演化算子之间的关系，示意图如下：

图5：粗粒化图例

图5展示了从某个微观状态 $s$ ⁽^t⁾出发，到达下一刻的宏观状态 $A$ ⁽^t⁺¹⁾的两条路径[2]：

先经过微观动力学达到 $s$ ⁽^t⁺¹⁾，再进行粗粒化得到 $A$ ⁽^t⁺¹⁾

先进行粗粒化得到 $A$ ⁽^t⁾，再经过宏观动力学到达 $A$ ⁽^t⁺¹⁾

如果我们把粗粒化和（宏观/微观）动力学看作是两个算子，那这两个算子的可交换性指的是：无论从哪个微观状态分布出发，走这两条路径得到的 $A$ ⁽^t⁺¹⁾的分布是一样的，即， $s (t) Φ P' = s (t) P Φ$ 。

对于一个成块的 $P$ ，和它的成块划分 $Φ$ ，我们首先展示的例子，其他情况类似。

对于这个 $Φ$ ，我们知道 $。$

$由于$ 和各自等于多个元素，。这相当于将 $P$ 的每一行按照划分进行加总，而 $P$ Φ中同一组的行是相同的。

另一方面， $Φ$ P′的含义是将 $P$ ′的每一行按照 $Φ$ 复制到对应的微观状态的行中。所以，我们会发现 $Φ$ P′和 $P$ Φ的结果是一样的。

推广到所有 $Φ$ 的情况的证明如下：

首先，，即将 $P$ 的每一行按照划分进行加总。

而 $Φ$ P′是把 $P$ ′的每一行按照 $Φ$ 复制到对应的微观状态的行中，所以当 $Φ$ _i_k=1时，。

根据成块性的定义，当 $Φ$ _i_k=1，即状态 $i$ 属于第 $k$ 组时，状态 $i$ 转移到第 $j$ 组的概率，所以 $Φ$ P′=PΦ，交换律成立。

5.3 一致性

当我们对一个成块的马尔科夫链，使用基于成块性划分的粗粒化方法构建了宏观动力学后，该宏观动力学与本来的微观动力学会保持一致 (Consistent)。

在本词条第8章，我们会指出基于成块性划分的粗粒化方法和HOM粗粒化方法的结果一致，而因为实验证明了HOM粗粒化方法能够保证一致性，因此基于成块性划分的粗粒化方法也能保证一致性。

具体的动力学的一致性检验方法请参考复杂网络中的因果涌现。

6. 成块性概念的变种

尽管成块性具有许多优良的特性，但它本身是一个非常严格的条件。在实际应用中，如果不允许一定的误差，几乎很难找到满足成块性的划分，从而难以对马尔科夫链进行有效的粗粒化。因此，成块性衍生出了多种变种概念，这些变种通过放宽某些限制条件，使得在实际问题中更容易找到有效的划分，并研究这些划分在多大程度上保留了宏观最大预测性、可交换性、一致性等重要性质。

6.1 强成块性 Strong/Ordinary Lumpability

为了与更多的成块性拓展概念相区分，上述成块性概念也被人们称为强成块性（Strong lumpability），或称作原始成块性（ordinary lumpability）。这种成块性是限制较严格的一种成块性概念。它要求矩阵具有严格的分块性，即同一组中的每个状态到其他分组的转出概率必须完全相同。

这里的'Strong'是与下面的'weak'相对的概念，指的是简化过程必须对任意初始状态分布都保持一致。

简单的例子：

此例子中， $[$ [1,2],[3,4]]是一个强成块的分组。

6.2 弱成块性 Weak Lumpability

弱成块性（weak lumpability）[1]是指简化过程仅对某些初始状态满足成块性，而不是对所有初始状态都满足。

例如，我们有一个简化过程，从 $s$ i出发时能满足成块性（式子2），但从 $s$ j出发时不满足。当 $s$ i到 $s$ j之间不连通，且初始状态为 $s$ i时，由于永远不会到达 $s$ j，该简化过程会一直满足成块性。

简单的例子：

此例子中， $[$ [1,2],[3],[4]]是一个强成块的分组。

我们留意到，该马尔科夫链从 $s$ 1或者 $s$ 2状态出发时，永远不会到达 $s$ 3和 $s$ 4。所以当我们把 $s$ 3和 $s$ 4划成一组，即分组为 $[$ [1,2],[3,4]]时，分组后的简化过程，如仍满足式子2的马尔科夫性约束。所以，对于 $s$ 1或者 $s$ 2项非零，而 $s$ 3和 $s$ 4项为零的初始状态分布 $π$ ， $[$ [1,2],[3,4]]是成块的。

对于 $s$ 3和 $s$ 4项非零的初始状态分布 $π$ ， $[$ [1,2],[3,4]]分组不满足式子2。所以，该分组仅对某些初始状态分布成块，故为弱成块分组。

6.3 精确成块性 Exact Lumpability

在强成块性中，要求分组内每一行的加总相同，即同一组中的每个状态到其他分组的转出概率相同。

而在精确成块性（exact lumpability）中，则要求分组内的每一列的加总相同，即同一组中的每个状态从其他分组的转入概率相同。

在文献[3]中给出的正式定义是： $P$ 的转置经过行归一化是强成块的。

另外，文献[3]还指出，精确成块的 $P$ 也是弱成块的。

在强成块性的例子中， $[$ [1,2],[3,4]]是一个强成块的分组，但不是一个精确成块的分组。

我们再举一个例子：

此例子中， $[$ [1,2],[3,4]]不是一个强成块的分组，但是一个精确成块的分组，这是因为每一个分块的列求和后的概率都相等。

6.4 严格成块性 Strict Lumpability

严格成块性（strict lumpability）[3]是指一个马尔可夫链同时满足强成块性和精确成块性。也就是说，同一组中的每个状态不仅从另一个分组的转入概率相等，而且到另一个分组的转出概率也相等。这是目前我们已知的最强的一种成块性。

简单的例子：

此例子中， $[$ [1,2],[3,4]]既是一个强成块的分组，又是一个精确成块的分组。

6.5 准成块性 Quasi Lumpability

强成块性对马尔科夫矩阵的分块性要求非常严格。在实际应用中，很难找到完全满足强成块性的矩阵，即使矩阵受到微小扰动，也可能不再满足成块性。为了考虑这种扰动情况，我们可以定义不成块但非常接近成块的情况[4]：

如果一个矩阵 $P$ 可以被分解为 $P$ =P−+Pϵ，其中 $P$ −是一个成块的矩阵，而 $P$ ϵ中的每个元素都小于 $ϵ$ ， $P$ 就是一个 $ϵ$ -准成块的矩阵。

比如说，我们对上面的成块的例子加上一点扰动：

就能获得一个 $ϵ$ -准成块的矩阵，其中 $ϵ$ =0.02。

6.6 比例成块性 Proportional Lumpability

比例成块性（Proportional Lumpability）[5]是基于连续时间马尔科夫链（CTMC）提出的，用于放松成块性限制的概念。目前尚未发现有研究直接将该概念应用于离散时间马尔科夫链（DTMC）。

如果将 DTMC 的转移概率矩阵 $P$ 视为一个差分算子，那么我们可以大概把CTMC的转移概率矩阵 $Q$ 看作是一个微分算子，详情请参阅马尔科夫链。 $Q$ 矩阵定义如下：

令 $I$ 为一个可数集， $I$ 上的矩阵 $Q$ =(q_i_j:i,j∈I)若满足下面三个条件，则称其为 $Q$ 矩阵：

有上面三个条件可知 $Q$ 矩阵的每一行中的非对角线元素可以为任意非负实数，只需要满足每行非对角元素之和有限这一个限制：。由于条件3使每一行的行和为零，所以对角线元素。 $Q$ 矩阵的非对角线元素 $q$ _i_j描述的是状态 $i$ 转移到状态 $j$ 的‘速率’（rate）。

强成块性在CTMC设定下跟DTMC是类似的，简单来说就是：

对于 $Q$ 矩阵，微观的离散状态空间 $S$ ，分组后的宏观状态空间 $A$ ，如果 $Q$ 满足强成块性的话：

其中，为微观状态 $s$ i到宏观状态 $A$ m的转移速率。也就是说，属于同一组的任意微观状态转移到宏观状态的‘速率’是一样的。

在CTMC设定下，比例成块的正式定义如下：

对 $S$ 中的任意一个状态，存在一个函数，使得：

我们称这样的CTMC对分组 $A$ 是 $κ$ -比例成块的。

不像DTMC的转移概率矩阵 $P$ 有一个每行加和为1的条件，CTMC设定下每行的转出速率，也就是非对角线元素之和，并没有数值上的约束。

所以，比例成块性描述的是，对一个本来强成块的 $Q$ ′的每一行 $i$ 乘以一个系数 $κ$ (si)，使得每行的转出速率都不一致的情况。反过来说，如果我们对于一个 $Q$ 的每一行的转出速率进行一个‘对齐’后能获得一个强成块的 $Q$ ′的话，那么 $Q$ 就是比例成块的。因为，

其中 $为强成块矩阵$ 。

目前，暂时没有在DTMC上的比例成块性定义。虽然CTMC上的定义比较简单，但无法直接迁移到DTMC上。这是因为从CTMC的速率矩阵 $Q$ 到DTMC的转移矩阵 $P$ 之间需要经过一个的泰勒展开转换， $t$ 为步长时间。

所以， $Q$ 和 $Q$ ′=KQ对应的转移矩阵分别为_和，并无简单的对应关系。

下面是CTMC的强成块性和比例成块性例子示意图：

图8：CTMC的强成块性和比例成块性例子示意图。Q1, Q2为强成块Q矩阵，Q3为比例成块Q矩阵，P1, P2, P3为对应的DTMC TPM。

其中， $Q$ 1为强成块的Q矩阵，设 $t$ =1代入 $P$ (t)=exp(tQ)，我们会得到一个强成块的 $P$ 1。

为什么强成块的Q矩阵能得到强成块的P矩阵呢？当我们计算P矩阵时，我们需要进行泰勒展开。这里我们检查一下展开中的 $($ Q1)2项。以这个例子为例， $q$ 13+q14=q23+q24。通过计算得知，

这里我们只计算了，但类似的计算可以放在 $Q$ 1的任意的分组里。

同样的，我们能用类似的方式来计算 $Q$ 的任意幂矩阵 $Q$ n，发现 $Q$ n也是强成块的。所以，也是强成块的。

接着，我们把 $Q$ 1中所有元素乘以2，得到 $Q$ 2，会得到另一个跟 $P$ 1不一样的强成块的 $P$ 2。这说明，在Q矩阵上的改动，反映到P矩阵上并不是简单的线性关系。

我们发现 $P$ 2的对角线元素较 $P$ 1小，而非对角线元素则较大。这是因为在 $Q$ 2中，随机游走粒子从每个状态离开的速率都增大了，所以会倾向流向其他状态，而不是回到本状态。

最后，我们把 $Q$ 1中第二行元素乘以2，得到一个比例成块的 $Q$ 3，并得到对应的 $P$ 3。因为对第二行进行了改动，所以 $P$ 3中 $s$ 1和 $s$ 2就不再满足能放在同一组里的条件，但 $s$ 3和 $s$ 4仍能划分在同一组里。所以， $P$ 3的强成块分组为 ${$ 1},{2},{3,4}。

在该例子中，虽然从 $Q$ 1到 $Q$ 3之间的操作比较简单，但 $P$ 1和 $P$ 3之间并没有一个明显的对应关系。比较清楚的是，当我们把 $Q$ 3的第2行速率调快了之后，停留在 $s$ 2的概率变小了，所以 $P$ 3的第2列就变小了。

这六种成块性的定义按照限制严格度大概的排序是：

准成块 Quasi < 比例成块 Proportional < 弱成块 Weak < 精准成块 Exact < 强成块 Strong/Ordinary < 严格成块 Strict

7. 成块性和粗粒化

马尔科夫链的粗粒化可以理解为对一个马尔科夫转移概率矩阵（TPM）进行分组，得到一个分组矩阵 $Φ$ 和它对应的宏观TPM $P$ ′。这一过程通常可以分为两部：先进行状态划分 $Φ$ ，再基于 $Φ$ 获取 $P$ ′。

对状态空间做粗粒化有硬划分和软划分两种。软划分可以看作把微观状态打散重构成了一些宏观状态，而硬划分则更为严格，直接将若干个微观状态划分为一个组。本文仅讨论硬划分，不涉及软划分。

成块性是对第一步，即对 $Φ$ 的约束要求；而上面提到的宏观最大预测性、可交换性和一致性是对 $P$ ′的约束。

从前面的成块性公式2和例子中，我们可以直观地理解：当马尔科夫矩阵存在块状结构，或者状态明显可以被划分为几类时，根据这样的划分，该矩阵就是成块的。对于简单的 $P$ ，如图8中的所示，我们能够根据上面的定理1很快的找出它的成块划分 $Φ$ ，并通过定义3迅速计算出对应的 $P$ ′。

7.1 基于成块性的粗粒化方法（未给定成块的划分的情况）

图8：Zhang[6] 文章中的示意图。图中左面四个矩阵都是成块的马尔科夫矩阵，而右面的P2是一个噪声矩阵，(P1)T P2 = 0

然而，在实际应用中，我们经常遇到的矩阵可能并不完美。例如，成块的矩阵的状态排序可能被打乱（如图8中的 $P$ 1），或者矩阵包含了如 $P$ 2的噪声（如图8中的 $P$ ， $P$ =P1+P2，）。

在这种情况下，我们通常面临的是像 $P$ 这样的矩阵。我们既无法确定它是否成块，也无法决定它的划分，甚至不知道它的马尔科夫秩。

针对这一问题，Anru Zhang[6]提出了一种寻找最优划分的方法。通过这种方法，我们可以找到最优的划分，并基于这个划分判断一个马尔科夫矩阵是否成块。具体步骤如下：

获取一个n*n维的马尔科夫矩阵P，或者是马尔科夫链的频率采样；

获取 $r$ <n 的马尔科夫秩，或指定一个 $r$ ；

对P进行SVD分解， $P$ =UΣVT，其中U为左奇异向量，V为右奇异向量。

通过下列公式得到最优划分 $Ω$ 1,Ω2,...,Ωr

其中， $v$ s是第 $s$ 类 $Ω$ s的特征向量。

这个算法的核心思想是：在最优的划分中， $Ω$ s中的状态 $i$ 的右奇异向量会和 $v$ s距离最小，也就是说，让每个微观态的右特征向量和它对应的宏观态的右特征向量尽可能接近。

这个算法看起来非常熟悉，实际上它与 k-Means 聚类算法非常相似。让 $v$ s和组里的 $V$ [i,:r]距离最小的方法，就是让 $v$ s成为 $V$ [i,:r]这若干个点的中心。

回顾一下k-Means算法把n个点聚成r类的目标函数，其中第 $i$ 个点被归到第 $c$ i类，而 $μ$ j为第 $j$ 类点的中心点：

我们看到这两个目标函数非常相似。因此，我们可以通过上述算法或 k-Means 聚类来获取最优的状态划分，进而判断马尔科夫矩阵的成块性。

8. 成块性的相关概念

8.1 因果态

因果态是计算力学中的一个概念，主要用于对历史状态序列的粗粒化划分，详情请参考计算力学。

定义 $t$ 时刻及以前的历史状态序列为，未来状态为 $t$ 时刻以后的状态序列。

对历史状态序列进行划分后得到的宏观态集合，其为因果态的充要条件是：

对于任意的宏观态，，有：，其中。

把马尔科夫链的状态分组和因果态理论中的粗粒化划分进行对比，我们发现成块性的要求和因果态的要求非常相似：它们都给出了一种对未来状态做预测的等价性。但是，二者又有区别，区别有以下三点：

1. 马尔可夫性假设

因果态并没有马尔科夫性的假设，但我们总可以把一个序列看成是一个状态，于是就能得到序列映射到序列的马尔科夫转移矩阵。在该概率转移矩阵上，我们可以比较因果态对应的划分映射和满足成块性的划分。

2. 微观和宏观最大预测性

上文提到，因果态的状态划分方式能保持微观层面上的最大预测性。也就是说，我们根据微观状态找到对应的因果态之后，即使我们不知道原本的微观状态了，我们还是能准确的得到未来的微观状态的分布。

而成块性与其不同的是，我们根据微观状态找到对应的宏观状态之后，能够准确的得到未来的宏观状态的分布。但是在粗粒化过程中，我们会丢失微观状态的辨别信息，而这个信息的损失是不可逆的。所以，我们就无法从宏观状态再还原到微观状态了。

所以，因果态同时保持了微观和宏观的最大预测性，而成块性只能保持宏观的最大预测性。

3. 因果态比成块性更严格，划分的成块性是满足因果态要求的必要条件

按照上面的叙述，我们会发现，因果态是比成块性更严格的限制，因为它要求在状态转移矩阵中，属于同一个因果态中的状态的行必须完全一致。

因果态的划分一定是一种成块的状态划分，但反之则不一定。所以说，划分的成块性是满足因果态要求的必要不充分条件。

二者之间的区别也可以用下图进行直观表示：

该图展示了我们是怎么处理和理解因果态和成块性的。首先，我们把每条序列看作是一个状态，把序列压缩到了一个 $t$ 时刻的状态空间，并用一个转移矩阵来描述状态（序列）之间的转移概率。

在因果态中，我们只需要对比转移矩阵的行，把相同的行划分成一组；而在成块性中，我们需要同时考虑矩阵的行与列，通过比较每一行到某几列的转移概率来做分组。

参考文献

1. Kemeny, John G., and J. Laurie Snell. Finite markov chains. Vol. 26. Princeton, NJ: van Nostrand, 1969. https://www.math.pku.edu.cn/teachers/yaoy/Fall2011/Kemeny-Snell_Chapter6.3-4.pdf

2. Coarse graining. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Coarse_graining&oldid=16170

3. Buchholz, Peter. "Exact and ordinary lumpability in finite Markov chains." Journal of applied probability 31.1 (1994): 59-75.

4. Franceschinis, Giuliana, and Richard R. Muntz. "Bounds for quasi-lumpable Markov chains." Performance Evaluation 20.1-3 (1994): 223-243.

5. Piazza, Carla, and Sabina Rossi. "Reasoning about proportional lumpability." International Conference on Quantitative Evaluation of Systems. Cham: Springer International Publishing, 2021.

6. Zhang, Anru, and Mengdi Wang. "Spectral state compression of markov processes." IEEE transactions on information theory 66.5 (2019): 3202-3231.

本词条由集智俱乐部众包生产，难免存在纰漏和问题，欢迎大家留言反馈或者前往对应的百科词条页面进行修改，一经修改，可以获得对应的积分奖励噢！

加入我们

亲爱的社区成员和知识爱好者：

我们正在寻找对知识分享充满热情的志愿者，加入我们的集智百科词条编写团队！无论你是某个领域的专家，还是对某一主题有浓厚兴趣，我们都欢迎你的加入。通过编写和编辑百科词条，你将有机会为全球读者提供准确、权威的信息，同时提升自己的写作和研究能力。

我们需要的帮助

编写新的集智百科词条，涵盖复杂系统、人工智能等多个领域

更新和完善现有词条，确保信息的准确性和时效性

校对和审核其他志愿者提交的内容，确保词条质量

我们希望你具备

良好的写作能力，能够清晰、简洁地表达复杂的概念

对某一领域有深入了解或浓厚兴趣

具备基本的网络搜索和信息整理能力

有责任心和团队合作精神，愿意为知识共享贡献力量

如果你对知识分享充满热情，愿意为全球读者提供有价值的信息，请立即加入我们！

扫码填表，添加负责人微信

让我们一起，用知识连接世界！

因果涌现读书会第六季

在霓虹灯的闪烁、蚁群的精密协作、人类意识的诞生中，隐藏着微观与宏观之间深刻的因果关联——这些看似简单的个体行为，如何跨越尺度，涌现出令人惊叹的复杂现象？因果涌现理论为我们揭示了答案：复杂系统的宏观特征无法通过微观元素的简单叠加解释，而是源于多尺度动态交互中涌现的因果结构。从奇异值分解（SVD）驱动的动态可逆性分析，到因果抽象与信息分解的量化工具，研究者们正逐步构建起一套跨越数学、物理与信息科学的理论框架，试图解码复杂系统的“涌现密码”。

为了系统梳理因果涌现最新进展，北京师范大学系统科学学院教授、集智俱乐部创始人张江老师领衔发起「因果涌现第六季」读书会，组织对本话题感兴趣的朋友，深入研读相关文献，激发科研灵感。

读书会将从2025年3月16日开始，每周日早9:00-11:00，持续时间预计10周左右。每周进行线上会议，与主讲人等社区成员当面交流，之后可以获得视频回放持续学习。诚挚邀请领域内研究者、寻求跨领域融合的研究者加入，共同探讨。