动机
已知马尔可夫(Markov)链的当前状态后,过去不再提供预测未来所需的额外信息。熟悉的公式在固定时刻成立;但实际问题往往从观察过程时才发现的时刻开始,例如首次到达某状态之时。到达后能否把过程视作重新开始的链?如果该时刻是停时,答案是可以;若选时方法依赖未来观察,则可能使选中时刻后的分布产生偏差。
以下 是有限或可数状态空间 上的时间齐次马尔可夫链,转移矩阵为 ,自然历史为 。 表示由 开始。
定义
定义 2.11.1
(根据已观察历史作出的决定)
取值于 的随机时间 称为停时,若每个有限 都有 。等价地,到时刻 时,已观察历史足以判断是否已经停止。对 ,首次到达时间定义为 ;空集的下确界取为 。
本章最常用的两种随机时间都是停时。
引理 2.11.2
(到达时间与返回时间都是停时)
对每个 ,首次到达时间 是停时。对每个 ,首次返回时间 是停时。
证明
(每个事件只读取到时刻 n 为止的路径)
事件 表示 全在 外,而 在 内;它是 中有限个事件之交。同样,对 , 表示 都不等于 而 ;另外 。
相反,固定期限之前的最后一次到访一般不是停时:要知道一次到访是最后一次,就必须查看其后的路径。
随机时刻所得的信息用 表示:当每个有限 均有 时,事件 属于它。下述定理只讨论 ;在 上并不定义或断言有 及其后路径。
定理与证明
定理 2.11.3
(在停时重新开始)
设 是停时,,而 、,则
当右边乘积前的概率为正时,这给出已知上述过去事件及 后,接下来 个状态的条件分布。因此未来具有从 重新开始的链的分布;即使 无界或有正概率等于无穷大,结论仍成立。
证明
(按停时的取值分拆)
对每个 ,事件 由时刻 的历史决定。反复在固定时间 使用普通马尔可夫性,得到
对互不相交的 求和。各项都是概率,可数可加性适用,不需要假设 。在 上,式中的 分别就是 ,故得结论。有限路径的概率决定其后离散时间路径的分布。
证明透视
停时条件用在哪里
证明只有一个想法和一个记账步骤。
- 想法是以固定时刻取代随机时刻。在 上,命题关乎固定时刻 ,那里可用普通马尔可夫性。该性质要求条件事件属于 ,而这是假设唯一被用到之处: 与 是停时合起来,正好给出 。
- 记账步骤是对 求和。这是非负项的可数和,所以不需要 的可积性,而 的情形根本不会被计入。
证明没有说的两件事:它没有说 与路径独立,通常两者并不独立;它也没有说未来与 独立,因为未来的分布明确取决于到达的状态。下面预看未来的反例显示,当 时第一步如何失效。
例题
例题 2.11.4
(连续返回的几何尾概率)
从状态 出发,令 。定义 及 ;若 ,则令 。这些都是停时。重新开始定理给出递推关系 ;即使先前返回事件概率为零,此等式仍成立。因此
若 是包括时间零在内的访问次数,则 。尾和公式给出: 时 ; 时期望无穷。后者还可由递减事件 的概率连续性得到 。这不保证平均返回时间有限:常返与正常返仍是不同性质。
例题 2.11.5
(到达某状态后重复尝试)
状态为 ,其中 吸收;由 必定转至 ,由 以各 概率转至 或 。从 出发,每次到达 便开始一次尝试;下一步到达 的成功概率为 。重新开始定理保证进行中的各次尝试结果独立,因此直到首次成功的尝试次数 满足
每次尝试由 经 到达下一个目的地,耗时两步。失败后回到 ,故吸收时间为 ,其均值是 。这个结论依赖题中指定的转移,并非所有到达时间的通式。
第三个例子显示:当到达可以发生在不同状态,甚至可能根本不发生时,如何使用重新开始定理。
例题 2.11.6
(经两个不同状态进入集合)
取状态 ,其中 吸收。由 以各 的概率转至 ;由 以各 的概率转至 或 ;由 必定转至 。从 出发,令 ,。在 之前链停留在 ,所以
同理 。因此 ;在其余概率为 的事件上,链先被 吸收,, 没有定义。取 ,对每个进入状态分别使用定理再相加:
给定 ,这是 ;它既不是从 重新开始的值 ,也不是从 重新开始的值 ,而是两者以进入分布 加权的平均。注意此处 无界,而定理并不需要任何界。
预看未来的反例
停时假设不能换成较弱的要求,即只要求随机时刻有限。
反例模式
随机时刻未必是重新开始的时刻
断言:若 是有限随机时刻且 ,则 之后的路径是从 重新开始的链。令 为独立的公平二元变量,这是一条每种转移概率均为 的马尔可夫链。若 则取 ,若 则取 。此时 有限且 有定义,但 不能由 决定,所以 不是停时。计算:,而 ,所以给定 及 后,下一个值以概率 为 ;从 重新开始的链,其下一个值为 的概率却是 。此例不违反普通马尔可夫性:条件 本身已提供关于 的信息。修正后的叙述就是上述定理:停止时必须能从当时历史判定选时规则。
常见错误
常见错误
(除以可能不发生的到达事件的概率)
首次到达时间可能等于无穷大。应在确实到达的事件上使用重新开始结论,而且只有该事件概率为正时才可除以它。像 这样的量,在对 作出约定之前并无意义。
常见错误
(以为停时必须忽略过去)
停时可以高度依赖过去:首次到达正是标准例子,而 本身通常与路径远非独立。不能使用的是作决定当刻尚未取得的信息。
常见错误
(丢弃最后一段行程)
要断言完整回返循环彼此独立,必须说明连续返回时刻及各循环存在的事件。当 时,从 出发的最后一段行程永不返回,不能悄悄丢弃它,也不能把它当作已完成的循环。
练习
快速检查
(对 和 ,证明 是停时。)
分别处理 与 。
解答 · 答案
若 ,则 。若 ,它是 与所有 的 之交;这些事件都在 中。
快速检查
(若 ,求时间零后至少返回三次的概率,以及包括时间零在内到访 的期望总次数。)
利用第一个例题。
解答 · 答案
至少返回三次的概率为 ;期望访问次数为 ,包括最初一次。
快速检查
(在重复尝试例子中,求吸收时间超过四步的概率及恰为六步的概率。)
吸收时间是 。
解答 · 答案
要求头两次均失败,概率是 。恰好六步即 ,两次失败后成功的概率是 。
快速检查
(一条链从 出发, 且 。已知 和 ,求 。能否不加说明便写 ?)
与第三个例题比较。
解答
定理给出 。在 上没有定义 ;即使给定 ,到达状态也未必是 。必须明确说明事件,并计入其他可能到达状态的贡献。