更改

马尔科夫链的粗粒化 (查看源代码)

2024年9月18日 (三) 16:49的版本

添加110字节、 2024年9月18日 (星期三)

无编辑摘要

第110行：第110行：

Lumpability是一种对分类的衡量，笔者暂时还没找到一个正式的中文翻译。

−

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

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

−

+

{{NumBlk|:|

<math>

\begin{aligned}

第122行：第122行：

\end{aligned}

</math>

+

|{{EquationRef|3}}}}

第137行：第138行：

\end{aligned}

</math>

−

|{{EquationRef|3}}}}

+

|{{EquationRef|4}}}}

这个公式表达的是，群组<math>A_i</math>到群组<math>A_j</math>的转移概率 = 群组<math>A_i</math>中任意状态<math>s_k</math>到群组<math>A_j</math>的转移概率 = 群组<math>i</math>中任意状态<math>s_k</math>到群组<math>A_j</math>中的状态的转移概率的和。

第146行：第147行：

所以，lumpability并不是一个马尔科夫链的特质，而是对马尔科夫链的某个state partition的特质。我们不能直接说某个马尔科夫链是lumpable或non-lumpable，但是我们可以说，对于某个马尔科夫链的某几个状态partition是lumpable或non-lumpable。

−

第176行：第176行：

#Hard Partitioning，即存在分组矩阵<math>V_{i, j} = 1\ if\ s_i \in s_j'\ and\ 0\ otherwise</math>；

#<math>V</math>是一个lumpable分组。

−

第222行：第221行：

\end{aligned}

</math>

−

第239行：第237行：

第2组的状态4到第1组的状态1，<math>p_{s_4 A_1} = \sum_{s_m \in A_1} p_{s_4 s_m} = p_{s_4 s_1} + p_{s_4 s_2} = 0.1 \times 2 = 0.2 </math>

−

这里我们就能看到，<math>p_{s_3 A_1} \neq p_{s_4 A_1}</math>，当同一组的两个状态<math>s_3</math>和<math>s_4</math>对其他组的转移概率不一样的话，如果我们强行按照这样来分组（也没办法强行，因为我们不知道<math>p_{A_2 A_1} = p_{s_3 A_1}</math>还是<math>p_{A_2 A_1} = p_{s_4 A_1}</math>），假设<math>p_{A_2 A_1} = 0.6</math>~~，我们会发现这样的粗粒化结果违背了一开始的定义，即粗粒化后的~~'''转移概率对所有的初始微观状态<math>\pi</math>都适用'''。因为当<math>\pi = s_4</math>的时候，<math>p_{A_2 A_1} = 0.6</math>这个转移概率就是错的，即使<math>\pi \neq s_4</math>~~，任何初始微观状态都会在某时刻达到~~<math>s_4</math>并导致转移概率出错。

+

这里我们就能看到，<math>p_{s_3 A_1} \neq p_{s_4 A_1}</math>，当同一组的两个状态<math>s_3</math>和<math>s_4</math>对其他组的转移概率不一样的话，如果我们强行按照这样来分组（也没办法强行，因为我们不知道<math>p_{A_2 A_1} = p_{s_3 A_1}</math>还是<math>p_{A_2 A_1} = p_{s_4 A_1}</math>），假设<math>p_{A_2 A_1} = 0.6</math>，我们会发现这样的粗粒化结果违背了Lumpability一开始的定义<ref name=":3" />（公式(3)），即粗粒化后的'''转移概率对所有的初始微观状态<math>\pi</math>都适用'''。因为当<math>\pi = s_4</math>的时候，<math>p_{A_2 A_1} = 0.6</math>这个转移概率就是错的，即使<math>\pi \neq s_4</math>，任何初始微观状态<math>\pi</math>都会在某时刻<math>n</math>达到<math>s_4</math>并导致转移概率出错。

第270行：第268行：

\end{aligned}

</math>

−

第277行：第274行：

[[文件:Lump fig1.png|缩略图|398x398像素|图2：Zhang<ref name=":0" /> 文章中的示意图。图中左面四个矩阵都是lumpable马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0|替代=]]

−

由上面的lumpability公式(3)和例子中我们能获得一个直观上的说法：当马尔科夫矩阵存在block结构，或者状态明显可被分成几类的时候，根据这样的partition，该矩阵就会lumpable，如图2中的<math>\bar{P}</math>所示，把相同的状态（行向量）分成一类的partition显然lumpable。

+

由上面的lumpability公式(4)和例子中我们能获得一个直观上的说法：当马尔科夫矩阵存在block结构，或者状态明显可被分成几类的时候，根据这样的partition，该矩阵就会lumpable，如图2中的<math>\bar{P}</math>所示，把相同的状态（行向量）分成一类的partition显然lumpable。

但是，有时候有些lumpable的矩阵的状态排序被打乱了（如图一中的<math>P_1</math>），或者矩阵包含了如<math>P_2</math>的噪声（如图2中的<math>P</math>，<math>P = P_1 + P_2</math>，<math>P_1^TP_2 = 0</math>）。

第286行：第283行：

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

−

# 获取r<n 的马尔科夫秩，或指定一个r；

+

#获取r<n 的马尔科夫秩，或指定一个r；

#对P进行SVD分解，<math>P = U \Sigma V^T</math>，其中U为左奇异向量，V为右奇异向量。

#通过下列公式得到最优partition <math>\Omega_1, \Omega_2, ... , \Omega_r</math>

Liangjh

97

个编辑