812
个编辑
更改
跳到导航
跳到搜索
第3行：
第3行： − Lump有‘块’的意思，我们会在正文中提到，判断一个马尔科夫链是否lumpable，是看它的马尔科夫状态转移矩阵这个大方块中的元素能不能结成一个个小方块。所以，集智百科编辑团队暂提供一个中文翻译为'''成块性'''。下文中的成块性就是指lumpability这个概念。+ 第11行：
第11行： − 为了严谨的介绍这一定义，我们会详细翻译文章中的部分。不感兴趣的读者可以跳到更简洁直观的‘lumpable partition的充分必要条件'部分。+ 第55行：
第55行： − 我们暂且先不考虑‘失败’的情况，先关注‘成功’的部分。书中接下来就定义了什么叫做lumpable 划分：+ − + − + − + − + − 从图3的lumpable例子中，我们看到对于分组矩阵<math>\Phi = \left ( \begin{array}{cc} 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{array} \right )</math>，lumpable的动力学TPM可以找到一个lumped process，而这个lumped process是满足马尔可夫性，且对所有初始状态都保持一致的。也就是说，无论<math>s^{(t)}</math>是什么，<math>\{ s^{(t)}, s^{(t+1)} \}</math>投影到宏观空间上的<math>\{ A^{(t)}, A^{(t+1)} \}</math>的<math> P( A^{(t+1)} | A^{(t)} )</math>都保持一致。+ − 对于例子中的non-lumpable矩阵，我们或许可以给它强制定义一个lumped process的TPM，比如<math> P_1' = \left ( \begin{array}{cc} 0.6 & 0.4 \\ 0.2 & 0.8 \\ \end{array} \right )</math>，但这个lumped process并不能对任何微观初始状态保持一致，只能对<math>s^{(t)} = \pi = \left [ \begin{array}{cc}1 & 0 & 0 & 0 \end{array} \right ]</math>适用。+ − + − + − 通过上面的例子，我们可以对lumpable partition有一些直观的理解。我们可以留意到，在lumpable partition中，有两个分组，所以有四个框。每一个框里，每一列相加的和都是一样的，比如左上角的框中，<math>0.3 + 0.3 = 0.2 + 0.4</math>。这就是lumpable partition更通俗的解释，在某些文献中，并不会使用上面提及的定义，而是直接使用这个通俗版的解释。<ref name=":1" />中作者指出，这两者之间是存在充分必要条件关系的。+ − + − + 第97行：
第97行： − 顺着这个条件，我们也能对lumpable partition，定义宏观动力学<math>\{A^{(0)}, ... , A^{(t-1)} \}</math>了：+ − + − + 第113行：
第113行： − 对于lumpable partition <math>A</math>定义宏观动力学后，我们就能走另外一条路径了：微观状态->粗粒化->宏观动力学->宏观状态。+ 第119行：
第119行： − 必要性是指，如果一个马尔可夫链的partition <math>A</math>是lumpable，那么就肯定会满足上述的这个特定条件。+ − 从lumpable partition 的定义可知，<math>A</math>的转移概率满足宏观马尔可夫性，且这个转移概率<math>Pr_{\pi} [ s^{(1)} \in A_j | s^{(0)} \in A_i ]</math>对每个<math>\pi</math>保持一致，即在<math>t=0</math>时无论从哪个具体的初始状态<math>\pi</math>开始，只要它属于<math>A_i</math>这个群组里，在<math>t=1</math>时刻转移到<math>A_j</math>的概率都相同。+ − + − 充分性是指，如果一个马尔可夫链的某个partition <math>A</math>满足这个条件，那么它就是lumpable。我们要证明的是，如果上述条件满足，那么马尔可夫性成立，即对于任何给定的<math>t</math>，转移概率<math>Pr \left [ s^{(t)} \in A_j | s^{(t-1)} \in A_i, \ldots, s^{(1)} \in A_k, s^{(0)} \in A_m \right ]</math>只依赖于<math>A_i</math>和<math>A_j</math>，而不依赖于<math>A_i</math>中的具体状态或是<math>t-1</math>前的宏观状态。+ 第135行：
第135行： − + 第143行：
第143行： − + − 所以，lumpability并不是一个马尔科夫链的特质，而是对马尔科夫链的某个state partition的特质。我们不能直接说某个马尔科夫链是lumpable或non-lumpable，但是我们可以说，对于某个马尔科夫链的某几个状态partition是lumpable或non-lumpable。+ + − ==Lumpability正例和反例==+ − − 对于一个马尔科夫链，有些分组partition是lumpable，有些分组是non-lumpable。这里用一个简单的例子提供正例和反例。 第210行：
第209行： − + 第230行：
第229行： − + 第246行：
第245行： − + − + − Strong lumpability 或 ordinary lumpability 是上面所述的lumpability的原本概念，是这六个变种中约束最强的一种。它要求矩阵具有严格的分块性。+ 第269行：
第268行： − + − + − Weak lumpability<ref name=":3" />是指lumped process不对所有的初始状态满足，而仅对某些初始状态满足。+ 第295行：
第294行： − + − + − 在strong lumpability中，<math>P</math>分组内每一行的加总是一样的，也就是说，同一组中的每个状态到另一个分组的转出概率是相同的。+ − 而在exact lumpability中，<math>P</math>分组内的每一列的加总是一样的，也就是说，同一组中的每个状态从另一个分组的转入概率是相同的。+ − + − + − 在Strong lumpability例子中，<math>[[1, 2], [3, 4]]</math>是一个strongly lumpable分组，但不是一个exactly lumpable分组。+ 第329行：
第328行： − + − + − Strict lumpability<ref name=":2"/>是指一个马尔可夫链同时满足strong和exact lumpability，也就是说，同一组中的每个状态不仅从另一个分组的转入概率相等，而且到另一个分组的转出概率也相等。+ 第353行：
第352行： − + − + − 我们可以看到，strong lumpability这种对于马尔科夫矩阵的分块性是一个很严格的要求。而我们在现实情况中，很难会找到strongly lumpable的矩阵，稍微加了一点扰动就不行了。如果我们考虑了这种扰动的情况，我们就可以定义不是lumpable但非常接近lumpable的情况：quasi<ref name=":5">Franceschinis, Giuliana, and Richard R. Muntz. "Bounds for quasi-lumpable Markov chains." Performance Evaluation 20.1-3 (1994): 223-243.</ref>+ − + − 比如说，我们对上面的strict lumpability例子加上一点扰动：+ 第400行：
第399行： − + − Proportional lumpability<ref name=":6">Piazza, Carla, and Sabina Rossi. "Reasoning about proportional lumpability." International Conference on Quantitative Evaluation of Systems. Cham: Springer International Publishing, 2021.</ref>是基于连续时间马尔科夫链CTMC(Continuoous-time markov chain)的设定提出来的一个放松lumpability限制的概念。目前暂未发现研究证明其能应用在离散时间马尔科夫链DTMC上。+ − Strong lumpability在CTMC设定下跟DTMC是类似的，简单来说就是：+ − + 第415行：
第414行： − 而Proportional Lumpability的定义是：+ 第425行：
第424行： − 这六种lumpability的定义按照限制严格度大概的排序是：+ − + − + + + 第435行：
第436行： − 而Lumpability就是一个指标，用来评价‘对于某一种硬划分的微观状态分组分案，是否对微观状态转移矩阵lumpable’。+ 第441行：
第442行： − 其中的某些分组方案lumpable，也有某些分组方案non-lumpable。+ 第448行：
第449行： − 所以，一个满足lumpability的良定义的粗粒化方案应该有四个条件：+ − + − + − + − 这一小节里我们讨论一下，对一个马尔科夫链的'''lumpable partition''' 与 HOM（Higher-order Macronodes，详情请参考[[复杂网络中的因果涌现]]），和Consistency之间的关联。+ − 我们这里使用一个简单的lumpable partition例子，来显示lumpability的粗粒化跟HON是对应的。+ 第487行：
第488行： − + − 首先，我们先按照lumpability的粗粒化定义，计算对应的宏观转移概率：+ 第527行：
第528行： − + − + − 我们得出这个结论的目标是，借助HOM方法的consistency的性质，说明lumpable partition的聚合方式，也有consistency的性质。+ 第547行：
第548行： − 回到上面lumpable partition 等于HOM的推断，我们就能得出，'''根据lumpability而做的粗粒化，构建的宏观网络和微观网络也是保持一致的。'''+ + + − + − + − 由上面的lumpability公式(4)和例子中我们能获得一个直观上的说法：当马尔科夫矩阵存在block结构，或者状态明显可被分成几类的时候，根据这样的partition，该矩阵就会lumpable，如图6中的<math>\bar{P}</math>所示，把相同的状态（行向量）分成一类的partition显然lumpable。+ − 但是，有时候有些lumpable的矩阵的状态排序被打乱了（如图6中的<math>P_1</math>），或者矩阵包含了如<math>P_2</math>的噪声（如图6中的<math>P</math>，<math>P = P_1 + P_2</math>，<math>P_1^TP_2 = 0</math>）。+ − + − + − + 第572行：
第575行： − 这个算法的意思是在最优的partition中，<math>\Omega_s</math>中的状态<math>i</math>的右奇异向量会和<math>v_s</math>距离最小，也就是说，让每个微观态的右特征向量和它对应的宏观态的右特征向量尽可能接近。+ 第583行：
第586行： − 我们看到这两个目标函数是非常相似的。所以，我们就可以通过上述算法或者kMeans来获取最优partition，然后根据这个partition来判断马尔科夫矩阵的lumpability。+
无编辑摘要
Lumpability是一种描述马尔科夫链的状态是否可聚类的性质，笔者暂时还没找到一个正式的中文翻译。
Lumpability是一种描述马尔科夫链的状态是否可聚类的性质，笔者暂时还没找到一个正式的中文翻译。
Lump有‘块’的意思。我们会在正文中提到，判断一个马尔科夫链是否lumpable，是看它的马尔科夫状态转移矩阵这个大方块中的元素能不能结成一个个小方块。所以，集智百科编辑团队暂提供一个中文翻译为'''成块性'''。下文中的成块性就是指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>中。
这个概念最早出现在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>中。
==最初定义==
==最初定义==
为了严谨的介绍这一定义，我们会详细翻译文章中的部分。不感兴趣的读者可以跳到更简洁直观的‘成块性的充分必要条件'部分。
首先定义<math>s^{(t)}</math>表示系统在<math>t</math>时刻处于各微观状态的概率，微观状态空间为<math>S=\{s_1, s_2, ... ,s_n\}</math>。
首先定义<math>s^{(t)}</math>表示系统在<math>t</math>时刻处于各微观状态的概率，微观状态空间为<math>S=\{s_1, s_2, ... ,s_n\}</math>。
需要注意的是，虽然任意一个状态划分 <math>A</math>都能走这样的路径，并形成lumped process，但不是所有的这些lumped process都是有意义且满足交换律的。他们不一定能够得出一个宏观动力学来描述式子（3）中微观状态的宏观投影，也不一定会拥有马尔科夫性。
需要注意的是，虽然任意一个状态划分 <math>A</math>都能走这样的路径，并形成lumped process，但不是所有的这些lumped process都是有意义且满足交换律的。他们不一定能够得出一个宏观动力学来描述式子（3）中微观状态的宏观投影，也不一定会拥有马尔科夫性。
我们暂且先不考虑‘失败’的情况，先关注‘成功’的部分。书中接下来就定义了什么叫做成块的划分：
'''''定义2'''''：'''lumpable partition 划分'''
'''''定义2'''''：'''成块的划分 lumpable partition'''
'''对于一个给定的状态 <math>A</math>，当下列两个条件都满足时，<math>A</math>是一个lumpable partition 划分。'''
'''对于一个给定的状态 <math>A</math>，当下列两个条件都满足时，<math>A</math>是一个成块划分（lumpable partition）。'''
# '''定义1中式子(3)描述的lumped process具有马尔科夫性，即式子(3.3)可写成<math>Pr_{\pi} \left [s^{(t)} \in A_m | s^{(t-1)} \in A_k, ... , s^{(1)} \in A_j, s^{(0)} \in A_i \right ] = Pr_{\pi} \left [s^{(t)} \in A_m | s^{(t-1)} \in A_k \right ]</math>'''
# '''定义1中式子(3)描述的lumped process具有马尔科夫性，即式子(3.3)可写成<math>Pr_{\pi} \left [s^{(t)} \in A_m | s^{(t-1)} \in A_k, ... , s^{(1)} \in A_j, s^{(0)} \in A_i \right ] = Pr_{\pi} \left [s^{(t)} \in A_m | s^{(t-1)} \in A_k \right ]</math>'''
# '''转移概率(Transition probability)，即式子(3.3)，对任何微观初始状态(starting vector) <math> \pi </math> 都保持一致'''
# '''转移概率(transition probability)，即式子(3.3)，对任何微观初始状态(starting vector) <math> \pi </math> 都保持一致'''
[[文件:Lumpable和non-lumpable的例子.png|缩略图|图3：对lumpable和non-lumpable矩阵做粗粒化|替代=|600x600像素]]不满足上述两个条件的，都不被定义为lumpable partition。也就是说，不是所有的lumped process都是lumpable的，即使他们的命名方式相似。
[[文件:Lumpable和non-lumpable的例子.png|缩略图|图3：对成块的和不成块的矩阵做粗粒化|替代=|600x600像素]]不满足上述两个条件的，都不被定义为成块的划分。也就是说，不是所有的lumped process都是成块的，即使他们的命名方式相似。
从图3的成块划分的例子中，我们看到对于分组矩阵<math>\Phi = \left ( \begin{array}{cc} 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{array} \right )</math>，成块的动力学TPM可以找到一个lumped process，而这个lumped process是满足马尔可夫性，且对所有初始状态都保持一致的。也就是说，无论<math>s^{(t)}</math>是什么，<math>\{ s^{(t)}, s^{(t+1)} \}</math>投影到宏观空间上的<math>\{ A^{(t)}, A^{(t+1)} \}</math>的<math> P( A^{(t+1)} | A^{(t)} )</math>都保持一致。
<br />
<br />
对于例子中的不成块的矩阵，我们或许可以给它强制定义一个lumped process的TPM，比如<math> P_1' = \left ( \begin{array}{cc} 0.6 & 0.4 \\ 0.2 & 0.8 \\ \end{array} \right )</math>，但这个lumped process并不能对任何微观初始状态保持一致，只能对<math>s^{(t)} = \pi = \left [ \begin{array}{cc}1 & 0 & 0 & 0 \end{array} \right ]</math>适用。
而<math>s^{(t)} = \pi = \left [ \begin{array}{cc}0 & 1 & 0 & 0 \end{array} \right ]</math>不适用这个lumped process。它适用的是<math> P_2' = \left ( \begin{array}{cc} 0.5 & 0.5 \\ 0.2 & 0.8 \\ \end{array} \right )</math>。这里的不适用是指，这个lumped process不能描述这个<math>\pi</math>为初始状态出发的微观状态序列投影的宏观状态序列。
而<math>s^{(t)} = \pi = \left [ \begin{array}{cc}0 & 1 & 0 & 0 \end{array} \right ]</math>不适用这个lumped process。它适用的是<math> P_2' = \left ( \begin{array}{cc} 0.5 & 0.5 \\ 0.2 & 0.8 \\ \end{array} \right )</math>。这里的不适用是指，这个lumped process不能描述这个<math>\pi</math>为初始状态出发的微观状态序列投影的宏观状态序列。
我们看到，对于这个分组矩阵<math>\Phi = \left ( \begin{array}{cc} 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{array} \right )</math>，马尔科夫矩阵有两个lumped process <math> P_1'</math>和<math> P_2'</math>，而它们各自只适用于一些微观初始状态(starting vector) <math> \pi </math>，并不满足定义2中的条件，所以<math>A</math>对于这个TPM来说不是一个lumpable partition。事实上，这个TPM只存在一个lumpable partition，就是不做任何的分组，所以它无法按照lumpability的定义进行粗粒化。
我们看到，对于这个分组矩阵<math>\Phi = \left ( \begin{array}{cc} 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{array} \right )</math>，马尔科夫矩阵有两个lumped process <math> P_1'</math>和<math> P_2'</math>，而它们各自只适用于一些微观初始状态(starting vector) <math> \pi </math>，并不满足定义2中的条件，所以<math>A</math>对于这个TPM来说不是一个成块的划分。事实上，这个TPM只存在一个成块的划分，就是不做任何的分组，所以它无法按照成块性的定义进行粗粒化。
==lumpable partition的充分必要条件==
==成块性的充分必要条件==
通过上面的例子，我们可以对成块性有一些直观的理解。我们可以留意到，在成块的划分中，有两个分组，所以有四个框。每一个框里，每一列相加的和都是一样的，比如左上角的框中，<math>0.3 + 0.3 = 0.2 + 0.4</math>。这就是成块性更通俗的解释，就是它'''成块'''了，在某些文献中，并不会使用上面提及的定义，而是直接使用这个通俗版的解释。<ref name=":1" />中作者指出，这两者之间是存在充分必要条件关系的。
设<math>p_{s_k \rightarrow s_m} = p(s^{(t)} = s_m | s^{(t-1)} = s_k)</math>，<math>p_{s_k \rightarrow A_i} = p(s^{(t)} \in A_i | s^{(t-1)} = s_k) = \sum_{s_m \in A_i} p_{s_k \rightarrow s_m}</math>，<math>p_{A_i \rightarrow A_j} = p(A^{(t)} = A_j | A^{(t-1)} = A_i)</math>
设<math>p_{s_k \rightarrow s_m} = p(s^{(t)} = s_m | s^{(t-1)} = s_k)</math>，<math>p_{s_k \rightarrow A_i} = p(s^{(t)} \in A_i | s^{(t-1)} = s_k) = \sum_{s_m \in A_i} p_{s_k \rightarrow s_m}</math>，<math>p_{A_i \rightarrow A_j} = p(A^{(t)} = A_j | A^{(t-1)} = A_i)</math>
作者提出了判断一个马尔科夫链对'''给定partition <math>A</math>''' 是否lumpable的充分必要条件为：
作者提出了判断一个马尔科夫链对'''给定划分 <math>A</math>''' 是否成块的充分必要条件为：
'''''定理1：'''''
'''''定理1：'''''
'''给定partition <math>A</math>是lumpable的充分必要条件为：'''
'''给定划分 <math>A</math>是成块的充分必要条件为：'''
'''对于任意一对<math>A_i, A_j</math>，每一个属于<math>A_i</math>的状态<math>s_k</math>的<math>p_{s_k \rightarrow A_j}</math>都是一样的。'''
'''对于任意一对<math>A_i, A_j</math>，每一个属于<math>A_i</math>的状态<math>s_k</math>的<math>p_{s_k \rightarrow A_j}</math>都是一样的。'''
顺着这个条件，我们也能对成块的划分，定义宏观动力学<math>\{A^{(0)}, ... , A^{(t-1)} \}</math>了：
'''''定义3'''''：'''lumpability的宏观动力学'''
'''''定义3'''''：'''成块性的宏观动力学'''
'''对于给定的微观状态<math>S</math>，微观动力学<math>p_{s_k \rightarrow s_m}</math>和lumpable partition <math>A</math>，宏观动力学<math>p_{A_i \rightarrow A_j}</math>等于<math>A_i</math>中任意状态<math>s_k</math>到<math>A_j</math>的概率：'''
'''对于给定的微观状态<math>S</math>，微观动力学<math>p_{s_k \rightarrow s_m}</math>和成块的划分 <math>A</math>，宏观动力学<math>p_{A_i \rightarrow A_j}</math>等于<math>A_i</math>中任意状态<math>s_k</math>到<math>A_j</math>的概率：'''
{{NumBlk|:|
{{NumBlk|:|
这个公式表达的是，群组<math>A_i</math>到群组<math>A_j</math>的转移概率 = 群组<math>A_i</math>中任意状态<math>s_k</math>到群组<math>A_j</math>的转移概率 = 群组<math>A_i</math>中任意状态<math>s_k</math>到群组<math>A_j</math>中的所有状态的转移概率的和。
这个公式表达的是，群组<math>A_i</math>到群组<math>A_j</math>的转移概率 = 群组<math>A_i</math>中任意状态<math>s_k</math>到群组<math>A_j</math>的转移概率 = 群组<math>A_i</math>中任意状态<math>s_k</math>到群组<math>A_j</math>中的所有状态的转移概率的和。
对成块的划分 <math>A</math>定义宏观动力学后，我们就能走另外一条路径了：'''微观状态->粗粒化->宏观动力学->宏观状态'''。我们发现这和'''微观状态->微观动力学->粗粒化->宏观状态'''，这两条路径，'''从任意一个微观状态出发，都能到达相同的宏观状态。'''所以，这满足了'''动力学'''和'''粗粒化'''这两个'''算子'''的'''可交换性（Exchangeability）'''。
'''必要性部分的证明：'''
'''必要性部分的证明：'''
必要性是指，如果一个马尔可夫链的划分 <math>A</math>是成块的，那么就肯定会满足上述的这个特定条件。
从成块的划分的定义可知，<math>A</math>的转移概率满足宏观马尔可夫性，且这个转移概率<math>Pr_{\pi} [ s^{(1)} \in A_j | s^{(0)} \in A_i ]</math>对每个<math>\pi</math>保持一致，即在<math>t=0</math>时无论从哪个具体的初始状态<math>\pi</math>开始，只要它属于<math>A_i</math>这个群组里，在<math>t=1</math>时刻转移到<math>A_j</math>的概率都相同。
我们设这个（<math>A_i</math>中任意微观状态<math>s_k</math>的）共同的转移概率为<math>\hat{p}_{A_i \rightarrow A_j}</math>。当初始状态<math>\pi</math>属于某个<math>A_i</math>时（<math>\pi \in A_i</math>），<math>p_{s_k \rightarrow A_j} = Pr_{\pi \in A_i} [ s^{(1)} \in A_j ] = \hat{p}_{A_i \rightarrow A_j}</math>。
我们设这个（<math>A_i</math>中任意微观状态<math>s_k</math>的）共同的转移概率为<math>\hat{p}_{A_i \rightarrow A_j}</math>。当初始状态<math>\pi</math>属于某个<math>A_i</math>时（<math>\pi \in A_i</math>），<math>p_{s_k \rightarrow A_j} = Pr_{\pi \in A_i} [ s^{(1)} \in A_j ] = \hat{p}_{A_i \rightarrow A_j}</math>。
所以，这说明了，如果一个马尔可夫链的lumped process满足lumpability，那么从任一集合到另一集合的转移概率必须是集合间的固定值，而与集合内的具体状态（不管是<math>\pi</math>还是<math>s_k</math>）无关。这个固定值就是式子（4）定义的宏观状态转移概率，所以满足了该条件。
所以，这说明了，如果一个马尔可夫链的lumped process满足成块性，那么从任一集合到另一集合的转移概率必须是集合间的固定值，而与集合内的具体状态（不管是<math>\pi</math>还是<math>s_k</math>）无关。这个固定值就是式子（4）定义的宏观状态转移概率，所以满足了该条件。
'''充分性部分的证明：'''
'''充分性部分的证明：'''
充分性是指，如果一个马尔可夫链的某个状态划分 <math>A</math>满足这个条件，那么它就是成块的。我们要证明的是，如果上述条件满足，那么马尔可夫性成立，即对于任何给定的<math>t</math>，转移概率<math>Pr \left [ s^{(t)} \in A_j | s^{(t-1)} \in A_i, \ldots, s^{(1)} \in A_k, s^{(0)} \in A_m \right ]</math>只依赖于<math>A_i</math>和<math>A_j</math>，而不依赖于<math>A_i</math>中的具体状态或是<math>t-1</math>前的宏观状态。
条件要求所有<math>s_k \in A_i</math>，转移概率<math>p_{s_k \rightarrow A_j} = p_{A_i \rightarrow A_j}</math>，这意味着无论我们从<math>A_i</math>中的哪个微观状态转移过来，转移到<math>A_j</math>的概率都是相同的。
条件要求所有<math>s_k \in A_i</math>，转移概率<math>p_{s_k \rightarrow A_j} = p_{A_i \rightarrow A_j}</math>，这意味着无论我们从<math>A_i</math>中的哪个微观状态转移过来，转移到<math>A_j</math>的概率都是相同的。
因此，当我们知道<math>t-1</math>的宏观状态是<math>A_i</math>时，我们计算<math>t</math>时刻转移到<math>A_j</math>的概率时，只需要用<math>p_{A_i \rightarrow A_j}</math>，而不需要关心<math>A_i</math>中的具体状态。
因此，当我们知道<math>t-1</math>的宏观状态是<math>A_i</math>时，我们计算<math>t</math>时刻转移到<math>A_j</math>的概率时，只需要用<math>p_{A_i \rightarrow A_j}</math>，而不需要关心<math>A_i</math>中的具体状态。
由于转移概率只依赖于群组<math>A_i</math>和<math>A_j</math>，而不依赖于<math>A_i</math>中的具体状态，因此我们可以将<math>A_i</math>中的所有状态合并为一个状态，并且这个合并后的链仍满足马尔可夫性。所以，上述条件为lumpability的充分条件。
由于转移概率只依赖于群组<math>A_i</math>和<math>A_j</math>，而不依赖于<math>A_i</math>中的具体状态，因此我们可以将<math>A_i</math>中的所有状态合并为一个状态，并且这个合并后的链仍满足马尔可夫性。所以，上述条件为成块性的充分条件。
'''请注意'''：lumpability有一个非常重要的前提，即我们要给定一个对马尔科夫链的state的partition，然后根据马尔科夫状态转移矩阵来决定这个partition对这个马尔科夫链是否lumpable。
'''请注意'''：成块性有一个非常重要的前提，即我们要给定一个对马尔科夫链的状态的划分，然后根据马尔科夫状态转移矩阵来决定这个划分对这个马尔科夫链是否成块的。
所以，成块性并不是一个马尔科夫链的特质，而是对马尔科夫链的某个状态划分的特质。直接说某个马尔科夫链是成块的或是不成块的是不严谨的，但是我们可以说，对于某个马尔科夫链的某几个状态划分是成块或不成块的。但是，通常为了简略表达，当我们说某个马尔科夫链成块时，我们表达的是它存在某种成块的状态划分。
==成块性的正例和反例==
对于一个马尔科夫链，有些分组是成块的，有些分组是不成块的。这里用一个简单的例子提供正例和反例。
我们用到的是这样一个转移矩阵：
我们用到的是这样一个转移矩阵：
第2组<math>A_2</math>的状态<math>s_4</math>到第1组<math>A_1</math>，<math>p_{s_4 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_4 \rightarrow s_m} = p_{s_4 \rightarrow s_1} + p_{s_4 \rightarrow s_2} = 0.1 \times 2 = 0.2 </math>
第2组<math>A_2</math>的状态<math>s_4</math>到第1组<math>A_1</math>，<math>p_{s_4 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_4 \rightarrow s_m} = p_{s_4 \rightarrow s_1} + p_{s_4 \rightarrow s_2} = 0.1 \times 2 = 0.2 </math>
这里我们就能看到，<math>p_{s_3 \rightarrow A_1} \neq p_{s_4 \rightarrow A_1}</math>，当同一组的两个状态<math>s_3</math>和<math>s_4</math>对其他组的转移概率不一样的话，如果我们强行按照这样来分组（也没办法强行，因为我们不知道<math>p_{A_2 \rightarrow A_1} = p_{s_3 \rightarrow A_1}</math>还是<math>p_{A_2 \rightarrow A_1} = p_{s_4 \rightarrow A_1}</math>），假设<math>p_{A_2 \rightarrow A_1} = 0.6</math>，我们会发现这样的粗粒化结果违背了Lumpability一开始的定义<ref name=":1" />（公式(3)），即粗粒化后的'''转移概率对所有的初始微观状态<math>\pi</math>都适用'''。因为当<math>\pi = s_4</math>的时候，<math>p_{A_2 \rightarrow A_1} = 0.6</math>这个转移概率就是错的，即使<math>\pi \neq s_4</math>，任何初始微观状态<math>\pi</math>都会在某时刻<math>n</math>达到<math>s_4</math>并导致转移概率出错。
这里我们就能看到，<math>p_{s_3 \rightarrow A_1} \neq p_{s_4 \rightarrow A_1}</math>，当同一组的两个状态<math>s_3</math>和<math>s_4</math>对其他组的转移概率不一样的话，如果我们强行按照这样来分组（也没办法强行，因为我们不知道<math>p_{A_2 \rightarrow A_1} = p_{s_3 \rightarrow A_1}</math>还是<math>p_{A_2 \rightarrow A_1} = p_{s_4 \rightarrow A_1}</math>），假设<math>p_{A_2 \rightarrow A_1} = 0.6</math>，我们会发现这样的粗粒化结果违背了成块性一开始的定义<ref name=":1" />（公式(3)），即粗粒化后的'''转移概率对所有的初始微观状态<math>\pi</math>都适用'''。因为当<math>\pi = s_4</math>的时候，<math>p_{A_2 \rightarrow A_1} = 0.6</math>这个转移概率就是错的，即使<math>\pi \neq s_4</math>，任何初始微观状态<math>\pi</math>都会在某时刻<math>n</math>达到<math>s_4</math>并导致转移概率出错。
</math>
</math>
对于这个马尔科夫矩阵，<math>\{\{1,2\}, \{3,4\}\}</math>是一个lumpable的分组。分组后的转移矩阵为：
对于这个马尔科夫矩阵，<math>\{\{1,2\}, \{3,4\}\}</math>是一个成块的分组。分组后的转移矩阵为：
<math>
<math>
\begin{aligned}
\begin{aligned}
==Lumpability概念的变种==
==成块性概念的变种==
===Strong/Ordinary Lumpability===
===强成块性 Strong/Ordinary Lumpability===
强成块性（Strong lumpability） 或 ordinary lumpability 是上面所述的成块性的原本概念，是这六个变种中约束最强的一种。它要求矩阵具有严格的分块性。
这里的'Strong'是与下面的'weak'相对的概念，指上文的lumped process满足对任意初始状态分布都保持一致的条件。
这里的'Strong'是与下面的'weak'相对的概念，指上文的lumped process满足对任意初始状态分布都保持一致的条件。
</math>
</math>
此例子中，<math>[[1, 2], [3, 4]]</math>是一个strongly lumpable分组。
此例子中，<math>[[1, 2], [3, 4]]</math>是一个强成块的分组。
===Weak Lumpability===
===弱成块性 Weak Lumpability===
弱成块性（weak lumpability）<ref name=":3" />是指lumped process不对所有的初始状态满足，而仅对某些初始状态满足。
一个简单的例子是，某个状态<math>s_i</math>到<math>s_j</math>不联通的，而lumped process适用于<math>s_i</math>但不适用于<math>s_j</math>。所以，当初始状态等于<math>s_i</math>时，因为永远不会到达<math>s_j</math>，所以lumped process会一直适用。
一个简单的例子是，某个状态<math>s_i</math>到<math>s_j</math>不联通的，而lumped process适用于<math>s_i</math>但不适用于<math>s_j</math>。所以，当初始状态等于<math>s_i</math>时，因为永远不会到达<math>s_j</math>，所以lumped process会一直适用。
</math>
</math>
此例子中，<math>[[1, 2], [3], [4]]</math>是一个strongly lumpable分组，而<math>[[1, 2], [3, 4]]</math>是一个weakly lumpable分组,
此例子中，<math>[[1, 2], [3], [4]]</math>是一个强成块的分组，而<math>[[1, 2], [3, 4]]</math>是一个弱成块的分组,
===Exact Lumpability===
===精确成块 Exact Lumpability===
强成块的<math>P</math>的分组内每一行的加总是一样的，也就是说，同一组中的每个状态到另一个分组的转出概率是相同的。
而在精确成块性（exact lumpability）中，<math>P</math>分组内的每一列的加总是一样的，也就是说，同一组中的每个状态从另一个分组的转入概率是相同的。
在<ref name=":2">Buchholz, Peter. "Exact and ordinary lumpability in finite Markov chains." ''Journal of applied probability'' 31.1 (1994): 59-75.</ref>中给出的正式定义是，<math>P</math>的'''转置'''经过'''行归一化'''是strong lumpable的。
在<ref name=":2">Buchholz, Peter. "Exact and ordinary lumpability in finite Markov chains." ''Journal of applied probability'' 31.1 (1994): 59-75.</ref>中给出的正式定义是，<math>P</math>的'''转置'''经过'''行归一化'''是强成块的。
另外，<ref name=":2"/>说明了exactly lumpable的<math>P</math>也是weakly lunpable的。
另外，<ref name=":2"/>说明了精确成块的<math>P</math>也是弱成块的。
在强成块性的例子中，<math>[[1, 2], [3, 4]]</math>是一个强成块的分组，但不是一个精确成块的分组。
我们再举一个例子：
我们再举一个例子：
此例子中，<math>[[1, 2], [3, 4]]</math>不是一个strongly lumpable分组，但是一个exactly lumpable分组,
此例子中，<math>[[1, 2], [3, 4]]</math>不是一个强成块的分组，但是一个精确成块的分组,
===Strict Lumpability===
===严格成块性 Strict Lumpability===
严格成块性（strict lumpability）<ref name=":2"/>是指一个马尔可夫链同时满足强成块性和精确成块性。也就是说，同一组中的每个状态不仅从另一个分组的转入概率相等，而且到另一个分组的转出概率也相等。
简单的例子：
简单的例子：
</math>
</math>
此例子中，<math>[[1, 2], [3, 4]]</math>既是一个strongly lumpable分组，又是一个exactly lumpable分组。
此例子中，<math>[[1, 2], [3, 4]]</math>既是一个强成块的分组，又是一个精确成块的分组。
===Quasi Lumpability===
===准成块性 Quasi Lumpability===
我们可以看到，强成块性这种对于马尔科夫矩阵的分块性是一个很严格的要求。而我们在现实情况中，很难会找到强成块的矩阵，稍微加了一点扰动就不行了。如果我们考虑了这种扰动的情况，我们就可以定义不成块但非常接近成块的情况：quasi<ref name=":5">Franceschinis, Giuliana, and Richard R. Muntz. "Bounds for quasi-lumpable Markov chains." Performance Evaluation 20.1-3 (1994): 223-243.</ref>
如果一个 <math>P</math>可以被分解为<math>P = P^- + P^{\epsilon}</math>，其中<math>P^-</math>是一个lumpable的矩阵，而<math>P^{\epsilon}</math>中的每个元素都小于<math>\epsilon</math>，<math>P</math>就是一个<math>\epsilon</math>-quasi-lumpable的矩阵。
如果一个 <math>P</math>可以被分解为<math>P = P^- + P^{\epsilon}</math>，其中<math>P^-</math>是一个成块的矩阵，而<math>P^{\epsilon}</math>中的每个元素都小于<math>\epsilon</math>，<math>P</math>就是一个<math>\epsilon</math>-quasi-lumpable的矩阵。
比如说，我们对上面的成块的例子加上一点扰动：
<math>
<math>
就能获得一个<math>\epsilon</math>-quasi-lumpable，<math>\epsilon=0.02</math>的矩阵。
就能获得一个<math>\epsilon</math>-quasi-lumpable，<math>\epsilon=0.02</math>的矩阵。
===Proportional Lumpability===
===比例成块性 Proportional Lumpability===
比例成块性（Proportional Lumpability）<ref name=":6">Piazza, Carla, and Sabina Rossi. "Reasoning about proportional lumpability." International Conference on Quantitative Evaluation of Systems. Cham: Springer International Publishing, 2021.</ref>是基于连续时间马尔科夫链CTMC(Continuoous-time markov chain)的设定提出来的一个放松成块性限制的概念。目前暂未发现研究证明其能应用在离散时间马尔科夫链DTMC上。
如果我们把DTMC的TPM <math>P</math>看作是一个差分的算子，相应的我们可以大概把CTMC的TPM <math>Q</math>看作是一个微分算子。
如果我们把DTMC的TPM <math>P</math>看作是一个差分的算子，相应的我们可以大概把CTMC的TPM <math>Q</math>看作是一个微分算子。
强成块性在CTMC设定下跟DTMC是类似的，简单来说就是：
对于微观的离散状态空间 <math>S</math>，微观TPM<math>Q</math>，分组后的宏观状态空间<math>A</math>，如果<math>Q</math>满足Strong lumpability的话：
对于微观的离散状态空间 <math>S</math>，微观TPM<math>Q</math>，分组后的宏观状态空间<math>A</math>，如果<math>Q</math>满足强成块性的话：
<math>Pr(A_m|s_i) = Pr(A_m|s_j), \forall s_i, s_j \in A_n,</math>
<math>Pr(A_m|s_i) = Pr(A_m|s_j), \forall s_i, s_j \in A_n,</math>
而比例成块性的定义是：
对<math>S</math>中的任意一个状态，存在一个函数<math>\kappa:S \rightarrow \mathcal{R}^+</math>，使得：
对<math>S</math>中的任意一个状态，存在一个函数<math>\kappa:S \rightarrow \mathcal{R}^+</math>，使得：
这六种成块性的定义按照限制严格度大概的排序是：
Proportional < Quasi < Weak < Exact < Strong/Ordinary < Strict Lumpability
比例成块 Proportional < 准成块 Quasi < 弱成块 Weak < 精准成块 Exact < 强成块 Strong/Ordinary < 严格成块 Strict
==Lumpability和粗粒化==
==成块性和粗粒化==
马尔科夫链的粗粒化不仅要对状态空间做，也要对转移矩阵和概率空间做。这三个部分可以同时做，也可以看作为：先对状态空间做，再对转移矩阵和概率空间做；即先对状态做分组，然后再获取对应的粗粒化后的转移矩阵。
马尔科夫链的粗粒化不仅要对状态空间做，也要对转移矩阵和概率空间做。这三个部分可以同时做，也可以看作为：先对状态空间做，再对转移矩阵和概率空间做；即先对状态做分组，然后再获取对应的粗粒化后的转移矩阵。
对状态空间做粗粒化有硬划分和软划分两种。软划分可以看作把微观状态打散重构成了一些宏观状态，而硬划分则是更严格的，把若干个微观状态分成一个组。
对状态空间做粗粒化有硬划分和软划分两种。软划分可以看作把微观状态打散重构成了一些宏观状态，而硬划分则是更严格的，把若干个微观状态分成一个组。
而成块性就是一个指标，用来评价‘某一种硬划分的微观状态分组分案，是否对于微观状态转移矩阵来说是成块的’。
我们把状态空间按照任意一个硬划分方案做分类，它都有对应后续的对转移矩阵和概率空间的粗粒化方案（公式(1)和(2)）<ref name=":2" />，其中有些分组满足交换律，有些则不满足。
我们把状态空间按照任意一个硬划分方案做分类，它都有对应后续的对转移矩阵和概率空间的粗粒化方案（公式(1)和(2)）<ref name=":2" />，其中有些分组满足交换律，有些则不满足。
其中的某些分组方案成块，也有某些分组方案不成块。
所以，整个链条应该是这样的：
所以，整个链条应该是这样的：
所以，一个满足成块性的良定义的粗粒化方案应该有四个条件：
#粗粒化后的<math>S'</math>和<math>T'</math>要符合马尔科夫链定义；
#粗粒化后的<math>S'</math>和<math>T'</math>要符合马尔科夫链定义；
#满足交换律；
#满足交换律；
#Hard Partitioning，即存在分组矩阵<math>V_{i, j} = 1\ if\ s_i \in s_j'\ and\ 0\ otherwise</math>；
#硬划分，即存在分组矩阵<math>V_{i, j} = 1\ if\ s_i \in s_j'\ and\ 0\ otherwise</math>；
#<math>V</math>是一个lumpable分组。
#<math>V</math>是一个成块的分组。
===Lumpable Partition粗粒化的一致性Consistency===
===成块划分和粗粒化的一致性Consistency===
这一小节里我们讨论一下，对一个马尔科夫链的成块的划分 与 HOM（Higher-order Macronodes，详情请参考[[复杂网络中的因果涌现]]），和Consistency之间的关联。
Higher-order Macronodes，是由Jian Xu<ref name=":3">J. Xu, T. L. Wickramarathne, and N. V. Chawla， 'Representing higher-order dependencies in networks,' Science Advances, vol. 2, Article ID el600028, 2016.a</ref>提出，根据给定的微观马尔科夫链和节点的聚类方案，得出一个和微观转移矩阵保持一致的宏观转移矩阵的方法。
Higher-order Macronodes，是由Jian Xu<ref name=":3">J. Xu, T. L. Wickramarathne, and N. V. Chawla， 'Representing higher-order dependencies in networks,' Science Advances, vol. 2, Article ID el600028, 2016.a</ref>提出，根据给定的微观马尔科夫链和节点的聚类方案，得出一个和微观转移矩阵保持一致的宏观转移矩阵的方法。
我们这里使用一个简单的成块的划分的例子，来显示成块性的粗粒化跟HON是对应的。
[[文件:Lumpability例子示意图.png|缩略图|图4：例子示意图|替代=]]
[[文件:Lumpability例子示意图.png|缩略图|图4：例子示意图|替代=]]
</math>
</math>
对于这个转移概率矩阵，<math>\{1, 2, \{34\}, 5, 6\}</math>是一个lumpable partition。
对于这个转移概率矩阵，<math>\{1, 2, \{34\}, 5, 6\}</math>是一个成块的划分。
首先，我们先按照成块性的粗粒化定义，计算对应的宏观转移概率：
<math>
<math>
\begin{aligned}
\begin{aligned}
[[文件:网络节点边权合并示意图.png|替代=|411x411像素]]
[[文件:网络节点边权合并示意图.png|替代=|411x411像素]]
'''但是'''，我们可以注意到，这三种计算方式都是待合并节点<math>A</math>中的各节点的出流的<math>W_i^{out}</math>加权，而我们知道，lumpability的特性决定了，群组里的各节点到其他群组的出流<math>W_i^{out}</math>都是一样的，对相同的<math>W_i^{out}</math>做任意加权平均的结果都等于<math>W_i^{out}</math>。也就是说，任意的加权方法对于lumpable partition来说都能得出相同的结果。
'''但是'''，我们可以注意到，这三种计算方式都是待合并节点<math>A</math>中的各节点的出流的<math>W_i^{out}</math>加权，而我们知道，成块性的特性决定了，群组里的各节点到其他群组的出流<math>W_i^{out}</math>都是一样的，对相同的<math>W_i^{out}</math>做任意加权平均的结果都等于<math>W_i^{out}</math>。也就是说，任意的加权方法对于成块的划分来说都能得出相同的结果。
由此，我们总结，'''lumpable partition的聚合方式和HOM的计算方式，无论入流还是出流都完全一致。'''
由此，我们总结，'''成块性的聚合方式和HOM的计算方式，无论入流还是出流都完全一致。'''
我们得出这个结论的目标是，借助HOM方法的一致性的性质，说明成块性的聚合方式，也有一致性的性质。
以下关于'''网络动力学的一致性'''的描述节选自[[复杂网络中的因果涌现]]：
以下关于'''网络动力学的一致性'''的描述节选自[[复杂网络中的因果涌现]]：
实验发现，对不同节点规模以及参数下的微观网络，使用HOM粗粒化后的宏观网络的不一致性随着迭代步数的增加都会收敛到0。这说明，HOM构建的宏观网络和微观网络是保持一致的。
实验发现，对不同节点规模以及参数下的微观网络，使用HOM粗粒化后的宏观网络的不一致性随着迭代步数的增加都会收敛到0。这说明，HOM构建的宏观网络和微观网络是保持一致的。
回到上面成块的划分 等于HOM的推断，我们就能得出，'''根据成块性而做的粗粒化，构建的宏观网络和微观网络也是保持一致的。'''
===基于Lumpability的粗粒化方法（未给定lumpable partition的情况）===
===基于成块性的粗粒化方法（未给定成块的划分的情况）===
[[文件:Lump fig1.png|缩略图|398x398像素|图6：Zhang<ref name=":4" /> 文章中的示意图。图中左面四个矩阵都是lumpable马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0|替代=]]
[[文件:Lump fig1.png|缩略图|398x398像素|图6：Zhang<ref name=":4" /> 文章中的示意图。图中左面四个矩阵都是成块的马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0|替代=]]
由上面的成块性公式(4)和例子中我们能获得一个直观上的说法：当马尔科夫矩阵存在block结构，或者状态明显可被分成几类的时候，根据这样的划分，该矩阵就是成块的，如图6中的<math>\bar{P}</math>所示，把相同的状态（行向量）分成一类的划分显然成块。
但是，有时候有些成块的矩阵的状态排序被打乱了（如图6中的<math>P_1</math>），或者矩阵包含了如<math>P_2</math>的噪声（如图6中的<math>P</math>，<math>P = P_1 + P_2</math>，<math>P_1^TP_2 = 0</math>）。
我们在实际问题中很多时候要面对的是像<math>P</math>这样的矩阵，我们既无法确定它是否lumpable，也无法决定它的partition，我们甚至不知道它的马尔科夫秩。
我们在实际问题中很多时候要面对的是像<math>P</math>这样的矩阵，我们既无法确定它是否成块，也无法决定它的划分，我们甚至不知道它的马尔科夫秩。
在这种情况下，Anru Zhang<ref name=":4">Zhang, Anru, and Mengdi Wang. "Spectral state compression of markov processes." ''IEEE transactions on information theory'' 66.5 (2019): 3202-3231.</ref><ref name=":4" />的文章中提供了一种寻找最优partition的方法。通过此方法我们能找到最优的partition，代入这个partition我们就能通过上面的充分必要条件来决定一个马尔科夫矩阵是否lumpable。具体步骤如下：
在这种情况下，Anru Zhang<ref name=":4">Zhang, Anru, and Mengdi Wang. "Spectral state compression of markov processes." ''IEEE transactions on information theory'' 66.5 (2019): 3202-3231.</ref><ref name=":4" />的文章中提供了一种寻找最优划分的方法。通过此方法我们能找到最优的划分，代入这个最优划分我们就能通过上面的充分必要条件来决定一个马尔科夫矩阵是否成块。具体步骤如下：
#先获取一个n*n维的马尔科夫矩阵P，或者是马尔科夫链的频率采样；
#先获取一个n*n维的马尔科夫矩阵P，或者是马尔科夫链的频率采样；
#获取r<n 的马尔科夫秩，或指定一个r；
#获取r<n 的马尔科夫秩，或指定一个r；
#对P进行SVD分解，<math>P = U \Sigma V^T</math>，其中U为左奇异向量，V为右奇异向量。
#对P进行SVD分解，<math>P = U \Sigma V^T</math>，其中U为左奇异向量，V为右奇异向量。
#通过下列公式得到最优partition <math>\Omega_1, \Omega_2, ... , \Omega_r</math>
#通过下列公式得到最优划分 <math>\Omega_1, \Omega_2, ... , \Omega_r</math>
<math>
<math>
其中，<math>v_s</math>是第<math>s</math>类<math>\Omega_s</math>的特征向量。
其中，<math>v_s</math>是第<math>s</math>类<math>\Omega_s</math>的特征向量。
这个算法的意思是在最优的划分中，<math>\Omega_s</math>中的状态<math>i</math>的右奇异向量会和<math>v_s</math>距离最小，也就是说，让每个微观态的右特征向量和它对应的宏观态的右特征向量尽可能接近。
<math>J(c^1, ... , c^n, \mu_1, ... , \mu_r) = \sum_{i=1}^n || x_i - \mu_{c^i} ||^2 </math>
<math>J(c^1, ... , c^n, \mu_1, ... , \mu_r) = \sum_{i=1}^n || x_i - \mu_{c^i} ||^2 </math>
我们看到这两个目标函数是非常相似的。所以，我们就可以通过上述算法或者kMeans来获取最优的状态划分，然后根据这个状态来判断马尔科夫矩阵的成块性。