动机
有限不可约马尔可夫(Markov)链总有平稳概率分布。同一句话放在可数无限状态空间却不成立。概率质量可以向任意遥远的状态漂移,不变权重的总和也可能无穷。甚至一条以概率一回到起点的链,其平均回返时间仍可以无穷。
无限最近邻游走把这些分别具体呈现出来。我们先使用上一节已证的有限边界计算,再说明极限事件为何正确。回返循环则把路径行为与平稳平衡联系起来。这些计算的价值,正是在于清楚展示有限状态结论需要哪些新假设才能延伸。
定义
定义 7.1.1
(击中时间与回返时间)
设 是可数状态空间 上的时齐马尔可夫链,转移概率为 ,并已指定初始状态或分布。以 表示 时的概率与期望。状态 的击中时间为 ,正回返时间为 。空集合的下确界约定为无穷。
定义 7.1.2
(常返、暂留与平稳概率)
若 ,称 为常返;若此概率小于一,称为暂留。常返状态在 时称为正常返,在期望无穷时称为零常返。这些定义把“会否回来”与“多久回来”分开。平稳概率序列 必须同时满足 及 。不能归一化的非负不变权重并不是平稳概率。
在 上的最近邻游走,每一步以概率 向右走一,以概率 向左走一,并独立于过去步伐。空间平移使所有状态有相同回返行为。状态可数只容许逐项求和,并不保证和有限。
主要结果
定理 7.1.3
(在无限整数线上击中较低水平)
对从整数 出发的最近邻游走,
若 ,则 。公平情形 的击中概率为一,但 。
定理 7.1.4
(回返概率与总到访次数)
对从 出发的可数马尔可夫链,设 ,,包括初始到访。则
若 ,期望为 ,且 几乎必然有限。若 ,则几乎必然到访无穷次,期望也无穷。
定理 7.1.5
(有限平均回返循环建立平稳分布)
设 , 几乎必然成立,且 。定义
则 是平稳概率,而且 。这个构造需要有限平均回返,并非只要求终究以概率一回来。
以下直接证明这一方向。一般不可约可数链的逆向及唯一性定理不包括在此证明内。对反射游走,我们会直接推导全部平稳候选,并明确分类每个参数情形。
证明或证明思路
赌徒破产事件的极限
证明
(赌徒破产事件取极限)
固定 。有限区间计算给出先到零而非 的概率:
随 增加,事件 递增。它们的并集恰好是 :若一条路径在有限时间击中零,在此之前的最大位置也有限,所以选足够高的上边界,路径不会先到达它。由概率的下连续性便可取极限。当 ,极限为 ;当 ,把分子分母除以 ,极限为一;公平公式也趋向一。
公平游走的有限吸收时间 平均为 。此时间不超过 ,故每个 都有 。让 趋向无穷便证明平均无穷,即使击中本身几乎必然发生。
当 ,设 。每步期望增量为 ,而事件 只取决于首 步,故
停止后的位置非负,因此 。单调收敛推出 。现在,停止之前所有增量的绝对值总和不超过可积变量 ,所以可以交换期望与这个和,得到 ,证得精确平均。此论证避免在尚未证明前就假定随机停时平均有限。
每次回返重新开始同一个实验
证明
(每次回返时重新开始)
每次有限回到 后,再回来一次的概率仍是 。这是停时上的强马尔可夫性。在离散时间,可把停时等于 的各事件分开,逐一用普通马尔可夫性,再对 相加而得到。归纳便有上述到访次数尾概率。尾和公式给出 。另一方面,对非负到访指示变量用托内利(Tonelli)定理,得 。这是同一数量的两种表示。
若 ,任意固定有限次回返都以概率一发生。把这些可数个概率一事件取交集,便得到无穷次回返。但这仍未交代回返间隔的平均长短。
循环占用为何满足流量平衡
证明
(循环占用平衡流量)
由托内利定理,;而 ,因为循环包括起始状态,却不包括最后回返。对固定 ,在每个事件 上向前一步取条件期望,得到
两个和只差端点,而 。所有重排都涉及非负项,故合法;有限 再容许归一化。除以 就证明平稳性及 。
证明透视
有限性究竟在哪里使用
证明分为两个阶段,只有第二阶段需要 。平衡等式 在各时刻 通过事件 使用马尔可夫性;这些事件由 决定,所以可以在随机和之内向前一步取条件。关键一步是交换端点:把循环平移一步,会去掉起始时对 的到访,并加上最后一次到访;因为 几乎必然有限且 ,两者抵消,所以等式在 也成立。每次交换求和次序都只涉及非负项,因此即使某些权重为无穷,这一阶段仍然成立。只有归一化要除以 ,有限平均回返正是在这唯一一步使用。对公平游走,循环几乎必然有限,但 ,归一化这一步没有有限的数可除。
例题
例题 7.1.6
(简单对称游走是零常返)
从零出发,第一步到 或 。击中结果及反射对称性显示,两个起点都几乎必然回到零,所以 。但从 击中零的平均时间无穷,因此从零的回返时间,即一步加上之后时间,其平均也无穷。故每个状态都是零常返。平均回返时间无穷并不妨碍回返概率为一。
反例模式
必定返回并不保证有平稳概率
断言:与有限不可约情形一样,各状态都常返的链必有平稳概率。考虑 上的对称游走,它是常返的。平稳的 须满足 ,即对每个 都有 ,所以 。对所有 非负迫使 ,而常数权重之和是 或 ,永远不等于一。断言不成立。修正的办法是回返循环定理的额外假设 ,而这个游走不满足它。
例题 7.1.7
(向任何一方偏移的游走都暂留)
设 。从 击中零的概率为 ;从 则为一,因为该侧漂移指向零。按第一步条件化,。若 ,对称论证给出 。因此所有有偏游走都满足 ,从零开始的总到访次数期望为 。若 ,回返概率为 ,包括初始时刻的总到访平均为二。
例题 7.1.8
(反射边界产生正常返链)
在 上,设 ;从每个正状态,以概率 向右、概率 向左。设 ,令 。相邻状态的细致平衡给出候选
它的和为一。由 ,把成对平衡相加即可证明平稳性,零点的自环也包含在内。零点的平均正回返时间为
若 ,则 ,平均回返时间为二。零点原地停留的一步也算在时刻一回返。
例题 7.1.9
(同一反射族也展示不能归一化的情形)
零点的平稳方程给出 。每个内部状态的平稳性表示,流量差 等于前一个流量差。初始流量差为零,因此每个平稳候选都必须满足 。
若 ,这些权重为常数,任何非零候选都不能求得有限和。击中结果显示链常返,但平均回返无穷,所以是零常返。若 ,权重增长而不能归一化;第一步分析给出回返概率 ,因此暂留。同一分布族展示了正常返、零常返及暂留,并且明确保留了边界条件。
常见错误
常见错误
(无穷次到访不等于有限平均回返)
正常返链与对称游走都几乎必然回来无穷次,两者的总到访期望也都是无穷。要区分它们,应考察两次回返之间的时间,而非无限期间的到访总数。
常见错误
(从无限击中方程中随意选一个解)
对 ,击中概率 满足 及 ()。 与 都是这组方程的解:对后者,令 ,则 ,而 。没有无穷远处的边界,方程本身不会选出真正的概率;有限边界的极限,或“击中概率是最小非负解”这一事实,才选出 。同样,对平稳分布要逐一验证非负、总质量为一以及每条平衡方程。
常返也不等于时刻 的分布收敛。整数线上的对称游走周期为二,而且没有平稳概率。一般而言,即使正常返也不会消除周期性。本节没有证明一个适用于所有可数链的收敛定理。
小结
有限赌徒破产结果,要在证明事件递增至所需事件后,才成为无限击中定理。暂留时重复回返给出几何型到访次数。有限平均循环则可通过归一化占用时间建立平稳概率。反射游走说明,在无限空间中,常返、正常返与可归一化平稳平衡必须分清。
习题
快速检查
(整数线游走有 ,从 出发。求终究击中零的概率;再求从零出发的回返概率及总到访零次数的期望。)
解答 · 答案
,所以从二击中零的概率为 。从零的回返概率为 ,总到访次数期望为 ,包括初始到访。这三个量涉及不同起点或不同事件。
快速检查
(向下偏移游走有 ,从 出发。求 及 ,并解释只解平均递推式而没有有限性论证为何不完整。)
解答 · 答案
因 ,击中概率为一,。停止增量论证先证明平均有限,再支持对随机长度的和交换期望。递推式本身可能有其他形式解,也没有保证候选期望真的有限。
快速检查
(反射游走有 。求平稳分布、其平均状态,以及零点的平均正回返时间。)
解答 · 答案
,故 。对等比级数求导或求尾和可得平均状态 。回返平均为 ,也等于 。
快速检查
(只用有限边界结果,证明从一出发的对称游走之 几乎必然有限,但平均无穷。)
解答 · 答案
对上边界 ,有 ,递增事件论证把此极限识别为 。同时,对每个 ,,故期望无穷,尽管时间几乎必然有限。
快速检查
(在一个三状态常返类中,从第一个状态出发,到首次正时间回返前的平均占用权重为 。求平均回返及循环构造所得平稳分布。另考虑可数无穷常返类,解释总质量无穷的循环权重为何不能以此构造归一化。)
解答 · 答案
循环占用总和为平均回返 ,故 。起始常返状态的坐标为 。若总占用质量无穷,除以这个量不能定义概率分布,有限平均循环构造便不适用。但单是此构造失败,并未证明任意可约链的所有可能平稳分布结论。