公平游戏与信息
定义 2.3.1
(-代数流、鞅与停时)
令 为递增的信息序列,形式上称为一个 -代数流(由递增的 -代数组成)。离散时间鞅 适应此-代数流,满足 ,并且 。
停时 的取值在 中,并对每个 满足 。
其下一个增量的条件平均为零;这是对公平性的精确表述,并不保证每个随机停下的规则都能保持初始期望。到了时间 ,只用当时已有的信息便可判断是否已停下。适应过程首次击中指定集合的时间是停时;查看未来再选取最后一次赢钱的时间,则未必是停时。
有界可选停时
定理 2.3.2
(有界时刻的可选停时)
设 是鞅, 是停时。对每个确定的整数 ,。特别地,若 几乎必然成立,则 。
证明
(把停时视为可预测地选取增量)
对任何确定的 及任何停时 ,截停时间 有界。其增量分解为
指示函数 是 可测的,因为其补集是 。增量可积、指示函数有界,故由条件期望可知每一项的平均为零。因此
对无界的 ,要把极限移入期望须另行证明;单靠几乎必然收敛并不足够。
有限公平赌徒破产问题
固定整数 及 。令 、,其中各个 相互独立,并且以各 的概率取 或 。使用由增量生成的自然-代数流。设 ,并约定空集的下确界为无穷。未截停的游走对所有 都有定义;截停后的游走保持在 中。
命题 2.3.3
(公平赌徒破产)
在此模型中, 几乎必然成立,,且 。
证明
(在有界时刻截停两个鞅)
及 都是鞅。后者可展开 ,再利用独立增量的平均为 、平方为 得出。由有界停时,对每个 有
因为 ,第二个等式给出 。由单调收敛定理,,因此 几乎必然成立。截停位置有界,故可对位置及其平方使用控制收敛定理。令 ,便得到
证明透视
有限性是推导出来而非假设的
论证从未在无界时刻 本身使用可选停时。它先在 使用有界定理,此时定理自动成立,然后才令 。两个鞅各有不同任务。二次鞅 把有界范围 转为对 一致的界 ;单调收敛把它变成 , 的有限性正由此而来。线性鞅 再确定 。在两条恒等式中取极限时,位置及其平方用控制收敛, 则用单调收敛。真正起作用的假设是截停位置有界;下一节显示,没有它,同一个取极限步骤便会失败。
此证明没有先假设期望停时有限再得出它有限。公式只适用于这里公平且增量独立的模型;有偏游走需要不同的鞅,击中概率也不同。
常见错误
(把公平公式用于有偏游走)
公式 依赖 是鞅。若每步以概率 上升、以概率 下降,取 、,则 ,而 ,不是 。有偏游走的 不是鞅,须改用另一个鞅。
例题 2.3.4
(上界五、起点二)
取 、。先到达 的概率为 ,先到达 的概率为 ,到达任一边界的平均步数为 。可用二次鞅核对:,而 。
例题 2.3.5
(紧邻两个边界的起点)
取 、。第一步必定到达 或 ,故 是确定的,与 一致;而 正是第一步向上的概率。在这个边缘情形中 有界,可直接应用有界定理,无须取极限。
例题 2.3.6
(偷看未来的有界时刻)
在同一游走中,若 令 ,否则令 。则 有界,但 。这并不与定理矛盾: 不属于 ,所以 不是停时。在时间零决定是否停下时,用到了尚未发生的第一步。
为何无界停时不同
上面的有限性证明依赖截停游走的有界范围。去掉下方边界,结论便会失效。
反例模式
几乎必然有限的停时仍可破坏可选停时
公平游走由 开始,令 。对每个正整数 ,改为在击中 或 时停下。把前述有限区间结果平移后,可知先到达 的概率是 ,且有限区间击中时间几乎必然有限。当 ,这些事件递增至 :一条在有限时间内到达 的路径必有有限最小值。因此 几乎必然成立,且 几乎必然成立,但 。
故若直接把 代入有界定理,便会错误得到 。事实上 :若它有限,由 及控制收敛定理,便有 ,矛盾。取极限需要控制:例如截停过程被常数界住,或在增量以一为界且 时,经 被可积变量界住。
常见错误
(由几乎必然有限推出期望有限)
此例也显示几乎必然有限的停时不等于有界停时,也不等于具有有限期望持续时间。在赌徒破产中, 来自有界范围,而不是来自 。
习题
快速检查
(在有限公平游戏中,若 、初始位置 ,求先击中 的概率及击中任一边界的平均时间。)
套用 及 。
解答 · 答案
概率是 ,平均持续时间是 。
快速检查
(对同一游戏,解释为何在尚未证明 有限之前,已可对 使用有界可选停时。)
检查有界定理的两个条件。
解答 · 答案
不超过确定的整数 ,而且是停时;各鞅在每个确定时间均可积。因此无须假设 便可应用定理。
快速检查
(在无界例子中,为何 等于对所有 的“先击中 而非 ”事件取并集?)
证明两个方向的包含关系。
解答 · 答案
若先击中 而非 ,则 有限。反过来,到首次击中 为止的有限路径有有限最小值;取 大于该最小值的绝对值,便保证没有先击中 。