为何研究边界问题?
设状态代表储备的单位数。每一步以概率 增加一个单位,或以概率 减少一个单位。储备到达零或目标 时便停止。我们想知道:先到目标的机会有多大?平均要等多久?两者是不同问题:概率满足齐次首步方程,历时则在每个内部状态额外累加一个时间单位。
假设各步独立、, 是整数,初始状态 。到达边界即停止。
定义 2.9.1
(离开时间、首达概率与平均历时)
对在边界停止、取值于 的游走 ,定义
概率和期望的下标表示起始状态。特别地 、 及 :从边界出发,停止时刻就是零。
首步方程及其解
定理 2.9.2
(两个吸收边界)
令 。对 ,先到 的概率及平均历时为
到达其中一个边界的时间几乎必然有限,而且 。
证明
(有限性、首步方程与最大值原理)
有限性。 从任何内部状态出发,最多连续 次下降便到达零;这些下降的概率至少为 ,且与之前的历史独立。条件于时刻 尚未停止,在下一个长度为 的区段仍未停止的概率至多为 。因此 ,它趋向零;由尾和公式, 也有有限的几何级数上界。这便保证以下首步方程可用。
方程。 按第一步的结果分情况,对 ,
第一式可重排为 。若 ,相邻差值构成公比为 的等比数列,故 ;代入两个边界值得到上述公式。若 ,相邻差值为常数,因而 。
对历时方程,若 ,一个特解是 :代入 得 。加上齐次方程的通解,再令两端为零,便得 。若 , 的二阶差分为 ,故可取二次特解 ;边界条件给出 。
唯一性。 为何代数解就是所求量,而且唯一?若两个解的边界值相同,其差 满足 。若它在内部取得正的最大值,由 可知两个相邻值也必须等于这个最大值。依此推至边界,便与边界值为零矛盾。对 同样论证,得 。
证明透视
一个证明里的三件工作
证明做了三件不同的事,各自用到不同的假设。
- 有限性只用到 :连续 次下降有固定的正概率。若没有 ,期望方程 可能只以 这种无用的形式成立。
- 求解纯粹是二阶线性递推的代数。唯一不显然的一步是历时方程中多出的 :第一步还消耗一个时间单位。若漏掉它,所得齐次方程配上零边界,其解为零,并不是平均历时。
- 唯一性同时用到 与 :最大值原理需要两个相邻状态都有正权重,内部最大值才会扩散到边界。
论证得以完成,是因为递推的解恰有两个自由常数,而边界值也恰有两个;最大值原理则排除了同一边界数据下的任何第二个解。
详解例子
例题 2.9.3
(向上有偏的游走)
取 、、、。此时 ,所以
直接验算:由 及 得 ,故 。向上的平均趋势不保证每个起点都是先到目标更可能:此处距离零只需一步,距离目标却要两步。平均历时的单位是步数,而不是储备单位。
例题 2.9.4
(公平游走)
若 、、,先到上界的概率为 ,平均历时为 。将起点移到 ,结果分别变为 和 。历时的对称性是交换两个边界时的对称性,并不是说每个起点的历时都相同。公平情形是公式中的退化情形 :此时 与 都为零,而另列的公式 正是 时 的极限。
第三个计算把趋势反转,再把上界移远,为下一节作准备。
例题 2.9.5
(向下有偏的游走与远方目标)
取 、、、。此时 ,所以
直接验算:由 及 得 ,故 。固定 而令 ,则 ,所以 且 ;因此 。移除目标使平均历时由 增至 ,因为原本停在 的路径现在要继续走到零。
移除上界
现在令独立步骤的游走由整数 出发,并令 ,不设上吸收边界。
命题 2.9.6
(由上方到达零)
对由 出发的游走,
其中在永不到达零的路径上取 。
证明
(把上界逐步提高)
先在到达 或 时停止。随 ,先到零而非 的事件递增至 :因为任何有限的到零路径都有有限最大值。由概率的下方连续性及有限边界公式,;当 时它等于 ,当 时等于 。
至于均值,设 为首次到达 的时间。随 增大, 递增至 ,故由单调收敛定理 。当 , 且 ,所以 ,。当 ,。当 ,事件 有正概率,所以广义期望为无穷大。
公平情形值得单独拿出来看,因为它推翻了一个诱人的推论。
反例模式
几乎必然有限不等于均值有限
断言:若首达时间几乎必然有限,则其期望有限。取公平游走 ,由 出发。上述命题给出 。但 ,而且
所以断言不成立。仅有概率的极限并不足以推出均值的极限,后者需要单调收敛等另外的论证。修正后的命题要求严格朝向零的趋势:当 ,。
常见错误
常见错误
(只凭趋势判断哪个边界先到)
正趋势 不表示从每个起点出发先到上界的概率都超过 。在向上有偏的例子中,,因为零只差一步,目标却差两步。概率同时取决于 和到两个边界的距离。
常见错误
(把 直接代入有偏公式)
当 ,式子 成为 ,而 的分母为零。公平情形需要另外求解递推,得 及 ;它们也正是 时有偏公式的极限。
练习与解答
快速检查
(公平游走在 内由 出发,求先到 的概率及平均停止时间。)
用 的公平情形公式。
解答 · 答案
公式给出 ,以及 步。
快速检查
(取 、、、。用公式求 与 ,然后直接验算。)
此时 。
解答 · 答案
此时 ,因此 ,。直接观察,第一步必到其中一个边界,所以 ;到上界的概率正是 。
快速检查
(半直线上的游走由 出发,、。求最终到达零的概率;其广义平均首达时间有限吗?)
先比较 与 。
解答 · 答案
由于 ,概率为 。有 的概率首达时间为无穷大,因此广义期望为无穷大。
快速检查
(有学生将 代入公平游走的平均历时方程。错在哪里?)
检查边界值与内部方程。
解答 · 答案
函数 是调和函数,边界值为 ,解的是首达概率问题。平均时间的边界值是 ,内部方程还有额外的 ;正确结果为 。