随机过程（2）——极限状态的平稳分布与周期（上），一些特殊的马尔科夫链

2021-08-10 11:31:17 浏览数 (1)

上一节笔记：随机过程（1）——引入，有限状态马尔科夫链，状态转移，常返与瞬时状态

———————————————————————————————————

大家好！

这一节我们接着上一节的内容，继续介绍与状态分类有关的一些内容。包括上一节最后，利用图来划分状态的方法的解释。以及在这基础上，我们也会对极限状态进行一些探讨。

那么我们开始吧。

目录

  • 闭集，不可约集
  • 极限下的平稳分布
  • 更加深层次的问题
    • 转移矩阵的极限状态（上）
  • 一些特殊的马尔科夫链

闭集，不可约集

这里的闭集（closed set）和不可约集（irreducible set）和集合论，优化，抽象代数等里面的用词可能有重复，但它们完全没有关系……这里的用词完全是为了描述状态之间可达性而使用的。

我们在上一节的最后给大家介绍了一个画图来划分状态的一个方法。但是为什么这可行呢？在这一节的开头，我们来给一个严格的解释。为此我们引入了闭集和不可约集的概念。

Definition 1: Closed Set 对于一个集合

A

，如果

forall i in A, j not in A

，都有

p(i, j) = 0

，那么称集合

A

是一个闭集。

这里的闭集就是直截了当的“闭”的含义，集合内所有的元素都“无法逃脱”。

Definition 2: Irreducible Set 对于一个集合

B

，如果满足

forall i, j in B

，都有

i leftrightarrow j

，那么就称集合

B

是不可约的。

有了这两个定义之后，还不足够来解决我们的问题，我们还需要一些引理以及一些评价描述。

Lemma 1: 如果

x

是一个常返状态，

x to y

，那么

y

也是一个常返状态。

在这之前我们先证明一个小结论。

Lemma 1-1:

E_x(N(y)) = sum_{n = 1}^infty p^n(x, y)

我们证明一下，首先不难得到

rho_{yy} = P_y(T_y < infty) = sum_{n = 1}^infty P_y(T_y = n)

另一方面，我们注意到

P_y(T_y = n) = sum_{x_i ne y}p(y, x_1)p(x_1, x_2)cdots p(x_{n - 1}, y)

同时，我们也会有

E_x(N(y)) = E_x(sum_{n = 1}^infty I(x_n = y)) = sum_{n = 1}^infty E_x(I(x_n = y)) = sum_{n = 1}^infty p^n(x, y)

同样的，这里我们用到了一个级数的交换顺序（主要是实分析的富比尼定理（Fubini））。不希望深究的记住这个就好。

好的，现在我们可以开始证明原引理了。

根据定义，我们可以得到

E_x(N(x)) = sum_{k = 1}^infty p^k(x, x) = infty

，另外还可以推出

y to x

，否则如果

x

跳到了

y

，却有

y not to x

，那么同样不符合常返的含义。

有了这两个性质，我们不难得到

exists j, l quad s.t. p^j(y, x) > 0, p^l(x, y) > 0

那么同样的，根据

x

常返，可以得到

exists k quad s.t. p^k(x, x) > 0

，那么这样的话，就会有

p^{j k l}(y, y) ge p^j(y, x) p^k(x, x) p^l(x, y)

还是那句话，这个不等式成立的原因是

y

再回到

y

，不仅仅只有

y to x to y

这一条路径。

有了这个式子之后，只需要两边对

k

求无穷和，就可以得到

y

是常返状态，这个最后一部分很简单，我们留给读者。

这个结论从直觉上来看也不难理解。无论什么时候，从

x

都有机会到达

y

，而根据

x

常返，

y

同时还有机会到达

x

，这个过程会一直反复下去。

Lemma 2: 在一个有限闭集中，至少有一个常返状态。

假如说任何一个状态都是瞬时状态。潜在的意思是

forall x, y in C ,E_x(N(y)) < infty

并且

C

是一个有限闭集。那么这个时候，我们可以得到

