重温马尔科夫随机过程

2024-07-18 00:34| 来源: 网络整理| 查看: 265

Why is a Markov Chain important? It is important because of its stationary distribution.

马尔科夫链随机过程之所以如此重要，在于其平稳分布（stationary distribution），也即对它而言，它存在一个平稳分布。

1. 记号的说明

q(i,j)==q(j|i)==q(i→j) 表示一个转移矩阵为 Q 的马氏链，从状态 i转移到状态 j 的概率

2. 马氏性

Xn 标识时刻 n 的状态，关于马氏性的数学表达为：

P(Xn+1=k|Xn=kn,Xn−1=kn−1,…,X1=k1)=P(Xn+1=k|Xn=kn) 也就是状态转移的概率只依赖与 3. 定理一

如果一个非周期马氏链具有概率转移矩阵 P ，且它的任何两个状态都是连通的，则 limn→∞Pnij 存在且与 i 无关（也即矩阵 Pn 的每一行元素都相同），记 limn→∞Pnij=π(j) ，我们有：

limn→∞Pn=⎡⎣⎢⎢⎢⎢⎢⎢π(1)π(1)⋯π(1)⋯π(2)π(2)⋯π(2)⋯⋯⋯⋯⋯⋯π(j)π(j)⋯π(j)⋯⋯⋯⋯⋯⋯⎤⎦⎥⎥⎥⎥⎥⎥

π(j)=∑i=0∞π(i)Pij 也即 π=πP

π 是方程 π=πP 的唯一非负解其中， π=[π(1),π(2),⋯,π(j),⋯] ， ∑i=0nπ(i)=1 （符合概率上对分布的要求）， π 称为马氏链的平稳分布。

马氏链的任何两个状态是连通的含义是指存在一个 n ，使得矩阵 Pn 的任何一个元素的数值都大于0.

两个状态 i,j 连通并非是指 i 可以直接一步转移到 j （ Pij>0 ），而是指 i 可以通过有限的 n 步转移到达 j （Pnij>0）

我们用 Xi 表示马氏链上跳转第 i 步后所处的状态，如果 limn→∞Pnij=π(j)存在，我们试着来证明上述结论的第二个结论：

P(Xn+1=j)==∑i=0∞P(Xn=i)P(Xn+1=j|Xn=i)∑i=0∞P(Xn=i)Pij

上式两边取极限就得到： π(j)=∑i=0∞π(i)Pij

平稳分布的考察

我们先来看马氏链的一个具体的例子。社会学家经常把人按其经济状况分成三类：下层（lower-class）、中层（middle-class）、上层（upper-class），我们用1,2,3分别代表这三个阶层（对应于马氏链中环境下的三个状态）。如下图所示：

社会学家们统计研究发现，决定一个收入阶层的最为重要的因素是就是其父母的收入阶层。如果一个人的收入属于下层类别，那么他的孩子属于下层收入的概率是0.65，属于中层收入的概率是0.28，属于上层收入的概率是0.07，如上图（标识状态转移矩阵）的第一行所示。使用矩阵的表示方式，转移概率矩阵为：

P=⎡⎣⎢0.650.150.120.280.670.360.070.180.52⎤⎦⎥ 假设当前这一代人处在下层、中层、上层的人的比例是概率分布向量 π0=[π0(1),π0(2),π0(3)] ，则他们的子女的分布比例将是 π1=π0P ，他们的孙子代的分布比例将是 π2=π1P=π0P2 ，第 n 代子孙的收入比例将是 πn=π0Pn。假设初始概率分布为 π0=[0.21,0.68,0.11] ，我们可以使用如下的python程序，计算前 n 代人的分布状况： import numpy as np pi_0 = np.array([.21 ,.68, .11]) P = np.array([[.65, .28, .07], [.15, .67, .18], [.12, .36, .52]]) x = pi_0 pi_n = [x] for i in range(11): print('{:.3f} {:.3f} {:.3f}'.format(x[0], x[1], x[2])) x = np.dot(x, P) pi_n.append(x)

运行的结果如下：

0: 0.210 0.680 0.110 1: 0.252 0.554 0.194 2: 0.270 0.512 0.218 3: 0.278 0.497 0.225 4: 0.282 0.492 0.226 5: 0.284 0.490 0.226 6: 0.285 0.489 0.225 7: 0.286 0.489 0.225 8: 0.286 0.489 0.225 9: 0.286 0.489 0.225 10: 0.286 0.489 0.225 11: 0.286 0.489 0.225 12: 0.286 0.489 0.225

我们发现从7代人开始，这个分布就稳定不变了，等等，这背后的意义是什么，是阶级固化呀，数学能不fascinating吗。

再来验证 πP=π，

print(pi_n[-1]) # [ 0.28658731 0.48848854 0.22492415] print(np.dot(pi_n[-1], P)) # [ 0.28654593 0.48850446 0.22494961]

接着我们问，这是偶然的吗，也即跟初始分布密切相关的吗？我们换一个初始概率分布 π0=[0.75,0.15,0.1] 试试看，继续计算前 n 代人的分布状况如下：

0: 0.750 0.150 0.100 1: 0.522 0.346 0.132 2: 0.407 0.426 0.167 3: 0.349 0.459 0.192 4: 0.318 0.475 0.207 5: 0.303 0.482 0.215 6: 0.295 0.485 0.220 7: 0.291 0.487 0.222 8: 0.289 0.488 0.224 9: 0.288 0.488 0.224 10: 0.287 0.488 0.225 11: 0.287 0.488 0.225 12: 0.287 0.488 0.225 ....

从第10代开始也达到令人发指的平稳。更为神奇的是，两者给定的不不同初始概率分布，最终都收敛到概率分布 π=[0.286,0.489,0.225]，也即收敛的行为和初始概率分布 π0 无关，收敛行为主要是由概率转移矩阵 P 决定的。我们不妨计算一下 Pn（这里的 Pn 仍表示矩阵乘法，而非按位相乘）：

t = P for i in range(100): if i > 18: print(t) t = np.dot(t, P)

输出为：

[[ 0.28650174 0.48852144 0.22497682] [ 0.28650126 0.48852163 0.22497712] [ 0.28650118 0.48852166 0.22497717]] [[ 0.28650156 0.48852151 0.22497693] [ 0.28650132 0.4885216 0.22497708] [ 0.28650127 0.48852162 0.22497711]] [[ 0.28650147 0.48852154 0.22497698] [ 0.28650135 0.48852159 0.22497706] [ 0.28650132 0.4885216 0.22497708]] [[ 0.28650143 0.48852156 0.22497701] [ 0.28650136 0.48852159 0.22497705] [ 0.28650135 0.48852159 0.22497706]] ...

我们发现，当 n 足够大的时候，这个 Pn矩阵的每一行都是稳定地收敛到 π=[0.286,0.489,0.225] 这个概率分布。自然地，这个收敛现象并非是某一个马氏链所独有的，而是绝大多数马氏链的共同行为。

定理二（细致平稳条件，detailed balance condition）

如果非周期马氏链的转移矩阵 P 和分布 π(x)满足：

π(x)Pij=π(j)Pji 则 π(x) 是马氏链的平稳分布，上式被称为细致平稳条件（detailed balance condition）。

证明：由细致平稳条件的定义可知：

∑i=0∞π(i)Pij=∑i=0∞π(j)Pji=π(j)∑i=0∞Pji=π(j)⇒πP=π 故 π 是平稳分布。

【本文地址】

公司简介

联系我们