更改

[[马尔科夫链]]是一类特殊的随机过程，在给定当前状态下，对于未来状态的预测便不再依赖于过去状态。它可以看作一个n维的状态的序列<math>s^{(t)}\ = \{1, ..., n\}^{(t)}</math>，每一步的状态转换都有马尔科夫矩阵（满足每一行和为1的条件的方阵）<math>P</math> 决定，即<math>p(s^{(t+1)}) = p(s^{(t)}) P</math>。<math>P</math> 的每一行对应的每个状态转移到其他状态的概率，即 <math>p_{ij} = p(s^{(t+1)} = j | s^{(t)} = i)</math>。比如，当 <math>s^{(t)}</math> 等于第一个状态的时候，<math>P</math> 的第一行展示了 <math>s^{(t+1)}</math> 状态的概率。

[[马尔科夫链]]是一类特殊的随机过程，在给定当前状态下，对于未来状态的预测便不再依赖于过去状态。它可以看作一个 n 维的状态的序列<math>s^{(t)}\ = \{1, ..., n\}^{(t)}</math>，每一步的状态转换都有马尔科夫矩阵（满足每一行和为1的条件的方阵）<math>P</math> 决定，即 <math>p(s^{(t+1)}) = p(s^{(t)}) P</math>。<math>P</math> 的每一行对应的每个状态转移到其他状态的概率，<math>p_{ij} = p(s^{(t+1)} = j | s^{(t)} = i)</math>。比如，当 <math>s^{(t)}</math> 等于第一个状态的时候，<math>P</math> 的第一行展示了 <math>s^{(t+1)}</math> 状态的概率。

对马尔科夫链做粗粒化的意义是什么呢？我们看到文献中着重强调这三点：

对马尔科夫链做粗粒化的意义是什么呢？我们看到文献中着重强调这三点：

#我们在研究一个超大的系统的时候，比如复杂城市系统时，并不会关注每一个微观的状态，在粗粒化中我们希望能过滤掉一些我们不感兴趣的噪声和异质性，而从微观尺度中总结一些中尺度或宏观尺度的规律；

 

#有些状态的转移概率非常相似，所以可以被看成同一类状态，对这种马尔科夫链做partitioning可以减少系统表示的冗余性；

# 我们在研究一个超大的系统的时候，比如复杂城市系统时，并不会关注每一个微观的状态，在粗粒化中我们希望能过滤掉一些我们不感兴趣的噪声和异质性，而从微观尺度中总结一些中尺度或宏观尺度的规律；

#在用到马尔科夫决策过程的强化学习里，对马尔科夫链做粗粒化可以减少状态空间的大小，提高训练过程的样本效率和任务表现。<ref name=":10">Hafner, Danijar, et al. "Mastering atari with discrete world models." arXiv preprint arXiv:2010.02193 (2020).</ref>

# 有些状态的转移概率非常相似，所以可以被看成同一类状态。对这些状态进行划分和归并可以减少马尔科夫链的冗余性，得到一个更简洁有效的系统表示；

# 在用到马尔科夫决策过程的强化学习里，对马尔科夫链做粗粒化可以减少状态空间的大小，提高训练过程的样本效率和任务表现<ref name=":10">Hafner, Danijar, et al. "Mastering atari with discrete world models." arXiv preprint arXiv:2010.02193 (2020).</ref>。

在粗粒化过程中，我们有很多目标。

在粗粒化过程中，我们有很多目标。

# 首先，我们想尽量降低压缩后的动力学维度；

 

# 其次，我们想在压缩过程中尽量保留动力学中的信息；

# 首先，我们想尽量'''降低'''动力学在压缩后的'''维度'''；

# 最后，我们想要压缩后的过程和原本的过程尽量保持一致。

# 其次，我们想在压缩过程中'''尽量'''保留动力学中的'''信息'''；

# 最后，我们希望压缩后的过程和原本的过程尽量'''保持一致'''。

在这篇文章里，我们会围绕着这三个维度展开讨论，并介绍一系列针对马尔科夫链的粗粒化方法。

在这篇文章里，我们会围绕着这三个维度展开讨论，并介绍一系列针对马尔科夫链的粗粒化方法。

马尔科夫链不只是一个马尔科夫矩阵那么简单，还涉及到了不同的状态，也会有状态之间的转移概率，所以我们可以从不同的角度来看待粗粒化：