sum_{y in C} E_x N(y) = sum_{y in C} sum_{n = 1}^infty p^n(x, y) = sum_{n = 1}^infty sum_{y in C} p^n(x, y) = sum_{n = 1}^infty 1 = infty

注意，这里也有一个交换顺序。

事实上这里就有一些不对劲了。注意到

C

有限，每一个元素又碰巧是有限的，所以求和不可能是无穷，这就矛盾了。因此这个性质就证明完了。

这个引理的证明关键是对于“常返”的量化。也就是

N(y)

这个量。直观来看，这个引理也不难理解。一个有限的集合内，状态反复横跳，不可能跳了无限步之后，每一个状态返回的次数都是有限步的。这也是上面那个式子告诉我们的结论。

有了这两个引理，我们为什么就可以说明，之前画图的方式是正确的呢？不妨再看看上一节这张图。

我们注意到，首先有限集合内一定有一个常返分布。那么我们可以先找非常返的状态，也就是说找到

T = {x: x to y, y not to x, exists y}

也就是说找到状态

x

的集合，使得存在状态

y

，它可以到，但是从这个

y

没办法回到

x

。这些自然就是瞬时状态。

去掉这个之后，对于

x

来说，其实剩下的就是常返的了。所以我们可以取

S- T

（这里

S

就是状态空间）的一个元素

x

，再取

C_x = {y: x leftrightarrow y }

因为根据Lemma 1，所有与

x

可以互相到达的状态

y

都是常返状态。而接下来，如果

T C_x = S

，说明元素取完了。否则就没取完，就再在

S - T - C_x

中继续取元素，按照上面一致的思路就可以。

这个构造的思路用到了上面提到的两个引理（Lemma 2主要用在第二步，也就是说如果不存在常返状态，那自然不可能构造出

C_x

。），而大家感兴趣可以发现，事实上构造完也就是这一张图。

好的，这一方面的铺垫结束，就可以进入极限状态的讨论了。

极限下的平稳分布

从这里开始，我们关注平稳分布（stationary distribution）。顾名思义，平稳分布就是“平稳的”，随着时间的推移，不再受到随机过程的变化制约的分布。要推出平稳分布的定义，我们要先看看，分布从之前转移到之后，应该如何计算。

这个也不难，注意到

P(X_n = j) = sum_{i}P(X_{n - 1} = i)p(i, j)

这个是拿概率公式直接就能推出来的结果。但是更加重要的观察是，如果我们设

q

是一个行向量，其中

q_i = P(X_0 = i)

，那么可以得到

qP^n

就是第

n

步的分布结果，这里

P

是转移矩阵。也就是说

(qP^n)_i = P(X_n = i)

这是一个很重要的观察。有了这个观察，就可以理解平稳分布了。

Definition 3: Stationary Distribution 如果

qP = q

，那么称

q

是一个平稳分布，用

pi

表示。

这个式子就相当于说，如果我从

q

这个分布出发，无论如何转移，最终的分布依然是

q

。这当然就是“平稳”的含义。这里还有一个细节，就是因为

pi

是一个概率分布，所以我们额外要求

sum_{i} pi _i = 1

。

好的，来看一个简单的题目。

Problem 1: 考虑转移矩阵

P = begin{bmatrix}0.6 & 0.4 \ 0.2 & 0.8end{bmatrix}

，确定它的平稳分布。

事实上，我们只需要求解

pi P = pi

，辅佐

sum_i pi_i = 1

就可以。最终的结果为

pi = (frac 13, frac 23)

。

细心的读者应该可以观察到，没有额外的和约束，这个方程组并没有一个唯一解，因为矩阵不可能满秩（想想为什么？）。

但是反过来，为什么有了这个和的约束，就能够有满足条件的解呢？

Theorem 1: 设转移矩阵

P

不可约，大小为

k times k

，那么方程解唯一，并且可以保证

forall x, pi_x > 0

。

这里的矩阵不可约性是高代的概念，但在这里可以直接把它同“状态不可约“的概念划等号。

首先观察一下方程组，事实上可以把它写成

pi(P - I) = 0

，且

sum_{x} pi_x = 1

。那么注意到

r(P - I) le k - 1

，所以根据线性代数的知识，可以得到

