更改

Lumpability是一种描述马尔科夫链的状态是否可聚类的性质，笔者暂时还没找到一个正式的中文翻译。

Lumpability是一种描述马尔科夫链的状态是否可聚类的性质，笔者暂时还没找到一个正式的中文翻译。

这个概念最早出现在Kemeny, Snell在1969年的Finite Markov Chains<ref name=":3">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>中。

==lumpable partition的充分必要条件==

==lumpable partition的充分必要条件==

通过上面的例子，我们可以对lumpable partition有一些直观的理解。我们可以留意到，在lumpable partition中，有两个分组，所以有四个框。每一个框里，每一列相加的和都是一样的，比如左上角的框中，<math>0.3 + 0.3 = 0.2 + 0.4</math>。这就是lumpable partition更通俗的解释，在某些文献中，并不会使用上面提及的定义，而是直接使用这个通俗版的解释。<ref name=":3" />中作者指出，这两者之间是存在充分必要条件关系的。

通过上面的例子，我们可以对lumpable partition有一些直观的理解。我们可以留意到，在lumpable partition中，有两个分组，所以有四个框。每一个框里，每一列相加的和都是一样的，比如左上角的框中，<math>0.3 + 0.3 = 0.2 + 0.4</math>。这就是lumpable partition更通俗的解释，在某些文献中，并不会使用上面提及的定义，而是直接使用这个通俗版的解释。<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>

第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=":3" />（公式(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>，我们会发现这样的粗粒化结果违背了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>并导致转移概率出错。

===Weak Lumpability===

===Weak Lumpability===

Weak lumpability 是指lumped process不对所有的初始状态满足，而仅对某些初始状态满足。

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>P</math>这样的矩阵，我们既无法确定它是否lumpable，也无法决定它的partition，我们甚至不知道它的马尔科夫秩。

我们在实际问题中很多时候要面对的是像<math>P</math>这样的矩阵，我们既无法确定它是否lumpable，也无法决定它的partition，我们甚至不知道它的马尔科夫秩。

在这种情况下，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=":3" />的文章中提供了一种寻找最优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" />的文章中提供了一种寻找最优partition的方法。通过此方法我们能找到最优的partition，代入这个partition我们就能通过上面的充分必要条件来决定一个马尔科夫矩阵是否lumpable。具体步骤如下：

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

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