马尔科夫链的成块性 - 版本历史

2026年11月1日 (日) 05:46 Jake

2026-11-01T05:46:10Z

Liangjh：/* 成块划分和粗粒化的可交换性 */

2026-05-01T09:14:43Z

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

Jake：/* 成块性为什么重要？ */

2025-07-27T03:39:02Z

成块性为什么重要？

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

2025-05-11T06:19:01Z

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

Liangjh：/* 比例成块性 Proportional Lumpability */

2025-05-09T08:58:30Z

比例成块性 Proportional Lumpability

Liangjh：/* 比例成块性 Proportional Lumpability */

2025-04-26T13:13:26Z

比例成块性 Proportional Lumpability

Liangjh：/* 比例成块性 Proportional Lumpability */

2025-04-26T12:39:54Z

比例成块性 Proportional Lumpability

Liangjh：/* 比例成块性 Proportional Lumpability */

2025-04-26T06:41:09Z

比例成块性 Proportional Lumpability

Liangjh：/* 比例成块性 Proportional Lumpability */

2025-04-25T15:21:34Z

比例成块性 Proportional Lumpability

Liangjh：/* 比例成块性 Proportional Lumpability */

2025-04-25T11:18:31Z

比例成块性 Proportional Lumpability

←上一版本		2026年11月1日 (日) 05:46的版本
第1行：		第1行：
−	成块性（Lumpability）是[[马尔科夫链的粗粒化]]~~理论中一种描述是否可聚类或可粗粒化的概念，最早由Kemeny和Snell在其1969年的著作Finite~~ Markov Chains<ref name=":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</ref>中提出。Lump一词有‘块’的意思。判断一个[[马尔科夫链]]是否可成块（lumpable），就是要判定是否存在一种状态划分方式，能够将原始的马尔科夫链压缩为一个保留其主要动力学特征的简化链。	+	成块性（Lumpability）是[[马尔科夫链的粗粒化]]理论中一种描述是否可聚类或可粗粒化的概念，最早由Kemeny和Snell在其1960年的著作Finite Markov Chains<ref name=":1">Kemeny, John G., and J. Laurie Snell. ''Finite markov chains''. Vol. 26. Princeton, NJ: van Nostrand, 1960. https://www.math.pku.edu.cn/teachers/yaoy/Fall2011/Kemeny-Snell_Chapter6.3-4.pdf</ref>中提出。Lump一词有‘块’的意思。判断一个[[马尔科夫链]]是否可成块（lumpable），就是要判定是否存在一种状态划分方式，能够将原始的马尔科夫链压缩为一个保留其主要动力学特征的简化链。

