【随机过程2】马尔可夫过程2 | 状态空间

6.4 状态空间的分解

定义：设 \(A\subset S\)，若对任意 \(i\in A\) 及 \(j\notin A\)，都有 \(p_{ij}=0\)，称 \(A\) 为闭集。若 \(A\) 的状态是相通的，则 \(A\) 为不可约的。

引理 6.1：\(A\) 为闭集的充要条件为：任意 \(i\in A\) 及 \(j\notin A\) 都有 \(p_{ij}^{(n)}=0,n\ge1\)。

推论：若 \(A\) 是闭集，对任意状态 \(i\in A\) 恒有 \(\sum_{j\in A}p_{ij}^{(n)}=1\)。

定理 6.5：所有常返态构成一个闭集。

推论：不可约马尔科夫链，所有状态都是常返的，或者所有状态都是非常返的。

定理 6.6：状态空间 \(S\) 可以分解为 \(S = T\cup C = T\cup C_1 \cdots \cup C_h \cdots\)，其中 \(T\) 表示非常返状态的集合，\(C_i\) 为基本的常返闭集，且有

1. 对任一确定的 \(k,C_k\) 中任意两个状态互通；
2. \(C_k\cap C_l = \varnothing,\forall h\ne l\)。

定理 6.7：有限状态马尔科夫链具有如下性质：

1. 状态空间 \(S\) 可分解为 \(S = T\cup C = T\cup C_1 \cdots \cup C_h\)，其中 \(T\) 表示非常返状态的集合，\(C_i\) 为基本的常返闭集；
2. 非常返状态集合 \(T\) 一定不是闭集；
3. 没有零常返状态；
4. 必有正常返状态；
5. 不可约马氏链的的状态都是正常返态；
6. 任意闭集 \(C_i\) 上的 \(n\) 步转移矩阵为随机矩阵。

6.5 极限特性与平稳分布

6.5.1 极限特性

定理 6.7：若状态 \(j\) 为非常返态或零常返态，则对任意 \(i \in S\)，有 \(\lim_{n\to\infty}p_{ij}^{(n)}=0\)。

推论 6.7.1：若马尔科夫链有一个零常返态，则必有无穷多个零常返态。

6.5.2 平稳分布

定义：一个定义在 \(S\) 上的概率分布 \(\pi=(\pi_1,\pi_2,...,\pi_i,...)\) 称为马尔科夫链的平稳分布，如果有 \(\pi=\pi P\)。

定理 6.9：若马尔科夫链是不可约的遍历链，则 \(\{\pi_i = 1 / \mu_i\}\) 是 \(\pi=\pi P(\pi_i\ge0,\sum_{i\in S}\pi_i=1)\) 的唯一解。

推论 6.9.1：不可约遍历链恒有唯一的平稳分布，且 \(\pi_j=\lim_{n\to\infty} p_{ij}^{(n)}\)。

定理 6.10：令 \(C_+\) 为马尔科夫链中全体正常返状态构成的集合，则有

1. 平稳分布不存在的充要条件为 \(C_+=\varnothing\)；
2. 平稳分布唯一存在的充要条件为只有一个基本正常返闭集；
3. 若马尔科夫链有多于一个基本正常返闭集，则其平稳分布有无穷多个。

定理 6.11：关于有限状态的马尔科夫链

1. 有限状态马尔科夫链的平稳分布总存在；
2. 有限不可约非周期的马尔科夫链存在唯一的平稳分布；
3. 若有多于一个基本正常返闭集，则其平稳分布有无穷多个；

栗子（平衡方程及其应用）：对非周期正常返的离散马氏链，平稳分布存在且满足 \(\pi P=\pi\)，可以写成 \(\pi_j(1-P_{jj}) = \sum_{i\ne j,i\in S} \pi_i P_{ij}\)，这被称为离散马氏链的平衡方程。左边表示从状态 \(j\) 流出的量，右边表示从其他状态流入状态 \(j\) 的量，在讨论一些实际工程问题时，可以借助平衡方程求解系统平稳分布。

6.6 转移矩阵的平均极限

