812
个编辑
更改
无编辑摘要
[[马尔科夫链]]是一类特殊的随机过程，在给定当前状态下，对于未来状态的预测便不再依赖于过去状态。它可以看作一个有n个可能状态取值的随机变量序列<math>\{s^{(1)}, s^{(2)}, ... , s^{(t)}\}</math>，其中<math>s^{(t)}</math>代表第t步的状态变量。由于马尔科夫链是随机过程，故我们通过描述状态变量的分布变化来描述其动力学。马氏链每一步状态的转移都由马尔科夫概率转移矩阵（满足每一行和为1的条件的方阵）<math>P</math>决定，即<math>p(s^{(t+1)}) = p(s^{(t)}) P</math>，这里<math>p(s^{(t)})</math>第t时刻的状态变量分布。
成块性（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），就是要判定是否存在一种状态划分方式，能够将原始的马尔科夫链压缩为一个保留其动力学特征的简化链。这种划分需确保：虽然抹除了聚类内部状态的微观差异，但能精确保持块间转移机制。这一特性为状态空间的合理划分提供了严格的数学判据。
符合成块性的粗粒化方案有很多很好的性质，如保证了对宏观层面上的最大预测性、保证了微观与宏观过程的一致性等。这使得成块性成为马尔科夫链维度约简研究中最常用的标准之一。
==最初定义==
==最初定义==
为了严谨地介绍这一定义，我们将详细翻译文章中的部分<ref name=":1" />。'''不感兴趣的读者可以跳到更简洁直观的‘成块性的充分必要条件'部分。'''
首先，我们形式化马尔科夫链的定义：设微观状态空间为有限集<math>S=\{s_1, s_2, ... ,s_n\}</math>，系统在<math>t</math>时刻的状态分布向量<math>s^{(t)} = [ Pr(s(t) = s_1), Pr(s(t) = s_2), ... , Pr(s(t) = s_n) ]，表示系统在各个微观状态的概率分布。
对于一个给定的状态划分（state partition） <math>A=\{A_1, A_2, ... ,A_r\}</math>，我们可以将其视为宏观状态空间。微观状态空间<math>S</math> 和 宏观状态空间<math>A</math> 之间存在硬性划分映射关系<math>\Phi:S \rightarrow A</math>为：<math>A_i \in S, A_i \neq \empty, A_i \cap A_j = \empty , \forall i, j, \cup_i A_i = S</math>，满足以下条件：1. <math>A</math>中的每个元素<math>A_i</math>都包括了若干个<math>s_i</math>；2. <math>A_i</math>和<math>A_j</math>之间没有交集，即每个<math>s_i</math>不会同时属于<math>A_i</math>和<math>A_j</math>；3. <math>S</math>中的每个元素必须属于某个<math>A</math>的元素，即<math>A</math>覆盖了<math>S</math>。
[[文件:Lumpable矩阵粗粒化示例.png|缩略图|500x500像素|图1：矩阵粗粒化示例]]在这里，我们考虑的是线性的马尔科夫过程的投影，所以<math>\Phi</math>是一个<math>n \times n</math>的投影矩阵。对于任意状态划分 <math>\Phi</math>，我们能够定义一个'''简化过程（lumped process）'''，即把微观的动力学轨迹<math>s^{(t)}</math>通过投影矩阵<math>\Phi</math>投影到<math>A</math>的空间上，<math>A^{(t)} = s^{(t)} \Phi</math>。
[[文件:Lumpable矩阵粗粒化示例.png|缩略图|500x500像素|图1：矩阵粗粒化示例]]我们考虑马尔科夫过程的线性投影，因此<math>\Phi</math>是一个<math>\{0,1\}^{n \times r}</math>的投影矩阵。对于任意 <math>\Phi</math>，我们可以定义一个'''简化过程（lumped process）'''，<math>\{A^{(t)}: A^{(t)} = s^{(t)} \Phi \}</math>，即通过投影矩阵<math>\Phi</math>将微观的动力学轨迹<math>s^{(t)}</math>投影到宏观状态空间<math>A</math>上。
例如图（1）所示的4状态马尔科夫链，选择投影矩阵<math>\Phi = \left ( \begin{array}{cc} 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{array} \right )</math>时，微观状态序列<math>\{ s_1, s_3, s_4, s_2, s_2, s_3 \}</math>将被压缩为<math>\{ A_1, A_2, A_2, A_1, A_1, A_2 \}</math>。
这些公式描述了：
这些公式描述了：
# 式子1.1：系统在<math>t=0</math>的微观状态<math>s^{(0)}</math>属于某个宏观状态<math>A_i</math>的概率；
# 式子1.1：初始宏观分布：系统在<math>t=0</math>的微观状态<math>s^{(0)}</math>属于某个宏观状态<math>A_i</math>的概率；
# 式子1.2：已知在<math>t=0</math>的微观状态<math>s^{(0)}</math>属于某个宏观状态<math>A_i</math>，那么在时间<math>t=1</math>的微观状态<math>s^{(1)}</math>属于某个宏观状态<math>A_j</math>的概率；
# 式子1.2：单步转移：已知在<math>t=0</math>的微观状态<math>s^{(0)}</math>属于某个宏观状态<math>A_i</math>，那么在时间<math>t=1</math>的微观状态<math>s^{(1)}</math>属于某个宏观状态<math>A_j</math>的概率；
# 式子1.3：已知历史微观状态<math>\{s^{(0)}, ... , s^{(t-1)} \}</math>对应的宏观状态，那么在时间<math>t</math>的微观状态<math>s^{(t)}</math>属于某个宏观状态<math>A_m</math>的概率；
# 式子1.3：历史依赖转移：已知历史微观状态<math>\{s^{(0)}, ... , s^{(t-1)} \}</math>对应的宏观状态，那么在时间<math>t</math>的微观状态<math>s^{(t)}</math>属于某个宏观状态<math>A_m</math>的概率；
我们看到从<math>s^{(t)}</math>到<math>A^{(t+1)}</math>存在 微观状态->微观动力学->粗粒化->宏观状态 的这一条路径（细心的读者可能会发现在图中还有另一条路径，我们会在后面讨论）。我们现在有了微观动力学<math>\{s^{(0)}, ... , s^{(t-1)} \}</math>，也有了微观到宏观的粗粒化过程<math>A</math>。所以式子（1）描述的简化过程正是先走微观动力学再聚合的这条路径的<math>A^{(t)}</math>。它描述了我们从任意一个初始状态<math>s^{(0)}=\pi</math>开始，走了<math>t</math>步微观动力学，然后在<math>t</math>时刻做粗粒化得到<math>A^{(t)}</math>的过程。需要注意的是，虽然任意一个状态划分<math>\Phi</math>都能走这样的路径，并形成简化过程，'''但不是所有的这些简化过程都和微观过程保持一致。'''他们不一定能够得出一个宏观动力学来描述式子（1）中微观状态的宏观投影，如图（2）中的第二个例子，也'''不一定会拥有马尔科夫性。'''
其中，我们把‘成功’的情况定义为成块的划分，而‘失败’的情况则是不成块的。
'''''定义2'''''：'''成块的划分 lumpable partition'''
'''''定义2'''''：'''成块的划分 lumpable partition'''
'''对于一个给定的状态 <math>A</math>，当下列两个条件都满足时，<math>A</math>是一个成块划分（lumpable partition）。'''
'''对于一个给定的状态划分 <math>\Phi</math>，当下列两个条件都满足时，<math>\Phi</math>是一个成块的划分（lumpable partition）。'''
'''1. 定义1中式子(1)描述的简化过程具有马尔科夫性，即式子(1.3)可写成'''{{NumBlk|:|<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>|{{EquationRef|2}}}}
'''1. 定义1中式子(1)描述的简化过程具有马尔科夫性，即式子(1.3)可写成式子(1.2)的形式'''{{NumBlk|:|<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>|{{EquationRef|2}}}}
'''2. 转移概率(transition probability)，即式子(1.3)（或式子(2)），对任何微观初始状态(starting vector) <math> \pi </math> 都保持一致，从而我们能够得出宏观的概率转移矩阵<math>P' = \Phi^T P (\Phi^T)^{-1} = \Phi^T P \Phi^{\dagger} = \Phi^T P \Phi (\Phi^T \Phi)^{-1}</math>'''
'''2. 转移概率(transition probability)，即式子(1.3)或式子(2)，对任何微观初始状态(starting vector) <math> \pi </math> 都保持一致，从而我们能够得出宏观的概率转移矩阵<math>P' = \Phi^T P (\Phi^T)^{-1} = \Phi^T P \Phi^{\dagger} = \Phi^T P \Phi (\Phi^T \Phi)^{-1}</math>'''
其中，因为<math>\Phi</math>不是方阵，我们定义<math>\Phi^{\dagger}</math>为<math>\Phi</math>的伪逆矩阵，满足<math>\Phi \Phi^{\dagger} \Phi = \Phi</math>。另外，<math>\Phi^T \Phi</math>是一个对角阵，对角线上的元素为每个<math>A_i</math>包括了多少个微观状态的计数，而它的逆矩阵就是把对角线上的元素全部取倒数。
其中，因为<math>\Phi</math>不是方阵，我们定义<math>\Phi^{\dagger}</math>为<math>\Phi</math>的伪逆矩阵，满足<math>\Phi \Phi^{\dagger} \Phi = \Phi</math>。另外，<math>\Phi^T \Phi</math>是一个对角阵，对角线上的元素为每个<math>A_i</math>包括了多少个微观状态的计数，而它的逆矩阵就是把对角线上的元素全部取倒数。
[[文件:Lumpable和non-lumpable的例子.png|缩略图|图2：对成块的和不成块的矩阵做粗粒化|替代=|600x600像素]]不满足上述两个条件的，都不被定义为成块的划分。也就是说，不是所有的简化过程都是成块的，即使他们的命名方式（lumpable process v.s. lumped process）相似。
[[文件:Lumpable和non-lumpable的例子.png|缩略图|图2：对成块的和不成块的矩阵做粗粒化|替代=|600x600像素]]不满足上述两个条件的，都不被定义为成块的划分。也就是说，不是所有的简化过程都是成块的，即使他们的命名方式（lumped process和lumpable process）相似。
从图（2）的成块划分的例子中，我们看到对于分组矩阵<math>\Phi = \left ( \begin{array}{cc} 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{array} \right )</math>，成块的动力学TPM可以找到一个简化过程，而这个简化过程是满足马尔可夫性，且对所有初始状态都保持一致的。也就是说，无论<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>都保持一致。
从图（2）的成块划分的例子中，我们看到对于分组矩阵<math>\Phi = \left ( \begin{array}{cc} 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{array} \right )</math>，成块的动力学TPM可以找到一个简化过程，而这个简化过程满足马尔可夫性，且对所有初始状态都保持一致。无论<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>都保持一致。
对于例子中的不成块的矩阵，我们或许可以给它强制定义一个简化过程的TPM，比如<math> P_1' = \left ( \begin{array}{cc} 0.6 & 0.4 \\ 0.2 & 0.8 \\ \end{array} \right )</math>，但这个简化过程并不能对任何微观初始状态保持一致，只能对<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>不适用这个简化过程。它适用的是<math> P_2' = \left ( \begin{array}{cc} 0.5 & 0.5 \\ 0.2 & 0.8 \\ \end{array} \right )</math>。这里的不适用是指，这个简化过程不能描述这个<math>\pi</math>为初始状态出发的微观状态序列投影的宏观状态序列。我们看到，对于这个分组矩阵<math>\Phi = \left ( \begin{array}{cc} 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{array} \right )</math>，马尔科夫矩阵有两个简化过程 <math> P_1'</math>和<math> P_2'</math>，而它们各自只适用于一些微观初始状态(starting vector) <math> \pi </math>，并不满足定义2中的条件，所以<math>A</math>对于这个TPM来说不是一个成块的划分。事实上，这个TPM只存在一个成块的划分，就是不做任何的分组，所以它无法按照成块性的定义进行粗粒化。在后面“成块性概念的变种”的部分，我们会提到，虽然对这个TPM做的划分不符合（强）成块性的要求，但是它实际上满足弱成块性 Weak Lumpability，即简化过程对部分微观初始状态使用。
对于例子中的不成块的矩阵，我们或许可以给它强制定义一个简化过程的TPM，比如<math> P_1' = \left ( \begin{array}{cc} 0.6 & 0.4 \\ 0.2 & 0.8 \\ \end{array} \right )</math>，但这个简化过程并不能对任何微观初始状态保持一致，只能对<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>不适用这个简化过程。它适用的是<math> P_2' = \left ( \begin{array}{cc} 0.5 & 0.5 \\ 0.2 & 0.8 \\ \end{array} \right )</math>。这里的不适用是指，这个简化过程不能描述以这个<math>\pi</math>为初始状态出发的微观状态序列投影的宏观状态序列。我们看到，对于这个例子，马尔科夫矩阵有两个简化过程 <math> P_1'</math>和<math> P_2'</math>，而它们各自只适用于一些微观初始状态(starting vector) <math> \pi </math>，并不满足定义2中的条件，所以<math>\Phi</math>对于这个TPM来说不是一个成块的划分。事实上，这个TPM只存在一个成块的划分，就是不做任何分组，因此它无法按照成块性的定义进行粗粒化。在后面“成块性概念的变种”的部分，我们会提到，虽然对这个TPM做的划分不符合（强）成块性的要求，但是它实际上满足弱成块性 Weak Lumpability，即简化过程对部分微观初始状态使用。
<br/>
==成块性的充分必要条件==
==成块性的充分必要条件==
通过上面的例子，我们对成块性有了初步的直观理解：在成块的划分中，有两个分组，所以有四个框。每一个框里，每一列相加的和都是一样的。例如，在左上角的框中，<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>，作者<ref name=":1" />提出了判断一个马尔科夫链对'''给定划分 <math>A</math>''' 是否成块的充分必要条件为：
'''''定理1：'''''
'''''定理1：'''''
'''给定划分 <math>A</math>是成块的充分必要条件为：'''
'''给定划分 <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</math>里的每一个状态<math>s_k</math>转移到<math>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_i</math>里的每一个状态<math>s_k</math>转移到<math>A_j</math>中的所有状态的转移概率之和是相同的，'''
{{NumBlk|:|
{{NumBlk|:|
|{{EquationRef|3}}}}
|{{EquationRef|3}}}}
满足这个条件后，我们就可以将<math>A_j</math>中的所有微观状态<math>s_l</math>合并为一个宏观状态<math>A_j</math>，因为它们从其他宏观状态的转入概率是一致的。同样的，我们也可以将<math>A_i</math>中的所有微观状态<math>s_k</math>合并为一个宏观状态<math>A_i</math>，因为这些微观状态<math>s_k</math>（和<math>A_i</math>）到其他宏观状态的转出概率是一致的。
例如，在下图中，<math>s_1</math>和<math>s_2</math>都属于<math>A_1</math>，它们到<math>A_1</math>和<math>A_1</math>的转移概率是一样的；同样，<math>s_3</math>和<math>s_4</math>都属于<math>A_2</math>，它们到宏观状态的转移概率也是一样的。因此，<math>[[1,2], [3, 4]]</math>是<math>P</math>的一个成块划分。
[[文件:成块性充分必要条件.png|居中|700像素|成块性充分必要条件实例]]
[[文件:成块性充分必要条件.png|居中|700像素|成块性充分必要条件实例]]
基于这个条件，我们可以定义成块划分的宏观动力学<math>A^{(t)} = A^{(t-1)} P'</math>：
'''''定义3'''''：'''成块性的宏观动力学'''
'''''定义3'''''：'''成块性的宏观动力学'''
|{{EquationRef|4}}}}
|{{EquationRef|4}}}}
这个公式表明，群组<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>P</math>和<math>P'</math>之间的关系：
我们也可以直接定义<math>P</math>和<math>P'</math>之间的关系：
<math>P' = \Phi^T P (\Phi^T)^{-1} = \Phi^T P \Phi (\Phi^T \Phi)^{-1}</math>，
<math>P' = \Phi^T P (\Phi^T)^{-1} = \Phi^T P \Phi (\Phi^T \Phi)^{-1}</math>，
其中，<math>\Phi^T \Phi</math>是一个对角阵，对角线上的元素为每个<math>A_i</math>包括了多少个微观状态的计数，而它的逆矩阵就是把对角线上的元素全部取倒数。
其中，<math>\Phi^T \Phi</math>是一个对角阵，对角线上的元素为每个<math>A_i</math>包括了多少个微观状态的计数，其逆矩阵就是把对角线上的元素全部取倒数。
根据成块划分 <math>\Phi</math>定义好宏观动力学后，我们就能走另外一条路径了：'''微观状态->粗粒化->宏观动力学->宏观状态'''。我们发现这和'''微观状态->微观动力学->粗粒化->宏观状态'''这两条路径，'''从任意一个微观状态出发，都能到达相同的宏观状态。'''所以，这满足了'''动力学'''和'''粗粒化'''这两个'''算子'''的'''可交换性（Exchangeability）'''。具体的证明我们会在后面的‘成块性满足的性质’部分介绍。
根据成块划分 <math>\Phi</math>定义好宏观动力学后，我们可以走另一条路径了：'''微观状态->粗粒化->宏观动力学->宏观状态'''。我们发现，这条路径与'''微观状态->微观动力学->粗粒化->宏观状态'''是一致的。'''无论从哪个微观状态出发，最终都能到达相同的宏观状态。'''所以，这满足了'''动力学'''和'''粗粒化'''这两个'''算子'''的'''可交换性（Exchangeability）'''。具体的证明将在后面的‘成块性满足的性质’部分介绍。
'''必要性部分的证明：'''
'''必要性部分的证明：'''
必要性是指，如果一个马尔可夫链的划分 <math>A</math>是成块的，那么就肯定会满足上述的这个特定条件。
必要性是指，如果一个马尔可夫链的划分 <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</math>的转移概率满足宏观马尔可夫性，且这个转移概率<math>Pr_{\pi} [ s^{(1)} \in A_j | s^{(0)} \in A_i ]</math>对每个<math>\pi</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>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>\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>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>是s^{(t-1)}</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>A_i</math>和<math>A_j</math>，而不依赖于<math>A_i</math>中的具体状态，因此我们可以将<math>A_i</math>中的所有状态合并为一个状态，并且这个合并后的链仍满足马尔可夫性。所以，上述条件为成块性的充分条件。
由于转移概率只依赖于群组<math>A_i</math>和<math>A_j</math>，而不依赖于<math>A_i</math>中的具体状态，因此我们可以将<math>A_i</math>中的所有状态合并为一个状态，并且合并后的链仍满足马尔可夫性。所以，上述条件为成块性的充分条件。
从这两个证明里，我们也可以看到微观动力学路径和宏观动力学路径的'''一致性'''。无论我们从<math>A_i</math>中的哪个具体状态<math>s^{(t-1)}</math>开始，只要当前的宏观状态是<math>A_i</math>，我们就可以计算下一步转移到<math>A_j</math>的概率，而不依赖于<math>s^{(t-1)}</math>。这表明，微观<math>s^{(t-1)}</math>->宏观<math>A^{(t-1)}</math>->宏观动力学-><math>A^{(t)}</math>不会影响未来状态的预测，因此微观和宏观两个路径得出的<math>A^{(t)}</math>的概率是一致的。同样的，具体的证明将在后面的‘成块性满足的性质’部分介绍。
'''请注意'''：成块性有一个非常重要的前提，即我们要给定一个对马尔科夫链的状态的划分，然后根据马尔科夫状态转移矩阵来决定这个划分对这个马尔科夫链是否成块的。
'''请注意'''：成块性有一个非常重要的前提：我们需要给定一个对马尔科夫链的状态划分，然后根据马尔科夫状态转移矩阵来判断这个划分对这个马尔科夫链是否成块。
所以，成块性并不是一个马尔科夫链本身的属性，而是对马尔科夫链的某个状态划分的属性。直接说某个马尔科夫链成块或是不成块是不严谨的。相反，我们应该说，对于某个马尔科夫链的某个状态划分是成块或不成块的。然而，为了简略表达，当我们说某个马尔科夫链成块时，我们通常是指它存在某种成块的状态划分。
这一前提也提醒我们，在讨论成块性时，必须明确状态划分的方式。不同的划分方式可能导致不同的结论。一个马尔科夫链可能在某种划分下是成块的，而在另一种划分下则不成块。因此，成块性更多地反映了状态划分与马尔科夫链的适配性，而不是马尔科夫链本身的特性。
<br/>
==成块性的正例和反例==
==成块性的正例和反例==
</math>
</math>
<br/>
==成块性满足的性质==
在[[马尔科夫链的粗粒化]]过程中，我们通常有多个目标：
#降低压缩后的动力学维度，以简化模型复杂性；
#首先，我们想尽量降低压缩后的动力学维度；
#保留动力学中有用的信息，以确保模型的有效性；
#其次，我们想在压缩过程中尽量保留动力学中有用的信息；
#保持压缩前后过程的一致性，以确保模型的可靠性。
#最后，我们想要压缩后的过程和原本的过程尽量保持一致。
然而，这些目标之间往往存在矛盾：压缩的维度越多，保留的信息就越少，压缩前后的一致性就越难保持。成块性作为一种较为严格的划分方式，虽然在压缩维度上可能不如其他方法显著，但它能够保留在宏观层面上所有有用的信息，并且确保粗粒化前后过程的一致性。
===宏观最大预测性===
===宏观最大预测性===
宏观最大预测性是指，在将微观状态粗粒化为宏观状态后，我们就不再需要微观状态，只用宏观状态就能预测后续的宏观状态。
具体来说，只需要知道宏观状态<math>A^{(t)}</math>，就可以最大化<math>A^{(t+1)}</math>的预测效果，而微观状态<math>s^{(t+1)}</math>虽然能提供一些额外信息，但是对于预测<math>A^{(t+1)}</math>并无帮助。这意味着条件互信息<math>I(A^{(t+1)}; s^{(t+1)} | A^{(t)}) = 0</math>。宏观动力学不需要任何来自微观状态的修正，就能独立且正确地反映系统在宏观层面上的演化。
尽管成块性划分能够准确预测宏观动力学，但它无法确保像[[计算力学]]中的因果态那样的微观最大预测性。因为在聚类过程中会损失微观状态的信息，使得我们无法辨别某个<math>A^{(t)}</math>具体是哪个微观态<math>s^{(t)}</math>。这个信息的损失是不可逆的，所以从微观粗粒化到宏观之后，就无法再还原到微观了。
[[文件:马尔科夫链的粗粒化定义.png|替代=|缩略图|图3：粗粒化图例]]
[[文件:马尔科夫链的粗粒化定义.png|替代=|缩略图|图3：粗粒化图例]]
图（3）展示了从某个微观状态<math>s^{(t)}</math>出发，到达下一刻的宏观状态<math>A^{(t+1)}</math>的两条路径<ref name=":7">Coarse graining. ''Encyclopedia of Mathematics.'' URL: <nowiki>http://encyclopediaofmath.org/index.php?title=Coarse_graining&oldid=16170</nowiki></ref>：
#先进过微观动力学达到<math>s^{(t+1)}</math>，再做粗粒化得到<math>A^{(t+1)}</math>
#先经过微观动力学达到<math>s^{(t+1)}</math>，再进行粗粒化得到<math>A^{(t+1)}</math>
#先做粗粒化得到<math>A^{(t)}</math>，再经过宏观动力学到达<math>A^{(t+1)}</math>
#先进行粗粒化得到<math>A^{(t)}</math>，再经过宏观动力学到达<math>A^{(t+1)}</math>
如果我们把粗粒化和（宏观/微观）动力学看作是两个算子，那这两个算子的可交换性指的是：无论从哪个微观状态分布出发，走这两条路径得到的<math>A^{(t+1)}</math>的分布是一样的，即，'''<math>s^{(t)} \Phi P' = s^{(t)} P \Phi</math>'''。
证明如下：
证明如下：
对于一个成块的<math>P</math>，和它的成块划分<math>\Phi</math>，我们针对<math>\Phi = \left ( \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ 0 & 1 \\ 0 & 1 \end{array} \right )</math>的例子，但所有其他的例子都一样的。
对于一个成块的<math>P</math>，和它的成块划分<math>\Phi</math>，我们针对<math>\Phi = \left ( \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ 0 & 1 \\ 0 & 1 \end{array} \right )</math>的例子，其他情况类似。
对于这个<math>\Phi</math>，我们知道<math>P_{11}=A_{11}</math>，<math>P_{12}+P_{13}+P_{14}=A_{12}</math>，<math>P_{21}=P_{31}=P_{41}=A_{21}</math>，<math>P_{22}+P_{23}+P_{24}=P_{32}+P_{33}+P_{34}=P_{42}+P_{43}+P_{44}=A_{22}</math>。
对于这个<math>\Phi</math>，我们知道<math>P_{11}=A_{11}</math>，<math>P_{12}+P_{13}+P_{14}=A_{12}</math>，<math>P_{21}=P_{31}=P_{41}=A_{21}</math>，<math>P_{22}+P_{23}+P_{24}=P_{32}+P_{33}+P_{34}=P_{42}+P_{43}+P_{44}=A_{22}</math>。
由于<math>A_{21}</math>和<math>A_{22}</math>的等于关系，<math>P \Phi = \left ( \begin{array}{cc} P_{11}' & P_{12}' \\ P_{21}' & P_{22}' \\ P_{21}' & P_{22}' \\ P_{21}' & P_{22}' \end{array} \right )</math>。这相当于将<math>P</math>的每一行按照划分进行加总，而<math>P \Phi</math>中同一组的行是相同的。
另一方面，<math>\Phi P'</math>的含义是将<math>P'</math>的每一行按照<math>\Phi</math>复制到对应的微观状态的行中。所以，我们会发现<math>\Phi P'</math>和<math>P \Phi</math>的结果是一样的。
===一致性Consistency===
===一致性Consistency===
这一小节里讨论马尔科夫链的成块划分 与 HOM（Higher-order Macronodes，详情请参考[[复杂网络中的因果涌现]]）之间的关系，以及它们与一致性的联系。
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>提出，根据给定的微观马尔科夫链和节点划分方案，得出一个和微观转移矩阵保持一致的宏观转移矩阵的方法。
我们通过一个简单的成块划分例子来展示成块性的粗粒化与HOM是对应的。
[[文件:Lumpability例子示意图.png|缩略图|图4：例子示意图|替代=]]
[[文件:Lumpability例子示意图.png|缩略图|图4：例子示意图|替代=]]
[[文件:HOM示例.png|411x411像素|缩略图|图5：HOM节点边权合并示意图|替代=]]
[[文件:HOM示例.png|411x411像素|缩略图|图5：HOM节点边权合并示意图|替代=]]
然后，我们简单介绍[[网络归并]]构建宏观HOM转移概率矩阵的计算方法。
在图4中，我们将节点3和4视为待合并的节点<math>A</math>。
1. 对于其他节点到待合并节点<math>A</math>的连边，即待合并节点的入流（图4中绿色的连边），我们直接加和即可，即<math>p_{s_1 \rightarrow A} = 0.3+0.1=0.4</math>，<math>p_{ s_2 \rightarrow A} = 0.2+0.3=0.5</math>
1. 入流：对于其他节点到待合并节点<math>A</math>的连边（图4中绿色的连边），直接加和即可。例如，<math>p_{s_1 \rightarrow A} = 0.3+0.1=0.4</math>，<math>p_{ s_2 \rightarrow A} = 0.2+0.3=0.5</math>
2. 对于待合并节点<math>A</math>到其他节点的连边，即待合并节点的出流（图4中棕色的连边），我们需要考虑三种情况：
2. 出流：对于待合并节点<math>A</math>到其他节点的连边（图4中棕色的连边），需要考虑三种情况：
#当待合并节点<math>A</math>间存在连边时；
#当待合并节点<math>A</math>间存在连边时；
#当待合并节点<math>A</math>指向同一个输出节点时；
#当待合并节点<math>A</math>指向同一个输出节点时；
待合并节点<math>A</math>的出流的计算方式都不一样，如图5所示。
待合并节点<math>A</math>的出流的计算方式都不一样，如图5所示。
'''但是'''，我们可以注意到，这三种计算方式都是待合并节点<math>A</math>中的各节点的出流的<math>W_i^{out}</math>加权，而我们知道，成块性的特性决定了，群组里的各节点到其他群组的出流<math>W_i^{out}</math>都是一样的，对相同的<math>W_i^{out}</math>做任意加权平均的结果都等于<math>W_i^{out}</math>。也就是说，任意的加权方法对于成块的划分来说都能得出相同的结果。
'''然而'''，我们可以注意到，这三种计算方式本质上都是对待合并节点<math>A</math>中各节点的出流<math>W_i^{out}</math>加权。而成块性的特性决定了，群组里的各节点到其他群组的出流<math>W_i^{out}</math>都是一样的。所以，对相同的<math>W_i^{out}</math>进行任意加权平均的结果仍然是<math>W_i^{out}</math>。这意味着，无论根据哪种情况采用哪种加权方法，对于成块划分来说，最终的结果都是一致的，且与成块性的粗粒化结果相同。
由此，我们总结，'''成块性的聚合方式和HOM的计算方式，无论入流还是出流都完全一致。'''
由此，我们总结，'''成块性的聚合方式和HOM的计算方式，无论入流还是出流都完全一致。'''
以下关于[[动力学的一致性检验]]的描述节选自[[复杂网络中的因果涌现]]：
以下关于[[动力学的一致性检验]]的描述节选自[[复杂网络中的因果涌现]]：
定义微观网络<math>G </math>与宏观网络<math>G_M </math>，在两个网络上[[随机游走]]，在未来某个时间<math>t </math> ， <math>G </math>上的预期分布为 <math>P_m(t) </math>， <math>G_M </math>上的预期分布为 <math>P_M(t) </math>。
定义微观网络<math>G </math>与宏观网络<math>G_M </math>，分别在两个网络上进行[[随机游走]]。在某个时间<math>t</math>，<math>G</math>上的预期分布为<math>P_m(t)</math>，而<math>G_M </math>上的预期分布为 <math>P_M(t)</math>。
将<math>P_m(t) </math>分布叠加到宏观上<math>G_M </math>的相同节点上，得到<math>P_{M|m}(t) </math>分布。用<math>P_M(t) </math>和<math>P_{M|m}(t) </math>之间的KL散度来衡量其不一致性（inconsistency），若结果为零则动力学一致。公式为：
将<math>P_m(t) </math>分布叠加到宏观宏观<math>G_M </math>的相同节点上，得到<math>P_{M|m}(t) </math>分布。通过计算<math>P_M(t) </math>和<math>P_{M|m}(t) </math>之间的KL散度来衡量其不一致性（inconsistency）。如果结果为零，则表示动力学一致。公式如下：
<math>inconsistency=\sum_{t=0}^T D_{KL}[P_M(t)||P_{M|m}(t)]</math>
<math>inconsistency=\sum_{t=0}^T D_{KL}[P_M(t)||P_{M|m}(t)]</math>
也就是说，不一致性 表示了 宏观和微观网络节点在不同时刻的概率分布的[[KL散度]]之和。
实验表明，对不同节点规模以及参数下的微观网络，使用HOM粗粒化后的宏观网络的不一致性随着迭代步数的增加都会收敛到零。这表明，HOM 构建的宏观网络与微观网络是保持一致的。
回到上面基于成块划分做的粗粒化过程与HOM等价的推断，我们可以得出结论，'''基于成块性划分的粗粒化方法构建的宏观网络与微观网络也是一致的。'''
<br/>
<br/>
==成块性概念的变种==
==成块性概念的变种==
尽管成块性具有许多优良的特性，但它本身是一个非常严格的条件。在实际应用中，如果不允许一定的误差，几乎很难找到满足成块性的划分，从而难以对马尔科夫链进行有效的粗粒化。因此，成块性衍生出了多种变种概念，这些变种通过放宽某些限制条件，使得在实际问题中更容易找到有效的划分，并研究这些划分在多大程度上保留了宏观最大预测性、可交换性、一致性等重要性质。
===强成块性 Strong/Ordinary Lumpability===
===强成块性 Strong/Ordinary Lumpability===
强成块性（Strong lumpability） 或 ordinary lumpability 是上面所述的成块性的原本概念，是这六个变种中约束最强的一种。它要求矩阵具有严格的分块性。
强成块性（Strong lumpability） 或 ordinary lumpability 是上述成块性的原始概念，也是六种变种中限制最严格的一种。它要求矩阵具有严格的分块性，即同一组中的每个状态到其他分组的转出概率必须完全相同。
这里的'Strong'是与下面的'weak'相对的概念，指上文的简化过程满足对任意初始状态分布都保持一致的条件。
这里的'Strong'是与下面的'weak'相对的概念，指的是简化过程必须对任意初始状态分布都保持一致。
简单的例子：
简单的例子：
===弱成块性 Weak Lumpability===
===弱成块性 Weak Lumpability===
弱成块性（weak lumpability）<ref name=":3" />是指简化过程不对所有的初始状态满足，而仅对某些初始状态满足。
弱成块性（weak lumpability）<ref name=":3" />是指简化过程仅对某些初始状态满足，而不是对所有初始状态都满足。
例如，某个状态<math>s_i</math>到<math>s_j</math>不联通，而简化过程适用于<math>s_i</math>但不适用于<math>s_j</math>。所以，当初始状态为<math>s_i</math>时，由于永远不会到达<math>s_j</math>，简化过程会一直适用。
简单的例子：
简单的例子：
===精确成块 Exact Lumpability===
===精确成块性 Exact Lumpability===
在强成块性中，要求分组内每一'''行'''的加总相同，即同一组中的每个状态到其他分组的'''转出'''概率相同。
而在精确成块性（exact lumpability）中，要求分组内的每一'''列'''的加总相同，即同一组中的每个状态从其他分组的'''转入'''概率相同。
在文献<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"/>还指出，精确成块的<math>P</math>也是弱成块的。
在强成块性的例子中，<math>[[1, 2], [3, 4]]</math>是一个强成块的分组，但不是一个精确成块的分组。
在强成块性的例子中，<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>是一个成块的矩阵，而<math>P^{\epsilon}</math>中的每个元素都小于<math>\epsilon</math>，<math>P</math>就是一个<math>\epsilon</math>-准成块的矩阵。
比如说，我们对上面的成块的例子加上一点扰动：
比如说，我们对上面的成块的例子加上一点扰动：
</math>
</math>
就能获得一个<math>\epsilon</math>-quasi-lumpable，<math>\epsilon=0.02</math>的矩阵。
就能获得一个<math>\epsilon</math>-准成块的矩阵，其中<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上。
比例成块性（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）提出的，用于放松成块性限制的概念。目前尚未发现有研究证明其能应用于离散时间马尔科夫链（DTMC）。
如果将 DTMC 的转移概率矩阵<math>P</math>视为一个差分算子，那么我们可以大概把CTMC的转移概率矩阵 <math>Q</math>看作是一个微分算子。
强成块性在CTMC设定下跟DTMC是类似的，简单来说就是：
强成块性在CTMC设定下跟DTMC是类似的，简单来说就是：
而在CTMC设定下，比例成块性的定义是：
对<math>S</math>中的任意一个状态，存在一个函数<math>\kappa:S \rightarrow \mathcal{R}^+</math>，使得：
对<math>S</math>中的任意一个状态，存在一个函数<math>\kappa:S \rightarrow \mathcal{R}^+</math>，使得：
<math>\forall A_m, A_n, A_m \neq A_n s_i, s_j \in A_m, \frac{Pr(A_m|s_i)}{\kappa(s_i)} = \frac{Pr(A_m|s_j)}{\kappa(s_j)}</math>
<math>\forall A_m, A_n, A_m \neq A_n s_i, s_j \in A_m, \frac{Pr(A_m|s_i)}{\kappa(s_i)} = \frac{Pr(A_m|s_j)}{\kappa(s_j)}</math>
我们称这样的CTMC对分组<math>A</math> 是 <math>\kappa</math>-比例成块的。
==成块性和粗粒化==
==成块性和粗粒化==
[[马尔科夫链的粗粒化]]可以理解为对一个马尔科夫TPM得到一个分组矩阵<math>\Phi</math>和它对应的宏观TPM<math>P'</math>。这个过程通常可以分为两部：先获取<math>\Phi</math>，再获取<math>P'</math>。
[[马尔科夫链的粗粒化]]可以理解为对一个马尔科夫转移概率矩阵（TPM）进行分组，得到一个分组矩阵<math>\Phi</math>和它对应的宏观TPM<math>P'</math>。这一过程通常可以分为两部：先进行状态划分<math>\Phi</math>，再基于<math>\Phi</math>获取<math>P'</math>。
对状态空间做粗粒化有硬划分和软划分两种。软划分可以看作把微观状态打散重构成了一些宏观状态，而硬划分则更为严格，直接将若干个微观状态划分为一个组。本文仅讨论硬划分，不涉及软划分。
成块性是对第一步，即对<math>\Phi</math>的约束要求；而上面提到的宏观最大预测性、可交换性和一致性是对<math>P'</math>的约束。
从前面的成块性公式（2）和例子中，我们可以直观地理解：当马尔科夫矩阵存在块状结构，或者状态明显可以被划分为几类时，根据这样的划分，该矩阵就是成块的。对于简单的<math>P</math>，如图6中的<math>\bar{P}</math>所示，我们能够根据上面的定理（1）很快的找出它的成块划分<math>\Phi</math>，并通过定义（3）迅速计算出对应的<math>P'</math>。
[[文件:Lump fig1.png|缩略图|398x398像素|图6：Zhang<ref name=":4" /> 文章中的示意图。图中左面四个矩阵都是成块的马尔科夫矩阵，而右面的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|替代=]]
然而，在实际应用中，我们经常遇到的矩阵可能并不完美。例如，成块的矩阵的状态排序可能被打乱（如图（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>这样的矩阵。我们既无法确定它是否成块，也无法决定它的划分，甚至不知道它的马尔科夫秩。
针对这一问题，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；
#获取<math>r<n</math> 的马尔科夫秩，或指定一个<math>r</math>；
#对P进行SVD分解，<math>P = U \Sigma V^T</math>，其中U为左奇异向量，V为右奇异向量。
#对P进行SVD分解，<math>P = U \Sigma V^T</math>，其中U为左奇异向量，V为右奇异向量。
#通过下列公式得到最优划分 <math>\Omega_1, \Omega_2, ... , \Omega_r</math>
#通过下列公式得到最优划分 <math>\Omega_1, \Omega_2, ... , \Omega_r</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>距离最小，也就是说，让每个微观态的右特征向量和它对应的宏观态的右特征向量尽可能接近。
这个算法看起来非常熟悉，实际上它与 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>类点的中心点：
<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>
我们看到这两个目标函数非常相似。因此，我们可以通过上述算法或 k-Means 聚类来获取最优的状态划分，进而判断马尔科夫矩阵的成块性。