97
个编辑
更改
无编辑摘要
马尔科夫链的粗粒化可以分成Hard partitioning和Soft partitioning。Hard partitioning是指把若干个微观状态分成一个宏观状态类，且一个微观状态不能同时属于多个宏观状态类，而soft partitioning则会有可能出现这种情况。
马尔科夫链的粗粒化可以分成Hard partitioning和Soft partitioning。Hard partitioning是指把若干个微观状态分成一个宏观状态类，且一个微观状态不能同时属于多个宏观状态类，而soft partitioning则会有可能出现这种情况。
我们这里主要讨论hard partitioning，主要参考的是Anru Zhang and Mengdi Wang的Spectral State Compression of Markov Processes。
我们这里主要讨论hard partitioning，主要参考的是Anru Zhang和Mengdi Wang的Spectral State Compression of Markov Processes<ref name=":0">Zhang, Anru, and Mengdi Wang. "Spectral state compression of markov processes." ''IEEE transactions on information theory'' 66.5 (2019): 3202-3231.</ref>。
首先讨论的是一个马尔科夫矩阵的rank秩。
首先讨论的是一个马尔科夫矩阵的rank秩。
Pr_{\pi}[f_1 \in A_j | f_0 \in A_i]
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_0 \in A_i]
Pr_{\pi}[f_n \in A_t |f_{n-1} \in A_s f_0 \in A_i]
[math]
[/math]
[[文件:Lump fig1.png|缩略图|398x398像素|图1：Zhang<ref name=":0" /> 文章中的示意图。图中左面四个矩阵都是lumpable马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0]]
作者提出了判断一个马尔科夫链对给定partition [math]A=\{A1, A2, ... ,Ar\}[/math]是否lumpable的充分必要条件为
对于任意一对[math]A_i, A_j[/math]，每一个属于[math]A_i[/math]的状态[math]s_k[/math]的[math]p_{kA_j}[/math]都是一样的。
对于任意一对[math]A_i, A_j[/math]，每一个属于[math]A_i[/math]的状态[math]s_k[/math]的[math]p_{kA_j}[/math]都是一样的。
也就是说[math]p_{k A_j} = \sum_{s_m \in A_j} p_{k m} = p_{A_i A_j} = p_{k A_j}, k \in A_i[/math]
也就是说[math]p_{k A_j} = \sum_{s_m \in A_j} p_{k m} = p_{A_i A_j} = p_{k A_j}, k \in A_i[/math]
直观上来说，当马尔科夫矩阵存在block结构，或者状态明显可被分成几种partition的时候，该矩阵就会lumpable，如图一中的[math]\bar{P}[/math]所示。
但是，有时候有些lumpable的矩阵的状态排序被打乱了（如图一中的[math]P_1[/math]），或者矩阵包含了如[math]P_2[/math]的噪声（如图一中的[math]P[/math]，[math]P = P_1 + P_2, P_1^TP_2 = 0[/math]）。
我们在实际问题中很多时候要面对的是像[math]P[/math]这样的矩阵，我们既无法确定它是否lumpable，也无法决定它的partition，我们甚至不知道它的马尔科夫秩。
在这种情况下，Anru Zhang<ref name=":0" />的文章中提供了一种寻找最优partition的方法，通过此方法我们能找到最优的partition，代入这个partition我们就能通过上面的充分必要条件来决定一个马尔科夫矩阵是否lumpable。具体步骤如下：
#先获取一个n*n维的马尔科夫矩阵P，或者是马尔科夫链的频率采样；
#获取r<n 的马尔科夫秩，或指定一个r；
#对P进行SVD分解，[math]P = U \Sigma V^T[/math]，其中U为左奇异向量，V为右奇异向量。
#<br />
（未完待续）
（未完待续）
<references />