←上一版本		2026年5月1日 (五) 09:14的版本
第407行：		第407行：

	根据成块性的定义，当<math>\Phi_{ik} = 1</math>，即状态<math>i</math>属于第<math>k</math>组时，状态<math>i</math>转移到第<math>j</math>组的概率<math>=\sum_m (P_{im} \Phi_{mj})=P'_{kj}</math>，所以<math>\Phi P' = P \Phi</math>，交换律成立。		根据成块性的定义，当<math>\Phi_{ik} = 1</math>，即状态<math>i</math>属于第<math>k</math>组时，状态<math>i</math>转移到第<math>j</math>组的概率<math>=\sum_m (P_{im} \Phi_{mj})=P'_{kj}</math>，所以<math>\Phi P' = P \Phi</math>，交换律成立。
		+
		+
		+
		+	反过来，如果粗粒化和动力学演化满足可交换性，即存在某个宏观转移矩阵 <math>P'</math>，使得
		+	<math>
		+	P\Phi=\Phi P'
		+	</math>
		+	那么也可以推出该划分满足成块性。
		+
		+	设状态 <math>i</math> 和状态 <math>i'</math> 属于同一个宏观块 <math>A_k</math>，也就是 <math>\Phi_{ik}=\Phi_{i'k}=1</math>。由于 <math>\Phi P'</math> 的作用是把宏观转移矩阵 <math>P'</math> 的第 <math>k</math> 行复制到所有属于 <math>A_k</math> 的微观状态行上，因此对于任意宏观块 <math>A_j</math>，都有
		+	<math>
		+	(\Phi P')_{ij} = P'_{kj}
		+	</math>
		+	以及
		+	<math>
		+	(\Phi P')_{i'j} = P'_{kj}
		+	</math>
		+	所以
		+	<math>
		+	(\Phi P')_{ij}=(\Phi P')_{i'j}
		+	</math>
		+
		+	又因为可交换性假设给出 <math>P\Phi=\Phi P'</math>，于是
		+	<math>
		+	(P\Phi)_{ij}=(P\Phi)_{i'j}
		+	</math>
		+
		+	而 <math>(P\Phi)_{ij}</math> 的含义是状态 <math>i</math> 转移到宏观块 <math>A_j</math> 的总概率：
		+	<math>
		+	(P\Phi)_{ij}=\sum_{m}P_{im}\Phi_{mj}=\sum_{s_m\in A_j}P_{im}
		+	</math>
		+	因此，对任意同属 <math>A_k</math> 的微观状态 <math>i,i'</math>，以及任意宏观块 <math>A_j</math>，都有
		+	<math>
		+	\sum_{s_m\in A_j}P_{im}
		+	=
		+	\sum_{s_m\in A_j}P_{i'm}
		+	</math>
		+	这正是成块性的充分必要条件。
		+
		+	因此，在强成块/ordinary lumpability 的意义下，成块性与“存在宏观转移矩阵 <math>P'</math> 使得 <math>P\Phi=\Phi P'</math>”是等价的。也就是说，成块性不是可交换性的一个附加性质，而是马尔科夫链中实现精确可交换粗粒化的具体结构条件。

	===一致性===		===一致性===

←上一版本		2025年7月27日 (日) 03:39的版本
第10行：		第10行：

	==成块性为什么重要？==		==成块性为什么重要？==
		+
		+	在[[因果涌现]]等研究中，需要对一个[[马尔可夫链]]进行[[粗粒化]]操作，即将马尔科夫链的状态数减少，并尽可能保持它的动力学不变，这就要求粗粒化操作和马尔科夫链的时间演化这两个操作必须保证是[[可交换的]]，因此这就直接可以导出马尔科夫链成块性的条件。

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

@@ 第708行： / 第708行： @@
-这个算法看起来非常熟悉，实际上它与 k-Means 聚类算法非常相似。让<math>v_s</math>和组里的<math>V[i:r]</math>距离最小的方法，就是让<math>v_s</math>成为<math>V[i:r]</math>这若干个点的中心。
+这个算法看起来非常熟悉，实际上它与 k-Means 聚类算法非常相似。让<math>v_s</math>和组里的<math>V[i,:r]</math>距离最小的方法，就是让<math>v_s</math>成为<math>V[i,:r]</math>这若干个点的中心。
 回顾一下k-Means算法把n个点聚成r类的目标函数，其中第<math>i</math>个点被归到第<math>c^i</math>类，而<math>\mu_j</math>为第<math>j</math>类点的中心点：
@@ 第715行： / 第715行： @@
 我们看到这两个目标函数非常相似。因此，我们可以通过上述算法或 k-Means 聚类来获取最优的状态划分，进而判断马尔科夫矩阵的成块性。
 ==成块性的相关概念==

←上一版本		2025年5月9日 (五) 08:58的版本
第614行：		第614行：


−	~~不像DTMC的移概率矩阵~~<math>P</math>有一个每行加和为1的条件，CTMC设定下每行的转出速率，也就是非对角线元素之和<math>\sum_{j\neq i}q_{ij}</math>，并没有数值上的约束。	+	不像DTMC的转移概率矩阵<math>P</math>有一个每行加和为1的条件，CTMC设定下每行的转出速率，也就是非对角线元素之和<math>\sum_{j\neq i}q_{ij}</math>，并没有数值上的约束。

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

@@ 第636行： / 第636行： @@
 其中，<math>Q_1</math>为强成块的Q矩阵，设<math>t=1</math>代入<math>P(t) = exp(tQ)</math>，我们会得到一个强成块的<math>P_1</math>。
-为什么强成块的Q矩阵能得到强成块的P矩阵呢？以这个例子为例，<math>q_{13}+q_{14} = q_{23}+q_{24}</math>。当我们计算P矩阵时，我们需要进行泰勒展开。这里我们检查一下展开中的<math>(Q_1)^2</math>项。通过计算得知，
+为什么强成块的Q矩阵能得到强成块的P矩阵呢？当我们计算P矩阵时，我们需要进行泰勒展开。这里我们检查一下展开中的<math>(Q_1)^2</math>项。以这个例子为例，<math>q_{13}+q_{14} = q_{23}+q_{24}</math>。通过计算得知，
 <math>
@@ 第648行： / 第648行： @@
 </math>
-同样的，如果<math>Q</math>强成块的话，<math>Q</math>的幂矩阵<math>Q^n</math>也是强成块的，所以<math>P = \sum_{n=0}^\infty \frac{ (tQ)^n }{ n! }</math>也是强成块的。
+这里我们只计算了<math>(Q_1^2)_{13}+(Q_1^2)_{14} = (Q_1^2)_{23}+(Q_1^2)_{24}</math>，但类似的计算可以放在<math>Q_1</math>的任意的分组里。
-对<math>Q_1</math>中'''所有元素'''乘以2，得到<math>Q_2</math>，会得到另一个跟<math>P_1</math>不一样的强成块的<math>P_2</math>。这说明，在Q矩阵上的改动，反映到P矩阵上并不是简单的线性关系。
 我们发现<math>P_2</math>的对角线元素较<math>P_1</math>小，而非对角线元素则较大。这是因为在<math>Q_2</math>中，随机游走粒子从每个状态离开的速率都增大了，所以会倾向流向其他状态，而不是回到本状态。
@@ 第658行： / 第660行： @@
-把<math>Q_1</math>中'''第二行元素'''乘以2，得到一个比例成块的<math>Q_3</math>，并得到对应的<math>P_3</math>。因为对第二行进行了改动，所以<math>P_3</math>中<math>s_1</math>和<math>s_2</math>就不再满足能放在同一组里的条件，但<math>s_3</math>和<math>s_4</math>仍能划分在同一组里。所以，<math>P_3</math>的强成块分组为<math>\{1\}, \{2\}, \{3, 4\}</math>。
+最后，我们把<math>Q_1</math>中'''第二行元素'''乘以2，得到一个比例成块的<math>Q_3</math>，并得到对应的<math>P_3</math>。因为对第二行进行了改动，所以<math>P_3</math>中<math>s_1</math>和<math>s_2</math>就不再满足能放在同一组里的条件，但<math>s_3</math>和<math>s_4</math>仍能划分在同一组里。所以，<math>P_3</math>的强成块分组为<math>\{1\}, \{2\}, \{3, 4\}</math>。
 在该例子中，虽然从<math>Q_1</math>到<math>Q_3</math>之间的操作比较简单， 但<math>P_1</math>和<math>P_3</math>之间并没有一个明显的对应关系。比较清楚的是，当我们把<math>Q_3</math>的'''第2行'''速率调快了之后，停留在<math>s_2</math>的概率变小了，所以<math>P_3</math>的'''第2列'''就变小了。
@@ 第667行： / 第669行： @@
 准成块 Quasi < 比例成块 Proportional < 弱成块 Weak < 精准成块 Exact < 强成块 Strong/Ordinary < 严格成块 Strict
 ==成块性和粗粒化==

←上一版本		2025年4月26日 (六) 12:39的版本
第648行：		第648行：
	</math>		</math>

−	~~所以，我们知道，如果~~<math>Q</math>强成块的话，<math>Q</math>的幂矩阵<math>Q^n</math>也是强成块的，所以<math>P = \sum_{n=0}^\infty \frac{ (tQ)^n }{ n! }</math>也是强成块的。	+	同样的，如果<math>Q</math>强成块的话，<math>Q</math>的幂矩阵<math>Q^n</math>也是强成块的，所以<math>P = \sum_{n=0}^\infty \frac{ (tQ)^n }{ n! }</math>也是强成块的。

@@ 第640行： / 第640行： @@
 以这个例子为例，<math>q_{13}+q_{14} = q_{23}+q_{24}</math>。当我们计算P矩阵时，我们需要进行泰勒展开。
-这里我们检查一下展开中的<math>Q^2</math>项。通过计算得知，
+这里我们检查一下展开中的<math>(Q_1)^2</math>项。通过计算得知，
 <math>
 \begin{aligned}
-(Q^2)_{13}+(Q^2)_{14}&=q_{11}q_{13}+q_{12}q_{23}+q_{13}q_{33}+q_{14}q_{43}+q_{11}q_{14}+q_{12}q_{24}+q_{13}q_{34}+q_{14}q_{44}\\
+(Q_1^2)_{13}+(Q_1^2)_{14}&=q_{11}q_{13}+q_{12}q_{23}+q_{13}q_{33}+q_{14}q_{43}+q_{11}q_{14}+q_{12}q_{24}+q_{13}q_{34}+q_{14}q_{44}\\
 &= q_{11}(q_{13}+q_{14})+q_{12}(q_{23}+q_{24})+q_{13}(q_{33}+q_{34})+q_{14}(q_{43}+q_{44})\\
 &= (q_{11}+q_{12})(q_{13}+q_{14})+(q_{13}+q_{14})(q_{33}+q_{34})\\
 &= (q_{21}+q_{22})(q_{13}+q_{14})+(q_{23}+q_{24})(q_{33}+q_{34})\\
-&= (Q^2)_{23}+(Q^2)_{24}
+&= (Q_1^2)_{23}+(Q_1^2)_{24}
 \end{aligned}
 </math>
 所以，我们知道，如果<math>Q</math>强成块的话，<math>Q</math>的幂矩阵<math>Q^n</math>也是强成块的，所以<math>P = \sum_{n=0}^\infty \frac{ (tQ)^n }{ n! }</math>也是强成块的。
@@ 第662行： / 第663行： @@
 把<math>Q_1</math>中'''第二行'''元素乘以2，得到一个比例成块的<math>Q_3</math>，并得到对应的<math>P_3</math>。因为对第二行进行了改动，所以<math>P_3</math>中<math>s_1</math>和<math>s_2</math>就不再满足能放在同一组里的条件，但<math>s_3</math>和<math>s_4</math>仍能划分在同一组里。所以，<math>P_3</math>的强成块分组为<math>\{1\}, \{2\}, \{3, 4\}</math>。
 在该例子中，虽然从<math>Q_1</math>到<math>Q_3</math>之间的操作比较简单， 但<math>P_1</math>和<math>P_3</math>之间并没有一个明显的对应关系。比较清楚的是，当我们把<math>Q_3</math>的'''第2行'''速率调快了之后，停留在<math>s_2</math>的概率变小了，所以<math>P_3</math>的'''第2列'''就变小了。