更改

为理解成块性(lumpability)的重要性，我们通过一个反例来揭示不满足成块性粗粒化的缺陷。给定图中的马尔科夫链，我们尝试将状态{1,2}合并为宏观态A，{3,4}合并为B。

为理解成块性(lumpability)的重要性，我们通过一个反例来揭示不满足成块性粗粒化的缺陷。给定图中的马尔科夫链，我们尝试将状态{1,2}合并为宏观态A，{3,4}合并为B。

[[文件:非一致性示例.png|居中|700像素]]

[[文件:非一致性示例.png|居中|700像素|图1：不满足一致性马尔科夫链示例]]

当我们构建粗粒化后的<math>2\times 2</math>的宏观马尔科夫链<math>P'</math>时，分组A到分组B的概率应满足：从<math>A</math>中'''任一微观态出发'''，转移到<math>B</math>的总概率必须相同。

当我们构建粗粒化后的<math>2\times 2</math>的宏观马尔科夫链<math>P'</math>时，分组A到分组B的概率应满足：从<math>A</math>中'''任一微观态出发'''，转移到<math>B</math>的总概率必须相同。

我们假设一个微观初始状态分布，比如(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, 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)不一样。'''宏观和微观的演化结果不一致，这样的粗粒化方案被称为不满足一致性。它构建的宏观动力学无法准确反映系统的演化，与本来的微观动力学存在偏差。'''

对于一个给定的状态划分（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>；3. <math>S</math>中的每个元素都必须属于某个<math>A</math>的元素，即<math>A</math>覆盖了<math>S</math>。

对于一个给定的状态划分（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>；3. <math>S</math>中的每个元素都必须属于某个<math>A</math>的元素，即<math>A</math>覆盖了<math>S</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>上。

[[文件:Lumpable矩阵粗粒化示例.png|居中|700像素|图2：矩阵粗粒化示例]]我们考虑马尔科夫过程的线性投影，因此<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>。

例如图（2）所示的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）描述的简化过程，是我们从任意一个初始状态<math>s^{(0)}=\pi</math>开始，走了<math>t</math>步微观动力学，然后在每一步<math>t</math>做粗粒化得到<math>A^{(t)}</math>的过程。在这里，我们强调初始状态分布<math> \pi </math>，是因为这三个概率的取值有可能会随着不同的<math> \pi </math>而变化。

式子（1）描述的简化过程，是我们从任意一个初始状态<math>s^{(0)}=\pi</math>开始，走了<math>t</math>步微观动力学，然后在每一步<math>t</math>做粗粒化得到<math>A^{(t)}</math>的过程。在这里，我们强调初始状态分布<math> \pi </math>，是因为这三个概率的取值有可能会随着不同的<math> \pi </math>而变化。

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

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

如图（2）中的第二个例子，因为简化过程的概率会受到初始状态<math> \pi </math>影响，或者因为它们不符合马尔科夫性，我们无法用这种‘失败’的简化过程来描述一个和微观过程保持一致的宏观动力学。下面，我们会把‘成功’的情况定义为成块的划分，而‘失败’的情况则是不成块的。

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

[[文件:Lumpable和non-lumpable的例子.png|缩略图|图2：对成块的和不成块的矩阵做粗粒化|替代=|600x600像素]]不满足上述两个条件的，都不被定义为成块的划分。也就是说，不是所有的简化过程都是成块的，即使他们的命名方式（lumped process和lumpable process）相似。

[[文件:Lumpable和non-lumpable的例子.png|缩略图|图3：对成块的和不成块的矩阵做粗粒化|替代=|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>都保持一致。

从图（3）的成块划分的例子中，我们看到对于分组矩阵<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>都保持一致。

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

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

[[文件:马尔科夫链的粗粒化定义.png|替代=|缩略图|图3：粗粒化图例]]

[[文件:马尔科夫链的粗粒化定义.png|替代=|缩略图|图5：粗粒化图例]]

图（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>：

图（5）展示了从某个微观状态<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>

我们通过一个简单的成块划分例子来展示成块性的粗粒化与HOM是对应的。

我们通过一个简单的成块划分例子来展示成块性的粗粒化与HOM是对应的。

[[文件:Lumpability例子示意图.png|缩略图|图4：例子示意图|替代=]]

[[文件:Lumpability例子示意图.png|缩略图|图6：例子示意图|替代=]]

<math>

<math>

[[文件:HOM示例.png|411x411像素|缩略图|图5：HOM节点边权合并示意图|替代=]]

[[文件:HOM示例.png|411x411像素|缩略图|图7：HOM节点边权合并示意图|替代=]]

然后，我们简单介绍[[网络归并]]构建宏观HOM转移概率矩阵的计算方法。

然后，我们简单介绍[[网络归并]]构建宏观HOM转移概率矩阵的计算方法。

在图4中，我们将节点3和4视为待合并的节点<math>A</math>。

在图（6）中，我们将节点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>的连边（图（6）中绿色的连边），直接加和即可。例如，<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>到其他节点的连边（图（6）中棕色的连边），需要考虑三种情况：

#当待合并节点<math>A</math>间存在连边时；

#当待合并节点<math>A</math>间存在连边时；

#当待合并节点<math>A</math>指向同一个输出节点时；

#当待合并节点<math>A</math>指向同一个输出节点时；

#当待合并节点<math>A</math>指向不同输出节点时；

#当待合并节点<math>A</math>指向不同输出节点时；

待合并节点<math>A</math>的出流的计算方式都不一样，如图5所示。

待合并节点<math>A</math>的出流的计算方式都不一样，如图（7）所示。

'''然而'''，我们可以注意到，这三种计算方式本质上都是对待合并节点<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>。这意味着，无论根据哪种情况采用哪种加权方法，对于成块划分来说，最终的结果都是一致的，且与成块性的粗粒化结果相同。

成块性是对第一步，即对<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>。

从前面的成块性公式（2）和例子中，我们可以直观地理解：当马尔科夫矩阵存在块状结构，或者状态明显可以被划分为几类时，根据这样的划分，该矩阵就是成块的。对于简单的<math>P</math>，如图（8）中的<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像素|图8：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>）。

然而，在实际应用中，我们经常遇到的矩阵可能并不完美。例如，成块的矩阵的状态排序可能被打乱（如图（8）中的<math>P_1</math>），或者矩阵包含了如<math>P_2</math>的噪声（如图（8）中的<math>P</math>，<math>P = P_1 + P_2</math>，<math>P_1^TP_2 = 0</math>）。

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

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