一般情况下，\(n\to\infty\) 时 \(P^n\) 的极限未必存在，主要是因为 \(P^n\) 可能有周期性。为了消除周期性，最直接的方法就是取平均。

定理 6.12：设 \(P\) 为有限马氏链的转移矩阵，则 \(L:=\lim_{n\to\infty} \frac{1}{n}(I+P+\cdots+P^{n-1})\) 存在，且满足 \(LP = PL = L = L^2\)。

推论：设有限不可约马氏链的转移矩阵为 \(P\)，平稳分布为 \(\pi\)，\(L=(l_{ij})=\lim_{n\to\infty} \frac{1}{n}(I+P+\cdots+P^{n-1})\)，则 \(\pi L=\pi\)，且 \(\pi_j=l_{ij} / \sum_{k=1}^N l_{ik}\)。

定理 6.13：设 \(P\) 是有 \(m\) 个状态的不可约马氏链的转移矩阵，则平稳分布概率为

\(\pi = (1,...,1)(I-P+{\mathbb 1})^{-1}\)，其中 \({\mathbb 1}\) 为全 1 的 \(m\times m\) 矩阵。

证明：关键是要证明矩阵 \((I-P+{\mathbb 1})\) 可逆。

Note：马尔科夫链在随机过程里面是比较简单的部分，大部分结论都很直观，凭直观感觉就能得到。

实际上这章马尔科夫链的主要内容就是在讨论几种状态：非常返态、正常返态、零常返态。归结起来，现在想象一个马尔可夫链的状态转移图，有很多节点（状态）和有向边（转移概率）。

首先对于几种状态的区别：

1. 正常返态就是说从一个状态开始，经过有限步总能再次回到当前状态，并且这个平均回转时间是有限的（中华好男人，常回家看看）；
2. 零常返态就是说从一个状态开始，经过有限步总能再次回到当前状态，但这个平均回转时间是无穷的（渣男海王，开空头支票）；
3. 非常返态就是说从一个状态开始，经过有限步之后就再也不能返回当前状态了（恩断义绝）；

如何判断每个节点的状态类型，基本只需要下面两条原则：

1. 如果两个状态相通，那么他们同为常返态或非常返态。
   1. 那么如果两个节点之间有双向边，他们一定是同一类型态；要出现常返态和非常返态的区别一定是由于单向边的存在；
   2. 进一步的，一个连通子图里面的所有状态一定是同一类型；要出现常返态和非常返态的区别，一定是两个连通子图 \(A,B\) 之间只有单向边；
   3. 假如只有 \(A\) 到 \(B\) 的单向边，那么连通子图 \(B\) 中的节点一定都是非常返态。
2. 零常返态只可能出现在状态个数为无穷的时候。

极限分布/平稳分布是怎样：

1. 极限分布与初始分布有关，平稳分布只与状态转移链本身的性质有关；
2. 由于最终一定会收敛到常返态，平稳分布一定是只对常返态非零；
3. 只考虑常返态的集合，平稳分布就是转移概率矩阵 \(P\) 的左特征向量；

下面讲个故事。

把概率想象成手里的money，初始分布概率就是每个节点手里的本钱；一个（不可约的）连通子图就是一个家族，家族里的每个人之间可以相互借钱来回周转；不同连通子图就是不同的家族。

（不可约的）连通子图内部，一个家族里面的钱再怎么周转也都是内部消化，每个人借出去的总能还回来，所以钱不会消失，总会有一个平衡。

如果有两个连通子图，并且它们之间只有单向边，相当于 \(A\) 总是把一部分 money 白送给 \(B\)，再厚的家底也得被掏空了。最后 \(A\) 家族就破产了（非常返态，不是闭集）。

如果 \(B\) 家族的钱只进不出，也就是没有向外的有向边（闭集），那么他们就会完成资本的积累，最终钱总会聚集到他们那里（常返态）。

如果有两个连通子图，他们相互之间没有任何边相联系，那就是他们互不打扰，两不相欠（各自有一个平稳分布）。100年之后各自有多少钱取决于现在各自有多少钱，不多不少（联合组成无穷个平稳分布，因为初始分布有无穷种情况）。