12-可数状态空间马尔可夫链一

回顾

设 是有限状态空间， 是转移矩阵。随机过程

称为马尔可夫链，如果

今天

现在令 为可数状态空间， 为转移矩阵。随机过程

仍称为马尔可夫链，如果

相关概念

• 平稳分布：

• 不可约性： 对任意 ，存在某个 ，使得

• 首次到达时间与首次返回时间： 对 ，定义

定义. 若状态 满足

则称 是常返的。否则，称 是暂留的。

注. 如果 有限且 不可约，则每个状态都是常返的。但是，当 只是可数时，会出现两种不同的情形：常返或暂留。

常返性

状态 是常返的，当且仅当

引理. 假设 不可约。定义格林函数

则下列四个条件等价：

1. 对某个 ，

2. 对所有 ，

3. 对某个 ，

4. 对所有 ，

常返性

状态 是常返的，当且仅当

假设 不可约，则下列两个条件等价：

1. 对某个 ，

2. 对所有 ，

因此，对一条不可约链，一个状态常返，当且仅当所有状态都常返。正因如此，不可约马尔可夫链可以分成两类：常返链和暂留链。

例.

• 上的简单随机游走是常返的；
• 上的简单随机游走是暂留的。

无限网络

设

是一个无限连通图，边电导为

固定源点 。

令

是一列包含源点 的有限连通子图，并满足

以及

包含 中两个端点都位于 的所有边。

对每个 ，构造一个修改后的网络 ：

• 将 中的所有顶点合并为一个顶点 ；
• 若 中的某个顶点与 相邻，则令它与 相邻；
• 对这样的顶点 ，定义

定义从 到无穷远的有效电阻为

引理. 上述定义是良定义的：极限存在，并且不依赖于子图序列 的选择。

有效电阻与逃逸概率

设

是一个无限连通图，边电导为

并固定源点 。回顾

定理.

证明. 对每个 ，有限网络中的逃逸概率公式给出

令 ，左侧事件递减到“从 出发后永不返回 ”这一事件，而右侧收敛到

所以

证毕。

有效电阻与流的能量

定义. 从 流向无穷远的流 ，是图 的边上的一个反对称函数，并满足

以及对所有 ，

流的强度定义为

流的能量定义为

其中求和遍历所有无向边。

定理.

推论. 假设 是一族两两不相交、并且将 与无穷远分离的边割集，则

无限网络上的随机游走

定理. 下列条件等价：

1. 网络上的随机游走是暂留的；
2. 存在 ，使得

3. 存在一个从 流向无穷远的流 ，使得

定理. 假设存在一族两两不相交、并且将 与无穷远分离的边割集 ，满足

则该网络上的随机游走是常返的。

上的简单随机游走

定理.

• 上的简单随机游走是常返的；
• 上的简单随机游走是常返的。

定理.

• 上的简单随机游走是暂留的；
• 当 时， 上的简单随机游走是暂留的。

正常返性

定义.

状态 是常返的，如果

状态 是正常返的，如果

引理. 假设 不可约。

下列两个条件等价：

1. 对某个 ，

2. 对所有 ，

下列两个条件也等价：

1. 对某个 ，

2. 对所有 ，

正常返性

定义. 如果

则称状态 是正常返的。

引理. 假设 不可约，则下列两个条件等价：

1. 对某个 ，

2. 对所有 ，

因此，对一条不可约链，一个状态正常返，当且仅当所有状态都正常返。正因如此，一条不可约常返马尔可夫链还可以分成两类：正常返链，以及另一类称为零常返链。

例. 上的简单随机游走是零常返的。

麻省理工学院开放式课程