exists v ne 0 quad s.t. vP = v

那么我们设

Q = (P I) / 2

，这里相当于我们构造了一条懒惰链（lazy chain）。因为

Q

的构造，实质上是让这个随机过程中，每一个状态有

frac 12

的概率在原地不动，另外

frac 12

才会按照

P

的标准去移动。

这样的话，因为

P

是不可约的，所以

forall x, y, x to y

。但是注意到，一个关键的思考在于，对于

Q

而言，从

x

到

y

，**一定存在一条经过

k - 1

步的路径**，从

x

到达

y

。具体可以看下图。

也就是说，对于

x to y

的一条给定的路径，我们可以通过“先去环，再懒惰”的步骤，保证我们的这个命题是成立的。换句话说，如果我设

R = Q^{k - 1}

，就一定可以得到

vR = v
forall x, y in S, r(x, y) > 0

如果没有

Q

的“懒惰性”，这一步是推不过来的。

接下来的推导就容易很多，首先，我们来证明

forall x in S, pi_x > 0

。

退而求其次，我们证明解的每一个元素都是同号的。现在我们假设这个解

v

不满足这个性质，那么会有

|v_y| = |sum_x v_x r(x, y) | < sum_x |v_x| r(x, y)

两边对

y

求和，就会导出矛盾。所以事实上都是同号的情况下，根据和为1，就可以得到非负。但是为什么它们又是恒正的呢？这是因为，首先向量的某一个元素一定是正数（否则全是0，和不可能为1）。不妨设为

v_x

，那么注意到

forall y , v_y = sum_x v_x r(x, y)

所以不难得到

v_y > 0

，因为

r(x, y) > 0

。所以这就证明完了这一个结论。

最后我们来看一下唯一性。如果这种情形下解不唯一，那么问题就大了。因为相当于有两个解，它们是正交的，满足同一个方程组。画画图很容易看出来，两个正交的解不可能都能够满足元素恒正，因此这个我们也证明完了。

这个证明的巧妙之处便是在于我们希望根据懒惰和不可约的概念，构造出一个性质很好的转移矩阵

R

，还是值得细细品味的。

在这个定理的最后，我们想直观的解释一下为什么

P

的不可约性如此重要。要说明这一点，我们要先用图来说明，究竟什么是“分布达到了平稳”。

注意到

pi P = pi

，事实上等价于这个式子

Lemma 3:

pi P = pi
Leftrightarrow sum_{y ne x} pi_y p(y, x) = sum_{x ne y} pi_x p(x, y)

为什么？首先注意到

pi P= pi

可以得到

forall y, sum_{x} pi_x p(x, y) = pi_y

把左边的式子中与

pi_y

有关的部分移项，可以得到

sum_{x ne y} pi_x p(x, y) = pi_y(1 - p(y, y)) = sum_{x ne y} pi_y p(y, x)

也就是我们的结论。简单来说，固定一个点

x

来看，我们会发现，这个性质的要求就是：从

x

点移出去的概率，等于从别的点移到

x

的概率，这当然不会使得

x

点所占有的概率

pi_x

发生改变，也就是平稳的一个形象解释。用图来描述就是这样的。

现在我们来看一下，如果没有不可约的条件，为什么就不唯一了。一个简单的例子就是，我们考虑两个有限闭集（如下图），那么我完全可以在两个集合的内部分别做一个刚才的概率转移。举个例子，对于这样的集合而言，假如说两个内部对应的平稳分布都是

pi' = (frac 12, frac 12)

，那么合在一起，这个分布就是

pi = (0, 0 , frac 12, frac 12)

，也可以是

pi= (frac12, frac12, 0, 0)

（相当于一个集合内做转移，另外一个集合内干脆让它们的概率直接归零，这在不可约集内是不可能发生的）。这就不是“唯一的”平稳分布了。

更加深层次的问题

极限状态下，其实还会有其他我们感兴趣的问题。平稳分布是否存在（注意，之前我们的定理并没有讨论存在性）？状态多久会被访问一次？这些问题的讨论都需要更加严格的定理来保证。

转移矩阵的极限状态（上）