马尔科夫链不只是一个马尔科夫矩阵那么简单，还涉及到了不同的状态，也会有状态之间的转移概率，所以我们可以从不同的角度来看待粗粒化：

#对马尔科夫矩阵做粗粒化：在看待一个方阵时，我们可以把它想象成一个网络的邻接矩阵。节点为状态，连边为状态转移概率，状态转移的过程为一个粒子在节点间跳转，而粗粒化则是对这个网络做降维。

# 对马尔科夫矩阵做粗粒化：在看待一个方阵时，我们可以把它想象成一个网络的邻接矩阵。节点为状态，连边为状态转移概率，状态转移的过程为一个粒子在节点间跳转，而粗粒化则是对这个网络做降维。

#对状态空间做粗粒化：我们这里讨论的是离散状态的马尔科夫链，状态空间的大小等于马尔科夫链的大小。粗粒化可以看作对状态空间做分组并投影到新的状态空间。

# 对状态空间做粗粒化：我们这里讨论的是离散状态的马尔科夫链，状态空间的大小等于马尔科夫链的大小。粗粒化可以看作对状态空间做分组并投影到新的状态空间。

#对概率空间做粗粒化：从概率论出发，把状态的发生看作事件，通过计算事件发生的频率来构建概率空间。在降维表达事件的同时也构建了新的概率空间。

# 对概率空间做粗粒化：从概率论出发，把状态的发生看作事件，通过计算事件发生的频率来构建概率空间。在降维表达事件的同时也构建了新的概率空间。

这三种出发点看似互有联系，但是具体关心的东西不同。第一种关注状态之间的连边拓扑结构，第二种关注不同状态的历史分布和相似性，第三种关注如何降维表达整个系统中的事件概率分布。

这三种出发点看似互有联系，但是具体关心的东西不同。第一种关注状态之间的连边拓扑结构，第二种关注不同状态的历史分布和相似性，第三种关注如何降维表达整个系统中的事件概率分布。

对马尔科夫链做粗粒化并没有一个统一的定义，目前该题目也没有一个完整的文献综述。在许多文献中，粗粒化coarse-graining，聚类/聚合partitioning/lumping/clustering/aggregation和降维dimension reduction是重叠等价的。

对马尔科夫链做粗粒化并没有一个统一的定义，目前该题目也没有一个完整的文献综述。在许多文献中，粗粒化（coarse-graining）、聚类/聚合（partitioning/lumping/clustering/aggregation）和降维（dimension reduction）是重叠等价的。

本词条只讨论离散时间马尔科夫链，且动力学<math>P</math>是时齐（不随时间变化）的，不讨论连续马尔科夫过程。我们可以定义微观状态空间为<math>S=\{s_1, s_2, ... ,s_n\}</math>，微观转移函数<math>P \in \mathcal{R}_{n \times n}</math>是一个大小为n的马尔科夫矩阵。同样的，粗粒化后的宏观状态空间为<math>S'=\{s'_1, s'_2, ... ,s'_r\}</math>，宏观转移函数<math>P' \in \mathcal{R}_{r \times r}</math>。

本词条只讨论离散时间马尔科夫链，且动力学 <math>P</math> 是时齐（不随时间变化）的，不讨论连续马尔科夫过程。我们可以定义微观状态空间为<math>S=\{s_1, s_2, ... ,s_n\}</math>，微观转移函数<math>P \in \mathcal{R}_{n \times n}</math>是一个大小为 n 的马尔科夫矩阵。同样的，粗粒化后的宏观状态空间为<math>S'=\{s'_1, s'_2, ... ,s'_r\}</math>，宏观转移函数<math>P' \in \mathcal{R}_{r \times r}</math>。

多数文献中会出现如图1的定义<ref name=":2">Coarse graining. ''Encyclopedia of Mathematics.'' URL: <nowiki>http://encyclopediaofmath.org/index.php?title=Coarse_graining&oldid=16170</nowiki></ref>：

多数文献中会出现如图1的定义<ref name=":2">Coarse graining. ''Encyclopedia of Mathematics.'' URL: <nowiki>http://encyclopediaofmath.org/index.php?title=Coarse_graining&oldid=16170</nowiki></ref>：