在已知信息下的公平性
我们可以按照已观察到的历史停止随机游走,例如到达边界便停止。停止的时间是随机的,也可能依赖之前的增量,因此不能不加论证便将它代入只对固定时间证明的公式。鞅描述一种特定的公平性,让我们能有条件地进行这种论证。
设 是概率空间上一列递增的 代数,代表各时刻可用的信息。若 是 可测,则时刻 的信息足以决定它的值。可积且适应这列信息的过程 称为鞅,若对每个 ,
可积是指每个固定时刻均有 ;适应是指 为 可测。公平性须在所有已知信息下成立,单靠各时刻的无条件均值相同并不足够。例如,若 相互独立、均值为零且一阶绝对矩有限,则对自然信息流,()是鞅:下一增量独立于过去,条件均值为零。对鞅定义取期望,可得每个固定 都有 。
反例模式
均值不变并不足够
设 以相同概率取 或 ,令 、、,并令 。这三个值的均值都是零,但 。一旦知道 ,下一个值便可预测,因此这个过程不是鞅。
只根据过去信息停止
取值于 的随机变量 称为停时,若每个 均有 。这表示到了时刻 ,已有的信息足以判断是否已经停止。对适应过程,首次到达时间 是停时,因为 。相反,选取某个未来时限前游走最后一次到零的时间,通常要看未来,未必是停时。
常见错误
(事后挑选最佳时刻停止)
“在 中取最大值的时刻停止”这类规则不是停时,即使它以 为上界。对从 出发的公平游走,令 为最早达到此最大值的时刻。则 是路径 的补事件,取决于 ,不属于 。四条等可能路径 分别给出 ,所以 。有界停时定理在此失效,因为在时刻一是否停止用到了下一个增量。
关键恒等式把停止后的值写成有限个增量之和:
指示变量是 可测:是否继续进行第 步,在时刻 已经决定。它有界,而增量可积,因此条件期望的定义给出
定理 19.1.1
(有界停时)
若 是可积离散时间鞅,停时 几乎必然满足 ,其中 是确定的整数,则 。
证明
(公平增量的有限和)
在上述恒等式取 ,对有限和逐项取期望。每项期望为零,且 几乎必然成立。
证明透视
停止和式中各假设的作用
整个证明建立在把 写成 加上由示性变量 开关的增量之上。停时性质只在这里使用: 是 的补事件,所以每个开关都在它所控制的增量之前设定。增量可积而示性变量有界,因此每个乘积可积,可以用塔性质把增量换成其条件均值,即零。
确定上界 用了两次,而且只在最后:它使和式有限,期望可以逐项通过;它还给出 。若 无界,恒等式 对每个 仍然成立;可能失效的只是 的极限。下面的例题用控制收敛补上这一步,而加倍下注的反例说明,没有这种控制就补不上。
公平游走的两个鞅
设 独立,且 ,令 。对自然信息流, 和 都是鞅。要证明后者,只需展开平方,并使用 及 。所有固定时刻的变量均可积。
例题 19.1.2
(吸收概率与平均时间)
取整数 和 ,令 为首次到达 或 的时间。从任何内部位置出发,连续 个 增量会迫使游走在接下来 步内被吸收。利用相继区块的独立性,
因此 几乎必然成立,而且 ;此和至多为 。对 使用有界停时定理,得 。由于 且它几乎必然收敛至 ,控制收敛定理给出 。吸收位置只有 或 ,故
同理,对 使用有界停时定理,得 。平方项用控制收敛, 用单调收敛。因为 ,所以
例如 、 时,到达上边界的概率为 ,平均吸收时间为 。这些公式依赖公平独立增量的模型;它们并不表示每条路径都恰好走八步。
例题 19.1.3
(有偏游走的破产概率)
设增量相互独立,、,其中 且 ;从 出发的游走在首次到达 或 的时刻 停止。令 ,则 是鞅,因为
连续 步向上仍会迫使吸收,现在每段的概率为 ,所以 几乎必然成立。有界停时给出 ,而 介于 与 之间,由控制收敛定理得 。记 ,这就是 ,因此
取 、、,则 ,概率为 。首步分析也一致:由 及 得 。
例题 19.1.4
(把到达时间截断在两步)
对从 出发的公平游走,令 为首次 的时刻。 无界,但 是以 为上界的停时,故 。逐一检查四条等可能路径即可确认。若 ,则 且 ,这包括路径 和 。水平 不可能在偶数时刻 首次到达,所以在路径 和 上游走在截断时刻停止,值为 和 。平均为 。
对每个截断时刻 ,同样的计算都成立:由于 ,得 。 增大时,未停止的路径越来越少,但取值越来越负;这就是 不是 的极限的原因。
为什么无界停时要格外小心
反例模式
首次胜出便停止的公平游戏
反复掷公平硬币,资本由零开始,第 次投注 在正面,首次出现正面后不再下注。令 为首次正面时间, 为第 次掷后资本。每个固定时刻的资本可积,下一步条件期望收益为零:在 前等概率得失 ,之后得失为零。因此 是鞅, 是停时。又 ,所以 几乎必然有限,且在此事件上 。然而 。
实际上,有正面出现时 ,否则为 ;每个 的期望都是零。罕见亏损的大小随 增长,所以几乎必然收敛至 不足以交换期望与极限。这个策略还需要无限额度的信用。此例推翻了仅凭停时几乎必然有限便能使用可选停止定理的想法。
练习
快速检查
(设 独立且 ,。证明 是鞅。)
解答 · 答案
。给定过去, 与 的条件期望均为零,因为 已知、 且 ;适应性和固定时间可积性直接成立。
快速检查
(对上述吸收游走取 、,求两个吸收概率和平均吸收时间。)
解答 · 答案
上边界概率为 ,下边界概率为 ,而 。
快速检查
(设 为独立公平掷币首次出现正面的时间。 是否有确定上界的停时?若 是同一信息流下任意可积鞅, 是多少?)
解答 · 答案
是。当 , 由前 次结果决定;当 ,它是整个样本空间。此停时至多为 ,故 。
快速检查
(在加倍下注例子中计算 ,并解释结果为何不与几乎必然收敛矛盾。)
解答 · 答案
除非前 次均为反面,差值均为零;在全反面时,绝对差值为 。故期望对每个 都是 。几乎必然收敛一般不保证绝对期望收敛:这里罕见亏损的大小不断增加。