我们希望先研究的是转移矩阵的极限状态。简单来说，对于一个状态

x

，我们希望讨论它到不同状态下的表现情况。也就是希望研究

p(x, cdot)

，也就是

P

中，

x

所在的那一行的情况。

从简单的情况来看，如果

x

所到达的状态

y

是一个瞬时状态，这没什么好说的，因为这个时候，我们根据瞬时状态的性质，可以得到

forall x, E_x(N(y)) = sum_{n = 1}^infty p^n (x, y) < infty

潜在意思是说，

p^n(x, y) to 0, forall x

，换句话说，如果

y

是瞬时的，那么极限状态下，从哪儿到达

y

的概率都会趋于0。

现在我们考虑状态

y

是常返状态的情况。事实上，我们在之前讨论过，一个有限的集合，在拆分出瞬时状态之后，就可以把它拆分成一个一个的有限不可约集，它们内部的所有状态都是常返的。所以我们其实研究某一个这样的有限不可约集就可以了。

讨论常返状态的极限情况，我们自然会先关注收敛性的问题。首先，对于某一个状态

x

，我们自然会有

p^n(x, cdot) = p^{n - 1}(x, cdot) P

它的极限如果存在，那么就回到了我们上面所提到的平稳分布。但是实际情况下，很多时候它的极限是不存在的，下面就是一个例子。

这代表随机过程会以

x to y to x to y

的形式一直走下去。也就是说无论经历了多少次，都不会有一个确定的状态。

但是对于这种情况，其实也并不是无迹可寻。比方说上面这个例子，虽然没有固定的某个平稳分布，但是每一个状态其实2轮就会被访问一次。这就引入了周期性（periodicity）的概念。

Definition 4: Period 定义状态的周期为集合

I_x = {n ge 1 : p^n(x, x) > 0}

元素的最大公约数。

直观来看，这个集合就是

x

有概率返回到

x

，要经过的转移次数的集合。比方说下面这一张图，可以看出，从左边走，回到

x

就需要3步，从右边走就需要4步。虽然左右两边各只有

frac 12

的概率，但是因为我们“有概率”通过3步和4步回到

x

，因此有

3 in I_x, 4 in I_x

。

关于集合

I_x

有一个很有意思的引理。

Lemma 4: 若

i, j in I_x

，那么

i jin I_x

用抽代的话来说，就是集合对加法运算封闭。证明也非常简单，注意到

p^i(x, x) > 0, p^j(x, x) > 0

，所以利用之前已经提到过好几次的思想，就可以得出

p^{i j}(x, x) > 0

。

接下来我们会关注周期性中的非周期（aperiodic）状态的情况，也就是所有状态的周期为1的情况。对于某个状态，如果它的周期为1，其实会诞生一些比较有趣的小结论，甚至会与初等数论有密切的联系。

Proposition 1: 如果状态

x

的周期为1，那么存在

n_0 in mathbb N^

，使得如果

n ge n_0

，那么

n in I_x

。

要说明这个，其实只需要说明，存在一个

k

，满足

k, k 1 in I_x

即可。我们先看一下为什么这样可以。首先我们可以根据这个，得到

2k, 2k 1, 2k 2 in I_x

，也就是说可以找到3个连续的数。然后根据这些，我们还可以得到

3k, 3k 1, 3k 2, 3k 3 in I_x

，也就是4个连续的数。

这个递推有什么作用呢？可以看出，这个推断下，如果不存在这样的一个

n_0

，那么不管从哪个时间点开始，经过最多

M

步，就会出现一个元素不在

I_x

内。但是事实上我可以根据上面的推断，让这个递推序列不断地进行下去，一定会有一个时刻生成

M 1

个连续的数，这就与我上面的论断矛盾了。

好的，我们现在回头来看，怎么构造出这样的

k

和

k 1

。首先，因为状态

x

非周期，所以只要有

{i_1, cdots, i_m} in I_x

，就一定会找到

c_1, cdots, c_m in mathbb Z

，使得

c_1i_1 cdots c_m i_m = 1

这是数论中著名的裴蜀（Bezout）定理。不知道的话没关系，后面也基本上用不上它。

