更改

除了对向量以及高维动力学的降维之外，[[马尔科夫链的简化]]（Lumping Markov Chain）也和因果涌现有着重要的联系。马尔可夫过程的模型约简<ref>Zhang A, Wang M. Spectral state compression of markov processes[J]. IEEE transactions on information theory, 2019, 66(5): 3202-3231.</ref>是状态转移系统建模中的一个重要问题。和因果涌现中的粗粒化相似，马尔科夫链的简化主要也是通过将多个状态合并成一个状态来降低马尔科夫链链的复杂度。该过程主要是通过识别一些状态的组合，使得合并后的系统仍然保留马尔科夫性质。

除了对向量以及高维动力学的降维之外，[[马尔科夫链的简化]]（Lumping Markov Chain）也和因果涌现有着重要的联系。马尔可夫过程的模型约简<ref>Zhang A, Wang M. Spectral state compression of markov processes[J]. IEEE transactions on information theory, 2019, 66(5): 3202-3231.</ref>是状态转移系统建模中的一个重要问题。和因果涌现中的粗粒化相似，马尔科夫链的简化主要也是通过将多个状态合并成一个状态来降低马尔科夫链链的复杂度。该过程主要是通过识别一些状态的组合，使得合并后的系统仍然保留马尔科夫性质。

从底层的理论角度，有限马尔可夫链的状态简化可以视为马尔科夫状态转移矩阵的一种特殊分解<ref>Barreto A M S, Fragoso M D. Lumping the states of a finite Markov chain through stochastic factorization[J]. IFAC Proceedings Volumes, 2011, 44(1): 4206-4211.</ref>，该分解称为随机因子分解。较小的马尔可夫链与原始模型具有相同的可约性<ref name=":16" />和相同的闭集数，两条链的平稳分布通过线性变换相关联。通过奇异值谱分析，可以通过马尔可夫过程的秩和特征，来描述它的可表示性、聚集性和集总性等性质。反之，也可以用谱方法来估计低秩马尔可夫模型的转移矩阵，估计马尔可夫特征跨越的前导子空间，并恢复状态空间的状态聚合和可分块划分等潜在结构。而奇异值谱的分布，反应的集总性和可逆性的概念起着核心作用<ref>Marin A, Rossi S. On the relations between lumpability and reversibility[C]//2014 IEEE 22nd International Symposium on Modelling, Analysis & Simulation of Computer and Telecommunication Systems. IEEE, 2014: 427-432.</ref>，反过来，马尔科夫过程的近似动力学可逆性，和有效信息与因果涌现也有着重要联系<ref name=":2"/><ref>F. Kelly, Reversibility and stochastic networks. New York: Wiley, 1979.</ref>。在约简的过程中，如果能巧妙地选择要合并的状态，使得合并后的转移矩阵保留了原始转移矩阵的主要奇异值（尤其是最大奇异值或靠前的几个奇异值），则可以认为新的链很好地近似了原始链的主要动力学特征。而对聚合方案的最优化策略<ref>P. Buchholz, Exact and ordinary lumpability in finite Markov chains, J. Appl. Probab. 31 (1994) 59–75.</ref><ref>Derisavi S, Hermanns H, Sanders W H. Optimal state-space lumping in Markov chains[J]. Information processing letters, 2003, 87(6): 309-315.</ref>，和因果涌现的最优化都会受可逆性影响。

'''给定一个state partition <math>A=\{A_1, A_2, ... ,A_r\}</math>'''，我们能够用下列公式描述一个粗粒化后的马尔科夫链(lumped process)，且这个转移概率对任何初始状态(starting vector) <math> \pi </math> 都是一样的：{{NumBlk|:|

<math>

&Pr_{\pi}[f_1 \in A_j | f_0 \in A_i] \\

&Pr_{\pi}[f_n \in A_t |f_{n-1} \in A_s, f_1 \in A_j, f_0 \in A_i]

</math>

|{{EquationRef|3}}}}这个概念最早出现在Kemeny, Snell在1969年的Finiteains<ref name=":32">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>中。书中的定义是这样的：'''给定一个state partition <math>A=\{A_1, A_2, ... ,A_r\}</math>'''，我们能够用下列公式描述一个粗粒化后的马尔科夫链(lumped process)，且这个转移概率对任何初始状态(starting vector) <math> \pi </math> 都是一样的：

如果我们要对马尔科夫链进行约简，首先就要对其状态进行聚类，而这种操作的重要前提就是马尔科夫链是否可约<ref name=":16">Gebali F, Gebali F. Reducible Markov Chains[J]. Analysis of Computer Networks, 2015: 157-189.</ref>。可约马尔可夫链描述的系统具有特定状态，一旦系统访问了其中一种状态，就无法访问其他状态。但如果从任何状态开始，系统都能够直接、一步或间接地通过一个或多个中间状态到达图中的任何其他状态，这样的马尔可夫链就称为不可约马尔可夫链（irreducible Markov Chain）。在可以长时间运行的系统中，我们会遇到不可约马尔可夫链，对马尔科夫概率转移矩阵实施粗粒化的方法，其实就利用了马尔科夫链的可约性与不可约性。关于具体的粗粒化马尔科夫链的方法，请参考[[马尔科夫链的粗粒化]]。

马尔科夫链的粗粒化不仅要对状态空间做，也要对转移矩阵和概率空间做。这三个部分可以同时做，也可以看作为：先对状态空间做，再对转移矩阵和概率空间做；即先对状态做分组，然后再获取对应的粗粒化后的转移矩阵。我们也提到过对状态空间做粗粒化有Hard Partitioning和Soft Partitioning两种。Soft Partitioning可以看作把微观状态打散重构成了一些宏观状态，而Hard Partitioning则是更严格的，把若干个微观状态分成一个组。而Lumpability就是一个指标，用来评价‘对于某一种Hard Partitioning的微观状态分组分案，是否对微观状态转移矩阵lumpable’。不管状态空间按照哪一个Hard Partitioning方案做分类，它都有对应后续的对转移矩阵和概率空间的粗粒化方案（，并满足上面提到的粗粒化的两个规则。但是，其中的某些分组方案lumpable，也有某些分组方案non-lumpable。

 

 

关于具体的粗粒化马尔科夫链的方法，请参考[[马尔科夫链的粗粒化]]。

==参考文献==

==参考文献==