那么现在只需要把

c_i

的符号区分一下，也就是说，设

a_k = c_k^ , b_k = c_k^-

，也就是说

a_k = max(c_k, 0)

，如果

c_k > 0

，

b_k = max(-c_k, 0)

，如果

c_k < 0

。这个时候可以得到

a_1i_1 cdots a_m i_m = 1 b_1i_1 cdots b_m i_m

根据封闭性，我们就找到了这样的

k

和

k 1

，所以这个命题也就证明完毕了。

下一个性质也比较有趣。

Proposition 2: 如果

x leftrightarrow y

，那么

x, y

具有相同的周期。

简单说一下，不妨设

x, y

的周期分别为

a, b

，并且不妨设

p^k(x, y) > 0, p^l(y, x) > 0

，同时我们取一个

n in I_y

，那么不难得到

k l in I_x, k l n in I_x

所以可以得到

a | n

（这里表示

a

整除

n

，也就是说

n / a

是一个整数），又因为

n

是可以随便取的，所以可以得到

a | b

，因为

b

就是

I_y

里所有元素的最大公约数。

有了

a | b

就简单了，因为

I_x, I_y

是对称的，也就是说同样的思路可以推出

b | a

，所以就有

a = b

，也就证明完了。

按照正常的顺序来说，我们应该介绍一些极限状态下，转移方程的性态。但是这些定理的证明难度很大，过程很多，剩下的部分恐怕是不太够我写，所以我们会先搁置这一部分，讨论一些比较简单的内容。下一节再回头介绍这些。

一些特殊的马尔科夫链

这一部分我们会介绍一些具有特殊性质的马尔科夫链。在具备这些性质之后，有些时候会对一些计算产生不小的帮助。

首先是双随机链（doubly stochastic chains）。

Definition 4: Doubly Stochastic Chains 如果一条马尔科夫链的转移矩阵满足

sum_x p(x, y) = 1

，那么称它为双随机的。

如果转移矩阵满足这个，事实上我们可以非常容易的找到它的平稳分布。事实上，假如它的大小是

k times k

，那么它的平稳分布就是

pi_x = frac 1 k

，也即本身这个分布就是一个均匀分布。读者可以自己验证这个结果。

然后就是细致平衡条件（detailed balance condition）。

Definition 5: Detailed Balance Condition 如果分布满足

pi_x p(x, y) = pi_y p(y, x)

，那么称它满足细致平衡条件。

我们在之前讨论平稳分布的时候说过，平稳的含义就是所有从

x

离开的概率等于回到

x

的概率。那么对于细致平衡条件来说，这就相当于是“任意两个点之间相互转移的概率相等”，很明显是一个比平稳更强的条件。更具体地说，分布满足这个条件，就一定是平稳分布。

有了这个条件之后，比较方便的地方同样是计算平稳分布上。这里我们举一个例子。

Problem 1: 考虑转移矩阵

P = begin{bmatrix}0.5 & 0.5 & 0 & 0 \ 0.05 & 0.5 & 0.45 & 0 \ 0 & 0.1 & 0.5 & 0.4 \ 0 & 0 & 0.3 & 0.7end{bmatrix}

，状态为

0, 1, 2, 3

（从左到右，从上到下），求解它的平稳分布。

如果要直接计算，这个题是比较复杂的，毕竟是一个四元线性方程组。虽然我们不知道这个转移矩阵的平稳分布会不会满足细致平衡条件，但我们一般的做法是先假设满足，然后推导看能否给出一个结果。

我们设

pi_0 = x

，那么我们有

pi_0 p(0, 1) = pi_1 p(1, 0)

所以可以得到

pi_1 = 10x

，同样的我们可以得到

pi_2 = 45 x, pi_3 = 60x

，最后根据和为1，就可以得到最终的平稳分布为

pi = (frac 1 {116}, frac {10}{116}, frac{45}{116}, frac{60}{116})

读者事实上可以检验的是，它确实满足细致平衡条件。比方说读者可以验证

0

和

2

这两个状态时候满足这样的关系。不过换句话说，假如说

p(0, 2) = 0

，但是

p(2, 0) ne 0

，那么必然不可能满足细致平衡条件。所以可以通过这种方式来检查目前的转移矩阵，是否可以用简便方法计算平稳分布。

接下来我们讲一个实际问题，很多地方会描述成醉汉走路问题。

Problem 2: 考虑一个无向图，一个醉汉会在某个点，按照相同的概率沿着它的邻边走下一步。描述出这个问题的转移矩阵，并分析最后的平稳分布。

我们画一张无向图来演示一下。

可以看出，如果在点

0

，那么下一次到达

1, 2, 3

的概率就各自为

frac 13

。

我们容易写出这样的式子

p(u, v) = frac{A(u, v)}{d(u)}

其中

A(u, v) = 1

表示

u, v

之间连了一条边（同样有

A(v, u ) = 1

），

d(u)

表示

u

的度，也就是邻边数。

有了这个式子之后，我们也是一样，通过细致平衡条件来看是否可以推出平稳分布。首先可以得到

pi_u p(u, v) = pi_v p(v, u)

那么代入上面的式子，我们就可以得到

frac{pi_u}{pi_v} = frac{d(u)}{d(v)}

所以我们再标准化一下，其实不难得到

pi_u = frac{d(u)}{sum_u d(u)}

。换句话说，醉汉最终更有可能去向邻边多的区域。我们也可以合理推断，对于一个毫无自主意识的醉汉来说，它最有可能出现在路口多的位置，当然这个结论要严格说明是需要我们下一节介绍的，与极限状态有关的一些大定理的，这里我们先卖个关子。

最后我们再来提一下逆马尔科夫链（reversible Markov chain）。逆马尔科夫链不是一个额外的定义，而只是把原先的马尔科夫链倒过来看所产生的结果，事实上，我们的这个说法也暴露了说，这样得到的一条随机过程仍然是一条马尔科夫链。

Proposition 3: 考虑

{X_n}

为一条马尔科夫链，具备平稳分布

pi

，且假设起始分布就是平稳分布。设

Y_m = X_{n - m}, 0 le m le n

，那么

Y_m

依然是一个马尔科夫链，并且有

hat p(i, j) = P(Y_{m 1} = j|Y_m = i) = frac{pi(j) p(j , i)}{pi(i)}

用图来描述大概就是这样的。

虽然这里我们也就画到了

Y_m

，但其实有了状态和转移矩阵，这条随机过程就可以一直这么走下去。

我们证明一下这个结论。走定义，我们会有

P(Y_{m 1} = j |Y_m = i, ldots, Y_0 = i_0) = P(X_{n - m - 1} = j | X_{n - m} = i, X_{n - m 1} = i_{m - 1}, ldots, X_n = i_0)
= frac{P(X_{n - m - 1} = j)p(j, i) cancel{p(i, i_{m - 1}} ) cdots cancel{p(i_1, i_0)}}{P(X_{n - m} = i) cancel{p(i, i_{m - 1})} cdots, cancel{p(i_1, i_0)}}

所以我们就证明完了。

这里我们故意跳了一步，读者可以自己补充，其实就和上一节，证明多步转移的公式的时候，使用的是同样的思想。

最后，一个小的发现是，如果

{X_n}

满足细致平衡条件，那么就可以得到

hat p (i, j) = p(i, j)

。相当于这一条马尔科夫链，正着走反着走，它的转移矩阵是不变的。

好的，这就是一些特殊情况了。事实上还有一个马尔科夫链的应用场地就是计算统计中的Metropolis-Hastings算法。但因为它本质上并不是随机过程的内容，我们这里就暂时不提它了。

小结

本节我们主要关注了马尔科夫链的极限状态和一些具有特殊性质的马尔科夫链。具体来说，我们结束了对常返与瞬时状态的讨论，并且在更深的层次上讨论了不同情况下，马尔科夫链的极限状态的存在性与相关的分析。

在这一部分，我们将一部分较为重要，但证明繁杂的结论放到了之后说。所以下一节我们会补上这一部分，并且开始对马尔科夫链中的离出链进行介绍。

definition

0 人点赞